Math 常见的几种最优化方法 - Poll的笔记 - 博客园
最优化方法与凸优化，我们研究凸优化，是因为凸优化比较好研究，其实正确的叫法应当叫最优化方法。

梯度下降法

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。

梯度下降的缺点：

靠近极小值时收敛速度减慢，如下图所示
直线搜索时可能会产生一些问题
可能会“之字形”地下降。

为什么计算函数极值用梯度下降算法而不直接令导数为0求解
并不是所有的函数都可以根据导数求出取得0值的点的, 现实的情况可能是:
1、可以求出导数在每个点的值, 但是直接解方程解不出来,
2、计算机更加适合用循环迭代的方法来求极值。

批量梯度下降法（BGD）

最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。

随机梯度下降法（SGD）

最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

牛顿法和拟牛顿法

牛顿法

如何通俗易懂地讲解牛顿迭代法？
五次及以上多项式方程没有根式解（就是没有像二次方程那样的万能公式）。没有根式解不意味着方程解不出来，数学家也提供了很多方法，牛顿迭代法就是其中一种。

代数解法

不总是收敛（不总是能求得足够近似的根）

充分条件：

也就是说有很多情况下选择牛顿法，根不收敛。

而且不能完整求出所有的根，只能求到起始点附近的根。

总结

应用牛顿法最好：

函数在整个定义域内最好是二阶可导的
起始点对求根计算影响重大，可以增加一些别的手段进行试错。

求解最值问题

牛顿法也被用于求函数的最值。由于函数取最值的点处的导数值为零，故可用牛顿法求导函数的零点，其迭代式为

高维情况的牛顿迭代式

高维情况依然可以用牛顿迭代求解，但是问题是Hessian矩阵引入的复杂性，使得牛顿迭代求解的难度大大增加，但是已经有了解决这个问题的办法就是Quasi-Newton methond，不再直接计算hessian矩阵，而是每一步的时候使用梯度向量更新hessian矩阵的近似。

关于牛顿法与梯度下降法效率的对比

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）

根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

优缺点

优点：二阶收敛，收敛速度快；
缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

拟牛顿法

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

针对牛顿法中海塞矩阵的计算问题，拟牛顿法主要是使用一个海塞矩阵的近似矩阵来代替原来的还塞矩阵，通过这种方式来减少运算的复杂度。其主要过程是先推导出海塞矩阵需要满足的条件，即拟牛顿条件（也可以称为拟牛顿方程）。然后我们构造一个满足拟牛顿条件的近似矩阵来代替原来的海塞矩阵。

外，在满足拟牛顿条件的基础上如何构造近似的海塞矩阵，这有很多种方法，比如：DFP算法，BFGS算法，L-BFGS算法以及Broyden类算法等。常用前两种。

在牛顿法推导中：

然后对f(x)求偏导：

令x=xk得到：

g等于f的一阶导。

简化：

于是：

在满足此条件的基础上如何构造近似海塞矩阵呢？下面介绍两个方法：DFP算法和BFGS算法。

DFP算法

BFGS算法

　　BFGS算法是用直接逼近海塞矩阵的方式来构造近似海塞矩阵，同样，我们使用迭代的方式来逐步逼近。我们使用B来表示海塞矩阵的近似矩阵，而在DFP算法中我们是直接使用D来构造近似海塞矩阵的逆矩阵。

共轭梯度法

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

注：绿色为梯度下降法，红色代表共轭梯度法

启发式优化方法

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多，包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。

　　还有一种特殊的优化算法被称之多目标优化算法，它主要针对同时优化多个目标（两个及两个以上）的优化问题，这方面比较经典的算法有NSGAII算法、MOEA/D算法以及人工免疫算法等。

解决约束优化问题—拉格朗日乘数法

拉格朗日乘数法的基本思想

　作为一种优化算法，拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数

　　如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题？拉格朗日乘数法从数学意义入手，通过引入拉格朗日乘子建立极值条件，对n个变量分别求偏导对应了n个方程，然后加上k个约束条件（对应k个拉格朗日乘子）一起构成包含了（n+k）变量的（n+k）个方程的方程组问题，这样就能根据求方程组的方法对其进行求解。

拉格朗日乘数法的基本形态

拉格朗日乘数法与KKT条件

我们上述讨论的问题均为等式约束优化问题，但等式约束并不足以描述人们面临的问题，不等式约束比等式约束更为常见，大部分实际问题的约束都是不超过多少时间，不超过多少人力，不超过多少成本等等。所以有几个科学家拓展了拉格朗日乘数法，增加了KKT条件之后便可以用拉格朗日乘数法来求解不等式约束的优化问题了。

　KKT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件.