萊文伯格-馬夸特方法

萊文伯格-馬夸特方法（英語：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. 到達了迭代的上限設定就結束。