高博的SLAM十四讲写的很好,但有些地方可能大家会有点疑问,或者说是不够详尽。 这里介绍细节的非线性最小二乘的方法。

1. 最小二乘问题

最简单的最小二乘问题:
$$ \underset{x}{min}\frac{1}{2}||f(x)||_{2}^{2} \tag{1}$$ 自变量 $x\epsilon\mathbb{R}^{n}$ ,f是任意非线性函数,设它为m维:$f(x)\epsilon\mathbb{R}^{m}$。
如果f的形式很简单,问题可能可以用解析形式求解,即令目标函数的导数为零,进而求得x的最优值。但实际应用中并不方便使用这种方法,更多的是使用迭代逼近的方法取找到导数为0的点。

1.1 梯度下降法

将目标函数 $||f(x)||^{2}$在x处进行taylor展开: $$||f(x+\Delta{x})||^{2} \thickapprox ||f(x)||^{2} + J(x)\Delta{x} + \frac{1}{2}\Delta{x}^{T}H\Delta{x} \tag{2}$$
J是目标函数$||f(x)||^{2}$关于x的导数,即jacobian矩阵,H为Hssian矩阵。
如果仅保留一阶项,整理有: $$||f(x)||^{2} - ||f(x+\Delta{x})||^{2} = -J(x)\Delta{x} \tag{3}$$
在$\Delta{x}$是下降的方向的前提下,即$J(x)\Delta{x}<0$,就可以把右边看作是目标函数从x到$x+\Delta{x}$下降的量。

进一步,$\Delta{x}$取多少才能使下降量尽可能大? 首先引入一个步长参数$\lambda$来控制学习率,而限定$\Delta{x}$为单位长度,则显然,当取$\lambda>0$,$\Delta{x}$与-J(x)同向时,右式最大。

即结论是函数沿负梯度方向下降最快,即: $\Delta{x^{*}} = -J^{T}(x)$ ,而具体下降的多少,则有步长$\lambda$来确定。

步长的确定: 通常full gradient的方法会使用 Line Search的方式来确定步长, SGD则使用自适应的learning rate, 如AdaDelt,Adam 等等

Armijo + Line Search的基本思想: 每次试一个步长,如果使用该步长,函数值会不会比当前点下降一定的程度,如果没有,就按比例减小步长,再试,直到满足条件(Arimigo-Goldstein condition)


1.2 牛顿法

2018-11-2日更新,阔别依旧呀~ 诸君~长出来了呀~

上面我们介绍说确定方向即可,只使用了一阶梯度的信息,如果我说,我想直接求出 $\Delta x$ 呢?
Easy~ 同样的,我们把(2)式子调整一下,保留二阶信息: $$ ||f(x)||^{2} - ||f(x+\Delta{x})||^{2} = -J(x)\Delta{x} - \frac{1}{2}\Delta{x}^{T}H\Delta{x} \tag{4}$$
我们希望取得的 $\Delta x$ 使得左边的下降量最大, 即求等号左边$ y(\Delta x) $ 的极大值, 对$\Delta x$求偏导,有下式: $$ H\Delta{x} = -J^T \tag{5} $$

牛顿法存在的问题就是需要计算H矩阵,这在问题规模比较大的时候非常困难,所以一般用拟牛顿法替代。


1.3 高斯-牛顿法

高斯-牛顿法则是不再直接对 $f(x)^2$ 展开,而是针对 $f(x)$ 进行展开: $$ f(x +\Delta{x}) \thickapprox f(x) + J(x)\Delta{x} \tag{6}$$ 不去寻找x使得目标函数最小,转而去寻找 $\Delta{x}$ 使得下降量最大; 先展开: $$ \frac{1}{2}||f(x) + J(x)\Delta{x}||^2 = \frac{1}{2}(||f(x)||_2^2 +2f(x)^T J(x)\Delta{x} + \Delta{x}^T J(x)^T J(x)\Delta{x}) \tag{7}$$
对上式求$\Delta{x}$偏导,使其等于0,最后得到下式: $$ J(x)^T J(x)\Delta{x} = -J(x)^T f(x) \tag{8}$$
最终也就变成了线性的标准求解形式 $ Ax = b $,就可以使用标准的求解方式计算(SVD分解、Choleskey分解等方法).


1.4 列文伯格-马夸尔特法

上述方法,存在的最大问题,就是当约束不充足,$J^T J$不满秩