作者：Frank
时间：2016-08-03

本节延续上节部分讲述非线性优化问题中的Levenberg-Marquardt算法。Gauss-Newton和Levenberg-Marquardt都是在直接法中求解相机姿态时最常用到的两种迭代算法。而Levenberg-Marquardt是结合了Gauss-Newton和梯度下降法的优点总结而来的迭代算法，因此这里会先介绍梯度下降法。

1. 梯度下降法

梯度下降法是一个一阶最优化算法，通常我们也将其称为最速下降法。

1.1. 梯度的概念

一个函数$D(\theta)$对它的一个变量$\theta$的梯度定义为：
$${\partial D(\theta) \over \partial \theta}=\lim_{\delta \theta \rightarrow 0}{D(\theta+\partial \theta)-D(\theta) \over \delta \theta}\tag{1}$$
某一点上的梯度指向标量场增长最快的方向，梯度的长度就是最大的变化率。

1.2. 梯度下降

我们知道对于一个函数沿着梯度的那个方向是下降最快的。例如为了选取一个$\theta$使得$D(\theta)$最小，我们可以先随机选择$\theta$一个初始值，然后不断的修改$\theta$以减小$D(\theta)$，知道$\theta$的值不再改变，对于梯度下降法，可以表示为：
$$\theta_j=\theta_j-\alpha {\partial D(\theta) \over \partial \theta_j}\tag{2}$$
即不断地向梯度的那个方向（减小最快的方向）更新$\theta$，最终使得$D(\theta)$最小。其中$\alpha$称为学习速率，取值太小会导致迭代过慢，取值太大可能错过最值点。

1.3. 梯度方向下降和函数最值

梯度下降法，基于这样的观察：如果实值函数F(x)在点a处可微且有定义，那么函数F(x)在a点沿着梯度相反的方向–$\Delta F(a)$下降最快。
因此，如果：$b=a-\alpha \Delta F(a) $，那么$F(b)\leq F(a)$。
考虑如下序列：$x_0,x_1,x_2……$，使得
$$x_{n+1}=x_n-\alpha \Delta F(x_n) \tag{3}$$
因此可以得到：$F(x_0) \geq F(x_1)…….$，如果顺利的话序列最终可以收敛到期望的极值。

注意：梯度下降得到的结果可能是局部最优值。如果F(x)是凸函数，则可以保证梯度下降得到的是全局最优值。

申明：本节引用来源：梯度下降法

2. Levenberg-Marquardt算法

梯度下降法和Gauss-Newton都是最优化方法。其区别之处在于：

1. 梯度下降法在寻找目标函数极小值时，是沿着反梯度方向进行寻找的。梯度的定义就是指向标量场增长最快的方向，在寻找极小值时，先随便定初始点（x0，y0）然后进行迭代不断寻找直到梯度的模达到预设的要求。但是梯度下降法的缺点之处在于：在远离极小值的地方下降很快，而在靠近极小值的地方下降很慢。
2. 而高斯牛顿法是一种非线性最小二乘最优化方法。其利用了目标函数的泰勒展开式把非线性函数的最小二乘化问题化为每次迭代的线性函数的最小二乘化问题。高斯牛顿法的缺点在于：若初始点距离极小值点过远，迭代步长过大会导致迭代下一代的函数值不一定小于上一代的函数值。

LM算法在高斯牛顿法中加入了因子μ，当μ大时相当于梯度下降法，μ小时相当于高斯牛顿法。（这儿我也不明白为什么，希望有大牛解答）。在使用Levenberg-Marquart时，先设置一个比较小的μ值，当发现目标函数反而增大时，将μ增大使用梯度下降法快速寻找，然后再将μ减小使用牛顿法进行寻找。
为了避免发散，有两种解决方法：

1. 调整下降步伐： $\beta^{s+1}=\beta^s+\alpha \Delta 0<\alpha<1$；
2. 调整下降方向：$(J^TJ+\lambda D)\Delta=J^Tr$；

LM方法的好处是可以调节：
如果下降太快，使用较小的λ，使之更接近高斯牛顿法；
如果下降太慢，使用较大的λ，使之更接近梯度下降法；

申明：本节引用来源：【math】梯度下降法(梯度下降法，牛顿法，高斯牛顿法，Levenberg-Marquardt算法)

转载请注明出处