查看“︁莱文伯格-马夸特方法”︁的源代码

'''莱文伯格-马夸特方法'''（{{lang-en|Levenberg–Marquardt algorithm}}）能提供數非線性最小化（局部最小）的數值解。此演算法能藉由執行時修改參數達到結合高斯-牛顿算法以及梯度下降法的優點，並對兩者之不足作改善（比如高斯-牛顿算法之反矩陣不存在或是初始值離局部極小值太遠）。<ref>{{Cite web|title=Levenberg-Marquardt backpropagation - MATLAB trainlm|url=https://www.mathworks.com/help/deeplearning/ref/trainlm.html|accessdate=2019-07-21|work=www.mathworks.com|archive-date=2020-10-25|archive-url=https://web.archive.org/web/20201025224709/https://www.mathworks.com/help/deeplearning/ref/trainlm.html}}</ref>

==問題描述==
假設 <math>f</math> 是一個從 <math>\real^m \rightarrow \real^n</math> 的非线性映射，也就是說 <math>\mathbf{P} \in \real^m</math> 且 <math>\mathbf{X} \in \real^n</math>, 那麼:

<math>
f(\mathbf{P}) = \mathbf{X}
</math>

而我們的目的就是希望任意給定一個 <math>\mathbf{x}</math> 以及合理的初始值 <math>\mathbf{p}_0</math>，我們能找到一個 <math>\mathbf{p}^{+}</math>，使得 <math>\mathbf{\epsilon}^T\mathbf{\epsilon}</math> 盡量小（局部極小），其中 <math>\mathbf{\epsilon} = f(\mathbf{p}^+)-\mathbf{x}</math>。
==解法==
像大多數最小化的方法一樣，這是一個迭代的方法。首先根據泰勒展开式我們能把 <math>f(\mathbf{p}+\mathbf{\delta_p})</math> 寫為下面的近似，這有兩個好處：第一是線性、第二是只需要一階微分。
<blockquote>
<math>
f(\mathbf{p}+\mathbf{\delta_p}) \approx f(\mathbf{p}) + \mathbf{J\delta_p}
</math>
</blockquote>
其中<math>\mathbf{J}</math>是<math>f</math>的[[雅可比矩阵]]。對於每次的迭代我們這麼作：假設這次 iteration 的點是 <math>\mathbf{p}_k</math>，我們要找到一個 <math>\mathbf{\delta}_{\mathbf{p},k}</math> 讓 <math>|\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}}|</math> 最小。
根據投影公式我們知道當下面式子被滿足的時候能有最小誤差：
<blockquote>
<math>
(\mathbf{J}^T\mathbf{J})\mathbf{\delta_{\mathbf{p},k}} = \mathbf{J}^T\mathbf{\epsilon}_{k}
</math>
</blockquote>
我們將這個公式略加修改得到：
<blockquote>
<math>
[\mu\mathbf{I}+(\mathbf{J}^T\mathbf{J})]\mathbf{\delta_{\mathbf{p},k}} = \mathbf{J}^T\mathbf{\epsilon}_{k}
</math>
</blockquote>
就是莱文伯格-马夸特方法。如此一來 <math>\mu</math> 大的時候這種算法會接近最速下降法，小的時候會接近高斯-牛顿方法。為了確保每次 <math>\mathbf{\epsilon}</math> 長度的減少，我們這麼作：先採用一個小的 <math>\mu</math>，如果 <math>\mathbf{\epsilon}</math> 長度變大就增加 <math>\mu</math>。

這個演算法當以下某些條件達到時結束迭代：
#如果發現 <math>\mathbf{\epsilon}</math> 長度變化小於特定的給定值就結束。
#發現 <math>\mathbf{\delta_p}</math> 變化小於特定的給定值就結束。
#到達了迭代的上限設定就結束。

==參考資料==
{{Reflist}}

{{Authority control}}
[[Category:統計演算法]]
[[Category:數學最佳化]]
[[Category:數值分析]]