CL关于一些优化算法的学习理解

梯度下降法、牛顿法、高斯-牛顿、L-M方法

最近看到了ORB SLAM中的后端优化部分，外加EPnP算法中也涉及到了高斯牛顿的优化算法，今天就打算把这玩意在原有的基础上搞得更透彻一点，这也是我为什么没把PnPsolver代码解读放出的原因，看完这个，回头再看，再加上EPnP的论文，看起来会轻松很多，那就开始吧。

就个人而言，对于优化算法的理解，其实就是两部分，一部分是下降方向在哪儿；另一部分是步长是多少，从这两个方面去学习
优化算法可能会更好一点吧。

梯度下降法

梯度下降法从另一个角度上来讲也是一种贪心算法，因为它每次的下降方向找的就是局部最大梯度的反方向。
具体的公式：

对于梯度下降法，我们找到的下降方向：梯度的负方向，那步长怎么定呢？查了相关的资料和博客，就步长这一块的计算，有很多的尝试，具体还是要看你的模型是什么样子的。

引用一篇博客中的话 https://www.cnblogs.com/pinard/p/5970503.html
算法的步长选择。在前面的算法描述中，我提到取步长为1，但是实际上取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数在变小，说明取值有效，否则要增大步长。前面说了。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。

这边再提一下梯度下降法的不同形式（BGD，SGD，MBGD）

批量梯度下降法（Batch Gradient Descent）

这种梯度求解方式就最常用的方式。在梯度更新方面，用了所有参数信息。

随机梯度下降法（Stochastic Gradient Descent）

随机梯度下降法和批量梯度下降法的原理类似，区别在于求梯度时没有用所有样本的数据，而是仅仅选取一个样本来求梯度。
随机梯度下降法和批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。两者有着各自的优缺点。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

小批量梯度下降法（Mini-batch Gradient Descent）

小批量梯度下降法相当于结合了批量和随机两种梯度计算方法。在所有的样本中随机取x个样本，x一般是取10，不过最终x怎么定还是要根据样本的数据，可以调整这个x的值。

牛顿法

原始牛顿法

牛顿法的基本思想是：在现有极小点估计值的附近对f(x)做二阶泰勒展开，进而找到极小点的下一个估计值。设Xk为当前的极小点估计值，则

函数直接在Xk附近的二阶泰勒展开式。由于求的是最值，由极值必要条件可知，应该满足 即 求得 于是给定初始值，则可以构造如下的迭代格式 如果是从矩阵的角度上来看（多元函数），这边的一阶导数就是梯度矩阵，这边的二阶导数就是海森矩阵。 当目标函数是二次函数时，由于二次泰勒展开函数与原目标函数不是近似而是完全相同的二次式，海森矩阵退化成了一个常数矩阵，从任一初始点出发，只要一步迭代即可达到函数的极小值点，因此牛顿法是一种具有二次收敛性的算法。对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的邻域，则其收敛速度也是很快的，这是牛顿法的主要优点。但是原始牛顿法由于迭代公式中没有步长因子，而不是定长迭代，对于非二次型目标，牛顿法可能不收敛。 原始牛顿法不能保证函数值稳定地下降。

阻尼牛顿法

阻尼牛顿法的出现是为了消除原始牛顿法的一些弊端。阻尼牛顿法每次的迭代方向还是采用的牛顿方向，但是每次迭代需沿此方向作一维搜索，寻求最优的步长因子。

牛顿法主要存在以下两个缺点：

1. 对目标函数有较严格的要求，函数必须具有连续的一、二阶偏导数，海森矩阵必须正定
2. 计算相当复杂，除需计算梯度之外，还需要计算二阶偏导数矩阵和它的逆矩阵。计算量、存储量都很大，且都以维度N的平方的增加，当N很大时这个问题更加突出。

拟牛顿法

前面两种牛顿法虽然收敛速度快，但是计算过程中需要计算目标函数的二阶偏导数（海森矩阵），计算复杂度较大，而且有时目标函数的海森矩阵无法保持正定，从而使牛顿法失效，为了克服这两个问题，提出了逆牛顿法。
这个方法的基本思想是：不用二阶偏导数而构造出可以近似海森矩阵（或海森矩阵的逆）的正定堆成阵。
拟牛顿法只是一个概念，具体的方法有DFP、BFGS和L-BFGS。
DFP算法是最早的拟牛顿法，该算法的核心是：通过迭代的方法，对海森矩阵的逆进行近似，迭代的格式为

这边的Ｄ是海森矩阵的逆。一般，初始化的Ｄ为单位矩阵。

BFGS算法中核心公式的推导过程和DFP完全类似，只是互换了其中的sk和yk的位置。BFGS算法近似的是海森矩阵，所以这边还有求逆的过程，所以这边应用到了Sherman-Morrison公式，直接给出了海森矩阵逆矩阵的递推公式。

L-BFGS(Lmited-memory BFGS 或　Limited-storage BFGS)算法的基本思想就是不再存储完整的海森逆矩阵，而是存储计算过程中的向量序列ｙ和ｓ，需要矩阵的时候，再利用向量序列的计算来代替，而且，向量序列也不是所有的都存，而是固定存最新的ｍ个参数，这边的更新主要就是海森逆矩阵这一块，由于这边我们只存储ｍ个参数，所有在计算到ｍ＋１，ｍ＋２时，必然会丢弃一些向量信息，那么肯定是考虑那些最早生成的向量，所以这边的海森逆矩阵只能是近似计算了，精度的损失带来的是存储空间的大大减少。

不过从个人角度上来讲，这些近似公式的出现，似乎都充满了哲学道理，人生嘛，啥都活明白了还待在尘世干嘛，不需要那么精确的嘛。以上一些推导和总结来自

link.
具体的推导他的博客里都有，很好的学习素材。

高斯-牛顿

高斯－牛顿是在牛顿法基础上进行了修改得到的，其最大的优点不需要计算海森矩阵，当然这项优点的代价是其仅适用于最小二乘问题。
最小二乘方法的目标是令残差的平方和最小：

如果是采用牛顿法求解该函数的最小值，需要计算其梯度向量与海森矩阵 公式中的最后一个列矩阵就是所谓的雅克比矩阵。 再看海森矩阵 观察二阶导数项，因为残差约等于０，因此这边的二阶导数项将被舍去，所以海森矩阵可以近似写成， 从这边可以看出高斯－牛顿法相对于牛顿法的不同就是在于采用了近似的海森矩阵降低了计算难度，但是同时，舍去项仅适用于最小二乘问题中残差较小的情形。

将近似的海森矩阵带入牛顿法迭代公式，得到高斯－牛顿法的迭代式，

L-M方法

与牛顿法一样，当初始值距离最小值较远时，高斯－牛顿法不能保证收敛。另外，当进行近似海森矩阵出现近似奇异时，高斯－牛顿也不能正确收敛。L-M算法算是对上述缺点的改进。
L-M方法是对梯度下降法与高斯-牛顿法进行线性组合以充分利用两种算法的优势。通过在Hessian矩阵中加入阻尼系数λ来控制每一步迭代的步长以及方向：

当λ增大时，H+λI趋向于λI，因此△ｘ趋向于梯度下降法给出的迭代方向；

当λ减小时，H+λI趋向于H，△ｘ趋向于高斯-牛顿法给出的方向。

这个信赖域半径怎么定呢？（这边给出的值是个人的经验值）

1. 近似模型和实际函数之间的差异

2. 上式的分子是世界函数下降的值，分母是近似模型下降的值。如果计算出的差异值接近于１，则近似是好的；如果差异值太小，说明实际减小的值远小于近似减小的值，则认为近似比较差，需要缩小近似范围。反之，如果差异值比较大，则说明实际下降的比预计的更大，可以放大近似范围。
3. 如果差异值＞３／４，将信赖域的半径扩大到原来的２倍；如果差异值＜１／４，将信赖域的半径缩小为原来的１／２。
   

图片来源于《视觉SLAM十四讲从理论到实践》

时间：2019年09月05日
作者：hhuchen
机构：河海大学机电工程学院