第 8 次作业

理论部分

习题 1

试用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}\) 为极小点。

习题 2

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

\(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}\)。这样,便求得两次迭代的解。实际上,我们可以注意到罚函数法的解可能会违背约束条件,通过不断地加大惩罚使得它收敛在可行域内。

习题 3

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

\(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.