在讲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)
所以高维牛顿法解最优化问题又可写成:
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 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方法的好处就是在于可以调节: 如果下降太快,使用较小的λ,使之更接近高斯牛顿法 如果下降太慢,使用较大的λ,使之更接近梯度下降法