莱文伯格-马夸特方法

莱文伯格-马夸特方法（Template:Lang-en）能提供數非線性最小化（局部最小）的數值解。此演算法能藉由執行時修改參數達到結合高斯-牛顿算法以及梯度下降法的優點，並對兩者之不足作改善（比如高斯-牛顿算法之反矩陣不存在或是初始值離局部極小值太遠）。

問題描述

假設 $f$ 是一個從 ${\mathrm{\Re }}^m\to {\mathrm{\Re }}^n$ 的非线性映射，也就是說 $𝐏\in {\mathrm{\Re }}^m$ 且 $𝐗\in {\mathrm{\Re }}^n$, 那麼:

$f(𝐏)=𝐗$

而我們的目的就是希望任意給定一個 $𝐱$ 以及合理的初始值 ${𝐩}_0$，我們能找到一個 ${𝐩}^{+}$，使得 ${\mathit{ϵ}}^T\mathit{ϵ}$ 盡量小（局部極小），其中 $\mathit{ϵ}=f({𝐩}^{+})-𝐱$。

解法

像大多數最小化的方法一樣，這是一個迭代的方法。首先根據泰勒展开式我們能把 $f(𝐩+{\mathit{\delta }}_{𝐩})$ 寫為下面的近似，這有兩個好處：第一是線性、第二是只需要一階微分。

$f(𝐩+{\mathit{\delta }}_{𝐩})\approx f(𝐩)+𝐉{\mathit{\delta }}_{𝐩}$

其中$𝐉$是$f$的雅可比矩阵。對於每次的迭代我們這麼作：假設這次 iteration 的點是 ${𝐩}_k$，我們要找到一個 ${\mathit{\delta }}_{𝐩,k}$ 讓 $|𝐱-f({𝐩}_k+{\mathit{\delta }}_{𝐩,k})|\approx |𝐱-f({𝐩}_k)-𝐉{\mathit{\delta }}_{𝐩,𝐤}|=|{\mathit{ϵ}}_k-𝐉{\mathit{\delta }}_{𝐩,𝐤}|$ 最小。 根據投影公式我們知道當下面式子被滿足的時候能有最小誤差：

$({𝐉}^T𝐉){\mathit{\delta }}_{𝐩,𝐤}={𝐉}^T{\mathit{ϵ}}_k$

我們將這個公式略加修改得到：

$[\mu 𝐈+({𝐉}^T𝐉)]{\mathit{\delta }}_{𝐩,𝐤}={𝐉}^T{\mathit{ϵ}}_k$

就是莱文伯格-马夸特方法。如此一來 $\mu$ 大的時候這種算法會接近最速下降法，小的時候會接近高斯-牛顿方法。為了確保每次 $\mathit{ϵ}$ 長度的減少，我們這麼作：先採用一個小的 $\mu$，如果 $\mathit{ϵ}$ 長度變大就增加 $\mu$。

這個演算法當以下某些條件達到時結束迭代：

1. 如果發現 $\mathit{ϵ}$ 長度變化小於特定的給定值就結束。
2. 發現 ${\mathit{\delta }}_{𝐩}$ 變化小於特定的給定值就結束。
3. 到達了迭代的上限設定就結束。