深入理解非线性二乘法求解图优化

求解图优化的实际过程如下：

(1)选择图中的节点和边缘类型，确定其参数形式； (2)向图中添加实际节点和边缘； (3)选择初始值，开始迭代； (4)在每一步迭代中，计算与当前估计值相对应的雅可比矩阵和海塞矩阵； (5)稀疏线性方程 H Δ x k = g H\Delta x_k=g HΔxk=g，梯度方向； （6）继续用GN或LM迭代。如果迭代结束，返回优化值。

图优化问题可以表示为n条边加和的形式 min ⁡ x ∣ ∣ f ( x ) ∣ ∣ 2 = 1 2 ∑ k = 1 n e k ( x k ) T Ω e k ( x k ) \min\limits_{x} ||f(x)||^2 =\frac{1}{2}\sum_{k=1}^{n}e_k(x_k)^T\Omega e_k(x_k) xmin​∣∣f(x)∣∣2=21​k=1∑n​ek​(xk​)TΩek​(xk​) 1.e函数在原理上表示一个误差，是一个矢量，作为优化变量 x k x_k xk​和 z k z_k zk​符合程度的一个度量。它越大表示 x k x_k xk​越不符合 z k z_k zk​。但是，由于目标函数必须是标量，所以必须用它的平方形式来表达目标函数。最简单的形式是直接做成平方： e k ( x k ) T e k ( x k ) e_k(x_k)^Te_k(x_k) ek​(xk​)Tek​(xk​)。进一步，为了表示我们对误差各分量重视程度的不一样，还使用一个信息矩阵 Ω \Omega Ω来表示各分量的不一致性。

2.信息矩阵 Ω \Omega Ω是协方差矩阵的逆，是一个对称矩阵。它的每个元素作 Ω i , j \Omega_{i,j} Ωi,j​为 e i e j e_ie_j ei​ej​的系数，可以看成我们对 e i e j e_ie_j ei​ej​这个误差项相关性的一个预计。最简单的是把 Ω \Omega Ω设成对角矩阵，对角阵元素的大小表明我们对此项误差的重视程度。

3.这里的 x k x_k xk​可以指一个顶点、两个顶点或多个顶点，取决于边的实际类型。所以，更严谨的方式是把它写成 e k ( z k , x k 1 , x k 2 … ) e_k(z_k,x_{k1},x_{k2}…) ek​(zk​,xk1​,xk2​…)，但是那样写法实在是太繁琐，我们就简单地写成现在的样子。由于 z k z_k zk​是已知的，为了数学上的简洁，我们把它写成的形式 e k ( x k ) e_k(x_k) ek​(xk​)。

对于一个最小二乘问题表示为 min ⁡ x 1 2 ∣ ∣ f ( x ) ∣ ∣ 2 \min \limits_{x}\frac{1}{2}||f(x)||^2 xmin​21​∣∣f(x)∣∣2 f是任意非线性函数,x表示需要优化的变量，函数的意义为找到x使得函数 1 2 ∣ ∣ f ( x ) ∣ ∣ 2 \frac{1}{2}||f(x)||^2 21​∣∣f(x)∣∣2能取最小值。

使用迭代的方法求解最小二乘问题，总体思路是从一个初始值出发，不断更新当前的优化变量，使目标函数下降，直到满足结束条件求解结束。

具体步骤如下

1.给定某个初始值 x 0 x_0 x0​

2.对于第k次迭代，寻找一个增量 Δ x k \Delta x_k Δxk​,使得$|f(x_k+\Delta x_k)||^2 $达到最小值。

3.若 Δ x k \Delta x_k Δxk​足够小，则停止

4.否则，令 x k + 1 = x k + Δ x k x_{k+1}=x_k+\Delta x_k xk+1​=xk​+Δxk​,返回第2步

那么对于每次迭代，如何找这个增量 Δ x k \Delta x_k Δxk​？

高斯牛顿法能得到这个增量。

高斯牛顿求解最小二乘问题步骤如下：

1.给定某个初始值 x 0 x_0 x0​

2.对于第k次迭代，通过解方程 H Δ x k = g H\Delta x_k=g HΔxk​=g，求得增量 Δ x k \Delta x_k Δxk​,使得 1 2 ∣ ∣ f ( x k + Δ x k ) ∣ ∣ 2 \frac{1}{2} ||f(x_k+\Delta x_k)||^2 21​∣∣f(xk​+Δxk​)∣∣2达到最小值。其中 H = J ( x k ) J ( x k ) g = − J ( x k ) f ( x k ) H=J(x_k)J(x_k)\\ g=-J(x_k)f(x_k) H=J(xk​)J(xk​)g=−J(xk​)f(xk​) 3.若 Δ x k \Delta x_k Δxk​