目录
牛顿法和拟牛顿法
共轭梯度法
启发式优化方法
解决约束优化问题——拉格朗日乘子法
我们每个人在生活或工作中都会遇到各种优化问题，比如“如何在一定成本下实现利润最大化”是每个企业和个人都必须考虑的问题。 最优化方法是一种数学方法。 它是研究如何在给定约束条件下寻求某些因素（量）以优化某个（或某个）指标的某些学科的总称。 随着学习的深入，博主越来越发现优化方法的重要性。 学习和工作中遇到的大部分问题都可以建模成优化模型来解决。 比如我们现在学习的机器学习算法，大部分机器学习算法的本质都是建立优化模型，通过优化的方法来优化目标函数（或者说损失函数），从而训练出最好的模型。 常见的优化方法有梯度下降法、牛顿法、拟牛顿法、共轭梯度法等。
1.梯度下降法（ ）
梯度下降法是最早、最简单、最常用的优化方法。 梯度下降法实现起来很简单。 当目标函数是凸函数时，梯度下降法的解是全局解。 一般来说，解不能保证是全局最优解，梯度下降法也不一定是最快的。 梯度下降法的优化思想是用当前位置的负梯度方向作为搜索方向。 由于该方向是当前位置下降最快的方向，因此也称为“最速下降法”。 最速下降法越接近目标值，步长越小，进度越慢。 梯度下降法的搜索迭代图如下所示：
梯度下降法的缺点：
（1）接近最小值时收敛速度变慢，如下图所示；
(2)直线搜索时可能会出现一些问题；
(3)可能存在“之字形”下降。
从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显较慢，并且使用梯度下降法求解问题需要多次迭代。
在机器学习中，在基本梯度下降法的基础上发展了两种梯度下降法，即随机梯度下降法和批量梯度下降法。
例如，对于线性回归（ ）模型，假设下面的 h(x) 是要拟合的函数，J(theta) 是损失函数，theta 是参数，需要迭代求解的值，theta 是解决了，那么最后就要拟合出组合函数h(theta)了。 其中m是训练集中的样本数，n是特征数。
1）批量梯度下降法（Batch，BGD）
(1)求J(theta)对于theta的偏导数，得到每个theta对应的梯度：
(2) 由于要最小化风险函数，因此根据各参数θ的梯度负方向更新各θ：
(3) 从上式可以看出，它得到了全局最优解，但在每一步迭代中，都必须使用训练集的所有数据。 如果m很大，那么可以想象这种方法的迭代。 速度会相当慢。 所以，这就引入了另一种方法——随机梯度下降。
对于批量梯度下降法，样本数为m，x为n维向量，一次迭代需要将所有m个样本带入计算，一次迭代的计算量为m*n2。
2）随机梯度下降（SGD）
(1) 上述风险函数可以写成如下形式。 损失函数对应训练集中每个样本的梯度，上面的batch梯度下降对应所有训练样本：
(2) 对于每个样本的损失函数，求theta的偏导数即可得到对应的梯度来更新theta：
(3)随机梯度下降对每个样本迭代更新一次。 如果样本量很大（例如数十万），则仅可以使用数万或数千个样本来迭代theta。 已经达到最优解。 与上面的批量梯度下降相比，一次迭代需要数十万个训练样本。 一次迭代不可能是最优的。 如果迭代10次，则需要遍历训练样本10次。 然而，与SGD相关的一个问题是，噪声比BGD更多，使得SGD在每次迭代中都不会朝着整体优化的方向发展。
随机梯度下降每次迭代只使用一个样本，一次迭代的计算量为n2。 当样本数m较大时，随机梯度下降法一次迭代的速度远高于批量梯度下降法。 两者之间的关系可以这样理解：随机梯度下降法以损失一小部分精度和增加一定迭代次数为代价，提高了整体优化效率。 增加的迭代次数远小于样本数量。
批量梯度下降和随机梯度下降总结：
批量梯度下降---最小化所有训练样本的损失函数，使最终的解是全局最优解，即解的参数是最小化风险函数，但对于大规模样本效率较低问题。
随机梯度下降---最小化每个样本的损失函数。 虽然不是每次迭代得到的损失函数都朝着全局最优方向，但总体方向是朝着全局最优解，并且最终结果往往接近全局最优解，因此适合大规模训练样本的情况。
2.牛顿法和拟牛顿法（'s&Quasi-）
1) 牛顿法
牛顿法是一种近似求解实复杂场方程的方法。 该方法利用函数f(x)的泰勒级数的前几项来求方程f(x)=0的根。牛顿法的最大特点是收敛速度快。
具体步骤：
首先，选择函数f(x)接近零点的x0，计算对应的f(x0)和切线斜率f'(x0)（其中f'表示函数f的导数）。 然后我们计算经过点(x0,f(x0))且斜率为f'(x0)的直线与x轴交点的x坐标，即求解为以下等式：
我们将新获得的点的 x 坐标命名为 x1。 通常 x1 比 x0 更接近方程 f (x) = 0 的解。 所以我们现在可以使用 x1 开始下一次迭代。 迭代公式可以简化如下：
已经证明，如果f'连续，且所求的零点x是孤立的，则零点x周围存在一个区域。 只要初始值 x0 位于该相邻区域内，牛顿法就一定收敛。 并且，如果f'(x)不为0，则牛顿法将具有平方收敛的性能。 粗略地说，这意味着牛顿法结果的有效数字将随着每次迭代而加倍。
由于牛顿法是根据当前位置的切线来确定下一个位置，因此牛顿法也被形象地称为“切线法”。 牛顿法的搜索路径（二维情况）如下图所示：
牛顿法搜索动态示例图：
关于牛顿法和梯度下降法的效率对比：
本质上，牛顿法是二阶收敛，而梯度下降是一阶收敛，因此牛顿法速度更快。 更简单的说，比如你想找到到一个盆地底部的最短路径，梯度下降法只选择距你当前位置坡度最大的方向，一步一步走。 ，不仅会考虑坡度是否足够大，还会考虑你迈出一步后坡度是否会变大。 因此，可以说牛顿法比梯度下降法看得更远，能更快地探底。 （牛顿法的视角更长远，所以少走弯路；相比之下，梯度下降法只考虑局部最优，没有全局思维。）
根据wiki上的解释，从几何角度来看，牛顿法使用二次曲面来拟合你当前位置的局部曲面，而梯度下降法则使用平面来拟合当前局部曲面。 通常情况下，二次曲面的拟合会比平面的拟合效果更好，因此牛顿法选择的下降路径会更符合真实的最优下降路径。
注：红色为牛顿法迭代路径，绿色为梯度下降法迭代路径。
牛顿法的优缺点总结：
优点：二阶收敛，收敛速度快；
缺点：牛顿法是一种迭代算法。 每一步都需要求解目标函数矩阵的逆矩阵，计算相对复杂。
2）拟牛顿法（Quasi-）
拟牛顿法是解决非线性优化问题最有效的方法之一。 它是由20世纪50年代美国国家实验室的物理学家WC提出的。 所设计的算法被认为是当时非线性优化领域最具创造性的发明之一。 很快R.和MJD证实，这种新算法比其他方法更快、更可靠，使得非线性优化学科一夜之间突飞猛进。
拟牛顿法的本质思想是改善牛顿法每次需要求解复矩阵的逆矩阵时，都使用正定矩阵来逼近该矩阵的逆矩阵的缺点，从而简化操作的复杂性。 拟牛顿法与最速下降法一样，只需要知道每次迭代时目标函数的梯度。 通过测量梯度的变化，构建足以产生超线性收敛的目标函数模型。 此类方法明显优于最速下降法，特别是对于困难问题。 另外，由于拟牛顿法不需要二阶导数的信息，因此有时比牛顿法更有效。 如今，优化软件包括大量用于解决无约束、约束和大规模优化问题的拟牛顿算法。
具体步骤：
拟牛顿法的基本思想如下。 首先，构建当前迭代xk中目标函数的二次模型：
这里Bk是一个对称正定矩阵，所以我们以这个二次模型的最优解作为搜索方向，得到一个新的迭代点：
其中，我们要求步长ak满足Wolfe条件。 该迭代与牛顿法类似，只不过使用近似Hesse矩阵Bk代替真实Hesse矩阵。 因此，拟牛顿法最关键的部分就是每次迭代中的矩阵Bk
更新。 现在假设得到新的迭代xk+1，得到新的二次模型：
我们尽可能使用上一步中的信息来选择 Bk。具体来说，我们要求
从而得到
这个公式称为正割方程。 常用的拟牛顿方法有DFP算法和BFGS算法。
3. 共轭梯度法 ( )
共轭梯度法是一种介于最速下降法和牛顿法之间的方法。 它只利用一阶导数信息，但克服了最速下降法收敛速度慢的缺点，并且避免了牛顿法需要存储和计算Hesse矩阵。 尽管存在反演的缺点，共轭梯度法不仅是求解大型线性方程组最有用的方法之一，而且也是求解大型非线性优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。 其优点是所需存储量小、步长收敛、稳定性高、不需要任何外部参数。
具体实现步骤请参考维基百科共轭梯度法。
下图是共轭梯度法和梯度下降法寻找最优解的路径对比示意图：
注：绿色代表梯度下降法，红色代表共轭梯度法。
代码：
function [x] = conjgrad(A,b,x)
r=b-A*x;
p=r;
rsold=r'*r;
for i=1:length(b)
Ap=A*p;
alpha=rsold/(p'*Ap);
x=x+alpha*p;
r=r-alpha*Ap;
rsnew=r'*r;
if sqrt(rsnew)<1e-10 break;
end
p=r+(rsnew/rsold)*p;
rsold=rsnew;
end
end
4.启发式优化方法
启发式方法是指人们在解决问题时采用的基于经验规则的发现方法。 其特点是在解决问题时，我们采用过去的经验，选择行之有效的方法，而不是系统地、有步骤地寻求答案。 启发式优化方法有很多种，包括经典的模拟退火法、遗传算法、蚁群算法、粒子群算法等。
还有一种特殊的优化算法称为多目标优化算法，它主要针对同时优化多个目标（两个或多个）。 这方面比较经典的算法有算法、MOEA/D算法和人工智能算法。 免疫算法等
5.解决约束优化问题——拉格朗日乘子法
请参考公众号文章及博文《拉格朗日乘子法》
