最优化方法 试题

1最优化方法 2024 学年春季学期期末试题

一、	(1) 请写出 (连续可微) 凸函数判定的一阶条件和 (二阶可微) 凸函数判定的二阶条件. (2) $\theta \in {\mathbb{R}}^n,x_n\in {\mathbb{R}}^n,y_n\in \{0,1\}$, $h(x,\theta )=\frac{1}{1+e^{-{\theta }^{T}x}}$. $$f(\theta )=-\sum _{1\le i\le n}\left[y_i\ln h(x_i,\theta )+(1-y_i)\ln (1-h(x_i,\theta ))\right]$$ 求证: $f(\theta )$ 是凸函数.
二、	(1) 写出 $f(x)$ 的共轭函数 $f^{\ast }(y)$ 的表达式. (2) $x\in {\mathbb{R}}^n$, $x_i>0$ 是 $x$ 的分量, 求 $f(x)=\sum _{1\le i\le n}{x}_i\ln x_i$ 的共轭函数 $f^{\ast }(y)$.
三、	(1) $F(x)$ 是凸函数, 请写出 $\partial F(x)$ 的定义. (2) $\epsilon >0$, 定义 $F(a,b)=a-\max \{0,a-\epsilon b\}$, 求 $F(a,b)=0$ 的充要条件. (3) 求 $F(a,b)$ 的次微分.
四、	$f(x)$ 是凸函数, 且满足梯度 $L$–利普希茨连续, 即 $\Vert \nabla f(x)-\nabla f(y)\Vert \le L\Vert x-y\Vert$. $x^{\ast }$ 是 $f$ 的全局最小值点. (1) 求证: $\forall x,y\in \mathbf{dom}f$, 有: $$f(y)\le f(x)+\nabla f(x{)}^T(y-x)+\frac{L}{2}{\Vert x-y\Vert }^2$$ (2) 求证: $$\frac{1}{2L}{\Vert \nabla f(x)\Vert }^2\le f(x)-f(x^{\ast })\le \frac{L}{2}{\Vert x-x^{\ast }\Vert }^2$$
五、	$f(x)$ 是凸函数.$x^{\ast }$ 是 $f$ 的全局最小值点. (1) 写出临近算子 ${\mathrm{prox}}_{tf}(x)$ 的定义. (2) 写出近似点算法的迭代公式和大致流程. (3) 已知从 $x_k$ 到 $x_{k+1}$ 的迭代系数为 $t_k$, 求证: $\frac{x_k-x_{k+1}}{t_k}\in \partial f(x_{k+1})$. (4) 证明:$$f(x_{k+1})\le f(x_k)-\frac{1}{t_k}{\Vert x_k-x_{k+1}\Vert }^2$$ (5) 证明: $$f(x_{k+1})\le f(x^{\ast })+\frac{1}{2t_k}\left({\Vert x_k-x^{\ast }\Vert }^2-{\Vert x_{k+1}-x^{\ast }\Vert }^2\right)$$ (6) 证明: $$f(x_k)-f(x^{\ast })\le \frac{{\Vert x_0-x^{\ast }\Vert }^2}{2{\sum }_{1\le i\le k-1}{t}_i}$$
六、	(1) $t>0,f(x)={\Vert x\Vert }_1$, 求 ${\mathrm{prox}}_{tf}(x)$. (2) $t>0,f(x)={\Vert x\Vert }_2$, 求 ${\mathrm{prox}}_{tf}(x)$. $$f(x)=\frac{1}{2}{x}^{T}Qx+q^{T}x+{\Vert x\Vert }_1$$$$Ax=b$$ 其中 $Q$ 是 $n\times n$ 正定矩阵, $q\in {\mathbb{R}}^n$. (3) 写出用增广拉格朗日法求解 $\min f$ 的表达式. (4) 写出用交替方向乘子法求解 $\min f$ 的表达式, 并说明这样做的理由.