LM算法

LM 算法 (Levenberg-Marquardt Algorithm)

1. 基础概念

1.1 非线性最小二乘问题

定义：给定一组观测数据 $\{(x_i, y_i)\}_{i=1}^n$，寻找参数 $\theta$ 使得模型 $f(x, \theta)$ 与观测值的残差平方和最小：

$$ \min_{\theta} F(\theta) = \frac{1}{2} \sum_{i=1}^n \left\| f(x_i, \theta) - y_i \right\|^2 $$

为什么是 $\frac{1}{2}$？：纯粹是为了数学推导方便，后续求导时会消掉。

1.2 雅可比矩阵 (Jacobian Matrix)

定义：设 $f: \mathbb{R}^n \rightarrow \mathbb{R}^m$，则雅可比矩阵 $J \in \mathbb{R}^{m \times n}$ 为：

$$ J = \begin{pmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \cdots & \frac{\partial f_2}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_m}{\partial x_1} & \frac{\partial f_m}{\partial x_2} & \cdots & \frac{\partial f_m}{\partial x_n} \end{pmatrix} $$

直观理解：

  • 梯度 $\nabla f$ 是雅可比向量（$m=1$ 时的特例）
  • 雅可比矩阵包含了所有一阶偏导数信息
  • 它描述了函数在每个维度上的局部线性变化率

特性：

  • 仅需一阶导数信息
  • 计算量远小于二阶导数（海森矩阵）

1.3 海森矩阵 (Hessian Matrix)

定义：设 $F: \mathbb{R}^n \rightarrow \mathbb{R}$，则海森矩阵 $H \in \mathbb{R}^{n \times n}$ 为：

$$ H_{ij} = \frac{\partial^2 F}{\partial x_i \partial x_j} $$

直观理解：

  • 海森矩阵是梯度的雅可比，即二阶偏导数组成的矩阵
  • 它描述了函数的局部曲率
  • 在最优化中，海森矩阵决定了参数更新的二阶信息

特性：

  • 对称矩阵（若二阶偏导连续）
  • 计算复杂度 $O(n^2)$，对于高维问题非常昂贵

1.4 三者关系

对于最小二乘问题 $F(x) = \frac{1}{2} \|f(x)\|^2$：

  • 梯度：$\nabla F = J^T f$（一阶信息）
  • 海森矩阵：$H \approx J^T J + \sum_i f_i \cdot \nabla^2 f_i$（二阶信息）

关键近似：在 LM 算法中，我们忽略二阶导数项，只用 $J^T J$ 来近似海森矩阵，从而避免计算昂贵的二阶导数。

2. 从梯度下降到高斯-牛顿

2.1 梯度下降法 (Gradient Descent)

更新规则：$\Delta x = -\alpha \nabla F$

  • 优点：离极值远时鲁棒性强
  • 缺点：线性收敛，速度慢

2.2 高斯-牛顿法 (Gauss-Newton)

核心思想：用 $J^T J$ 近似海森矩阵，避免二阶导数计算。

更新规则：$(J^T J) \Delta x = -J^T f$

  • 优点：二阶收敛速度
  • 缺点：要求 $J^T J$ 可逆，且仅在极值附近表现良好

2.3 LM 算法：两者的融合

核心公式：

$$ (J^T J + \lambda I) \Delta x = -J^T f $$

$\lambda$ 的作用：

  • $\lambda$ 大 → 趋向梯度下降（稳定但慢）
  • $\lambda$ 小 → 趋向高斯-牛顿（快但不稳定）

3. Marquardt 的改进：自适应阻尼

3.1 原始版本 (Levenberg)

$$ (J^T J + \lambda I) \Delta x = -J^T f $$

3.2 改进版本 (Marquardt)

$$ (J^T J + \lambda \cdot \text{diag}(J^T J)) \Delta x = -J^T f $$

为什么用 $\text{diag}(J^T J)$ 而不是 $I$？

  • 单位矩阵 $I$ 对所有参数的约束是均一的
  • 实际问题中，不同参数的量级可能差别很大
  • $\text{diag}(J^T J)$ 能根据参数梯度的大小自动缩放约束
  • 在梯度小的维度允许更大的步长
  • 显著提高在"狭长山谷"地形下的收敛速度

4. 增益比例 (Gain Ratio) $\rho$

4.1 定义

在实际工程中，$\lambda$ 的调整不是简单看 $F(x)$ 是否减小，而是引入指标 $\rho$：

$$ \rho = \frac{F(x) - F(x + \Delta x)}{L(0) - L(\Delta x)} $$
  • 分子：实际下降值
  • 分母：基于线性近似（泰勒展开）预期的理论下降值

4.2 更新策略

$\rho$ 范围线性近似效果$\lambda$ 调整含义
$\rho \approx 1$非常好减小 $\lambda$更接近高斯-牛顿，加速收敛
$\rho \approx 0$ 或 $<0$很差增加 $\lambda$切换到梯度下降模式
$0.25 < \rho < 0.75$一般保持 $\lambda$稳定

5. 信赖域 (Trust Region) 视角

进阶理解：LM 算法可以看作是一种信赖域方法。

  • $\lambda$ 与信赖域半径成反比
  • 增加 $\lambda$ = 缩小信赖域半径（因为不确定当前方向是否正确，只敢在很小范围内尝试）
  • 减少 $\lambda$ = 扩大信赖域半径（线性近似可靠，允许更大步长）

6. 迭代停止准则

  1. $\|J^T f\| < \epsilon_1$（梯度足够小）
  2. $\|\Delta x\| < \epsilon_2$（步长足够小）
  3. 达到最大迭代次数

7. 算法对比总结

特性梯度下降 (GD)高斯-牛顿 (GN)LM 算法
收敛速度线性（慢）二阶（快）介于两者之间
鲁棒性强（离极值远时好）弱（容易跳过极值）极强（自动切换模式）
要求一阶导数一阶导数 + $J^TJ$ 可逆一阶导数
计算复杂度低中中（需解线性方程组）

8. 适用场景

  • 曲线拟合
  • 图像配准
  • 光束法平差 (Bundle Adjustment)
  • 非线性最小二乘优化