Levenberg-Marquardt算法浅谈

在讲Levenberg-Marquardt算法之前我想先谈下牛顿法和高斯牛顿法。

牛顿法

如果有一点数值计算知识的同学对牛顿迭代法并不陌生，先贴个经典例图来镇楼。

这里写图片描述

一般来说我们利用牛顿法使用来求f(x)=0的解。求解方法如下： 先对f(x)一阶泰勒展开得 f(x+Δ)=f(x)+f′(x)Δ=0f(x+Δ)=f(x)+f′(x)Δ=0 f(x+\Delta)=f(x)+f'(x)\Delta=0 所以我们有Δ=x−x0=−f(x0)f′(x0),即x=x0−f(x0)f′(x0)Δ=x−x0=−f(x0)f′(x0),即x=x0−f(x0)f′(x0) \Delta=x-x_0=-\frac{f(x_0)}{f'(x_0)},即x=x_0-\frac{f(x_0)}{f'(x_0)} 因此也就得到了我们的牛顿迭代公式： xn=xn−1−f(xn−1)f′(xn−1)xn=xn−1−f(xn−1)f′(xn−1) x_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})} 求解最优化问题min f(x)min f(x) min　f(x) 牛顿法首先则是将问题转化为求 f′(x)=0f′(x)=0 f'(x) = 0 这个方程的根。 一阶展开：f′(x)≈f′(x0)+(x－x0)f′′(x0)f′(x)≈f′(x0)+(x－x0)f″(x0) f '(x) ≈ f '(x_0)+(x－x_0)f ''(x0) 令 f′(x0)+(x－x0)f′′(x0)=0f′(x0)+(x－x0)f″(x0)=0 f'(x_0)+(x－x_0)f ''(x_0) = 0 求解得到x，相比于x0，f′(x)<f′(x0)求解得到x，相比于x0，f′(x)<f′(x0) 求解得到x，相比于x_0，f '(x)<f'(x0)

高斯牛顿法

在讲牛顿法的时候，我们举的例子x是一维的，若如果我们遇到多维的x该如何办呢？这时我们就可以利用雅克比，海赛矩阵之类的来表示高维求导函数了。 比如f(X)=0,其中X=[x0,x1,...,xn]f(X)=0,其中X=[x0,x1,...,xn] f(X)=0,其中X=[x_0,x_1,...,x_n] 所以我们有雅克比矩阵： Jf=⎡⎣⎢⎢⎢⎢∂f∂x0⋮∂f∂x0⋯⋱⋯∂f∂xn⋮∂f∂xn⎤⎦⎥⎥⎥⎥Jf=[∂f∂x0⋯∂f∂xn⋮⋱⋮∂f∂x0⋯∂f∂xn] J_f=\begin{bmatrix} \frac{\partial f}{\partial x_0}&\cdots&\frac{\partial f}{\partial x_n}\\ \vdots&\ddots&\vdots\\ \frac{\partial f}{\partial x_0}&\cdots&\frac{\partial f}{\partial x_n} \end{bmatrix} 有海赛矩阵： Hf=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢∂2f∂x20∂2f∂x1∂x0⋮∂2f∂xn∂x0∂2f∂x0∂x1∂2f∂x21⋮∂2f∂xn∂x1......⋱...∂2f∂x0∂xn∂2f∂x1∂xn⋮∂2f∂x2n⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥Hf=[∂2f∂x02∂2f∂x0∂x1...∂2f∂x0∂xn∂2f∂x1∂x0∂2f∂x12...∂2f∂x1∂xn⋮⋮⋱⋮∂2f∂xn∂x0∂2f∂xn∂x1...∂2f∂xn2] H_f=\begin{bmatrix}\frac{\partial^2f}{\partial x_0^2}&\frac{\partial^2f}{\partial x_0 \partial x_1}&...&\frac{\partial^2f}{\partial x_0 \partial x_n}\\ \frac{\partial^2f}{\partial x_1 \partial x_0}&\frac{\partial^2f}{\partial x_1^2}&...&\frac{\partial^2f}{\partial x_1 \partial x_n}\\\vdots&\vdots&\ddots&\vdots\\ \frac{\partial^2f}{\partial x_n \partial x_0}&\frac{\partial^2f}{\partial x_n \partial x_1}&...&\frac{\partial^2f}{\partial x_n^2} \end{bmatrix}

所以高维牛顿法解最优化问题又可写成：

Xn+1=Xn−Hf(xn)−1∇f(xn)Xn+1=Xn−Hf(xn)−1∇f(xn)

X_{n+1}=X_n-H_f(x_n)^{-1}\nabla f(x_n) 梯度 代替了低维情况中的一阶导 Hessian矩阵代替了二阶导 求逆代替了除法 例：不妨设目标函数为：

s(x)=∑i=0nf2(xi)s(x)=∑i=0nf2(xi)

s(x)=\sum_{i=0}^nf^2(x_i) 所以梯度向量在方向上的分量：

gj=2∑i=0nfi∂fi∂xj (1)gj=2∑i=0nfi∂fi∂xj (1)

g_j=2\sum_{i=0}^nf_i\frac{\partial f_i}{\partial x_j}　　　　(1) Hessian 矩阵的元素则直接在梯度向量的基础上求导：

Hjk=2∑i=0n(∂fi∂xj∂fi∂xk+fi∂2fi∂xj∂xk)Hjk=2∑i=0n(∂fi∂xj∂fi∂xk+fi∂2fi∂xj∂xk)

H_{jk}=2\sum_{i=0}^n (\frac{\partial f_i}{\partial x_j}\frac{\partial f_i}{\partial x_k}+ f_i\frac{\partial^2 f_i}{\partial x_j\partial x_k}) 高斯牛顿法的一个小技巧是，将二次偏导省略，于是：

Hjk≈∑i=0nJijJik (2)Hjk≈∑i=0nJijJik (2)

H_jk\approx\sum_{i=0}^nJ_{ij}J_{ik}　　　　　　(2) 其中JijJijJ_{ij}为雅克比矩阵中的第i行j列元素 将(1)(2)改写成 矩阵相乘形式：

g=2JTffg=2JfTf

g=2J_f^Tf

H≈2JTfJfH≈2JfTJf

H\approx2J_f^TJ_f 代入牛顿法高维迭代方程的基本形式，得到高斯牛顿法迭代方程：

xs+1=xs+Δ,其中Δ=−(JTfJf)−1JTffxs+1=xs+Δ,其中Δ=−(JfTJf)−1JfTf

x^{s+1}=x^s+\Delta,其中\Delta=-(J_f^TJ_f)^{-1}J_f^Tf

Levenberg-Marquardt算法

引用维基百科的一句话就是：

莱文贝格－马夸特方法（Levenberg–Marquardt algorithm）能提供数非线性最小化（局部最小）的数值解。此算法能借由执行时修改参数达到结合高斯-牛顿算法以及梯度下降法的优点，并对两者之不足作改善（比如高斯-牛顿算法之反矩阵不存在或是初始值离局部极小值太远）

在我看来，就是在高斯牛顿基础上修改了一点。 在高斯牛顿迭代法中，我们已经知道

Δ=−(JTfJf)−1JTffΔ=−(JfTJf)−1JfTf

\Delta=-(J_f^TJ_f)^{-1}J_f^Tf 在莱文贝格－马夸特方法算法中则是

Δ=−(JTfJf+λI)−1JTffΔ=−(JfTJf+λI)−1JfTf

\Delta=-(J_f^TJ_f+\lambda I)^{-1}J_f^Tf 在我看来好像就这点区别。至少我看的维基百科是这样的。 然后Levenberg-Marquardt方法的好处就是在于可以调节: 如果下降太快，使用较小的λ，使之更接近高斯牛顿法 如果下降太慢，使用较大的λ，使之更接近梯度下降法