阻尼最小二乘算法研究综述

肖艳丽 李明星

摘要：最小二乘法（LSM） 是一种经典的数学优化方法，基本原理是通过最小化误差的平方和以确定数据与方程之间的最佳函数匹配关系。LSM简单易行，在许多领域应用广泛。众多学者对LSM进行广泛研究，提出了各种改进方法，其中比较著名的是阻尼最小二乘法（LMA）。通过研读近几年有关阻尼最小二乘算法文献，将不同学者对阻尼最小二乘算法的改进策略研究进行梳理。

关键词：最小二乘算法；阻尼最小二乘法；综述；最优化

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.

英文關键词Key Words：least squares method； Levenberg-Marquardt Algorithm； overview； optimization

0 引言

当今世界科学技术发展日新月异，尤其是计算机领域的进步极大地促进了其它相关领域发展。几乎所有的科学领域都离不开计算机科学，工程领域也不例外。大多数工程问题的核心内容都可以归结为最优化问题，解决最优化问题的方法有很多。其中阻尼最小二乘法（Levenberg-Marquardt Algorithm，LMA）是经典的寻优算法，自从数学家提出算法的基本思想后，众多学者对其开展了深入研究，提出了各种改进方法，极大地提高了寻优效果，在众多领域获得了广泛应用。作为一种著名的经典寻优算法，阻尼最小二乘法的发展历程却鲜有人能讲述清楚。本文从该算法的起源开始论述，对算法的提出、应用及改进等进行深入讨论分析，为从事算法研究的科技人员提供参考。

1 最小二乘法理论的提出

早在15-17世纪，欧洲航海家开辟新航路的过程中遇到很多困难。为了解决大洋航行中的船舶导航问题，科学家在研究天文学和大地测量学过程中提出了最小二乘法（Least Square Method，LSM）。在大洋航行时不能依靠陆地导航，于是航海家把目光转向了夜空中的满天繁星，希望借助天体为远洋航行指明方向，因此需要研究天体运行规律，通过计算能够对特定天体的运行图轨迹作出准确预测[1]。

Legendre[2]第一次简明扼要地阐述了最小二乘法的基本原理，将其描述为利用线性方程组对数据进行拟合的代数过程，并利用该方法对研究地球形状的数据进行了演示。Legendre的最小二乘法及其在天文学、大地测量学中的地位立刻得到了时代认可。

2 阻尼最小二乘法的提出

最小二乘法创立后，因其简单易行，行之有效，在许多领域得到了广泛应用。但是在实际应用中也出现了很多问题，对复杂问题尤其是非线性问题的处理效果不尽人意。于是学者开始对最小二乘算法进行优化研究，提出了众多改进方法。其中比较著名的是Kenneth Levenberg[3]提出的阻尼最小二乘法（Damped Least Squares，DLS）。之后Wynne[4]及Morrison[5]等学者对该方法进行了再研究。

阻尼最小二乘法又称Levenberg-Marquardt Algorithm（LMA or LM）。阻尼最小二乘法是求解非线性最小二乘问题的标准方法，最小二乘法主要来源于拟合问题，具体来说就是当有一组观测数据时，构造一个含参数的方程，使得方程尽可能地拟合观测数据。为了达到尽可能拟合的效果，需要将观测值、函数值与误差平方和取最小值，由此便可以确定所构造方程的参数值。当方程中的参数是非线性关系时，即所谓的非线性最小二乘问题。当遇到非线性最小二乘问题时，需要首先给定一个初始值，然后通过多次迭代的方法尽可能减小函数值与观测值之间的误差平方和，通过多次迭代以确定所构造方程中参数的合理取值。对于一般的非线性方程而言，求解待定参数的方程组往往是奇异或病态的，这时若强行求解，所得解的误差往往会非常大，应用于地球物理反演效果会非常差。阻尼最小二乘法的精妙之处恰恰体现于此，为了防止方程组出现奇异或病态，在方程中Marquardt加上一个阻尼项，这样就改善了方程的病态情况。

阻尼最小二乘法的算法优越性体现于阻尼因子的调节作用，兼顾了高斯-牛顿法和最速下降法的优点，在两种算法中取得了某种加权选择。当阻尼因子为零时，阻尼最小二乘变为高斯-牛顿法；当阻尼因子为无穷大时，阻尼最小二乘近似变为最速下降法。具体求解实际问题时，在利用阻尼最小二乘法寻找目标函数极小值的过程中，迭代初期由于所选择初始值往往远离目标函数极小值，需要选择尽可能小的阻尼因子，此时的算法类似于高斯-牛顿法，可充分利用高斯-牛顿法迭代步长大的特点，提高寻优效率，保证目标函数值尽快下降。当出现目标函数值不降反增的情况时，说明当前的阻尼因子已不适应，需要增大阻尼因子，减小迭代步长，使得寻优向最速下降法靠近，通过逐步增大阻尼因子，保证目标函数始终朝着下降的方向迭代。由此看来阻尼最小二乘法实际上是在高斯-牛顿法和最速下降法（又称梯度下降法）之间取得了某种平衡。

阻尼最小二乘法主要用于解决曲线拟合问题。但是跟很多拟合算法一样，它只能找到一个局部最小值，而不一定是全局最小。阻尼最小二乘法比高斯-牛顿法寻优效果更好，有时尽管初始值距离全局最小值较远，但算法依旧能得到较为满意的解。当然随着现实中待解决寻优问题越来越复杂，经典的阻尼最小二乘法越来越显得力不从心，此时需要对阻尼最小二乘法进行相应改进。

3 阻尼最小二乘法改进与应用

相比高斯最初提出的最小二乘法，阻尼最小二乘法有更好的计算效果，一经提出就引起了数学家的广泛兴趣，众多学者对其展开深入研究并提出新的改进形式，其中大多是针对权因子、阻尼系数和阻尼因子选取问题提出新的改进方法，也有学者将该方法应用到其它领域。下面对文献中有关方法的改进和应用情况进行分类总结。

针对阻尼最小二乘法的改进策略有多种，其中王大麒等[6]通过研究建立了一套ω权的选择原理，导出按精度比例齐步下降权公式，针对q和s权也提出了新的计算方法；朱匀华等[7-8]经过严格的理论推导，解决了比较关键的限制系数选取问题；李以柏等[9]在阻尼因子中引入权重概念，提高了程序的稳定性，加快了收敛速度；陈钟琦[10]在改进的阻尼最小二乘公式中提出加入高截止阻尼因子，将阻尼最小二乘法与最速下降法有机结合起来，克服了高阻尼因子对算法的效果不利影响；卢进等[11]基于传统的最小二乘法，提出自适应阻尼因子最小二乘参数辨识算法，根据目标函数值在相邻两次迭代中的非线性程度，确定增加或减少阻尼因子。上述几种改进方法多是从公式中阻尼因子角度考虑，从理论上提升了算法的寻优效果。也有其他学者从其它角度对算法进行分析改进，对算法的数学本质进行深入研究，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]）研究基礎上对阻尼最小二乘法的问题来源、数学本质及其与梯度下降法和高斯牛顿法的关系进行详细论述，在此基础上开发了阻尼最小二乘算法程序，基于经典数学函数对阻尼最小二乘算法的寻优效果进行计算分析；陈德豪等[20]分析了常用阻尼最小二乘法的不足，提出三点搜索法，提高了计算速度。以上改进方法大多从算法的数学公式出发，从理论角度推导新的改进公式，提高了算法的寻优速度。

除了对算法数学本质及算法改进策略进行研究，还有一些学者对算法在具体领域的应用情况进行讨论分析。孙若昧等[21]对多个地震实时资料进行阻尼最小二乘反演，成功获得了台网下方的层状速度模型；何宗海[22]利用阻尼最小二乘法计算地震的震源加速度，反演了云南地区的Q值分布；宋林平[23]利用阻尼加权最小二乘法进行地震走时层析成像；Kalachand等[24]运用阻尼最小二乘法进行广角地震反射时间反演；阮百尧等[25]利用奇异值分解法和阻尼最小二乘法进行电阻率测深曲线的一维反演，对初始模型的要求和收敛速度不同，比较了两种方法的优缺点，奇异值分解法对初始模型的要求比阻尼最小二乘法低，且收敛速度快，阻尼最小二乘法的收敛稳定性比奇异值分解法好；赵龙等[26]讨论了递推阻尼最小二乘法，并将其应用到惯导/双星组合导航系统中；王进等[27]采用阻尼最小二乘优化算法实现了电力系统综合静态负荷建模，计算过程中采用可变大小阻尼因子，验证了模型的描述能力和算法的可行性；孙明玮等[28]提出了有限时间窗口递推阻尼最小二乘法，克服了传统工程方法由于进行时间递推容易导致误差累积造成信息失真的缺陷；张国芹等[29]利用阻尼最小二乘法研究了数字化数据误差处理问题；马英杰等[30]利用阻尼最小二乘法拟合了描述土壤水分特征曲线的Van Genuchten方程参数；Jose Pujol[31]对Levenberg和Marquardt的推导过程进行详细对比讨论，并以埋藏球体的重力反演问题为例，对阻尼最小二乘算法的反演效果进行了分析；孙秩超[32]对阻尼最小二乘法进行系统研究，针对算法改进策略进行分析，提出了设置迭代参数上下限的可行性方法，结合Fletcher研究成果，提出了阻尼因子调整策略，并应用改进的阻尼最小二乘算法对瞬变电磁数据进行拟合处理与解释；李培[33]利用阻尼最小二乘法进行瑞雷面波反演，反演中对参数选择范围进行限制，每次迭代根据收敛情况选取适当的阻尼因子，在求得横波速度修正量以后，计算最佳寻优步长，利用此算法对层状介质模型和含软弱夹层模型进行了反演试算；张皓等[34]将阻尼最小二乘算法用于某铁矿重力资料反演中，反演结果与地质推断以及大功率激电解释结果相吻合；王晟等[35]利用阻尼最小二乘算法进行CARS光谱温度拟合；张亚兵等[36]在研究煤层裂隙发育带的过程中分析初始阻尼因子选取与最终计算结果的关系，认为初始阻尼因子λ应介于（120，200）区间，并通过对比煤层裂隙发育与底板构造间的对应关系，证实了策略的有效性；王亚强[37]采用正则化方法将宽约束和平滑处理的先验信息融入到阻尼最小二乘反演过程中以提高图像重建的质量；王园园等[38]利用阻尼最小二乘法进行瞬变电磁反演计算，计算过程中采用可变阻尼因子，取得了较好的反演结果；王寅等[39]将阻尼最小二乘法用于激光诱导击穿光谱重叠特征谱线分离提取，在迭代过程中根据每一步迭代后所反馈的信息动态调整迭代步长，从而有效防止迭代的发散，保证了迭代的快速收敛；陈诚[40]进行三轴天线座阻尼最小二乘跟踪策略研究，采用连续可调阻尼因子，取得了较好的跟踪效果；平晶晶[41]基于阻尼最小二乘算法对表面等离激元定向耦合器的优化问题进行研究；陈恒等[42]基于阻尼最小二乘法和模拟退火法联合反演岩石激电谱参数；项伟等[43]利用阻尼最小二乘法实现了任意欧拉角坐标转换；林茂琼等[44]基于阻尼最小二乘法开发了鲁棒自校正预测控制器，相比通常的最小二乘法有更强的鲁棒性。以上学者基于阻尼最小二乘算法在地球物理反演或其它数学计算领域进行了大量研究工作，证明阻尼最小二乘法在具体计算过程中具有良好的寻优效果，能够满足数学寻优计算的实际需要。

还有一些学者从数学角度或与其它算法结合角度，对算法的应用进行了分析研究。林茂琼等[45]利用阻尼最小二乘法进行神经网络权值的学习；王阿霞等[46]采用弯曲法进行有倾角的层状介质两点射线追踪，采用阻尼最小二乘法迭代求解，并通过分段线性插值改进迭代初值，通过规格化变加法型阻尼最小二乘法为乘法型阻尼最小二乘法，不仅解决了收敛效果与迭代步长之间的矛盾，而且使收敛速度明显加快。总之，众多学者对阻尼最小二乘法进行了理论分析及改进研究，充实了其数学理论，并将算法推广到实际寻优计算中，验证了算法的寻优效果。

4 结语

作为一种经典寻优方法，阻尼最小二乘法从一提出就表现出旺盛的生命力，历经半个多世纪的发展，获得了广泛认可。尤其在工程计算领域，作为一种长盛不衰的最优化算法，寻优效果令人满意。相信随着其进一步改进优化，一定能在最优化问题中得到更好的应用。

参考文献：

[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] 王大麒，朱匀华，陈志恬.阻尼最小二乘法中权的选择原理[J].中山大学学报，1980（1）：24-39.

[7] 朱匀华，陈志恬.阻尼最小二乘法的目标函数分离形式（Ⅰ）[J].中山大学学报，1983（1）：65-71.

[8] 朱匀华，陈志恬.阻尼最小二乘法的目标函数分离形式（Ⅱ）[J].中山大学学报，1984（2）：72-74.

[9] 李以柏，郑永梅.阻尼最小二乘法的一种改进[J].厦门大学学报：自然科学版，1985，24（4）：522-526.

[10] 陈钟琦.高阻尼因子对阻尼最小二乘法效果的影响和克服[J].现代地质，1988，2（2）：255-265.

[11] 盧进，王小华，郭姝言，等.基于递推阻尼最小二乘法的电力系统频率跟踪[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] 孙若昧，郑斯华，马林，等.阻尼最小二乘法联合测定震源位置和介质速度参数[J].地震，1986（4）：29-37.

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

[23] 宋林平.阻尼加权最小二乘地震走时层析成象[J].计算物理，1995，12（4）：499-504.

[24] KALACHAND，戴成泰.运用阻尼最小二乘法的广角地震反射时间反演[J].石油物探译丛，1995（5）：27-37.

[25] 阮百尧，葛为中.奇异值分解法与阻尼最小二乘法的对比[J].物探化探计算技术，1997，19（1）：47-49.

[26] 赵龙，刘淮，陈哲.递推阻尼最小二乘及其在INS/双星组合中的应用[J].北京航空航天大学学报，2003，29（12）：1136-1138.

[27] 王进，李欣然，苏盛.用阻尼最小二乘优化算法实现电力系统综合静态负荷建模[J].长沙电力学院学报：自然科学版，2004，19（1）：40-46.

[28] 孙明玮，张奇，邵继法，等.鲁棒递推阻尼最小二乘算法[J].航空计算技术，2003，33（1）：22-25.

[29] 张国芹，朱长青，王光霞.GIS数据误差处理的阻尼最小二乘算法[J].测绘学院学报，2004，21（1）：8-10.

[30] 马英杰，虎胆·吐马尔拜，沈冰.利用阻尼最小二乘法求解Van Genuchten方程参数[J].农业工程学报，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] 孙秩超.瞬变电磁数据改进阻尼最小二乘拟合算法研究[D].长春：吉林大学，2009.

[33] 李培.基于奇异值分解的瑞雷面波加权阻尼最小二乘反演[D].长沙：中南大学，2011.

[34] 张皓，刘建松，黄金辉，等.最优化阻尼最小二乘法重力二维反演方法及其應用[J].中国西部科技，2011，11（31）：34-36.

[35] 王晟，胡志云，张振荣，等.阻尼最小二乘算法CARS光谱温度拟合[J].强激光与粒子束，2012，12（11）：2565-2570.

[36] 张亚兵，陈同俊，崔若飞，等.基于阻尼最小二乘法的煤层裂隙P波方位属性预测[J].煤田地质与勘探，2012，40（4）：79-81，85.

[37] 王亚强.改进的阻尼最小二乘层析算法及影响因素分析[D].秦皇岛：燕山大学，2013.

[38] 王园园，刘斌，王晨.基于阻尼最小二乘法的瞬变电磁反演算法研究[J].电子测试，2013（1）：1-7.

[39] 王寅，赵南京，刘文清，等.阻尼最小二乘法用于激光诱导击穿光谱重叠特征谱线分离提取[J].光谱学与光谱分析，2015，35（2）：309-314.

[40] 陈诚.三轴天线座阻尼最小二乘跟踪策略研究[J].现代雷达，2015，37（7）：44-47.

[41] 平晶晶.基于阻尼最小二乘法的表面等离激元定向耦合器的优化[D].南京：南京航空航天大学，2016.

[42] 陈恒，严良俊，代小威，等.模拟退火法与阻尼最小二乘法联合反演岩石激电谱参数[J].工程地球物理学报，2016，13（2）：170-174.

[43] 项伟，白征东，汤晓禹.阻尼最小二乘法在任意欧拉角坐标转换中的应用[J].大地测量与地球动力学，2016，36（2）：167-170.

[44] 林茂琼，陈增强，袁著祉.基于阻尼最小二乘法的鲁棒自校正预测控制器[J].南开大学学报：自然科学版，1998，31（2）：79-83.

[45] 林茂琼，陈增强，贺江峰，等.基于阻尼最小二乘法的神经网络自校正一步预测控制器[J].控制与决策，1999，14（2）：165-168.

[46] 王阿霞，张文波.阻尼最小二乘法在射线追踪中的应用[J].西安工程学院学报，2001，23（1）：43-45.

（责任编辑：何 丽）