[科普中國]-L-M方法

L-M方法全稱Levenberg-Marquardt方法，是非線性回歸中回歸參數(shù)最小二乘估計的一種估計方法。由D.W.Marquardt于1963年提出，他是根據(jù)1944年K.Levenbevg的一篇論文發(fā)展的。這種方法是把最速下降法和線性化方法(泰勒級數(shù))加以綜合的一種方法。因為最速下降法適用于迭代的開始階段參數(shù)估計值遠(yuǎn)離最優(yōu)值的情況，而線性化方法，即高斯牛頓法適用于迭代的后期，參數(shù)估計值接近最優(yōu)值的范圍內(nèi)。兩種方法結(jié)合起來可以較快地找到最優(yōu)值1。

基本介紹Gauss-Newton算法(1809)是一個古老的處理非線性最小二乘問題的方法，該方法在迭代過程中要求矩陣 列滿秩；而這一條件限制了它的應(yīng)用。為克服這個困難，Levenberg(1944)提出了一個新的方法，但未受到重視。后來，Marquardt(1963) 又重新提出，并在理論上進行了探討，得到了Levenberg-Marquardt方法，簡稱L-M方法。再后來，F(xiàn)letcher(1971) 對其實現(xiàn)策略進行了改進，得到了Levenberg- Marquardt-Fletcher方法。實際上，若將L-M方法與信賴域方法結(jié)合，效果可能更好2。

L-M方法通過求解下述優(yōu)化模型來獲取搜索方向：

其中，μk> 0，由最優(yōu)性條件知滿足

即

實際上，利用約束優(yōu)化問題的最優(yōu)性條件，L-M方法可以看作是Gause-Newton方法受信賴域方法的啟發(fā)產(chǎn)生的，因為dk可視為下述約束優(yōu)化問題的最優(yōu)解

這里，。

下面討論dk的下降性質(zhì)，若，則對任意,

所以dk是f(x) 在點的下降方向。引入線搜索，我們便得到非線性最小二乘問題的L-M方法：

由于dk的取值與有關(guān)，所以從嚴(yán)格意義上講， 應(yīng)記為。

L-M方法與Gauss-Newton方法的區(qū)別在于前者的搜索方向里面引入了參數(shù)μk2。

相關(guān)結(jié)論根據(jù)線性代數(shù)的知識，矩陣對向量的作用無非是改變后者的長度和方向，為此，對de(1k)，我們有下述結(jié)論。

性質(zhì)1 關(guān)于μ> 0單調(diào)不增，且當(dāng)μ→∞時，→0。

（文中性質(zhì)的證明請見參考書）

從幾何直觀來看，當(dāng)矩陣接近奇異時，由Gauss-Newton算法得到的搜索方向的模相當(dāng)?shù)卮?，而在L-M方法中，通過引入正參數(shù)μ就避免了這種情形出現(xiàn)。

下面看參數(shù)μ對搜索方向角度的影響，

性質(zhì)2 與的夾角θ關(guān)于μ> 0單調(diào)不增。

根據(jù)性質(zhì)1和2，當(dāng)μ=0時，就是Gauss-Newton方向。當(dāng)μ> 0逐漸增大時，的長度逐漸縮短，方向則逐漸偏向最速下降方向，可以設(shè)想，當(dāng)參數(shù)μ充分大時，的方向與目標(biāo)函數(shù)的負(fù)梯度方向一致，不但如此，下面的結(jié)果表明，我們引入?yún)?shù)μk可以使得搜索方向的求解更加趨于穩(wěn)定，從而我們有理由相信L-M方法的數(shù)值效果應(yīng)該比Gauss-Newon方法好一些。

性質(zhì)3的條件數(shù)關(guān)于μ單調(diào)不增。

基于以上討論，在具體的算法中，我們采用類似于調(diào)整信賴域半徑的策略來調(diào)整參數(shù)μ，這就得到Levenberg-Marquardt-Fletcher方法2。

應(yīng)用范圍Levenberg-Marquardt算法是最優(yōu)化算法中的一種。最優(yōu)化是尋找使得函數(shù)值最小的參數(shù)向量。它的應(yīng)用領(lǐng)域非常廣泛，如：經(jīng)濟學(xué)、管理優(yōu)化、網(wǎng)絡(luò)分析 、最優(yōu)設(shè)計、機械或電子設(shè)計等等。
根據(jù)求導(dǎo)數(shù)的方法，可分為2大類。第一類，若f具有解析函數(shù)形式，知道x后求導(dǎo)數(shù)速度快。第二類，使用數(shù)值差分來求導(dǎo)數(shù)。根據(jù)使用模型不同，分為非約束最優(yōu)化、約束最優(yōu)化、最小二乘最優(yōu)化。

Levenberg-Marquardt算法是使用最廣泛的非線性最小二乘算法，中文為列文伯格-馬夸爾特法。它是利用梯度求最大（?。┲档乃惴?，形象的說，屬于“爬山”法的一種。它同時具有梯度法和牛頓法的優(yōu)點。當(dāng)λ很小時，步長等于牛頓法步長，當(dāng)λ很大時，步長約等于梯度下降法的步長。圖1顯示了算法從起點，根據(jù)函數(shù)梯度信息，不斷爬升直到最高點（最大值）的迭代過程。共進行了12步。（備注：圖1中綠色線條為迭代過程）。

LM算法的實現(xiàn)并不算難，它的關(guān)鍵是用模型函數(shù) f 對待估參數(shù)向量p在其領(lǐng)域內(nèi)做線性近似，忽略掉二階以上的導(dǎo)數(shù)項，從而轉(zhuǎn)化為線性最小二乘問題，它具有收斂速度快等優(yōu)點。LM算法屬于一種“信賴域法”，所謂的信賴域法，即是：在最優(yōu)化算法中，都是要求一個函數(shù)的極小值，每一步迭代中，都要求目標(biāo)函數(shù)值是下降的，而信賴域法，顧名思義，就是從初始點開始，先假設(shè)一個可以信賴的最大位移s，然后再以當(dāng)前點為中心，以s為半徑的區(qū)域內(nèi)，通過尋找目標(biāo)函數(shù)的一個近似函數(shù)（二次的）的最優(yōu)點，來求解得到真正的位移。在得到了位移之后，再計算目標(biāo)函數(shù)值，如果其使目標(biāo)函數(shù)值的下降滿足了一定條件，那么就說明這個位移是可靠的，則繼續(xù)按此規(guī)則迭代計算下去；如果其不能使目標(biāo)函數(shù)值的下降滿足一定的條件，則應(yīng)減小信賴域的范圍，再重新求解。

LM算法需要對每一個待估參數(shù)求偏導(dǎo)，所以，如果你的擬合函數(shù) f 非常復(fù)雜，或者待估參數(shù)相當(dāng)?shù)囟啵敲纯赡懿贿m合使用LM算法，而可以選擇Powell算法（Powell算法不需要求導(dǎo)）。

本詞條內(nèi)容貢獻者為:

杜強 - 高級工程師 - 中國科學(xué)院工程熱物理研究所