作业11¶

提交截至时间：2023/01/21 周六 12:00（中午）

习题1. 写出下述非线性规划的KKT条件并求解

(1) maximize $f(x)=(x-3)^{2}$

suject to $1\le x\le5$

(2) minimize $f(x)=(x-3)^{2}$

suject to $1\le x\le5$

解:

(1)原问题等价于

\[\begin{cases}minimize&-f(x)=-(x-3)^{2}\\ g_{1}(x)=-x+1\le5\\ g_{2}(x)=x-5\le0\end{cases}\]

求目标函数和约束函数的梯度得,

\[\nabla_{x}f(x)=-2(x-3),\nabla_{x}g_{1}(x)=-1,\nabla_{x}g_{2}(x)=1\]

将约束引入广义Lagrange 乘子 $v_{1},v_{2},$ 在KKT条件上有

\[\begin{cases}-2(x^{*}-3)-v_{1}^{*}+v_{2}^{*}=0\\ v_{1}^{*}(-x^{*}+1)=0\\ v_{2}^{*}(x^{*}-5)=0\\ v_{1}^{*}\ge0,v_{2}^{*}\ge0\end{cases}\]

若 $v_{1}^{*}\ne0,v_{2}^{*}\ne0,$ 无解.

若 $v_{1}^{*}=0,v_{2}^{*}\ne0,$ 得 $x^{*}=5,v_{2}^{*}=4,-f(x^{*})=-4.$

若 $v_{1}^{*}\not=0,v_{2}^{*}=0$ 得 $x^{*}=1,v_{1}^{*}=4,-f(x^{*})=-4.$

若 $v_{1}^{*}=0,v_{2}^{*}=0,$ 得 $x^{*}=3,f(x^{*})=0$.

因此最优点 $x^{*}=1$ 或 $x^{*}=5,$ maximize f(x) = 4.

(2)原问题等价于

\[\begin{cases}minimize&f(x)=(x-3)^{2}\\ g_{1}(x)=-x+1\le5\\ g_{2}(x)=x-5\le0\end{cases}\]

求目标函数和约束函数的梯度得,

\[\nabla_{x}f(x)=-2(x-3),\nabla_{x}g_{1}(x)=-1,\nabla_{x}g_{2}(x)=1\]

将约束引入广义Lagrange 乘子 $v_{1}$ $v_{2}$ 在KKT条件上有

\[\begin{cases}2(x^{*}-3)-v_{1}^{*}+v_{2}^{*}=0\\ v_{1}^{*}(-x^{*}+1)=0\\ v_{2}^{*}(x^{*}-5)=0\\ v_{1}^{*}\ge0,v_{2}^{*}\ge0\end{cases}\]

若 $v_{1}^{*}\ne0,v_{2}^{*}\ne0,$ 无解.

若 $v_{1}^{*}=0,v_{2}^{*}\ne0,$ 得 $x^{*}=5,v_{2}^{*}=-4<0$ 不是KKT点.

若 $v_{1}^{*}\ne0,v_{2}^{*}=0$ 得 $x^{*}=1,v_{1}^{*}=-4<0$,不是KKT点

若 $v_{1}^{*}=0,v_{2}^{*}=0,$ 得 $x^{*}=3,f(x^{*})=0$

因此最优点 $x^{*}=3$, $minimizef(x)=0.$

习题2. 考虑等式约束的最小二乘问题

minimize $||Ax-b||_{2}^{2}$

suject to $Gx=h$

其中 $A\in\mathbb{R}^{m\times n},rank(A)=n,G\in\mathbb{R}^{p\times n},rank(G)=p$. 给出KKT条件,推导原问题最优解$x^{*}$ 以及对偶问题最优解 $v^{*}$的表达式。

解: 求得 Lagrangian 函数为

\[L(x,v)=||Ax-b||_{2}^{2}+v^{T}(Gx-h)\]

\[=x^{T}A^{T}Ax+(G^{T}v-2A^{T}b)^{T}x-v^{T}h\]

可通过如下最优性条件得到函数最小值,令梯度为0得,

\[\nabla_{x}L(x,v)=2A^{T}Ax+G^{T}v-2A^{T}b=0\]

因此当 $x=\frac{1}{2}(A^{T}A)^{-1}(G^{T}v-2A^{T}b)$ 时, Lagrangian 函数取得最小值.

对偶函数为 $g(x)=-\frac{1}{4}(G^{T}v-2A^{T}b)^{T}(A^{T}A)^{-1}(G^{T}v-2A^{T}b)-v^{T}h.$

最优性条件为

\[\begin{cases}2A^{T}(Ax^{*}-b)+G^{T}v^{*}=0\\ Gx^{*}=h\end{cases}\]

解方程得,

\[\begin{cases}v^{*}=2(G(A^{T}A)^{-1}G^{T})^{-1}(G(A^{T}A)^{-1}A^{T}b-h)\\ x^{*}=(A^{T}A)^{-1}(A^{T}b-G^{T}(G(A^{T}A)^{-1}G^{T})^{-1}(G(A^{T}A)^{-1}A^{T}b-h))\end{cases}\]

习题3. 用 Lagrange 乘子法证明:矩阵 $A\in\mathbb{R}^{m\times n}$ 的2范数 $$ ||A||{2}=max{||x||{2}=1,x\in\mathbb{R}^{n}}||Ax|| $$

的平方是 $A^{T}A$ 的最大特征值。

证明: 优化问题为

maximize $f(x)=x^{T}A^{T}Ax$

suject to $x^{T}x=1$

Lagrange 函数为:

\[L(x)=x^{T}A^{T}Ax-\lambda(x^{T}x-1)\]

$\frac{\partial L}{\partial x}=2A^{T}Ax-2\lambda x$

令$\frac{\partial L}{\partial x}=0$,有: $A^{T}Ax=\lambda$

这表示在 $f(x)$ 的极大值点 $x$ 是 $A^{T}A$ 的特征向量, $\lambda$ 是对应的特征值。此时,

\[f(x)=x^{T}A^{T}Ax=x^{T}\lambda x=\lambda x^{T}x=\lambda\]

因此说明,为使 $f(x)$ 最大, $f(x)=\lambda_{max}(A^{T}A)$,其中 $\lambda_{max}$ 表示最大特征值。即

\[||A||_{2}^{2}=\lambda_{max}(A^{T}A)\]

习题4. 用 Lagrange 乘子法求欠定方程 $Ax=b$ 的最小二范数解,其中 $A\in\mathbb{R}^{m\times n}$ ,$m\le$ $n,rank(A)=m$

证明: 优化问题为

maximize $f(x)=\frac{1}{2}||x||_{2}^{2}$

suject to $Ax=b$

Lagrange 函数为:

\[L(x,\lambda)=\frac{1}{2}x^{T}x-\lambda^{T}(Ax-b)\]

$\frac{\partial L}{\partial x}=x-A^{T}\lambda$

令$\frac{\partial L}{\partial x}=0$,有:

\[x=A^{T}\lambda\]

\[g(\lambda)=-\frac{1}{2}\lambda^{T}AA^{T}\lambda+\lambda^{T}b\]

令$\frac{\partial g}{\partial\lambda}=0$：

\[-AA^{T}\lambda+b=0\]

由 $A\in\mathbb{R}^{m\times n},rank(A)=m$ 得 $AA^{T}$ 可逆,因此

\[\lambda=(AA^{T})^{-1}b\]

因此, $x$ 满足 $Ax=b$ 的最小二范数解:

\[x=A^{T}(AA^{T})^{-1}b\]

习题5. 用最速下降法和精确线搜索计算 $min~f(x)=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}$,初始点 $x^{(0)}=(2,2,1)^{T}$ 当 $(f(x^{(n+1)})-f(x^{(n)}))<0.001$ 时迭代终止,

解: 由题意得, $f(x)=x^{T}x,\nabla_{x}f(x)=2x$,设最速下降法的步长为入,那么

\[f(x-\lambda\nabla_{x}f(x))=(x-\lambda\nabla_{x}f(x))^{T}(x-\lambda\nabla_{x}f(x))\]

\[=x^{T}x-2\lambda\nabla_{x}f(x)^{T}x+\lambda^{2}\nabla_{x}f(x)^{T}\nabla_{x}f(x)\]

在 $x-\lambda\nabla_{x}f(x)$ 方向上,使 $f(x)$ 最小的 $\lambda$ 满足

\[\frac{\partial f(x-\lambda\nabla_{x}f(x))}{\partial\lambda}=-2\nabla_{x}f(x)^{T}x+2\lambda\nabla_{x}f(x)^{T}\nabla_{x}f(x)\]

得

\[\lambda=\frac{\nabla_{x}f(x)^{T}x}{\nabla_{x}f(x)^{T}\nabla_{x}f(x)}=\frac{1}{2}\]

所以,

$x^{(1)}=x^{(0)}-\frac{1}{2}\nabla_{x}f(x^{(0)})=(0,0,0)^{T}$

$f(x^{(1)})=0$

$x^{(2)}=x^{(1)}-\frac{1}{2}\nabla_{x}f(x^{(1)})=(0,0,0)^{T}$

$f(x^{(2)})=0$

同理可得, $f(x^{(n)})=0(n>0)$ 因此当 $|(f(x^{(n+1)})-f(x^{(n)})|=0<0.001$ 时,迭代终止

习题6. 使用梯度下降法和固定步长 $\lambda=0.01$ 计算 $min~f(x)=(x_{1}-1)^{2}+16(x_{2}-2)^{2}$ 初始点 $x^{(0)}=(2,3)^{T}$,迭代两步后终止

解: 具体迭代结果:

| k | $x^{(k)^{T}}$ | $g_{k}^{T}$ | $f_{k}$ | $||g_{k}||_{\infty}$ | |---|---|---|---|---| | 0 | (2,3) | (2,32) | 17 | 32 | | 1 | (1.98, 2.68) | [1.96, 21.76] | 8.3588 | 21.76 | | 2 | (1.96, 2.46) | [1.9208, 14.7968] | 4.3434 | 14.7968 |

习题7. 考虑问题

$min~f(x)=3x_{1}^{2}+3x_{2}^{2}-x_{1}^{2}x_{2}$.

从初始点 $x^{(0)}=(1.5,1.5)^{T}$ 出发,用Newton方法求迭代两步后该问题的解(可用编写程序辅助计算).

解: $f(x)$ 的一、二阶导数分别为

$g(x)=(6x_{1}-2x_{1}x_{2},6x_{2}-x_{1}^{2})^{T}$ $G(x)=(\begin{matrix}6-2x_{2}&-2x_{1}\\ -2x_{1}&6 \end{matrix})$

$f(x)$ 有三个稳定点:

极小点 $x_{(1)}=(0,0)^{T},$ 鞍点 $x_{(2)}=(3\sqrt{2},3)^{T}和x_{(3)}=(-3\sqrt{2},3)^{T}.$ 在这三个点的Hesse 矩阵分别为

$G(x_{(1)})=(\begin{matrix}6&0\\ 0&6\end{matrix})$

$G(x_{(2)})=(\begin{matrix}0&-6\sqrt{2}\\ -6\sqrt{2}&6\end{matrix})$

$G(x_{(3)})=(\begin{matrix}0&6\sqrt{2}\\ 6\sqrt{2}&6\end{matrix})$

下面我们从 $x^{(0)}=(1.5,1.5)^{T},$ 这时 Newton方法在每一迭代步的信息见下表

| k | $x^{(k)^{T}}$ | $f_k$ | $||g_{k}||_{\infty}$ | | ---- | ------------------ | ------- | -------------------- | | 0 | (1.5000, 1.5000) | 10.1250 | 8.1125 | | 1 | (-3.7500, -2.2500) | 89.0156 | 48.0633 | | 2 | (0.6250, -3.1250) | 31.6895 | 20.6151 | | 3 | (0.3190,0.0014) | 0.3052 | 1.9155 | | 4 | (-0.0020,-0.0172) | 0.0009 | 0.1037 | | 5 | (-0.0000, -0.0000) | 0.0000 | 0.0000 | | 6 | (-0.0000,-0.0000) | 0.0000 | 0.0000 |

习题8. 试用DFP法计算下述二次函数的极小点

$min~f(x)=3x_{1}^{2}+x_{2}^{2}-2x_{1}x_{2}-4x_{1}$

解: 假设我们从 $x^{(0)}=(-2,4)^{T}$ 开始(没有规定时,可以随机选取一个初始点),并取

\[\overline{H}^{(0)}=(\begin{matrix}1&0\\ 0&1\end{matrix})\]

\[\nabla f(x)=[(6x_{1}-2x_{2}-4),(2x_{2}-2x_{1})]^{T}\]

$\nabla f(x^{(0)})=(-24,12)^{T}$

\[p^{(0)}=-\overline{H}^{(0)}\nabla f(x^{(0)})=-(\begin{matrix}1&0\\ 0&1\end{matrix})(\begin{matrix}-24\\ 12\end{matrix})=(\begin{matrix}24\\ -12\end{matrix})\]

利用一维搜索,即 $min_{\lambda}f(x^{(0)}+\lambda p^{(0)})$,可算得

\[\lambda_{0}=\frac{5}{34}\]

\[x^{(1)}=x^{(0)}+\lambda_{0}p^{(0)}=\binom{-2}{4}+\frac{5}{34}(\begin{matrix}24\\ -12\end{matrix})=(\frac{26}{17},\frac{38}{17})^{T}\]

从而

\[\nabla f(x^{(1)})=(\frac{12}{17},\frac{24}{17})^{T}\]

\[\Delta x^{(0)}=x^{(1)}-x^{(0)}=(\frac{26}{17},\frac{38}{17})^{T}-(-2,4)^{T}=(\frac{60}{17},-\frac{30}{17})^{T}\]

\[g^{(0)}=\nabla f(x^{(1)})-\nabla f(x^{(0)})=(\frac{6}{17},\frac{12}{17})^{T}-(-12,6)^{T}=(\frac{210}{17},-\frac{90}{17})^{T}\]

\[\overline{H}^{(1)}=\overline{H}^{(0)}+\frac{\Delta x^{(0)}(\Delta x^{(0)})^{T}}{(\Delta g^{(0)})^{T}\Delta x^{(0)}}-\frac{\overline{H}^{(0)}\Delta g^{(0)}(\Delta g^{(0)})^{T}\overline{H}^{(0)}}{(\Delta g^{(0)})^{T}\overline{H}^{(0)}\Delta g^{(0)}}\]

$=\left( \begin{array}{c c} 1 & 0 \\ 0 & 1 \end{array} \right) + \frac{ \left( \frac{60}{17}, -\frac{30}{17} \right)^T \left( \frac{60}{17}, -\frac{30}{17} \right) }{ \left( \frac{210}{17}, -\frac{90}{17} \right) \left( \frac{60}{17}, -\frac{30}{17} \right)^T } - \frac{ \left( \begin{array}{c c} 1 & 0 \\ 0 & 1 \end{array} \right) \left( \frac{210}{17}, -\frac{90}{17} \right)^T \left( \frac{210}{17}, -\frac{90}{17} \right) \left( \begin{array}{c c} 1 & 0 \\ 0 & 1 \end{array} \right) }{ \left( \frac{210}{17}, -\frac{90}{17} \right) \left( \begin{array}{c c} 1 & 0 \\ 0 & 1 \end{array} \right) \left( \frac{210}{17}, -\frac{90}{17} \right)^T }$

$=\frac{1}{986}\left( \begin{array}{c c} 269 & 299 \\ 299 & 862 \end{array} \right)$

\[p^{(1)}=-\overline{H}^{(1)}\nabla f(x^{(1)})=-\frac{1}{986}(\begin{matrix}269&299\\ 299&862\end{matrix})(\begin{matrix}\frac{12}{17}\\ \frac{24}{17}\end{matrix})=-(\begin{matrix}\frac{18}{29}\\ \frac{42}{29}\end{matrix})\]

再由一维搜索 $min_{\lambda}f(x^{(1)}+\lambda p^{(1)})$,得

\[\lambda_{1}=\frac{29}{34}\]

\[x^{(2)}=x^{(1)}+\lambda_{1}p^{(1)}=(\begin{matrix}\frac{26}{17}\\ \frac{38}{17}\end{matrix})+\frac{29}{34}(\begin{matrix}-\frac{18}{29}\\ -\frac{42}{29}\end{matrix})=(\begin{matrix}1\\ 1\end{matrix})\]

\[\nabla f(x^{(2)})=(0,0)^{T}\]

可知 $x^{(2)}=(1,1)^{T}$ 为极小点。

习题9. 试用二次罚函数法求解如下优化问题:

$min~f_{0}(x)=\frac{1}{3}(x_{1}+1)^{3}+x_{2}$

s.t. $f_{1}(x)=1-x_{1}\le0$

$f_{2}(x)=-x_{2}\le0$

从初始点 $x^{(0)}=(2,0)^{T}$ 开始,计算迭代两步后的解。

解: 我们不妨取 $M1=1,c=2$。由此,构造无约束优化问题:

\[min~p_{1}(x)=\frac{1}{3}(x_{1}+1)^{3}+x_{2}+[min(0,x_{1}-1)]^{2}+[min(0,x_{2})]^{2}\]

易求得在 $x^{(0)}$ 处的梯度(严格上是次梯度)为 $((x_{1}+1)^{2},1)^{T}=(9,1)$。假设这里采用固定步长 $\lambda=0.1$,则 $x^{(1)}=(1.1-0.1)^{T}$。这里假定这是该无约束优化问题的最优解,实际上,需要迭代至收敛。

然后,进行第二轮迭代,此时 $M2=c*M1=2$。由此,构造无约束优化问题:

\[min~p_{1}(x)=\frac{1}{3}(x_{1}+1)^{3}+x_{2}+2*[min(0,x_{1}-1)]^{2}+2*[min(0,x_{2})]^{2}\]

易求得在 $x^{(1)}$ 处的梯度为 $((x_{1}+1)^{2},1+4x_{2})^{T}=(4.41,0.6)$。仍假设这里采用固定步长 $\lambda=0.1$, 则 $x^{(2)}=(0.659-0.16)^{T}$。这样,便求得两次迭代的解。实际上,我们可以注意到罚函数法的解可能会违背约束条件,通过不断地加大惩罚使得它收敛在可行域内。

习题10. 试用内点法求解如下优化问题:

$min~f_{0}(x)=\frac{1}{3}(x_{1}+1)^{3}+x_{2}$

$s.t.f_{1}(x)=1-x_{1}\le0$

$f_{2}(x)=-x_{2}\le0$

解: 参考讲义 Lec35,例3.