---

[toc]

前置知识

最小二乘问题

定义：$min\ f(x)=\large\frac{1}{2}\normalsize\sum_{i=1}^mr_i^2(x)=\large\frac{1}{2}\normalsize r(x)^Tr(x)=\large{\frac{1}{2}}\normalsize{||r(x)||_2^2}$

其中，$r(x)$称为剩余函数，如果$r(x)$有一个不是线性函数，那么就是非线性最小二乘问题

f(x)的导数

设$J(x)$是$r(x)$的Jacobi矩阵,$J(x)=[\nabla{r_1(x),…,\nabla{r_m(x)}}]^T=\nabla{r(x)}$

梯度

$$\begin{aligned} &\because \frac{\partial (r(x)^Tr(x))}{\partial{r(x)}}=2r(x)\\ &\therefore \frac{\partial r(x)^Tr(x)}{\partial{x}}=\frac{\partial{r(x)^Tr(x)}}{\partial{r(x)}}\frac{\partial{r(x)}}{\partial{x}}\\ &\therefore \frac{\partial{r(x)^Tr(x)}}{\partial x}=2r(x)\nabla{r(x)}\\ &\therefore \nabla{f(x)}=\nabla{(\frac{1}{2}r(x)^Tr(x))}=r(x)\nabla{r(x)}\\ &\therefore \nabla{f(x)}=r(x)J(x) \end{aligned}$$

Hesse矩阵

$$\begin{aligned} \nabla^2f(x)&=\nabla(r(x)\nabla{r(x)})\\ &=\nabla{r(x)}^T\nabla{r(x)}+r(x)\nabla^2r(x)\\ &=J(x)^TJ(x)+S(x) \end{aligned}$$

其中$S(x)=r(x)\nabla^2r(x)$

Gauss-Newton方法

对$f(x)$,进行一阶Taylor展开，得到$f(x+\Delta{x})\approx f(x)+f’(x)\Delta{x}=f(x)+J(x)\Delta{x}$

代入$\Delta x=arg\ min\ \frac{1}{2}||f(x+\Delta x)||^2_2$,得到

$$\begin{aligned} F(\Delta x)&=\frac{1}{2}||f(x+\Delta{x})||^2_2\\ &=\frac{1}{2}(f(x)^Tf(x)+(J(x)\Delta{x})^T(J(x)\Delta{x})+2f(x)^TJ(x)\Delta{x})\\ \end{aligned}$$

对$\Delta x$求导，得到

$$\begin{aligned} \frac{\partial{F(\Delta{x})}}{\partial{\Delta{x}}}=f(x)^TJ(x)+2J(x)^TJ(x)\Delta{x} \end{aligned}$$

其中，如果令$g(x)=J(x)\Delta{x}$,则$(J(x)\Delta{x})^T(J(x)\Delta{x})=g(x)^Tg(x)$,则

$$\begin{aligned} \frac{\partial (J(x)\Delta{x})^T(J(x)\Delta{x})}{\partial{\Delta x}}&=\frac{\partial{g(x)^Tg(x)}}{\partial{g(x)}}\frac{\partial{g(x)}}{\partial{x}}\\ &=2g(x)J(x)\\ &=2J(x)^TJ(x)\Delta{x} \end{aligned}$$

所以令$f(x)^TJ(x)+2J(x)^TJ(x)\Delta{x}=0$

得到$J(x)^TJ(x)\Delta{x}=-f(x)^TJ(x)$

因为$f(x_{k+1})-f(x_k)=G_{k+1}(x_{k+1}-x_k)$,即牛顿方程$G_{k}d_k=g_k$

又$G(x)=J(x)^TJ(x)+S(x)$,所以$(J_k^TJ_k+S_k)d_k=-J_k^Tf_k$

忽略$S_k$后，即是$J(x)^TJ(x)\Delta{x}=-f(x)^TJ(x)$

所以Guass-Newton方程就是Newton方程中忽略$S_k$得到的

LM方法

对$f(x)$,进行一阶Taylor展开，得到$f(x+\Delta{x})\approx f(x)+f’(x)\Delta{x}=f(x)+J(x)\Delta{x}$

所以$\Delta{x^*}=arg\ min_{\Delta{x}}(\frac{1}{2}||f(x)+J(x)\Delta{x}||^2_2)$

加入阻尼项,$\Delta{x^*}=arg\ min_{\Delta{x}}(\frac{1}{2}||f(x)+J(x)\Delta{x}||^2_2+\frac{1}{2}\mu{\Delta{x}^T\Delta{x}})=M(\Delta{x})$

求导，得到

$$\begin{aligned} \frac{\mathrm{d}M(\Delta{x})}{\mathrm{d}\Delta{x}}&=\frac{1}{2}\frac{\mathrm{d}}{\mathrm{d}\Delta{x}}(f(x)^Tf(x)+(J(x)\Delta{x})^T(J(x)\Delta{x})+2f(x)^TJ(x)\Delta{x}+\mu{\Delta{x}^T\Delta{x}})\\ &=f(x)^TJ(x)+J(x)^TJ(x)\Delta{x}+\mu\Delta{x}\\ &=f(x)^TJ(x)+(J(x)^TJ(x)+\mu{I})\Delta{x} \end{aligned}$$

令其等于0，也就是$(J(x)^TJ(x)+\mu{I})\Delta{x}=-f(x)^TJ(x)$

所以$\Delta{x^*}=-(J(x)^TJ(x)+\mu{I})^{-1}f(x)^TJ(x)$