Levenberg-Marquardt 演算法

Levenberg-Marquardt 演算法，又叫LM算法，係一種使用最細平方法求解非線性衲合問題嘅數值最佳化演算法。個方法結合埋牛頓法特別係高斯-牛頓法佮正則化技術、強制遞減函數值嘅。個演算法得名自Kenneth Levenberg同Donald Marquardt。

Levenberg-Marquardt 演算法頑健性明顯強過高斯-牛頓法，即使喺比較勩嘅起始條件下都高概率收斂得，但始終嘸保證會收斂得到。另外，喺近最細值嘅初始值時，通常會有啲慢。

描述 
對於非線性函數，最細平方最細化問題：

從初始值開始行可以解到個問題。

似高斯-牛頓法一樣，F(x)喺每一𨂾入便着線性化替代，個替代問題係：

J 係函數 F嘅Jacobi矩陣。

標準高斯-牛頓𨂾計算新點作為線性方程組嘅解具有係數矩陣嘅。若果個矩陣係病態嘅或者奇異嘅，演算法只行得一𨂾冇咁好嘅𨂾或者根本冇𨂾係求得到嘅。另外，尤其係喺條件勩同「近乎奇異咁嚌」嘅矩陣情況下，仲會有相當大嘅數值困難。 Levenberg-Marquardt 演算法透過捉線性方程組嘅係數矩陣展開成形式嚟規避啲問題，其中係確保成個項係正定嘅對角矩陣。

完整嘅 Levenberg-Marquardt 疊代𨂾係：

其中係𨂾長。

對角矩陣嘅一種廣泛使用嘅形式係 ， 其中有同埋單位矩陣。種形式亦都喺 Levenberg 同 Marquardt 嘅原始文章入便着提出到。喺情況下，Levenberg-Marquardt 疊代𨂾着約化成高斯-牛頓𨂾。反之喺情況下，單位矩陣喺條式入便占地位主導過，而 Levenberg-Marquardt 疊代𨂾着約化成梯度𨂾。透過揀選可以喺梯度𨂾同高斯-牛頓𨂾之間平滑變化。

另一種視角係，線性化嘅替代問題係：

僅衹喺線性化點四周圍一柵細區域入便逼近得原始問題好啲。之但係，嘸受限制嘅最細化行得非常大𨂾並且行出得個細柵範圍。因此，無限制嘅最佳化着受限制嘅最佳化取代：

其中；即令個最佳化僅衹限於線性化點四周圍嘅一柵細鄰域。出於呢種原因，種類型嘅方法通常嗌做信賴域方法。可以證明受限制嘅最佳化啱好可以推出作為線性方程組個係數矩陣。

收斂 
Levenberg-Marquardt 方法喺局部會變成高斯-牛頓法。因此個收斂係局部上線性嘅；甚至係二次嘅，喺接近最佳點嗰陣。

文獻 

K. Levenberg: A Method for the Solution of Certain Problems in Least Squares, Quart. Appl. Math. 2, 164-168, 1944.
 D. Marquardt: An Algorithm for Least-Squares Estimation of Nonlinear Parameters, SIAM J. Appl. Math. 11, 431-441, 1963.
 Jorge J. Moré: The Levenberg-Marquardt algorithm: Implementation and theory. In G. A. Watson (ed.): Numerical Analysis. Dundee 1977, Lecture Notes Math. 630, 1978, S. 105–116
 P. Gill, W. Murray und M. Wright: Practical Optimization, Academic Press 1981
 J. E. Dennis, Jr., und R. B. Schnabel: Numerical methods for unconstrained optimization and nonlinear equations. Prentice-Hall Series in Computational Mathematics, Englewood Cliffs 1983

Levenberg-Marquardt 演算法啲實現自由使得嘅：

gnuplot ，免費嘅圖形程序
 lmdif ，喺Fortran 入便，來自Netlib / Minpack 嘅經典實現。許可證：公共領域
 lmfit ，基於 Netlib :: Minpack :: lmfid 嘅自包含 C庫，用於一般最細化同使用最細平方法嘅曲線擬合。 FreeBSD 許可證
 levmar ，喺C / C++ 入便，帶有用於Matlab 、 Perl同Python 嘅接口。許可證： GPL
 mpfit, 喺IDL 入便實現
 csmpfit, mpfit 嘅C#端口

數值分析