肖艷麗 李明星

摘要：最小二乘法（LSM） 是一種經(jīng)典的數(shù)學優(yōu)化方法，基本原理是通過最小化誤差的平方和以確定數(shù)據(jù)與方程之間的最佳函數(shù)匹配關(guān)系。LSM簡單易行，在許多領(lǐng)域應用廣泛。眾多學者對LSM進行廣泛研究，提出了各種改進方法，其中比較著名的是阻尼最小二乘法（LMA）。通過研讀近幾年有關(guān)阻尼最小二乘算法文獻，將不同學者對阻尼最小二乘算法的改進策略研究進行梳理。

關(guān)鍵詞：最小二乘算法；阻尼最小二乘法；綜述；最優(yōu)化

DOIDOI：10.11907/rjdk.173231

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2018）008-0009-04

英文摘要Abstract：As a classical mathematical optimization method，least square method（LSM） determines the optimal function matching relationship between data and function by minimizing the sum of squares of errors.LSM is simple and easy to use，and has been widely used in many fields.Many scholars have conducted extensive research on LSM，and proposed various improvement methods，among which the most famous is Levenberg Marquardt Algorithm （LMA）.By studying the literatures about LMA published in recent years，this paper summarizes and analyzes the improvement strategies of LMA.

英文關(guān)鍵詞Key Words：least squares method； Levenberg-Marquardt Algorithm； overview； optimization

0 引言

當今世界科學技術(shù)發(fā)展日新月異，尤其是計算機領(lǐng)域的進步極大地促進了其它相關(guān)領(lǐng)域發(fā)展。幾乎所有的科學領(lǐng)域都離不開計算機科學，工程領(lǐng)域也不例外。大多數(shù)工程問題的核心內(nèi)容都可以歸結(jié)為最優(yōu)化問題，解決最優(yōu)化問題的方法有很多。其中阻尼最小二乘法（Levenberg-Marquardt Algorithm，LMA）是經(jīng)典的尋優(yōu)算法，自從數(shù)學家提出算法的基本思想后，眾多學者對其開展了深入研究，提出了各種改進方法，極大地提高了尋優(yōu)效果，在眾多領(lǐng)域獲得了廣泛應用。作為一種著名的經(jīng)典尋優(yōu)算法，阻尼最小二乘法的發(fā)展歷程卻鮮有人能講述清楚。本文從該算法的起源開始論述，對算法的提出、應用及改進等進行深入討論分析，為從事算法研究的科技人員提供參考。

1 最小二乘法理論的提出

早在15-17世紀，歐洲航海家開辟新航路的過程中遇到很多困難。為了解決大洋航行中的船舶導航問題，科學家在研究天文學和大地測量學過程中提出了最小二乘法（Least Square Method，LSM）。在大洋航行時不能依靠陸地導航，于是航海家把目光轉(zhuǎn)向了夜空中的滿天繁星，希望借助天體為遠洋航行指明方向，因此需要研究天體運行規(guī)律，通過計算能夠?qū)μ囟ㄌ祗w的運行圖軌跡作出準確預測[1]。

Legendre[2]第一次簡明扼要地闡述了最小二乘法的基本原理，將其描述為利用線性方程組對數(shù)據(jù)進行擬合的代數(shù)過程，并利用該方法對研究地球形狀的數(shù)據(jù)進行了演示。Legendre的最小二乘法及其在天文學、大地測量學中的地位立刻得到了時代認可。

2 阻尼最小二乘法的提出

最小二乘法創(chuàng)立后，因其簡單易行，行之有效，在許多領(lǐng)域得到了廣泛應用。但是在實際應用中也出現(xiàn)了很多問題，對復雜問題尤其是非線性問題的處理效果不盡人意。于是學者開始對最小二乘算法進行優(yōu)化研究，提出了眾多改進方法。其中比較著名的是Kenneth Levenberg[3]提出的阻尼最小二乘法（Damped Least Squares，DLS）。之后Wynne[4]及Morrison[5]等學者對該方法進行了再研究。

阻尼最小二乘法又稱Levenberg-Marquardt Algorithm（LMA or LM）。阻尼最小二乘法是求解非線性最小二乘問題的標準方法，最小二乘法主要來源于擬合問題，具體來說就是當有一組觀測數(shù)據(jù)時，構(gòu)造一個含參數(shù)的方程，使得方程盡可能地擬合觀測數(shù)據(jù)。為了達到盡可能擬合的效果，需要將觀測值、函數(shù)值與誤差平方和取最小值，由此便可以確定所構(gòu)造方程的參數(shù)值。當方程中的參數(shù)是非線性關(guān)系時，即所謂的非線性最小二乘問題。當遇到非線性最小二乘問題時，需要首先給定一個初始值，然后通過多次迭代的方法盡可能減小函數(shù)值與觀測值之間的誤差平方和，通過多次迭代以確定所構(gòu)造方程中參數(shù)的合理取值。對于一般的非線性方程而言，求解待定參數(shù)的方程組往往是奇異或病態(tài)的，這時若強行求解，所得解的誤差往往會非常大，應用于地球物理反演效果會非常差。阻尼最小二乘法的精妙之處恰恰體現(xiàn)于此，為了防止方程組出現(xiàn)奇異或病態(tài)，在方程中Marquardt加上一個阻尼項，這樣就改善了方程的病態(tài)情況。

阻尼最小二乘法的算法優(yōu)越性體現(xiàn)于阻尼因子的調(diào)節(jié)作用，兼顧了高斯-牛頓法和最速下降法的優(yōu)點，在兩種算法中取得了某種加權(quán)選擇。當阻尼因子為零時，阻尼最小二乘變?yōu)楦咚?牛頓法；當阻尼因子為無窮大時，阻尼最小二乘近似變?yōu)樽钏傧陆捣?。具體求解實際問題時，在利用阻尼最小二乘法尋找目標函數(shù)極小值的過程中，迭代初期由于所選擇初始值往往遠離目標函數(shù)極小值，需要選擇盡可能小的阻尼因子，此時的算法類似于高斯-牛頓法，可充分利用高斯-牛頓法迭代步長大的特點，提高尋優(yōu)效率，保證目標函數(shù)值盡快下降。當出現(xiàn)目標函數(shù)值不降反增的情況時，說明當前的阻尼因子已不適應，需要增大阻尼因子，減小迭代步長，使得尋優(yōu)向最速下降法靠近，通過逐步增大阻尼因子，保證目標函數(shù)始終朝著下降的方向迭代。由此看來阻尼最小二乘法實際上是在高斯-牛頓法和最速下降法（又稱梯度下降法）之間取得了某種平衡。

阻尼最小二乘法主要用于解決曲線擬合問題。但是跟很多擬合算法一樣，它只能找到一個局部最小值，而不一定是全局最小。阻尼最小二乘法比高斯-牛頓法尋優(yōu)效果更好，有時盡管初始值距離全局最小值較遠，但算法依舊能得到較為滿意的解。當然隨著現(xiàn)實中待解決尋優(yōu)問題越來越復雜，經(jīng)典的阻尼最小二乘法越來越顯得力不從心，此時需要對阻尼最小二乘法進行相應改進。

3 阻尼最小二乘法改進與應用

相比高斯最初提出的最小二乘法，阻尼最小二乘法有更好的計算效果，一經(jīng)提出就引起了數(shù)學家的廣泛興趣，眾多學者對其展開深入研究并提出新的改進形式，其中大多是針對權(quán)因子、阻尼系數(shù)和阻尼因子選取問題提出新的改進方法，也有學者將該方法應用到其它領(lǐng)域。下面對文獻中有關(guān)方法的改進和應用情況進行分類總結(jié)。

針對阻尼最小二乘法的改進策略有多種，其中王大麒等[6]通過研究建立了一套ω權(quán)的選擇原理，導出按精度比例齊步下降權(quán)公式，針對q和s權(quán)也提出了新的計算方法；朱勻華等[7-8]經(jīng)過嚴格的理論推導，解決了比較關(guān)鍵的限制系數(shù)選取問題；李以柏等[9]在阻尼因子中引入權(quán)重概念，提高了程序的穩(wěn)定性，加快了收斂速度；陳鐘琦[10]在改進的阻尼最小二乘公式中提出加入高截止阻尼因子，將阻尼最小二乘法與最速下降法有機結(jié)合起來，克服了高阻尼因子對算法的效果不利影響；盧進等[11]基于傳統(tǒng)的最小二乘法，提出自適應阻尼因子最小二乘參數(shù)辨識算法，根據(jù)目標函數(shù)值在相鄰兩次迭代中的非線性程度，確定增加或減少阻尼因子。上述幾種改進方法多是從公式中阻尼因子角度考慮，從理論上提升了算法的尋優(yōu)效果。也有其他學者從其它角度對算法進行分析改進，對算法的數(shù)學本質(zhì)進行深入研究，Henri P Gavin[12]在前人（M I A Lourakis[13]， K Madsen et al[14]， D W Marquardt[15]， H B Nielson[16]， W H Press et al[17]， Mark K Transtrum et al[18]， Mark K et al[19]）研究基礎(chǔ)上對阻尼最小二乘法的問題來源、數(shù)學本質(zhì)及其與梯度下降法和高斯牛頓法的關(guān)系進行詳細論述，在此基礎(chǔ)上開發(fā)了阻尼最小二乘算法程序，基于經(jīng)典數(shù)學函數(shù)對阻尼最小二乘算法的尋優(yōu)效果進行計算分析；陳德豪等[20]分析了常用阻尼最小二乘法的不足，提出三點搜索法，提高了計算速度。以上改進方法大多從算法的數(shù)學公式出發(fā)，從理論角度推導新的改進公式，提高了算法的尋優(yōu)速度。

除了對算法數(shù)學本質(zhì)及算法改進策略進行研究，還有一些學者對算法在具體領(lǐng)域的應用情況進行討論分析。孫若昧等[21]對多個地震實時資料進行阻尼最小二乘反演，成功獲得了臺網(wǎng)下方的層狀速度模型；何宗海[22]利用阻尼最小二乘法計算地震的震源加速度，反演了云南地區(qū)的Q值分布；宋林平[23]利用阻尼加權(quán)最小二乘法進行地震走時層析成像；Kalachand等[24]運用阻尼最小二乘法進行廣角地震反射時間反演；阮百堯等[25]利用奇異值分解法和阻尼最小二乘法進行電阻率測深曲線的一維反演，對初始模型的要求和收斂速度不同，比較了兩種方法的優(yōu)缺點，奇異值分解法對初始模型的要求比阻尼最小二乘法低，且收斂速度快，阻尼最小二乘法的收斂穩(wěn)定性比奇異值分解法好；趙龍等[26]討論了遞推阻尼最小二乘法，并將其應用到慣導/雙星組合導航系統(tǒng)中；王進等[27]采用阻尼最小二乘優(yōu)化算法實現(xiàn)了電力系統(tǒng)綜合靜態(tài)負荷建模，計算過程中采用可變大小阻尼因子，驗證了模型的描述能力和算法的可行性；孫明瑋等[28]提出了有限時間窗口遞推阻尼最小二乘法，克服了傳統(tǒng)工程方法由于進行時間遞推容易導致誤差累積造成信息失真的缺陷；張國芹等[29]利用阻尼最小二乘法研究了數(shù)字化數(shù)據(jù)誤差處理問題；馬英杰等[30]利用阻尼最小二乘法擬合了描述土壤水分特征曲線的Van Genuchten方程參數(shù)；Jose Pujol[31]對Levenberg和Marquardt的推導過程進行詳細對比討論，并以埋藏球體的重力反演問題為例，對阻尼最小二乘算法的反演效果進行了分析；孫秩超[32]對阻尼最小二乘法進行系統(tǒng)研究，針對算法改進策略進行分析，提出了設(shè)置迭代參數(shù)上下限的可行性方法，結(jié)合Fletcher研究成果，提出了阻尼因子調(diào)整策略，并應用改進的阻尼最小二乘算法對瞬變電磁數(shù)據(jù)進行擬合處理與解釋；李培[33]利用阻尼最小二乘法進行瑞雷面波反演，反演中對參數(shù)選擇范圍進行限制，每次迭代根據(jù)收斂情況選取適當?shù)淖枘嵋蜃?，在求得橫波速度修正量以后，計算最佳尋優(yōu)步長，利用此算法對層狀介質(zhì)模型和含軟弱夾層模型進行了反演試算；張皓等[34]將阻尼最小二乘算法用于某鐵礦重力資料反演中，反演結(jié)果與地質(zhì)推斷以及大功率激電解釋結(jié)果相吻合；王晟等[35]利用阻尼最小二乘算法進行CARS光譜溫度擬合；張亞兵等[36]在研究煤層裂隙發(fā)育帶的過程中分析初始阻尼因子選取與最終計算結(jié)果的關(guān)系，認為初始阻尼因子λ應介于（120，200）區(qū)間，并通過對比煤層裂隙發(fā)育與底板構(gòu)造間的對應關(guān)系，證實了策略的有效性；王亞強[37]采用正則化方法將寬約束和平滑處理的先驗信息融入到阻尼最小二乘反演過程中以提高圖像重建的質(zhì)量；王園園等[38]利用阻尼最小二乘法進行瞬變電磁反演計算，計算過程中采用可變阻尼因子，取得了較好的反演結(jié)果；王寅等[39]將阻尼最小二乘法用于激光誘導擊穿光譜重疊特征譜線分離提取，在迭代過程中根據(jù)每一步迭代后所反饋的信息動態(tài)調(diào)整迭代步長，從而有效防止迭代的發(fā)散，保證了迭代的快速收斂；陳誠[40]進行三軸天線座阻尼最小二乘跟蹤策略研究，采用連續(xù)可調(diào)阻尼因子，取得了較好的跟蹤效果；平晶晶[41]基于阻尼最小二乘算法對表面等離激元定向耦合器的優(yōu)化問題進行研究；陳恒等[42]基于阻尼最小二乘法和模擬退火法聯(lián)合反演巖石激電譜參數(shù)；項偉等[43]利用阻尼最小二乘法實現(xiàn)了任意歐拉角坐標轉(zhuǎn)換；林茂瓊等[44]基于阻尼最小二乘法開發(fā)了魯棒自校正預測控制器，相比通常的最小二乘法有更強的魯棒性。以上學者基于阻尼最小二乘算法在地球物理反演或其它數(shù)學計算領(lǐng)域進行了大量研究工作，證明阻尼最小二乘法在具體計算過程中具有良好的尋優(yōu)效果，能夠滿足數(shù)學尋優(yōu)計算的實際需要。

還有一些學者從數(shù)學角度或與其它算法結(jié)合角度，對算法的應用進行了分析研究。林茂瓊等[45]利用阻尼最小二乘法進行神經(jīng)網(wǎng)絡權(quán)值的學習；王阿霞等[46]采用彎曲法進行有傾角的層狀介質(zhì)兩點射線追蹤，采用阻尼最小二乘法迭代求解，并通過分段線性插值改進迭代初值，通過規(guī)格化變加法型阻尼最小二乘法為乘法型阻尼最小二乘法，不僅解決了收斂效果與迭代步長之間的矛盾，而且使收斂速度明顯加快?？傊?，眾多學者對阻尼最小二乘法進行了理論分析及改進研究，充實了其數(shù)學理論，并將算法推廣到實際尋優(yōu)計算中，驗證了算法的尋優(yōu)效果。

4 結(jié)語

作為一種經(jīng)典尋優(yōu)方法，阻尼最小二乘法從一提出就表現(xiàn)出旺盛的生命力，歷經(jīng)半個多世紀的發(fā)展，獲得了廣泛認可。尤其在工程計算領(lǐng)域，作為一種長盛不衰的最優(yōu)化算法，尋優(yōu)效果令人滿意。相信隨著其進一步改進優(yōu)化，一定能在最優(yōu)化問題中得到更好的應用。

參考文獻：

[1] STIGLER S M.The history of statistics：the measurement of uncertainty before 1900[M].Cambridge：Belknap Press of Harvard University Press，1986.

[2] Legendre A M.Nouvelles méthodes pour la détermination des orbites des comètes [M].Paris：Nabu Press，1805.

[3] LEVENBERG K.A method for the solution of certain non-linear problems in least squares[J].Quarterly of Applied Mathematics，1944，2（4）：164-168.

[4] WYNNE C G.Lens designing by electronic digital computer：I[J].Proceedings of the Physical Society，1959，73（5）：777-787.

[5] MORRISON D D.Methods for nonlinear least squares problems and convergence proofs[J].Proceedings of the Seminar on Tracking Programs and Orbit Determination，1960，2012（1）：1409-1415.

[6] 王大麒，朱勻華，陳志恬.阻尼最小二乘法中權(quán)的選擇原理[J].中山大學學報，1980（1）：24-39.

[7] 朱勻華，陳志恬.阻尼最小二乘法的目標函數(shù)分離形式（Ⅰ）[J].中山大學學報，1983（1）：65-71.

[8] 朱勻華，陳志恬.阻尼最小二乘法的目標函數(shù)分離形式（Ⅱ）[J].中山大學學報，1984（2）：72-74.

[9] 李以柏，鄭永梅.阻尼最小二乘法的一種改進[J].廈門大學學報：自然科學版，1985，24（4）：522-526.

[10] 陳鐘琦.高阻尼因子對阻尼最小二乘法效果的影響和克服[J].現(xiàn)代地質(zhì)，1988，2（2）：255-265.

[11] 盧進，王小華，郭姝言，等.基于遞推阻尼最小二乘法的電力系統(tǒng)頻率跟蹤[J].電子科技，2014，27（12）：17-19.

[12] GAVIN H P.The Levenberg-Marquardt method for nonlinear least squares curve-fitting problems[EB/OL].http：//people.duke.edu/～hpgavin/ce281/lm.pdf.

[13] LOURAKIS M I A.A brief description of the Levenberg-Marquardt algorithm implemented by levmar[EB/OL].http：//users.ics.forth.gr/lourakis/levmar/levmar.pdf.

[14] MADSEN K，NIELSEN N B，TINGLEFF O.Methods for nonlinear least squares problems[J].Society for Industrial & Applied Mathematics，2004（1）：1409-1415.

[15] MARQUARDT D W.An algorithm for least-squares estimation of nonlinear parameters[J].Journal of the Society for Industrial and Applied Mathematics，1963，11（2）：431-441.

[16] NIELSEN H B.Damping parameter in marquardt′s method [EB/OL].http：//www.imm.dtu.dk/documents/ftp/tr99/tr05_99.pdf.

[17] PRESS W H，TEUKOSKY S A，VETTERLING W T，et al.Numerical recipes in C[M].United Kingdom：Cambridge University Press，1992.

[18] TRANSTRUM M K， SETHNA J P.Improvements to the Levenberg-Marquardt algorithm for nonlinear least-squares minimization [EB/OL].https：//arxiv.org/abs/1201.5885.

[19] MARK K T，BENJAMIN B M， JAMES P S.Why are nonlinear fits to data so challenging[J].Physical Review Letters，2010，104 （6） ：1-4.

[20] 陳德豪，張琰.常用阻尼最小二乘算法的改進[J].物測科技，1994（1）：31-52.

[21] 孫若昧，鄭斯華，馬林，等.阻尼最小二乘法聯(lián)合測定震源位置和介質(zhì)速度參數(shù)[J].地震，1986（4）：29-37.

[22] 何宗海.用阻尼最小二乘法研究云南地區(qū)的Q值分布[J].西北大學學報：自然科學版，1995，25（3）：237-240.

[23] 宋林平.阻尼加權(quán)最小二乘地震走時層析成象[J].計算物理，1995，12（4）：499-504.

[24] KALACHAND，戴成泰.運用阻尼最小二乘法的廣角地震反射時間反演[J].石油物探譯叢，1995（5）：27-37.

[25] 阮百堯，葛為中.奇異值分解法與阻尼最小二乘法的對比[J].物探化探計算技術(shù)，1997，19（1）：47-49.

[26] 趙龍，劉淮，陳哲.遞推阻尼最小二乘及其在INS/雙星組合中的應用[J].北京航空航天大學學報，2003，29（12）：1136-1138.

[27] 王進，李欣然，蘇盛.用阻尼最小二乘優(yōu)化算法實現(xiàn)電力系統(tǒng)綜合靜態(tài)負荷建模[J].長沙電力學院學報：自然科學版，2004，19（1）：40-46.

[28] 孫明瑋，張奇，邵繼法，等.魯棒遞推阻尼最小二乘算法[J].航空計算技術(shù)，2003，33（1）：22-25.

[29] 張國芹，朱長青，王光霞.GIS數(shù)據(jù)誤差處理的阻尼最小二乘算法[J].測繪學院學報，2004，21（1）：8-10.

[30] 馬英杰，虎膽·吐馬爾拜，沈冰.利用阻尼最小二乘法求解Van Genuchten方程參數(shù)[J].農(nóng)業(yè)工程學報，2005，21（8）：179-180.

[31] JOSE P.The solution of nonlinear inverse problems and the Levenberg-Marquardt method[J].Geophysics，2007，72（4）：1-16.

[32] 孫秩超.瞬變電磁數(shù)據(jù)改進阻尼最小二乘擬合算法研究[D].長春：吉林大學，2009.

[33] 李培.基于奇異值分解的瑞雷面波加權(quán)阻尼最小二乘反演[D].長沙：中南大學，2011.

[34] 張皓，劉建松，黃金輝，等.最優(yōu)化阻尼最小二乘法重力二維反演方法及其應用[J].中國西部科技，2011，11（31）：34-36.

[35] 王晟，胡志云，張振榮，等.阻尼最小二乘算法CARS光譜溫度擬合[J].強激光與粒子束，2012，12（11）：2565-2570.

[36] 張亞兵，陳同俊，崔若飛，等.基于阻尼最小二乘法的煤層裂隙P波方位屬性預測[J].煤田地質(zhì)與勘探，2012，40（4）：79-81，85.

[37] 王亞強.改進的阻尼最小二乘層析算法及影響因素分析[D].秦皇島：燕山大學，2013.

[38] 王園園，劉斌，王晨.基于阻尼最小二乘法的瞬變電磁反演算法研究[J].電子測試，2013（1）：1-7.

[39] 王寅，趙南京，劉文清，等.阻尼最小二乘法用于激光誘導擊穿光譜重疊特征譜線分離提取[J].光譜學與光譜分析，2015，35（2）：309-314.

[40] 陳誠.三軸天線座阻尼最小二乘跟蹤策略研究[J].現(xiàn)代雷達，2015，37（7）：44-47.

[41] 平晶晶.基于阻尼最小二乘法的表面等離激元定向耦合器的優(yōu)化[D].南京：南京航空航天大學，2016.

[42] 陳恒，嚴良俊，代小威，等.模擬退火法與阻尼最小二乘法聯(lián)合反演巖石激電譜參數(shù)[J].工程地球物理學報，2016，13（2）：170-174.

[43] 項偉，白征東，湯曉禹.阻尼最小二乘法在任意歐拉角坐標轉(zhuǎn)換中的應用[J].大地測量與地球動力學，2016，36（2）：167-170.

[44] 林茂瓊，陳增強，袁著祉.基于阻尼最小二乘法的魯棒自校正預測控制器[J].南開大學學報：自然科學版，1998，31（2）：79-83.

[45] 林茂瓊，陳增強，賀江峰，等.基于阻尼最小二乘法的神經(jīng)網(wǎng)絡自校正一步預測控制器[J].控制與決策，1999，14（2）：165-168.

[46] 王阿霞，張文波.阻尼最小二乘法在射線追蹤中的應用[J].西安工程學院學報，2001，23（1）：43-45.

（責任編輯：何 麗）