2020-06-23优化算法整理

what

特点

梯度下降法

批量梯度下降

选择适当的初值x0，并以当前位置的负梯度方向作为搜索方向（为当前位置的最快下降方向），选取适当的步长（学习率），不断迭代更新x的值，极小化目标函数，最终达到收敛。

样本很大-随机梯度下降法/小批量梯度下降法

*函数在一点沿梯度方向的变化率最大

每迭代一步，都要用到训练集所有的数据，风险函数最小，最终求解的是全局的最优解

更准确

速度慢，对于大规模样本问题效率低下

随机梯度下降

每次迭代只使用一个样本，迭代次数增加

准确度下降，最终结果往往是在全局最优解附近，适用于大规模训练样本情况

小批量梯度下降

每次迭代使用固定数量（小于总体）的样本来对参数进行更新

牛顿

牛顿法

利用迭代点X k处的一阶导数(梯度)和二阶导数(海森矩阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值

二阶收敛，收敛速度快；但每一步都需要求解目标函数的海森矩阵的逆矩阵，计算比较复杂。

初始点选择很重要

适合设计变量数目小 目标函数阶次低

拟牛顿法

用其他矩阵来代替海森矩阵

DFP

BFGS

改善牛顿法每次需要求解复杂的海森矩阵的逆矩阵的缺陷，它使用正定矩阵来近似海森矩阵的逆，从而简化了运算的复杂度

共轭梯度法

每个搜索方向是相互共轭的，重点自于优化方向和优化步长的选择

如何寻找共轭方向？

初始已知点的负梯度方向为初始方向，沿此方向继续搜索，接下来的共轭方向由迭代点的负梯度方向和上一次的共轭方向线性组合来确定。

每一个共轭方向都依赖迭代点负梯度

每一次优化方向可与之前的优化方向正交

一阶导，速度快

最有效算法之一

适合优化变量数目较多的中等规模优化问题

启发式优化

（采用经验规则进行选择的方法）

遗传算法

利用生物进化和遗传的经验，根据生物分离和自由组合的规律，能够对非线性、多变量、多目标的自适应系统进行运算。

参数编码（字符、二进制）-初始群体的设定-适应度函数的设计（适应度高的个体参与遗传、适应度低淘汰）-遗传操作设计（复制、交叉、变异）-控制参 数设定

使用交换和突变产生新个体，进行不断的优化，结果不断逼近全局最优解

能够进行并行式运算

运行时间长

蚁群算法

模拟蚂蚁寻找食物的过程（应用于求解TSP问题）

初始化，将蚂蚁置于顶点上，蚂蚁按照概率函数选择下一个城市，记录迭代最佳路线，并更新信息素值

正反馈机制

适合图上搜索路径问题

粒子群算法

模拟鸟群捕食行为，鸟类知道自己距离食物的距离，故搜寻距离食物最近的鸟的周围区域。

求解实数问题，求解速度快

可能会求得局部最优解

模拟退火算法

物体逐渐降温，最终到达晶体态（能量最低），对应于算法中的全局最优解。温度下降过快，原子缺少时间排列（较高能量的非晶体）这就是局部最优解。

跳出局部最优：增加点能量再次冷却

Metropolis法则进行比较两状态，以概率接受新状态

以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局最优解

渐进收敛性

大规模组合优化 非凸函数