最优化方法 试题

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$ 的表达式, 并说明这样做的理由.

提示.

提示.

一、

(1) 一阶条件: 对于定义在凸集上的可微函数 $f,f$ 是凸函数当且仅当 $f(y)\ge f(x)+\nabla f^{\top }(x)(y-x),\forall x,y\in \text{dom}f$ 二阶条件: 对于定义在凸集上的可微函数 $f,f$ 是凸函数当且仅当 ${\nabla }^{2}f(x)\ge 0,\forall x\in \text{dom}f$ (2) 由于凸函数的线性组合仍是凸函数, 故原问题等价于证明 $n=1$ 时的情况, 等价于证明 $\ln h(x_1,\cdot )$ 和 $\ln (1-h(x_1,\cdot ))$ 均为凸函数. 又注意到 ${\theta }^{\top }x$ 关于 $\theta$ 线性, 从而只需要证明 $\ln \frac{1}{1+e^{-z}}$ 和 $\ln \frac{e^{-z}}{1+e^{-z}}(z\in \mathbb{R})$ 是凸函数即可. $$(\ln \frac{1}{1+e^{-z}}{)}^{\prime \prime }=(-\frac{e^{-z}}{1+e^{-z}}{)}^{\prime }=-(\frac{1}{1+e^{-z}}{)}^{\prime }=\frac{e^{-z}}{(1+e^{-z}{)}^2}>0$$$$(\ln \frac{e^{-z}}{1+e^{-z}}{)}^{\prime \prime }=(\frac{1+e^{-z}}{e^{-z}}(\frac{e^{-z}}{1+e^{-z}}{)}^{\prime }{)}^{\prime }=(-\frac{1}{1+e^{-z}}{)}^{\prime }=\frac{e^{-z}}{(1+e^{-z}{)}^2}>0$$

$\square$

2最优化方法 2025 学年春季学期期末试题

一、	(1) 请写出 (连续可微) 凸函数判定的一阶条件和 (二阶可微) 凸函数判定的二阶条件. (2) 对于 $x\in {\mathbb{R}}^n,y\in \mathbb{R},y>0$, 证明函数$$f(x,y)=\frac{\Vert x{\Vert }_2^2}{y}$$是凸函数.
二、	(1) 写出临近算子 ${\text{prox}}_h(x)$ 的定义. (2)$h(x)=\Vert x{\Vert }_1$ 时, 计算 ${\text{prox}}_{th}(x)$. (3) 设 $h(x)=g(\lambda x+a)$($\lambda \ne 0$). 证明 ${\text{prox}}_h(x)=\frac{1}{\lambda }({\text{prox}}_{{\lambda }^{2}g}(\lambda x+a)-a)$
三、	考虑凸问题$$\underset{x}{\min }\frac{1}{2}{x}^{\top }Ax+b^{\top }x$$$$l\le x\le u$$其中 $A$ 是半正定对称阵. (1) 把该问题改写为可以使用交替方向乘子法的形式, 并写出该问题的增广拉格朗日函数. (2) 写出用交替方向乘子法求解的算法步骤并说明理由.
四、	(1) 设 $f$ 是凸函数, 满足 $\Vert \nabla f(x)-\nabla f(y)\Vert \le L\Vert x-y\Vert$.$\forall x,y\in \text{dom}(f),$ 求证$$|f(y)-f(x)-\nabla f^{\top }(x)(y-x)|\le \frac{L}{2}\Vert x-y{\Vert }^2$$(2) 设 $f$ 是凸函数, 满足 $\Vert {\nabla }^{2}f(x)-{\nabla }^{2}f(y)\Vert \le L\Vert x-y\Vert$.$\forall x,y\in \text{dom}(f)$, 写出$$|f(y)-f(x)-\nabla f^{\top }(x)(y-x)-\frac{1}{2}({\nabla }^{2}f(x)(x-y),(x-y))|$$应满足的不等式.
五、	(1) 写出 $f(x)$ 的次梯度的定义. (2) 写出 $f(x)$ 的二次共轭函数 $f^{\ast \ast }(x)$ 的定义. (3) 设 $f$ 还是闭凸函数, 那么我们知道 $\forall x\in \text{dom}(f),f(x)=f^{\ast \ast }(x)$. 求证$$y\in \partial f(x)\iff x\in \partial f^{\ast }(y)$$
六、	设 $t\in \mathbb{R},x\in {\mathbb{R}}^n$. 定义 $f(t,x)=\ln (t^2-x^{\top }x),\text{dom}(f)=\{(t,x)|t>0,t^2-x^{\top }x>0\}$. 求 $f(t,x)$ 的共轭函数.

提示.

提示.

一、

$\square$