常见的优化算法

前言
梯度下降法
牛顿法和拟牛顿法
- 牛顿法
  - 方法说明
  - 牛顿法的优缺点总结：
- 拟牛顿法
  - 搜索极值
共轭梯度法
- 方法的表述
- 算法
序列二次规划
参考

前言

最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。

常见的优化算法有很多，涵盖了数学、工程、机器学习等多个领域。以下是一些常见的优化算法的概述：

1) 梯度下降法(Gradient Descent)

原理：通过计算目标函数的梯度(偏导数)来更新参数，使得目标函数最小化。梯度下降法的基本思想是沿着梯度的反方向更新参数，以最快的速度减少目标函数值。

种类：

• 批量梯度下降(Batch Gradient Descent)：每次迭代计算整个数据集的梯度，适合数据量小的情况。

• 随机梯度下降(Stochastic Gradient Descent, SGD)：每次迭代使用一个样本来计算梯度，适合数据量大的情况。

• 小批量梯度下降(Mini-batch Gradient Descent)：每次迭代使用数据集的一个小批量样本，结合了批量和随机梯度下降的优点。

2) 牛顿法(Newton's Method)

原理：利用目标函数的二阶导数(即Hessian矩阵)来加速优化过程。与梯度下降法相比，牛顿法每次更新时考虑了函数的曲率，因此收敛速度较快，但计算代价较高。

应用：适用于目标函数二阶导数可计算且问题规模较小的情况。

3) 拟牛顿法(Quasi-Newton Methods)

原理：拟牛顿法不直接计算Hessian矩阵，而是通过近似的方法来估算它，从而降低计算成本。最著名的拟牛顿法是BFGS(Broyden–Fletcher–Goldfarb–Shanno)算法。

应用：适用于中等规模的优化问题，尤其是在计算Hessian矩阵过于昂贵时。

4) 共轭梯度法(Conjugate Gradient Method)

原理：对于二次优化问题，共轭梯度法是一种迭代优化方法，它通过构造一组共轭方向来减少迭代次数。每一步的方向都是与之前的搜索方向“共轭”的。

应用：常用于大型稀疏线性系统的优化问题，尤其适用于内存限制较大的情境。

5) 启发式优化算法

a) 遗传算法(Genetic Algorithm, GA)

原理：遗传算法是一种基于自然选择和遗传机制的全局优化方法，通过模拟生物的进化过程来寻找最优解。基本操作包括选择、交叉、变异等。

应用：适用于搜索空间复杂、目标函数非线性且没有明显数学形式的优化问题。

b) 粒子群优化(Particle Swarm Optimization, PSO)

原理：粒子群优化是一种模拟鸟群觅食行为的优化算法。每个“粒子”代表一个潜在解，粒子通过个体历史最优位置和全体群体历史最优位置来更新自己的位置。

应用：适用于全局优化问题，特别是高维、多峰值问题。

c) 模拟退火(Simulated Annealing, SA)

原理：模拟退火算法模仿物理学中的退火过程，通过控制“温度”逐渐降低，从而在搜索空间中找到全局最优解。它允许接受一些次优解来跳出局部最优解。

应用：适用于解决组合优化问题，如旅行商问题(TSP)和调度问题。

6) 拉格朗日乘子法(Lagrange Multiplier Method)

原理：拉格朗日乘子法是一种求解约束优化问题的技术。通过引入拉格朗日乘子，将约束条件合并到目标函数中，从而转化为无约束问题进行优化。

应用：常用于带有等式约束的优化问题。高等数学里面有关于这部分的学习和使用，就不做介绍了。

7) 线性规划(Linear Programming, LP)

原理：线性规划求解的是具有线性目标函数和线性约束条件的优化问题。常用的求解方法有单纯形法和内点法。

应用：广泛应用于物流、生产调度、资源分配等领域。

用于求解线性规划类问题的工具个人推崇Lingo, 非常好用，Mathematica求解这类问题有大量丰富的函数，也强烈推荐使用。

8) 凸优化(Convex Optimization)

原理：凸优化问题是指目标函数是凸函数且约束条件也是凸的优化问题。凸优化理论提供了强大的数学工具，保证了全局最优解的存在和可求解性。

应用：许多工程和机器学习问题都可以建模为凸优化问题，如支持向量机(SVM)中的最优化问题。

9) 深度学习中的优化算法

原理：在神经网络和深度学习中，常用的优化算法有：

• Adam：结合了动量法和自适应学习率的方法，常用于训练神经网络。

• RMSprop：改进了梯度下降法，通过对历史梯度的平方进行加权平均来动态调整学习率。

• Adagrad：根据梯度的平方和调整每个参数的学习率，适用于稀疏数据。

下面对用于工作中比较多的一些优化算法做一些相关的介绍。

梯度下降法

梯度下降法(英语：Gradient descent)是一个一阶最优化算法，通常也称为最陡下降法，但是不该与近似积分的最陡下降法(英语：Method of steepest descent)混淆。要使用梯度下降法找到一个函数的局部极小值，必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。如果相反地向梯度正方向迭代进行搜索，则会接近函数的局部极大值点；这个过程则被称为梯度上升法。

这里简要的说明下梯度的定义：

$grad f(x_0,x_1,\dots,x_n)=(\frac{\partial f}{\partial x_0},\dots,\frac{\partial f}{\partial x_j},\dots,\frac{\partial f}{\partial x_n})$

函数在某一点的梯度是这样一个向量，它的方向与取得最大方向导数的方向一致，而它的模为方向导数的最大值。

这里注意三点：

• 梯度是一个向量，即有方向有大小；
• 梯度的方向是最大方向导数的方向；
• 梯度的值是最大方向导数的值。

描述

梯度下降方法基于以下的观察:如果实值函数F(x)在点a处可微且有定义,那么函数F(x)在a点沿着梯度相反的方向-∇F(a)下降最多。

因而，如果

$\mathbf{b}=\mathbf{a}-\gamma\nabla F(\mathbf{a})$

对于一个足够小数值 $\gamma>0$ 时成立，那么 $F(\mathbf{a})\geq F(\mathbf{b})$

考虑到这一点，我们可以从函数 F 的局部极小值的初始估计 $\mathbf{x}_{0}$ 出发，并考虑如下序列 ${\displaystyle\mathbf{x}_{0},\mathbf{x}_{1},\mathbf{x}_{2},\dots}$ 使得

$\mathbf{x}_{n+1}=\mathbf{x}_{n}-\gamma _{n}\nabla F(x_n),n\geq 0$

因此可得到

$F(\mathbf{x}_{0})\geq F(\mathbf{x}_{1})\geq F(\mathbf{x}_{2})\geq\cdots$

如果顺利的话序列 ( $\mathbf{x}_{n}$ )收敛到期望的局部极小值。注意每次迭代步长 $\gamma$ 可以改变。

下图示例了这一过程，这里假设 F 定义在平面上，并且函数图像是一个碗形。蓝色的曲线是等高线(水平集)，即函数 F 为常数的集合构成的曲线。红色的箭头指向该点梯度的反方向。(一点处的梯度方向与通过该点的等高线垂直)。沿着梯度下降方向，将最终到达碗底，即函数 F 局部极小值的点。

例子

梯度下降法处理一些复杂的非线性函数会出现问题，例如Rosenbrock函数

$f(x,y)=(1-x)^{2}+100(y-x^{2})^{2}.\quad$

其最小值在 (x,y)=(1,1) 处，数值为 f(x,y)=0。但是此函数具有狭窄弯曲的山谷，最小值 (x,y)=(1,1) 就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢。如下图所示

缺点

梯度下降法的缺点包括:

• 靠近局部极小值时速度减慢。

• 直线搜索可能会产生一些问题。

• 可能会“之字型”地下降。

从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。

在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

比如对一个线性回归(Linear Logistics)模型，假设下面的h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数。

$h(\theta)=\sum_{j=0}^n\theta_jx_j$

$J(\theta)=\frac{1}{2m}\sum_{i=1}^m(y^i-h_\theta(x^i))^2$

批量梯度下降法

(1)将J(theta)对theta求偏导，得到每个theta对应的的梯度：

$\frac{\partial J(\theta)}{\partial\theta_j}=-\frac{1}{m}\sum_{i=1}^m(y^i-h_\theta(x^i))x^i_j$

(2)由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta：

${\theta_j}^{'}=\theta_j+\frac{1}{m}\sum_{i=1}^m(y^i-h_\theta(x^i))x_j^i$

(3)从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。

　　对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为 $m*n^2$ 。

随机梯度下降

(1)上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：

$J(\theta)=\frac{1}{m}\sum_{i=1}^m\frac{1}{2}(y^i-h\theta(x^i))^2=\frac{1}{m}\sum_{i=1}^mcost(\theta,(x^i,y^i))$

$cost(\theta,(x^i,y^i))=\frac{1}{2}(y^i-h_\theta(x^i))^2$

(2)每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta：

$\theta_j^{'}=\theta_j+(y^i-h\theta(x^i))x_j^i$

(3)随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况(例如几十万)，那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

　　随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

牛顿法和拟牛顿法

牛顿法

牛顿法(英语：Newton’s method)又称为牛顿-拉弗森方法(英语：Newton-Raphson method)，它是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。

方法说明

首先,选择一个接近函数f(x)零点的x0,计算相应的f(x0)和切线斜率f’(x0)(这里f表示函数f的导数)。然后我们计算穿过点(x0,f(x0))并且斜率为f’(x0)的直线和x轴的交点的x坐标,也就是求如下方程的解:

$0=(x-x_0)\cdot f^{'}(x_0)+f(x_0)$

我们将新求得的点的x坐标命名为x1,通常x1会比x0更接近方程f(x)=0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示:

$x_{n+1}=x_n-\frac{f(x_n)}{f^{'}(x_n)}$

然而当f(x)=0在x=a处有m重根时,这时牛顿法会降为线性收敛,虽然使用牛顿法也可以继续算下去,但收敛速度会减慢。

牛顿法的优缺点总结：

• 优点：二阶收敛，收敛速度快；

• 缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

拟牛顿法

拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。

搜索极值

与牛顿法相同,拟牛顿法是用一个二次函数以近似目标函数f(x). f(x)的阶泰勒展开是

$x_k{\displaystyle f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{T}\Delta x+{\frac{1}{2}}\Delta x^{T}B\Delta x.}$

其中, $\nabla f$ 表示f(x)的梯度,B表示Hessian矩阵H[f(x)]的近似.梯度 $\nabla f$ 可进一步近似为下列形式

${\displaystyle\nabla f(x_{k}+\Delta x)\approx\nabla f(x_{k})+B\Delta x.}$

令上式等于0,计算出Newton步长△x,

${\displaystyle\Delta x=-B^{-1}\nabla f(x_{k}).}$

然后构造H[f(x)]的近似B满足

${\displaystyle\nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\Delta x.}$

以下方式更新B

$B_{k+1}=\arg\min _{B}\|B-B_{k}\|_{V}.$

近似Hessian矩阵一般以单位矩阵等作为初期值. 最优化问题的解 $x_{k}$ 由根据近似所得的 $B_{k}$ 计算出的Newton步长更新得出.

以下为该算法的总结:

• $\Delta x_{k}=-\alpha B_{k}^{-1}\nabla f(x_{k})$

• $x_{k+1}=x_{k}+\Delta x_{k}$

• 计算新一个迭代点下的梯度 $\nabla f(x_{k+1})$

• 令 $y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$

• 利用 $y_{k}$ , 直接近似Hessian矩阵的逆矩阵 $B_{k+1}^{-1}$ . 近似的方法如下表:

Method	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
DFP法	$\left(I-{\frac {y_{k}\,\Delta x_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}$	$H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}-{\frac {H_{k}y_{k}y_{k}^{T}H_{k}^{T}}{y_{k}^{T}H_{k}y_{k}}}$
BFGS法	$B_{k}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{T}}{\Delta x_{k}^{T}B_{k}\,\Delta x_{k}}}$	$\left(I-{\frac {y_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)^{T}H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{T}}{y_{k}^{T}\,\Delta x_{k}}}$
Broyden法	$B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{T}\,\Delta x_{k}}}\,\Delta x_{k}^{T}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})\Delta x_{k}^{T}H_{k}}{\Delta x_{k}^{T}H_{k}\,y_{k}}}$
Broyden族	$(1-\varphi _{k})B_{k+1}^{BFGS}+\varphi _{k}B_{k+1}^{DFP},\qquad \varphi \in [0,1]$
SR1法	$B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{T}}{(y_{k}-B_{k}\,\Delta x_{k})^{T}\,\Delta x_{k}}}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{T}}{(\Delta x_{k}-H_{k}y_{k})^{T}y_{k}}}$

共轭梯度法

共轭梯度法(英语：Conjugate gradient method)，是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法。共轭梯度法是一个迭代方法，它适用于系数矩阵为稀疏矩阵的线性方程组，因为使用像Cholesky分解这样的直接方法求解这些系统所需的计算量太大了。这种方程组在数值求解偏微分方程时很常见。

共轭梯度法也可以用于求解无约束的最优化问题。

方法的表述

要求解下列线性系统

$Ax=b$

其中 $n\times n$ 矩阵 A 是对称的，正定的，并且是实系数的。将系统的唯一解记作 x∗

算法

经过一些简化，可以得到下列求解 $Ax=b$ 的算法，其中A是实对称正定矩阵。

序列二次规划

序列二次规划(Sequential Quadratic Programming，SQP)是一类用于解决非线性优化问题的迭代方法，广泛应用于约束优化问题，尤其是在控制、机器人学和工程设计中。SQP方法通过将非线性问题转化为一系列二次规划问题来逐步逼近最优解。它的基本思想是在每次迭代中通过求解一个二次优化问题，找到一个改进方向，并在此方向上更新当前解。

SQP方法的基本步骤

目标函数和约束的泰勒展开

• 对于给定的非线性目标函数和约束条件，SQP方法首先对目标函数和约束条件在当前点进行一阶(梯度)和二阶(Hessian矩阵)泰勒展开。

构造二次规划子问题

• 使用当前点的信息(包括目标函数的梯度和约束的雅可比矩阵、Hessian矩阵等)来构造一个近似的二次规划问题(QP)。

• 该QP问题通常形如

$\min\limits_{\delta x}\frac{1}{2}\delta x^TH_k\delta x+g_k^T\delta x$

• 其中，Hk是目标函数的Hessian矩阵的近似，gk是目标函数梯度的近似，δx是当前解的改进方向。

解二次规划子问题

• 通过求解上面构造的QP子问题，得到一个搜索方向(即改进方向)δx，并更新当前解：

$x_{k+1}=x_k+\delta x_k$

判断收敛性

• 判断算法是否满足收敛准则(例如目标函数的变化足够小、梯度足够接近零、约束条件得到满足等)。如果收敛条件满足，则终止；否则，返回步骤1继续迭代。

约束处理

• SQP方法通过引入拉格朗日乘子来处理约束问题。约束可以是等式约束或不等式约束，常见的约束类型包括线性约束和非线性约束。

SQP的优点

• 高效性: SQP在大多数优化问题中表现出较快的收敛速度，尤其适用于具有光滑目标函数和约束的非线性优化问题。

• 适应性: 能够处理各种类型的约束(包括等式约束、不等式约束、边界约束等)。

• 精确性: 由于每一步都通过求解一个二次规划问题，它能较精确地逼近局部最优解。

SQP的缺点

• 计算成本高: 每次迭代都需要求解一个二次规划问题，这可能需要较高的计算资源，尤其是在问题规模较大时。

• 需要二阶导数信息: SQP需要目标函数和约束的Hessian矩阵(或其近似)，这在某些情况下可能难以获得，或者计算复杂。

• 对初始值敏感: SQP对初始解有一定的依赖性，若初始解距离最优解较远，可能会收敛到局部最优解。

应用领域

SQP方法在许多领域中得到了广泛应用，特别是以下几类问题：

• 机器人学中的路径规划和轨迹优化:SQP常用于求解具有非线性约束的运动规划问题，如机器人路径的优化。

• 控制理论: SQP用于求解最优控制问题，尤其是涉及非线性动力学和约束的控制问题。

• 结构优化: 在工程设计中，SQP可用于结构优化问题，例如材料分布的优化。

• 经济学和金融中的最优决策: SQP也可用于经济学和金融领域中的非线性最优化问题，如投资组合优化。

参考

[1] chatGPT

[2] 维基百科

[3] 几种常见的优化算法

[4] 牛顿法