LM算法推导：阻尼法与置信域法

应用领域

LM 算法用于解决非线性最小二乘问题，问题定义如下：
\min _{x} \frac{1}{2}\|f(\boldsymbol{x})\|_{2}^{2}

LM 算法有两种推导和实现，一种是算法发明者使用的 阻尼法，一种是后来学者补充的 置信域法。这里分别作出推导。

阻尼法推导 Damped Method

1. 一阶泰勒展开近似

对 f(x) 在 x_n 处泰勒展开：
f(\boldsymbol{x_n}+\Delta \boldsymbol{x}) \approx f(\boldsymbol{x_n}) +\boldsymbol{J}(\boldsymbol{x_n}) \Delta \boldsymbol{x}

将问题转化为：对于每次迭代，求最优的 Δx。表达如下：
\Delta \boldsymbol{x}^{*} =\arg \min _{\Delta \boldsymbol{x}} \frac{1}{2}\|f(\boldsymbol{x_n}) +\boldsymbol{J_n}(\boldsymbol{x_n}) \Delta \boldsymbol{x}\|^{2}

2. 加入阻尼项

\Delta \boldsymbol{x}^{*} =\arg \min _{\Delta \boldsymbol{x}} \frac{1}{2}\|f(\boldsymbol{x_n}) +\boldsymbol{J_n}(\boldsymbol{x_n}) \Delta \boldsymbol{x}\|^{2} +\frac{1}{2}μΔx^TΔx

  • μ 为阻尼系数

阻尼项 \frac{1}{2}μΔx^TΔx 可以看作是对于过大的 Δx 的惩罚。

3. 求极值

令关于 Δx 的导数=0 ：

\boldsymbol{J}(\boldsymbol{x_n})^{T} f(\boldsymbol{x_n}) +\boldsymbol{J}(\boldsymbol{x_n})^{T} \boldsymbol{J}(\boldsymbol{x_n}) \Delta \boldsymbol{x} +μΔx =\mathbf{0}

得最优解：

Δ\boldsymbol{x}^* = -(\boldsymbol{J}(\boldsymbol{x_n})^{T} \boldsymbol{J}(\boldsymbol{x_n})+μ\boldsymbol{I})^{-1} \boldsymbol{J(x_n)}^Tf(\boldsymbol{x_n})

简化表示：
\boldsymbol{J}(\boldsymbol{x_n})^T\boldsymbol{J}(\boldsymbol{x_n}) = \boldsymbol{H} \\ \boldsymbol{J}(\boldsymbol{x_n})^Tf(\boldsymbol{x_n}) = \boldsymbol{g}

简化后的最优解：
Δx^*=-(H+μI)^{-1}g

4. 阻尼系数 μ 的调节

上面的最优解表达式中还有一个阻尼系数 μ 没有确定，这里给出它的确定方法。

定义增益率(gain ratio) ρ：(也有叫它下降率的reduction ratio)
\rho=\frac{f(\boldsymbol{x}+\Delta \boldsymbol{x})-f(\boldsymbol{x})}{\boldsymbol{J}(\boldsymbol{x}) \Delta \boldsymbol{x}}

ρ 表达了一阶泰勒展开近似与真实函数的相似程度，分子部分是 f 函数在经历了自变量 Δx 变化后的变化情况，分母部分是一阶泰勒展开近似在经历了 Δx 后的变化情况。

  • 分子越大，f 下降的大，ρ 越大 → 说明这里的泰勒展开近似是比较准确的，应减小阻尼系数
  • 分子越小，f 下降的小，ρ 越小 → 说明这里的泰勒展开近似不太准确，应增大阻尼系数

介绍两种阻尼系数的调节方案：
方案一 (Marquardt 1963)：
\begin{align*} \text { if } \quad &ρ<0.25 \\ &\mu:=\mu * 2 \\ \text { else if } \quad &ρ>0.75 \\ &\mu:=\mu / 3 \end{align*}
ρ<0.25 时会增大阻尼系数，ρ>0.75 时减少阻尼系数。

方案二 (Nielsen 1999)：
\begin{align*} \text { if } \quad &ρ>0 \\ & \mu :=\mu * \max \left\{\frac{1}{3}, 1-(2 ρ-1)^{3}\right\} ; \quad \nu:=2 \\ \text { else } \\ & \mu:=\mu * \nu ; \quad \nu:=2 * \nu \end{align*}
方案二中，对于错误的 Δx，也就是 ρ<0 的情况，将会迅速增大阻尼系数，使下一步的 Δx 趋向于更小。比方案一多了一个参数 ν。

5. 总结

阻尼法的LM算法的每步迭代过程为：

  1. 计算迭代增量 Δx，依据 Δx^*=-(H+μI)^{-1}g
  2. 计算增益率 ρ，用于调节 μ，依据 \rho=\frac{f(\boldsymbol{x}+\Delta \boldsymbol{x})-f(\boldsymbol{x})}{\boldsymbol{J}(\boldsymbol{x}) \Delta \boldsymbol{x}}
  3. 调节阻尼系数 μ，用于下一次迭代计算 Δx

置信域法推导 Trust Region Method

1. 一阶泰勒展开近似

这一步与阻尼法是一致的。
对 f(x) 在 x_n 处泰勒展开：
f(\boldsymbol{x_n}+\Delta \boldsymbol{x}) \approx f(\boldsymbol{x_n}) +\boldsymbol{J}(\boldsymbol{x_n}) \Delta \boldsymbol{x}

将问题转化为：对于每次迭代，求最优的 Δx。表达如下：
\Delta \boldsymbol{x}^{*} =\arg \min _{\Delta \boldsymbol{x}} \frac{1}{2}\|f(\boldsymbol{x_n}) +\boldsymbol{J_n}(\boldsymbol{x_n}) \Delta \boldsymbol{x}\|^{2}

2. 加入置信域约束项

对于每一步迭代，使用 d 来约束增量 Δx，构成如下带小于等于号的约束优化问题
\Delta \boldsymbol{x}^{*} =\arg \min _{\Delta \boldsymbol{x}} \frac{1}{2}\|f(\boldsymbol{x_n}) +\boldsymbol{J_n}(\boldsymbol{x_n}) \Delta \boldsymbol{x}\|^{2} \\ \quad\text{s.t.} \quad Δx^TΔx \le d

  • d 是置信域的范围，对于每一步的迭代，d 是一个已知量。

3. 求解约束优化问题

对于这种小于等于号的约束优化问题，是需要分两情况进行考虑。

情况1：
假设最优解 Δx^* 位于 Δx^TΔx < d 的范围内，则此时带约束的最优解就是无约束情况下的最优解，通过以下方式对这种假设进行求解和验证：

  1. 求无约束的最优解，得 Δx^*=-H^{-1}g；
  2. 验证此最优解是否满足 Δx^TΔx < d；
  3. 如果满足则此解为带约束的最优解， 如果不满足说明最优解不在Δx^TΔx < d 的范围内，而在Δx^TΔx = d 的范围上，此时应通过下一种情况继续求解。

情况2：
假设最优解位于Δx^TΔx = d 的范围上，此时就是一个等式约束优化问题:
\Delta \boldsymbol{x}^{*} =\arg \min _{\Delta \boldsymbol{x}} \frac{1}{2}\|f(\boldsymbol{x_n}) +\boldsymbol{J_n}(\boldsymbol{x_n}) \Delta \boldsymbol{x}\|^{2} \\ \quad\text{s.t.} \quad Δx^TΔx = d

需要引入拉格朗日乘子 λ（为方便写成\frac{1}{2}λ），构成拉格朗日方程：
L(Δx)=\frac{1}{2}\|f(\boldsymbol{x_n}) +\boldsymbol{J_n}(\boldsymbol{x_n}) \Delta \boldsymbol{x}\|^{2} +\frac{1}{2}λ(Δx^TΔx - d)
此时最优解需满足如下条件：
\begin{align*} &\text{1).} \quad \frac{∂L(Δx)}{∂Δx}=0 \Rightarrow Δx^*=-(H+λI)^{-1}g\\ \\ &\text{2).} \quad Δx^TΔx=d \end{align*}

可以看到上面的等式 1) 是与阻尼法的最优解的形式是一样的，但是阻尼法中的阻尼系数 μ 是已知的,在每一个迭代中都需要调节，而这里的拉格朗日乘子 λ 是未知的而且也是无需知道的，在每一步迭代中需要调节的是置信域范围 d。所以两个式子形式相同但是含义不一样。
联立 1) 2) 可解此等式约束问题得最优解 Δx*。

4. 置信域范围 d 的调节

上面的求解约束优化问题的过程中，还有一个置信域范围 d 需要在每一步迭代的事先确定。这里给出它的确定方法。
与阻尼法一样，首先需要计算 ρ

\rho=\frac{f(\boldsymbol{x}+\Delta \boldsymbol{x})-f(\boldsymbol{x})}{\boldsymbol{J}(\boldsymbol{x}) \Delta \boldsymbol{x}}

然后调节置信域范围 d：
\begin{align*} \text{if} \quad &ρ < 0.25 \\ &d := d/2 \\ \text{else if} \quad &ρ > 0.75 \\ &d := max\{d, 3 ∗ ∥Δx*∥\}\end{align*}

5. 总结

置信域法的LM算法的每步迭代过程为：

  1. 计算迭代增量 Δx，通过求解约束优化问题得到
  2. 计算增益率 ρ，用于调节 d，依据 \rho=\frac{f(\boldsymbol{x}+\Delta \boldsymbol{x})-f(\boldsymbol{x})}{\boldsymbol{J}(\boldsymbol{x}) \Delta \boldsymbol{x}}
  3. 调节置信域范围 d，用于下一次迭代计算 Δx
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容