第六章-Levenberg-Marquardt方法

非线性最小二乘法•1.改进的Gauss-Newton法•2.Levenberg-Marquardt方法•3.信赖域(L-M)方法一、非线性最小二乘法1.一般形式：2)()()()(minxfxfxfxST;),...,,())(),...,(),(()(2121TnTmxxxxxfxfxfxf其中：线性最小二似非线性函数，再模仿思想：用线性函数来近乘法求解。,))(()()(kkkxxxAxfxf所以。),...,2,1(),()()()(mixxxfxfxfkTkikii则由泰勒公式可知，次的迭代点设已知第kxk。其中nmjkixxnmmnkxxfxf...xfxf...xfxAk))(()(1111分析求解.222)()()()(kkkkkkxfdAxxAxfxS。其中：kkxxd法可得问题，由线性最小二乘对于)(minx可逆时则有当kTkAA则有记,)(kkxAA,])([])([kkkTkkkxfdAxfdA)(min,])([])([)(xxfdAxfdAxkkkTkkk则可用记题的极小点。问题的极小点近似原问)(kTkkkTkxfAdAA)1()()(1kTkkTkkxfAAAd)2(收敛阶至少是二阶的。当　　是收敛的由迭代得到的则：，充分接近）满足一定条件且（性质：若,0*)()2(;)1(*0xfxxxxfk)()(11kTkkTkkkkkxfAAAxdxx，则有迭代公式令kkkdxxx1)3(3.改进的Gauss-Newton法：,)()(2)()(2)(1miTiixfxAxfxfxS因为矩阵。的在点是则HessexxHkk)(,2kTkkAAH记）式可改写为（1)(kkkxSdH)4()(1kkkxSHd即)5(所以)(11kkkkxSHxx)6(公式，式称为NewtonGauss)6(方向。）式称为（NewtonGauss5。令)()()(2)(kTkkkTkkxfAxfxAxSg则由其正定性可知：存在若,)(1kTkAA为下降方向kd0)(2)(1kkTkTkkTkgAAgdxS。奇异，则解不出否则，若kkTkdAA。此时令kkgd算法（共五步）改进的NewtonGauss。精度给定初始点0,:10xStep。令0:k;)(:2)(kjkikijAxxfaStep计算：。mikjkikikjgxxfxfg1)()()(nArankxfAgnArankxfAAAdStepkTkkkTkkTkk)()()()()(:31如果如果令1()((),...,());()TimjmnffxfxfxAxx已知：。。其中令)(min:,:41kktkkkkktdxftdtxxStep。转否则算法结束则若2,1:,;,,||)(||:51*StepkkxxxfAStepkkTkGauss-Newton法的优缺点:优点:(1)对于零残量问题(即()0fx),有局部二阶收敛速度.(2)对于小残量问题(即()fx较小,或者接近于线性),有快的局部收敛速度.(3)对于线性最小二乘问题,一步达到极小点.缺点:(1)对于不是很严重的大残量问题,有较慢的收敛速度.(2)对于残量很大的问题或者()fx的非线性程度很大的问题,不收敛.(3)如果()kAx不满秩,方法没有定义.(4)不一定总体收敛.二、Levenberg-Marquadt方法为了克服由雅可比矩阵奇异，导致线性搜索得不到进一步下降方向.只能得到极小点的一个差的估计.改进策略：采用信赖域的方法.：通常()fx是非线性函数，Gauss-Newton法用线性化模型代替()fx，得到线性最小二乘问题.这种线性化并不是对所有的kxx都成立，因此，考虑约束线性化最小二乘问题.考虑如下的信赖域模型：22min()()()..kkkkkfxAxxxstxxh.其中kh为信赖域半径.这个方程的解可由解如下方程组得到:()TTkkkkkAxAxIzAxfx(7)从而:11()TTkkkkkkkxxAxAxIAxfx.如果1()TTkkkkkAxAxAxfxh,则0k;否则0k.由于TkkkAxAxI正定(适当调整k),从而(7)产生的方向z是下降方向.这种方法是由Levenberg(1944)和Marqurdt(1963)提出的,称为Levenberg-Marqurdtmethod.简称L-M方法.迭代继续！的对角元的措施使方法采用适当增加)()(.2xAxAMLT方程组：方法求解如下满足当前的迭代点MLxSxkk,0)(.3(**))()()(:))()((kTkkkTkxfxAzxCzIxAxA过大！能够成立又不至于使为正定，且中不断调整使是一个正数，它在迭代其中)()()(:1kkkxSxSxC。得到下一迭代点然后令11kkkxzxx时，迭代无法继续！）接近于（条件数为奇异或法的迭代中，当1)()(.11BBxAxABNewtonGaussT!)(30.4敛速度的增加，否则将影响收尽可能限制方向。因而充分大时便接近负梯度偏移，当方向逐步向负梯度表明方向的增大，下面的性质方向；随着就是，得到的若取XSzNewtonGausszdisadvantage:thatifthevalueofislarge,thecalculatedHessianmatrixisnotusedatall.）的解，那么有：是方程组（，设**0.5z))()()()(122zyzxAxfyxAxfkkkk（：性质).()(2kkxSzxS适当大，总成立：：只要性质充分接近。与方向充分大时，方向：当性质)(3kxSz。并返回：则令若1),()(:2StepxSzxSStep放大。遇到困难时将缩小，迭代：一次成功迭代后将采用进退方法调整.6调整算法：.7。的初值，控制终止常数，初始点给定和步长缩小因子子初始：给定步长放大因xxf),(,101。得求解zxfxAzIxAxAStepTT)()())()((:1。否则返回则迭代终止，）（若令1)(;,::3StepxfxAzxxStepT8．L-M方法总结：比例系数0为常数，I是单位矩阵。从(7)式可看出:如果比例系数0，则为高斯-牛顿法;如果取值很大，则L-M算法接近梯度下降法.每迭代成功一步，则减小一次，这样在接近误差目标的时候，逐渐与高斯-牛顿法相似.由于L-M算法算法利用了近似的二阶导数信息，它比梯度下降法快得多.实践证明，采用L-M算法可以较原来的梯度下降法提高速度几十甚至上百倍.当足够大时，总可以保证TAxAxI是正定的，从而保证其可逆.算法的每次迭代都对进行自适应调整.当接近解时，逐渐减小，权值调整类似于高斯-牛顿法，利用类似于二阶导数的信息，可以快速收敛到最优解.当远离解时，逐渐增大，权重调整又类似于梯度下降法，可以进行全局搜索.所以LM算法同时具备了牛顿法和梯度法的优点，但计算Ax要占用较多的内存.三、信赖域(L-M)方法1．最重要的一类信赖域模型：21min()2..kTTkkkkqsfxgssGsstsh,（8）其中，ksxx,kg是目标函数()fx在当前迭代点kx处的梯度，nnkGR对称，是()fx在kx处Hesse阵2()kfx.这个模型可以由解kkGIsg(9)确定ks来表征,其中是一个非负数.如果kG正定,且牛顿修正1kkksGg满足kksh,则即为上述问题的解.(9)式中0.否则，可以假定约束有效(积极)约束,从而模型(8)可以写成:21min()2..kkTTkkkTqsfxgssGsstssh,（10）引进Lagrange函数:()21(,)()2kTkLsqsssh(11)由于约束2Tkssh是有效约束,由约束最优化的最优性条件可知:0.令(,)0sLs,有0kkgGss（减号变加号）(12)此即是(9)式.(12)式和2Tkssh为问题的一阶必要条件.所有的Levenberg-Marquardt方法都要确定一个0，使得kGI正定，并解(9)式以确定ks.9.Levenberg-Marquardt方法初始步：给出0x和00，0k。第k次迭代格式：(1)给出kx和k，计算kg和kG，若kg，停止.(2)求解kkGI，如果不正定,置4kk,并重复这一步,直到kkGI正定.(3)解方程组()kkkGIsg,求出ks.(4)求()(),,kkkkkfxsqsr的值.(5)若0.25kr,置14kk;若0.75kr,置1/2kk;否则1kk.(6)若0kr，置1kkxx,否则,令1kkkxxs.(7)令1kk,转(1).