从零开始推导LM算法原理

1. 概述

LM（Levenberg-Marquardt） 算法是一种用于求解非线性最小二乘问题的优化算法，可以被认为是梯度下降法和高斯-牛顿法的智能融合，通过一个自适应机制在两者之间平滑切换。

核心目的： 稳健、高效地最小化误差平方和函数，旨在解决高斯-牛顿法在遇到病态或非正定海森近似矩阵时的不稳定性问题，同时提供比梯度下降法更快的收敛速度。

用数学形式表达，其目标与高斯牛顿法完全相同：最小化

其中 β 是参数向量，ri 是残差。

2. 直观理解

要理解LM，必须先理解其前身算法的缺陷：

梯度下降法 (最速下降法)：

• 优点：非常稳健，只要步长足够小，它总能保证函数值下降。
• 缺点：收敛速度慢，特别是在接近最小值时，它会 zig-zag 前进。

高斯-牛顿法 ：

• 优点：收敛速度快（接近二次收敛），利用Hessian矩阵的近似（JTJJTJ）捕捉曲率信息，从而能做出更优的步长和方向预测。
• 缺点：不稳健，当近似Hessian矩阵是奇异的或病态的，或者当当前猜测点远离解时（导致线性近似很差），高斯-牛顿更新步可能根本不是一个下降方向，导致算法发散。

LM算法的核心思想： 当相信局部二次近似是准确的时，就更像高斯-牛顿法（追求速度）；当不相信时，就退化成更稳健的梯度下降法（保证收敛）。

LM通过引入一个阻尼因子u来实现这一思想。

3. 详细推导

第一步：修改正规方程 高斯-牛顿法的正规方程为：

第二步：分析阻尼项的作用

• 当 μ 很大时，项 μI 主导了方程左边的系数矩阵，此时方程正好是梯度下降法的步长方向（负梯度方向），只是步长为 1/μ，梯度下降方向是函数值下降的保证，但可能很慢： ：

• 当 μ 很小时，项 μI的影响可以忽略不计，方程退化为标准的高斯-牛顿方程，算法表现出高斯-牛顿法的快速收敛特性：

• 数值稳定性评估：矩阵 JTJ可能不是满秩的，导致其不可逆，但矩阵 (JTJ+μI) 只要 μ>0，就一定是正定的，因此总是可逆的，这确保了求解步骤的数值稳定性。

第三步：自适应调整阻尼因子 μμ LM算法的智能核心就在于如何根据当前迭代的表现自动调整 μμ，其策略基于一个简单概念：评估二次近似模型的好坏。

• 如果 ρρ 很大（例如 > 0.75）：说明实际下降量比预测的还要多，局部二次模型非常准确，可以减小 μμ（例如乘以 1/3），让下一步更接近高斯-牛顿法，迈出更大的一步。
• 如果 ρρ 很小（例如 < 0.25）：说明实际下降量远小于预测值，局部模型非常不准确，需要增加 μμ（例如乘以 2），让下一步更接近梯度下降法，迈出更小、更稳健的一步。
• 如果 ρρ 处于中间值：说明近似效果可以接受，保持 μμ 不变进行下一步。

虽然ρ=1是理想情况，但在实际数值优化中，要求模型完全精确（ρ=1）是不现实且不必要的。因此，算法设置了一个“足够好”的范围（ρ>0.75），只要模型在这个范围内，就认为它是可靠的，可以激进地减小μ；同样，ρ<0.25代表模型“足够差”，需要保守地增大μ；这些阈值是经验值，可以根据具体问题调整。

4. 完整LM算法流程

初始化： 参数向量 β0β0，阻尼因子 μ0μ0（例如 μ0=0.001μ0=0.001），缩放因子 ν>1ν>1（例如 ν=2,10ν=2,10），停止阈值 ϵϵ，设 k=0k=0。

开始迭代：

5. 优缺点总结

优点：

• 稳健性：比纯高斯-牛顿法稳定得多，不容易发散。
• 效率：通常比梯度下降法收敛快得多。
• 自适应：无需手动调整学习率，算法自动在速度与稳健性之间权衡。
• 数值稳定：正则化的正规方程总是可解的。

缺点：

• 内存消耗：需要计算和存储雅可比矩阵 JJ（m×n）以及矩阵 JTJ（n×n ），对于超大规模问题（n 极大），这可能成为瓶颈。
• 计算成本：每次迭代都需要求解一个线性方程组，虽然系数矩阵是 n×n 的（n 是参数数量），但对于中等规模问题，这通常是可接受的。
• 局部最小值：和所有基于梯度的优化器一样，LM只能找到局部最小值。

总而言之，Levenberg-Marquardt 算法通过其精巧的自适应阻尼机制，成功地将梯度下降法的稳健性和高斯-牛顿法的速度结合在一起，使其成为解决中小规模非线性最小二乘问题最强大、最流行的工具之一。

6. 预测下降量的公式推导

公式清楚地表明，预测下降量由两部分组成：一部分来自阻尼项 μkδk，另一部分来自梯度项 Jkrk。