第 7 次作业

理论部分

习题 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||_{2} \]

的平方是 \(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 |