GN和LM的基本原理及算法流程，优劣分析

GN和LM的基本原理及算法流程，优劣分析

• 1.问题引出-最小二乘法
• 2.牛顿法
• 3.GN法（高斯牛顿法）
• 4.LM法（列文伯格-马夸特）

1.问题引出-最小二乘法

来看一个生活中的例子。比如说，有五把尺子：

我们有一组测量数据y1,y2…,yn.首先，把测试得到的值画在笛卡尔坐标系中，分别记作 $y_i$yi​：

其次，把要猜测的线段长度的真实值用平行于横轴的直线来表示（因为是猜测的，所以用虚线来画），记作$y$y, 每个点都向$y$y做垂线，垂线的长度就是$\vert y-y_i \vert$∣y−yi​∣，也可以理解为测量值和真实值之间的误差：

因为误差是长度，还要取绝对值，计算起来麻烦，就干脆用平方来代表误差：$\vert y-y_i \vert \rightarrow (y-y_i)^2$∣y−yi​∣→(y−yi​)2
误差的平方和就是（$S_{\epsilon ^2}$Sϵ2​代表误差）：$S_{\epsilon ^2}=\sum (y-y_i)^2$Sϵ2​=∑(y−yi​)2
因为$y$y 是猜测的，所以可以不断变换：

自然误差的平方和$S_{\epsilon ^2}$Sϵ2​也是不断变化的。
法国数学家，阿德里安-马里·勒让德提出让总的误差的平方最小的[公式] 就是真值，这是基于，如果误差是随机的，应该围绕真值上下波动
勒让德的想法变成代数式就是：$S_{\epsilon ^2}=\sum (y-y_i)^2最小 \Rightarrow 真值y$Sϵ2​=∑(y−yi​)2最小⇒真值y
这个猜想也蛮符合直觉的，来算一下。

这是一个二次函数，对其求导，导数为0的时候取得最小值：

$\frac {d}{dy}S_{\epsilon ^2}=\frac {d}{dy}\sum (y-y_i)^2\\= 2((y-y_1)+(y-y_2)+(y-y_3)+(y-y_4)+(y-y_5))=0$dyd​Sϵ2​=dyd​∑(y−yi​)2=2((y−y1​)+(y−y2​)+(y−y3​)+(y−y4​)+(y−y5​))=0
进而：
$5y=y_1+y_2+y_3+y_4+y_5 \Rightarrow y= \frac {y_1+y_2+y_3+y_4+y_5}{5}$5y=y1​+y2​+y3​+y4​+y5​⇒y=5y1​+y2​+y3​+y4​+y5​​
正好是算术平均数。
原来算术平均数可以让误差最小啊，这下看来选用它显得讲道理了。
以下这种方法：
$S_{\epsilon ^2}=\sum (y-y_i)^2最小 \Rightarrow 真值y$Sϵ2​=∑(y−yi​)2最小⇒真值y
就是最小二乘法。

2.牛顿法

首先回顾一下泰勒展开公式：$f(x)=\frac {f(x_0)}{0!}+\frac{f^{'}(x_0)}{1!}(x-x_0)+\frac {f^{''}(x_0)}{2!}(x-x_0)^2+......+\frac {f^{(n)}(x_0)}{n!}(x-x_0)^n$f(x)=0!f(x0​)​+1!f′(x0​)​(x−x0​)+2!f′′(x0​)​(x−x0​)2+......+n!f(n)(x0​)​(x−x0​)n
待优化的目标函数： $\Vert f(x+\Delta x)\Vert_2^2$∥f(x+Δx)∥22​
我们将目标函数在x处进行二阶泰勒展开。对照上述通式，目标函数泰勒展开如下：$\Vert f(x+\Delta x)\Vert_2^2 \approx \Vert f(x)\Vert_2^2+J(x)\Delta x+\frac 12\Delta x^TH(x)\Delta x$∥f(x+Δx)∥22​≈∥f(x)∥22​+J(x)Δx+21​ΔxTH(x)Δx
其中 J(x) 是 ||f(x)||2 关于x的Jacobian矩阵（一阶导数），H(x)则是Hessian矩阵（二阶导数）。
我们可以选择保留泰勒展开的一阶或二阶项，对应的求解方法则为一阶梯度或二阶梯度法。如果保留一阶梯度，那么增量的方向为：
$\Delta x^*=-J^T(x)$Δx∗=−JT(x)
它的直观意义非常简单，只要我们沿着反向梯度方向前进即可。当然，我们还需要该方向上取一个步长 λ，求得最快的下降方式。这种方法被称为最速下降法。
另一方面，如果保留二阶梯度信息，那么增量方程为：
$\Delta x^*=argmin\Vert f(x)\Vert_2^2+J(x)\Delta x+\frac 12\Delta x^TH(x)\Delta x$Δx∗=argmin∥f(x)∥22​+J(x)Δx+21​ΔxTH(x)Δx
求右侧等式关于 ∆x 的导数并令它为零，就得到了增量的解：
$H\Delta x=-J^T$HΔx=−JT
该方法称又为牛顿法。我们看到，一阶和二阶梯度法都十分直观，只要把函数在迭代点附近进行泰勒展开，并针对更新量作最小化即可。由于泰勒展开之后函数变成了多项式，所以求解增量时只需解线性方程即可，避免了直接求导函数为零这样的非线性方程的困难。
牛顿法相比于梯度下降法的优点是什么呢? 为什么会有这样的优点？ 我们来直观的理解一下。
如下图所示。红点和蓝点的梯度（一阶导数）是一样的，但是红点出的二阶导数比蓝点大，也就是说在红点处梯度变化比蓝点处更快，那么最小值可能就在附近，因此步长就应该变小；而蓝点处梯度变化比较缓慢，也就是说这里相对平坦，多走一点也没事，那么可以大踏步往前，因此步长可以变大一些。所以我们看到牛顿法迭代优化时既利用了梯度，又利用了梯度变化的速度（二阶导数）的信息。

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法收敛更快。比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。也就是说梯度下降法更贪心，只考虑了眼前，反而容易走出锯齿形状走了弯路；而牛顿法目光更加长远，所以少走弯路。

而牛顿法则需要计算目标函数的 H 矩阵，这在问题规模较大时非常困难，我们通常倾向于避免 H 的计算。所以，接下来我们详细地介绍两类更加实用的方法：高斯牛顿法和列文伯格——马夸尔特方法。

更新中

3.GN法（高斯牛顿法）

4.LM法（列文伯格-马夸特）