实用优化算法总结

实用优化算法的种类繁多，并且各自使用的领域有所区别，为此，设计有多种优化算法，本文着重介绍其中几种，见目录。
如有需要，matlab版代码会后期放出来
最优化问题，可以分为两大部分“无约束最优化问题”和“约束最优化问题”。

无约束最优化问题

黄金分割法

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

$α^l_i$αil​=$a$a_i$+$+(1-$τ$τ)$($($b$b_i-$a$a_i$)$)
$α^r_i$αir​=$a$a_i$+$+$τ$τ($b$b_i-$a$a_i$)$)
步骤4：若$α_i^l$αil​<$α_i^r$αir​，则$a$a_i+1=$a$a_i，$b$b_i+1=$α^r_i$αir​ ，否则$a$a_i+1=$α^l_i$αil​，$b$b_i+1=$b$b_i ，转步骤2
通过上述算法步骤，容易得知当$τ$τ时，从区间[$a$a₀，$b$b₀]开始迭代，经过m次迭代后，区间长度为$τ$τ^m($b$b₀-$a$a₀).

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

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

由于matlab涉及到多个文件，代码资源上传至网络较为方便，可自行下载。
例题：$f(x)=e^x+1/e^x$f(x)=ex+1/ex 在[-1，2]区间内的极小值点、极小值，运行结果如下：

最速下降法

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

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

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

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

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

牛顿法

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

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

基本牛顿法

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

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

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

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

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

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

阻尼牛顿法

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

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

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

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

当$g^T_kd_k<0$gkT​dk​<0，即$-g^T_kG^{-1}_kg_k<0$−gkT​Gk−1​gk​<0，则$d_k$dk​为下降方向

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

$(G_k+v_kI)d=-g_k$(Gk​+vk​I)d=−gk​
此时矩阵$(G_k+v_kI)$(Gk​+vk​I)的特征值为$λ_i+v_k,i∈N$λi​+vk​,i∈N，若是所有特征值均大于0，则$v_k$vk​取合适值即可。

拟牛顿法

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

• 秩一矫正：$H_{k+1}=H_k+βuu^T$Hk+1​=Hk​+βuuT （$u,β∈R^n$u,β∈Rn$\times$×$R^n$Rn）
  $H_{k+1}^{SR1}=H_k+\frac{(s_k-H_ky_k)(s_k-H_ky_k)^T}{ (s_k-H_ky_k)^Ty_k}$Hk+1SR1​=Hk​+(sk​−Hk​yk​)Tyk​(sk​−Hk​yk​)(sk​−Hk​yk​)T​
  实现简单，但此方法不能满足正定继承性
• DFP公式：
  $H_{k+1}^{DFP}=H_k+\frac{s_ks_k^T}{s_k^Ty_k}-\frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}$Hk+1DFP​=Hk​+skT​yk​sk​skT​​−ykT​Hk​yk​Hk​yk​ykT​Hk​​
  满足正定继承性，即$H_0$H0​为正定则$H_k$Hk​为正定
• BFGS公式：(被誉为最好用的算法)
  $H_{k+1}^{BFGS}=H_k+(1+\frac{y_k^TH_ky_k}{y_k^Ts_k})\frac{s_ks_k^T}{y_k^Ts_k}-(\frac{s_ky_k^TH_k+H_ky_ks_k^T}{y_k^Ts_k})$Hk+1BFGS​=Hk​+(1+ykT​sk​ykT​Hk​yk​​)ykT​sk​sk​skT​​−(ykT​sk​sk​ykT​Hk​+Hk​yk​skT​​)

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

例题：利用DFP拟牛顿法求解$min(x_1^2+x_2^2-x_1x_2+2x_1-4x_2)$min(x12​+x22​−x1​x2​+2x1​−4x2​)的最优解，运行结果如下图

好用！

共轭方向法

下次更新再写吧
未完待续……

约束最优化问题

三道例题见-> 已上传