莱文伯格-马夸特方法

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

问题描述

假设 ${\displaystyle f}$ 是一个从 ${\displaystyle \Re ^{m}\rightarrow \Re ^{n}}$ 的非线性映射，也就是说 ${\displaystyle \mathbf {P} \in \Re ^{m}}$ 且 ${\displaystyle \mathbf {X} \in \Re ^{n}}$, 那么:

${\displaystyle f(\mathbf {P} )=\mathbf {X} }$

而我们的目的就是希望任意给定一个 ${\displaystyle \mathbf {x} }$ 以及合理的初始值 ${\displaystyle \mathbf {p} _{0}}$，我们能找到一个 ${\displaystyle \mathbf {p} ^{+}}$，使得 ${\displaystyle \mathbf {\epsilon } ^{T}\mathbf {\epsilon } }$ 尽量小（局部极小），其中 ${\displaystyle \mathbf {\epsilon } =f(\mathbf {p} ^{+})-\mathbf {x} }$。

解法

像大多数最小化的方法一样，这是一个迭代的方法。首先根据泰勒展开式我们能把 ${\displaystyle f(\mathbf {p} +\mathbf {\delta _{p}} )}$ 写为下面的近似，这有两个好处：第一是线性、第二是只需要一阶微分。

${\displaystyle f(\mathbf {p} +\mathbf {\delta _{p}} )\approx f(\mathbf {p} )+\mathbf {J\delta _{p}} }$

其中${\displaystyle \mathbf {J} }$是${\displaystyle f}$的雅可比矩阵。对于每次的迭代我们这么作：假设这次 iteration 的点是 ${\displaystyle \mathbf {p} _{k}}$，我们要找到一个 ${\displaystyle \mathbf {\delta } _{\mathbf {p} ,k}}$ 让 ${\displaystyle |\mathbf {x} -f(\mathbf {p} _{k}+\mathbf {\delta } _{\mathbf {p} ,k})|\approx |\mathbf {x} -f(\mathbf {p} _{k})-\mathbf {J\mathbf {\delta } _{\mathbf {p} ,k}} |=|\mathbf {\epsilon } _{k}-\mathbf {J\mathbf {\delta } _{\mathbf {p} ,k}} |}$ 最小。 根据投影公式我们知道当下面式子被满足的时候能有最小误差：

${\displaystyle (\mathbf {J} ^{T}\mathbf {J} )\mathbf {\delta _{\mathbf {p} ,k}} =\mathbf {J} ^{T}\mathbf {\epsilon } _{k}}$

我们将这个公式略加修改得到：

${\displaystyle [\mu \mathbf {I} +(\mathbf {J} ^{T}\mathbf {J} )]\mathbf {\delta _{\mathbf {p} ,k}} =\mathbf {J} ^{T}\mathbf {\epsilon } _{k}}$

就是莱文伯格-马夸特方法。如此一来 ${\displaystyle \mu }$ 大的时候这种算法会接近最速下降法，小的时候会接近高斯-牛顿方法。为了确保每次 ${\displaystyle \mathbf {\epsilon } }$ 长度的减少，我们这么作：先采用一个小的 ${\displaystyle \mu }$，如果 ${\displaystyle \mathbf {\epsilon } }$ 长度变大就增加 ${\displaystyle \mu }$。

这个算法当以下某些条件达到时结束迭代：

1. 如果发现 ${\displaystyle \mathbf {\epsilon } }$ 长度变化小于特定的给定值就结束。
2. 发现 ${\displaystyle \mathbf {\delta _{p}} }$ 变化小于特定的给定值就结束。
3. 到达了迭代的上限设定就结束。