最优化方法：五、无约束最优化方法

主要参考书目：

• 最优化方法及其应用/郭科，陈聆，魏友华.-北京：高等教育出版社,2007.7(2013.7重印)

在第四章中，我们解决了确定搜索步长的问题，现在解决确定搜索方向的问题。

1、最速下降法

• 基本思路
  搜索方向总沿着f(X)$f(X)$在Xk$X_k$点的负梯度方向，因为在Xk$X_k$点的某个邻域内，该方向上目标函数下降最快。
  即
  
  Pk=−▽f(Xk).$$P_k=-▽f(X_k).$$
• 具体细节
  运用于正定二次函数可以得到显式递推公式：
  
  Xk+1=Xk−gTkgkgTkAgkgk.$$X_{k+1}=X_k-{\displaystyle \frac{g_k^T{g}_k}{g_k^{T}A{g}_k}}{g}_k.$$
• 特点
  该方法虽然叫做“最速下降法”，实际上收敛速度并不快。
  其主要原因是每次迭代后下一次的搜索方向总是和前一次相互垂直，产生锯齿现象，使得收敛速度较为缓慢。
  锯齿现象如图：
  

2、牛顿法

• 基本思路
  每轮迭代在迭代的起始点Xk$X_k$处用一个适当的二次函数来近似该点处的目标函数，由此用Xk$X_k$指向近似二次函数极小点的方向来构造搜索方向Pk$P_k$。
  如图：
  
• 具体细节
  假设原函数二阶可导且Hesse矩阵正定。
  则可以通过在Xk$X_k$处进行泰勒展开来寻找近似二次函数，找到该函数后就可以找到指向其极小点的方向Pk$P_k$作为搜索方向。而搜索步长tk$t_k$恒取1。
  其中
  
  Pk=−[▽2f(Xk)]−1▽f(Xk).$$P_k=-[{▽}^{2}f(X_k){]}^{-1}▽f(X_k).$$
• 特点
  该方法收敛很快，但是：
  (1)迭代只能保证函数值不升，而不能保证函数值下降。
  (2)要求Hesse矩阵必须正定。
  (3)要求初始点比较接近极值点或者有利于接近极值点。
  (4)当Hesse矩阵奇异时，无法求出搜索方向。
  (5)计算内存需求较大。

3、修正牛顿法

• 基本思路
  保留牛顿法确定的搜索方向，同时用一维搜索来确定步长。
• 特点
  继承了牛顿法优点的基础上，对初始点的要求不再那么严格了。但牛顿法的其他缺陷未能得到克服。

4、共轭方向法

特别地，当Q为单位矩阵时，称d(1),d(2)$d^{(1)},d^{(2)}$正交。

以上这种从任意点出发，沿某组共轭方向进行一维搜索的方法称为共轭方向法。
一般地，在n维空间可以找到n个互相共轭的方向，故而对于n元正定二次函数，利用共轭方向法总可以在n次迭代内找到极小点。
对于n元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就可以求得极小值，则称这种算法具有二次终止性。
一般来说，具有二次终止性的算法在应用于一般函数时，收敛速度较快。
至此，只是叙述了共轭方向法的基本思路，尚未言明如何寻找共轭方向。以下将介绍共轭梯度法

5、共轭梯度法

• 基本思路
  
• 具体细节
  设
  
  Pk+1=−▽f(Xk+1)+λkPk,  k=0,1,2,⋯,n−2.$$P_{k+1}=-▽f(X_{k+1})+{\lambda }_k{P}_k,k=0,1,2,\cdots ,n-2.$$
  
  通过计算可以确定：
  
  因为实际的目标函数并不一定是正定二次函数，所以在进行一轮迭代（就是每个方向都进行一次）后不一定能取得极小点。此时，我们令X0=Xk$X_0=X_k$再进行下一轮迭代即可。同时这样也克服了因舍入误差导致向量不再共轭的问题。
• 特点
  共轭梯度法可以看做最速下降法的一种改进（λk=0${\lambda }_k=0$即是最速下降法），收敛较快，与牛顿法相比则不必计算Hesse矩阵，对目标函数的性质要求较少，计算所需内存较少。

6、变尺度法

• 基本思路
  保持牛顿法收敛快的优点，同时避免Hesse矩阵的计算。
  牛顿法的迭代公式为：
  
  Xk+1=Xk−G−1kgk,k=0,1,2,⋯$$X_{k+1}=X_k-G_k^{-1}{g}_k,k=0,1,2,\cdots$$
  
  这里可以通过某种近似矩阵Hk$H_k$来代替G−1k$G_k^{-1}$,同时考虑到搜索步长，迭代公式变为：
  
  Xk+1=Xk−tkHkgk,$$X_{k+1}=X_k-t_k{H}_k{g}_k,$$
  
  Hk$H_k$需要满足一些条件：
  (1)Hk$H_k$正定，保证了迭代公式具有下降性质。
  (2)Hk$H_k$之间具有简单迭代形式，如Hk+1=Hk+Ek$H_{k+1}=H_k+E_k$，其中Ek$E_k$称为校正矩阵，该公式称为校正公式。
  (3)Hk$H_k$必须满足拟牛顿条件：
  
  其中g$g$为梯度。
  变尺度法的不同即是校正矩阵的不同，以下介绍两种常用算法：
• DFP算法
  
  Hk+1=Hk+SkSTkSTkyK−HkykyTkHkyTkHkyk.$$H_{k+1}=H_k+{\displaystyle \frac{S_k{S}_k^T}{S_k^T{y}_K}}-{\displaystyle \frac{H_k{y}_k{y}_k^T{H}_k}{y_k^T{H}_k{y}_k}}.$$
• BFGS算法
  考虑形式：
  
  Hk+1=Hk+SkSTkyTkSK−HkykyTkHkyTkHkyk+β(yTkSk)(yTkHkyk)WKWTk,$$H_{k+1}=H_k+{\displaystyle \frac{S_k{S}_k^T}{y_k^T{S}_K}}-{\displaystyle \frac{H_k{y}_k{y}_k^T{H}_k}{y_k^T{H}_k{y}_k}}+\beta (y_k^T{S}_k)(y_k^T{H}_k{y}_k)W_K{W}_k^T,$$
  
  其中
  
  Wk=SkyTkSk−HkykyTkHkyk.$$W_k={\displaystyle \frac{S_k}{y_k^T{S}_k}}-{\displaystyle \frac{H_k{y}_k}{y_k^T{H}_k{y}_k}}.$$
  
  可见，当β=0$\beta =0$时，即为DFP算法。
  而当β=1STkyk$\beta ={\displaystyle \frac{1}{S_k^T{y}_k}}$时，即是BFGS算法，其校正公式为：
  
  Hk+1=Hk+1STkyk[(1+yTkHkykSTkyk)SkSTk−HkyKSTk−SkyTkHk]$$\begin{gathered} H_{k+1}= \\ {H}_k+{\displaystyle \frac{1}{S_k^T{y}_k}}[(1+{\displaystyle \frac{y_k^T{H}_k{y}_k}{S_k^T{y}_k}})S_k{S}_k^T-H_k{y}_K{S}_k^T-S_k{y}_k^T{H}_k] \end{gathered}$$
• 特点
  对于DFP算法，由于一维搜索的不精确和计算误差的累积可能导致某一轮的Hk$H_k$奇异，而BFGS法则不是很容易发生此种情况。BFGS算法比DFP算法更具有好的数值稳定性。

7、坐标轮换法

• 基本思路
  依次在每个维度进行一维搜索。
  假设目标函数为f(x,y)$f(x,y)$，则依次在[1,0],[0,1]$[1,0],[0,1]$方向进行搜索。
• 特点
  算法简单，但计算效率较低。

8、单纯形法

• 基本思路
  对于n维问题，在n维空间中选择n+1个点作为顶点构成n维单纯形，找到这n+1个点中最差的点，并向其反方向搜索得到一个新点，与其余n个点构成新的单纯形。知道满足收敛条件。
• 具体细节
  
  
  
• 特点
  该方法占用内存很少，可以方便的求解一些精度要求较低的问题。但对于维度较高（>10）的问题不是很有效。