莱文贝格-马夸特方法

维基百科,自由的百科全书
跳转至: 导航搜索

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

問題描述[编辑]

假設 f 是一個從 \real^m \rightarrow \real^n 的非线性映射,也就是說 \mathbf{P} \in \real^m\mathbf{X} \in \real^n, 那麼:


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

而我們的目的就是希望任意給定一個 \mathbf{x} 以及合理的初始值 \mathbf{p}_0,我們能找到一個 \mathbf{p}^{+},使得 \mathbf{\epsilon}^T\mathbf{\epsilon} 盡量小(局部極小),其中 \mathbf{\epsilon} = f(\mathbf{p}^+)-\mathbf{x}

解法[编辑]

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


f(\mathbf{p}+\mathbf{\delta_p}) \approx f(\mathbf{p}) + \mathbf{J\delta_p}

對於每次的迭代我們這麼作:假設這次 iteration 的點是 \mathbf{p}_k,我們要找到一個 \mathbf{\delta}_{\mathbf{p},k}|\mathbf{x}-f(\mathbf{p}+\mathbf{\delta}_{\mathbf{p},k})| \approx |\mathbf{x}-f(\mathbf{p}) - \mathbf{J\mathbf{\delta}_{\mathbf{p},k}}| = |\mathbf{\epsilon}_{k}-\mathbf{J\mathbf{\delta}_{\mathbf{p},k}}| 最小。 根據投影公式我們知道當下面式子被滿足的時候能有最小誤差:


(\mathbf{J}^T\mathbf{J})\mathbf{\delta_p} = \mathbf{J}^T\mathbf{\epsilon}_{k}

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


[\mu\mathbf{I}+(\mathbf{J}^T\mathbf{J})]\mathbf{\delta_p} = \mathbf{J}^T\mathbf{\epsilon}_{k}

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

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

  1. 如果發現 \mathbf{\epsilon} 長度變化小於特定的給定值就結束。
  2. 發現 \mathbf{\delta_p} 變化小於特定的給定值就結束。
  3. 到達了迭代的上限設定就結束。