Levenberg-Marquardt 演算法

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

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

描述

對於非線性函數$F:\mathbb {R} ^{m}\to \mathbb {R} ^{n},\;m<n$，最細平方最細化問題（其中自變數嘅數量少過函數分量嘅數量）：

$\min _{x\in \mathbb {R} ^{m}}\|F(x)\|_{2}^{2}$

從初始值$x_{0}$開始行可以解到個問題。

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

$\min _{x\in \mathbb {R} ^{m}}\|F(x_{k})+J(x_{k})(x-x_{k})\|_{2}^{2}$

J 係函數 F嘅Jacobi矩陣。

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

完整嘅 Levenberg-Marquardt 疊代𨂾係：

$x_{k+1}=x_{k}-\alpha _{k}\left(J(x_{k})^{T}J(x_{k})+\Delta _{k}\right)^{-1}J(x_{k})^{T}F(x_{k})$

其中$\alpha _{k}>0$係𨂾長。

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

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

$\min _{x\in \mathbb {R} ^{m}}\|F(x_{k})+J(x_{k})(x-x_{k})\|_{2}^{2}$

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

$\min _{\|x-x_{k}\|<r_{k}}\|F(x_{k})+J(x_{k})(x-x_{k})\|_{2}^{2}$

其中$r_{k}>0$；即令個最佳化僅衹限於線性化點四周圍嘅一柵細鄰域。出於呢種原因，種類型嘅方法通常嗌做信賴域方法。可以證明受限制嘅最佳化啱好可以推出$J^{T}J+\beta _{k}I$作為線性方程組個係數矩陣。

收斂

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#端口