常见的几种最优化方法（梯度降低法、牛顿法、拟牛顿法、共轭梯度法等）

咱们每一个人都会在咱们的生活或者工做中遇到各类各样的最优化问题，好比每一个企业和我的都要考虑的一个问题“在必定成本下，如何使利润最大化”等。最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。随着学习的深刻，博主愈来愈发现最优化方法的重要性，学习和工做中遇到的大多问题均可以建模成一种最优化模型进行求解，好比咱们如今学习的机器学习算法，大部分的机器学习算法的本质都是创建优化模型，经过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的最优化方法有梯度降低法、牛顿法和拟牛顿法、共轭梯度法等等。html

1. 梯度降低法（Gradient Descent）

梯度降低法是最先最简单，也是最为经常使用的最优化方法。梯度降低法实现简单，当目标函数是凸函数时，梯度降低法的解是全局解。通常状况下，其解不保证是全局最优解，梯度降低法的速度也未必是最快的。梯度降低法的优化思想是用当前位置负梯度方向做为搜索方向，由于该方向为当前位置的最快降低方向，因此也被称为是”最速降低法“。最速降低法越接近目标值，步长越小，前进越慢。梯度降低法的搜索迭代示意图以下图所示：算法

梯度降低法的缺点：机器学习

　　（1）靠近极小值时收敛速度减慢，以下图所示；函数

　　（2）直线搜索时可能会产生一些问题；性能

　　（3）可能会“之字形”地降低。学习

从上图能够看出，梯度降低法在接近最优解的区域收敛速度明显变慢，利用梯度降低法求解须要不少次的迭代。优化

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

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

1）批量梯度降低法（Batch Gradient Descent，BGD）3d

（1）将J(theta)对theta求偏导，获得每一个theta对应的的梯度：

（2）因为是要最小化风险函数，因此按每一个参数theta的梯度负方向，来更新每一个theta：

（3）从上面公式能够注意到，它获得的是一个全局最优解，可是每迭代一步，都要用到训练集全部的数据，若是m很大，那么可想而知这种方法的迭代速度会至关的慢。因此，这就引入了另一种方法——随机梯度降低。

对于批量梯度降低法，样本个数m，x为n维向量，一次迭代须要把m个样本所有带入计算，迭代一次计算量为m*n²。

2）随机梯度降低（Stochastic Gradient Descent，SGD）

（1）上面的风险函数能够写成以下这种形式，损失函数对应的是训练集中每一个样本的粒度，而上面批量梯度降低对应的是全部的训练样本：

（2）每一个样本的损失函数，对theta求偏导获得对应梯度，来更新theta：

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

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

对批量梯度降低法和随机梯度降低法的总结：

批量梯度降低---最小化全部训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，可是对于大规模样本问题效率低下。

随机梯度降低---最小化每条样本的损失函数，虽然不是每次迭代获得的损失函数都向着全局最优方向， 可是大的总体的方向是向全局最优解的，最终的结果每每是在全局最优解附近，适用于大规模训练样本状况。

2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）

　　1）牛顿法（Newton's method）

　　牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f (x)的泰勒级数的前面几项来寻找方程f (x) = 0的根。牛顿法最大的特色就在于它的收敛速度很快。

　　具体步骤：

　　首先，选择一个接近函数 f (x)零点的 x₀，计算相应的 f (x₀) 和切线斜率f  ' (x₀)（这里f ' 表示函数 f  的导数）。而后咱们计算穿过点(x_0,  f  (x₀)) 而且斜率为f '(x₀)的直线和 x 轴的交点的x坐标，也就是求以下方程的解：

　　咱们将新求得的点的 x 坐标命名为x₁，一般x₁会比x₀更接近方程f  (x) = 0的解。所以咱们如今能够利用x₁开始下一轮迭代。迭代公式可化简为以下所示：

　　已经证实，若是f  ' 是连续的，而且待求的零点x是孤立的，那么在零点x周围存在一个区域，只要初始值x₀位于这个邻近区域内，那么牛顿法一定收敛。 而且，若是f  ' (x)不为0, 那么牛顿法将具备平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增长一倍。下图为一个牛顿法执行过程的例子。

　　因为牛顿法是基于当前位置的切线来肯定下一次的位置，因此牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维状况）以下图所示：

　　牛顿法搜索动态示例图：

关于牛顿法和梯度降低法的效率对比：

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

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

注：红色的牛顿法的迭代路径，绿色的是梯度降低法的迭代路径。

牛顿法的优缺点总结：

　　优势：二阶收敛，收敛速度快；

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

　　2）拟牛顿法（Quasi-Newton Methods）

　　拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证明了这种新的算法远比其余方法快速和可靠，使得非线性优化这门学科在一晚上之间日新月异。

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

　　具体步骤：

　　拟牛顿法的基本思想以下。首先构造目标函数在当前迭代x_k的二次模型：

　　这里B _k是一个对称正定矩阵，因而咱们取这个二次模型的最优解做为搜索方向，而且获得新的迭代点：

　　其中咱们要求步长a _k 知足Wolfe条件。这样的迭代与牛顿法相似，区别就在于用近似的Hesse矩阵B _k 

代替真实的Hesse矩阵。因此拟牛顿法最关键的地方就是每一步迭代中矩阵B _k

的更新。如今假设获得一个新的迭代x _k+1，并获得一个新的二次模型：

　　从而获得

3. 共轭梯度法（Conjugate Gradient）

 

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

 参考：http://www.cnblogs.com/maybe2030/p/4751804.html