优化算法使用总结——0.618法、梯度下降、牛顿法、共轭梯度、外罚、内罚

实用优化算法总结

实用优化算法的种类繁多，并且各自使用的领域有所区别，为此，设计有多种优化算法，本文着重介绍其中几种，见目录。
本篇中涉及到的实验代码已上传至GitHub

最优化问题，可以分为两大部分“无约束最优化问题”和“约束最优化问题”。

无约束最优化问题

黄金分割法

黄金分割法，也叫0.618（$\tau =0.618$）法，这个方法可所谓足够简单，同时它适用的范围也就相对有限，需要给定单峰目标函数，以及代求区间[$a$₀，$b$₀]
算法设计：
步骤1：给定$a$₀>0，$b$₀>0，i=0，ε>0，$\tau =0.618$
步骤2：若$b$_i-$a$_i<ε，则$\alpha$^*=$\frac{b_i+a_i}{2}$，输出$\alpha$^*，算法停止
步骤3：计算

${\alpha }_i^l$= $a$ _i $+$(1- $\tau$) $($ $b$ _i- $a$ _i $)$
${\alpha }_i^r$= $a$ _i $+$ $\tau$( $b$ _i- $a$ _i $)$
步骤4：若 ${\alpha }_i^l$< ${\alpha }_i^r$，则 $a$ _i+1= $a$ _i， $b$ _i+1= ${\alpha }_i^r$ ，否则 $a$ _i+1= ${\alpha }_i^l$， $b$ _i+1= $b$ _i ，转步骤2
通过上述算法步骤，容易得知当 $\tau$时，从区间[ $a$ ₀， $b$ ₀]开始迭代，经过m次迭代后，区间长度为 $\tau$ ^m( $b$ ₀- $a$ ₀).

看流程图可能思路更清晰：

那我们可能会想，既然区间在每次迭代都会缩短，那如何使它每次缩短到不能再缩短就可以达到最快速度了，基于这种想法，$\tau$可以取不同值，相较于0.618，事实上我们可以用斐波那契数列来替换每次的$\tau$

例题：$f(x)=e^x+1/e^x$ 在[-1，2]区间内的极小值点、极小值，运行结果如下：

最速下降法

最速下降法，又叫梯度下降法，具有代码实现简单、原理简单的特点。
通过梯度概念的学习，我们都知道梯度代表的方向是函数递增最快的方向，所以负梯度方向就是函数递进最快的方向，由此，我们利用函数每次的负梯度方向作为搜索方向，利用上述的黄金分割法搜索目标函数在搜索方向上的极小值作为前进的步长，就可得到最速下降法，详情见下方算法设计。

这里提到的搜索方向、步长类似于神经网络中的概念，如步长类似于学习率

算法设计：
步骤1：给出$x_0\in R^n$$\times$$R^n$，k=0，ε>0
步骤2：若终止条件满足($||g_k||<\epsilon$)，则迭代停止
步骤3：计算$d_k=-g_k$
步骤4：在$d_k$方向上利用一维精确线性搜索(如黄金分割法、多项式插值法)求步长${\alpha }_k$
步骤5：$x_{k+1}=x_k+{\alpha }_k{d}_k，k=k+1$，转步骤2

缺点：会产生Zigzag现象，由于采用精确搜索、且搜索方向为负梯度方向，造成了该方法收敛速度不够快，效率不高的缺点。

例题：$min(x_1^2+2x_2^2)$，初始点为$x_0=(4,4)$，求最小值点。运行结果如下图：

牛顿法

这个方法是个大家庭，其中有基本牛顿法、阻尼牛顿法、拟牛顿法
相较于梯度下降法，梯度下降法只用到了一次导数，而牛顿法引入高阶导数，提高了算法效率。
利用泰勒展开式：
$q_k(x)=f(x)=f(x_k)+▽f^T(x-x_k)+\frac{1}{2}(x-x_k{)}^T{G}_k(x-x_k)$
当G_k正定时，$q_k(x)$有唯一极小点，同时

$▽q_k(x+1)=0$
$G_k(x_{k+1}-x_k)+▽f_k=0$
$x_{k+1}=x_k+G_k^{-1}▽f_k$ 【 递推式】
通过上述的分析，可以得到牛顿法的递推式 $x_{k+1}=x_k+G_k^{-1}▽f_k$，令 $d_k=-G_k^{-1}▽f_k$（ $▽f_k$即 $g_k$）

基本牛顿法

算法设计：
步骤1：给出$x_0\in R^n$$\times$$R^n$，k=0，ε>0
步骤2：若终止条件满足($||g_k||<\epsilon$)，则迭代停止
步骤3：计算$d_k$
步骤4：计算$x_{k+1}=x_k+d_k，k=k+1$，转步骤2

特点：
1.当初始点选取位置靠近最优解位置时，算法可以达到二次收敛
2.对于正定二次函数，牛顿法可以一次迭代求出最优解
3.对多数问题并非全局收敛，收敛至鞍点、极大点的概率不小
4.计算量相对于梯度下降法增大，且计算机计算逆矩阵较为耗时

例题1：$x_1^2+4x_2^2+9x_3^2-2x_1+18x_2$ 的极小点，求解结果如下：
初始点取得是$x_0=(1,1,1)$

通过结果可以得知，对于正定二次函数，基本牛顿法经过一次迭代即可求解。

例题2：利用Newton法求解$min(x_1-1{)}^2+2x_2^2$的极小点，$x_0=(0,1{)}^T$，求解结果如下图：

借助图像可以看出来，基本牛顿法对于非二次函数问题，求解较为低效。

阻尼牛顿法

算法设计：
步骤1：给出$x_0\in R^n$$\times$$R^n$，k=0，ε>0
步骤2：若终止条件满足($||g_k||<\epsilon$)，则迭代停止
步骤3：计算$d_k$，在$d_k$方向上利用一维精确线性搜索(如黄金分割法、多项式插值法)求步长${\alpha }_k$
步骤4：计算$x_{k+1}=x_k+{\alpha }_k{d}_k，k=k+1$，转步骤2

相较于基牛顿法，阻尼牛顿法在其基础上，使用了线性搜索，克服了基本牛顿法的3、4缺点

LM方法：克服$G^{-1}$奇异、非正定的问题

由于上述的基本牛顿法、阻尼牛顿法，均使用到了$G^{-1}$，且要求$G$为正定矩阵，但现实情况不可能总符合要求。

当$g_k^T{d}_k<0$，即$-g_k^T{G}_k^{-1}{g}_k<0$，则$d_k$为下降方向

当$G$非正定时，我们知道特征值（${\lambda }_i,i\in N$）非全部大于0，此时我们需要对矩阵$G$进行改造：($I$为单位矩阵，$v_k>0$)

$(G_k+v_{k}I)d=-g_k$
此时矩阵 $(G_k+v_{k}I)$的特征值为 ${\lambda }_i+v_k,i\in N$，若是所有特征值均大于0，则 $v_k$取合适值即可。

拟牛顿法

也是本人最为喜欢的一种优化算法，方法思想，引入矩阵$H_k$逼近$G_k^{-1}$，而并非直接计算$G_k^{-1}$。
算法设计：
步骤1：给出$x_0\in R^n$$\times$$R^n$，对称正定矩阵$H_0\in R^n$$\times$$R^n$，$k=0，\epsilon >0$
步骤2：若终止条件满足($||g_k||<\epsilon$)，则迭代停止
步骤3：计算$d_k=-H_k{g}_k$，在$d_k$方向上线性搜索求步长${\alpha }_k$，计算$x_{k+1}=x_k+{\alpha }_k{d}_k$
步骤4：更新$H_k$得$H_{k+1}$，使得$H_{k+1}$满足A式，$k=k+1$，转步骤2
A式：

• 秩一矫正：$H_{k+1}=H_k+\beta u{u}^T$ （$u,\beta \in R^n$$\times$$R^n$）
  $H_{k+1}^{SR1}=H_k+\frac{(s_k-H_k{y}_k)(s_k-H_k{)}^T}{(s_k-H_k{y}_k{)}^T{y}_k}$
  实现简单，但此方法不能满足正定继承性
• DFP公式：
  $H_{k+1}^{DFP}=H_k+\frac{s_k{s}_k^T}{s_k^T{y}_k}-\frac{H_k{y}_k{y}_k^T{H}_k}{y_k^T{H}_k{y}_k}$
  满足正定继承性，即$H_0$为正定则$H_k$为正定
• BFGS公式：(被誉为最好用的算法)
  $H_{k+1}^{BFGS}=H_k+(1+\frac{y_k^T{H}_k{y}_k}{y_k^T{s}_k})\frac{s_k{s}_k^T}{y_k^T{s}_k}-(\frac{s_k{y}_k^T{H}_k+H_k{y}_k{s}_k^T}{y_k^T{s}_k})$

特点：
1.克服了牛顿法计算量大的问题
2.避免了矩阵非正定的问题
3.效率高，收敛快，具有二次终止性

例题：利用DFP拟牛顿法求解$min(x_1^2+x_2^2-x_1{x}_2+2x_1-4x_2)$的最优解，运行结果如下图

好用！

共轭方向法

由于对于二次函数，形如$f(x)=\frac{1}{2}{x}^{T}Gx+b^{T}x+C$，当 $G$正定时， Newton只需要迭代一次即可找到最优解，而梯度下降法需要无数次。但同时Newton法每迭代一步计算量较大，反而最速下降法计算量十分小，故一种折中的算法：共轭方向法
引入：
如二维二次函数要在两次迭代内最小计算量求出最优解：

迭代点	搜索方向	最优步长
$x_0$	$d_0$	$a_0$
$x_1$	$d_1$	$a_1$
$x^{\ast }=x_2$
$▽f(x_2)=G{x}_2+b=G(x_1+a_1{d}_1)+b=(G{x}_1+b)+a_{1}G{d}_1=0$
又因为精确搜索$▽f(x_{k+1}{)}^T{d}_k=0$
得$(G{x}_1+b{)}^T{d}_0=0$
得$0=d_0^T((G{x}_1+b)+a_{1}G{d}_1)=a_1{d}_0^{T}G{d}_1$
则满足$d_0^{T}G{d}_1=0$，即两次迭代中搜索方向为共轭方向

设$G$为n阶正定矩阵，$d_1,d_2,d_3......d_k$为n维向量，如果$d_i^{T}G{d}_j=0$($i\ne j$，$i,j=1,2,\mathrm{3......}k$)，则称$d_1,d_2,d_3......d_k$向量组关于$G$共轭。

共轭梯度法

由于共轭方向法需要在计算前提供一组完整的共轭方向，这显然无法达到自动化算法的目的，故我们想要算法在迭代过程中自动计算下一次迭代的共轭方向，引入共轭梯度法
算法设计：
步骤1：$x_0\in R^n，k=0$
步骤2：若$||g_k||\leqq \epsilon$，停止迭代
步骤3：若$k=0，则{\beta }_{-1}=0，否则计算{\beta }_{k-1}，令d_k=-g_k+{\beta }_{k-1}{d}_{k-1}$
步骤4：一维精确搜索得步长${\alpha }_k$
步骤5：$x_{k+1}=x_k+{\alpha }_k{d}_k，k++，转步骤2$

注：
①$d_0=-g_0$
②$d_k=-g_k+{\beta }_{k-1}{d}_{k-1}，由d_k^{T}G{d}_{k-1}=0得{\beta }_{k-1}=\frac{g_k^{T}G{d}_{k-1}}{d_{k-1}^{T}G{d}_{k-1}}$
若采用非精确搜索，则FR、PRP可能产生上升的方向，导致效果不好。
共轭梯度法和共轭方向法均满足有限终止性

同时${\beta }_{k-1}$还有其他形式：
FR共轭梯度法:${\beta }_{k-1}=\frac{g_k^T{g}_k}{g_{k-1}^T{g}_{k-1}}$
PRP共轭梯度法:${\beta }_{k-1}=\frac{g_k^T(g_k-g_{k-1})}{g_{k-1}^T{g}_{k-1}}$
重开始的共轭梯度法：即每迭代n次，就重新将搜索方向设为负梯度方向

约束最优化问题

一般约束优化问题

等下次更新吧

$minf(x)$