LM算法求解大残差非线性最小二乘问题研究
|
摘要
针对传统LM算法求解大残差非线性最小二乘问题时存在算法失效的现象,分析Hessian矩阵与其近似矩阵的相似度对LM算法有效性的影响,提出一种依据残差变化方向搜索信赖域区间的自寻优LM算法。优化阻尼系数的更新算法,引入大残差引起的局部不收敛判断条件,以最速下降法结束当前迭代。迭代过程均以目标函数值的减小作为接受条件,算法稳定可靠。圆拟合测试结果证明:自寻优LM算法对待求参数初始值的选取不敏感,在15°夹角短圆弧、大残差等极端条件下仍可获得较快的收敛速度和良好拟合效果。自寻优LM算法具有较强的鲁棒性和稳定性,性能明显优于传统LM算法。
The traditional Levenberg-Marquardt algorithm(LM algorithm) is always invalid in solving large residual nonlinear least squares problems. Thus, how the similarity between Hessian matrix and its approximate matrix influences the effectiveness of the traditional LM algorithm is analyzed. And a self-optimizing LM algorithm that the residual changing direction is used to search for trust-region intervals is proposed. The updating algorithm of damping coefficient is improved; A judging condition is introduced to solve the local divergence caused by large residual; and the LM algorithm is substituted by the steepest descent method. It is the unique accepting condition that the objective function value is decreased continuously in the iterative process. The self-optimizing LM algorithm is stable and reliable. Circle fitting tests show that the self-optimizing LM algorithm is insensitive to the initial value of searching parameters. Under the extreme conditions such as large residual and the short arc of 15° included angle, the convergence is fast and the fitting results are good, which proves that this new algorithm is robust and stable and its performance is superior to the traditional LM algorithm.
The traditional Levenberg-Marquardt algorithm(LM algorithm) is always invalid in solving large residual nonlinear least squares problems. Thus, how the similarity between Hessian matrix and its approximate matrix influences the effectiveness of the traditional LM algorithm is analyzed. And a self-optimizing LM algorithm that the residual changing direction is used to search for trust-region intervals is proposed. The updating algorithm of damping coefficient is improved; A judging condition is introduced to solve the local divergence caused by large residual; and the LM algorithm is substituted by the steepest descent method. It is the unique accepting condition that the objective function value is decreased continuously in the iterative process. The self-optimizing LM algorithm is stable and reliable. Circle fitting tests show that the self-optimizing LM algorithm is insensitive to the initial value of searching parameters. Under the extreme conditions such as large residual and the short arc of 15° included angle, the convergence is fast and the fitting results are good, which proves that this new algorithm is robust and stable and its performance is superior to the traditional LM algorithm.
引文
[1]WANG X H,LI C.Convergence of newton’s method and uniqueness of the solution of equations in banach space II[J].Acta Mathematica Sinica,2003,19(2):405-412.
[2]PROINOV P D.General local convergence theory for a class of iterative processes and its applications to newton’s method[J].Journal of Complexity,2009,25(1):38-62.
[3]MARQUARDT D W.An algorithm for the least-squares estimation of nonlinear parameters[J].Journal of the Society for Industrial and Applied Mathematics,1963,11(2):431-441.
[4]LEVENBERG K.A method for the solution of certain non-linear problems in least squares[J].Quarterly Journal of Applied Mathmatics,1944,2(2):164-168.
[5]魏荣,卢俊国,王执铨.基于Levenberg-Marquardt算法和最小二乘方法的小波网络混合学习算法[J].信息与控制,2001,30(5):440-442.
[6]TRANSTRUM M K,MACHTA B B,SETHNA J P,Why are nonlinear fits to data so challenging[J].Phys Rev Lett,2010(104):060201.
[7]TRANSTRUMA M K,SETHNA J P.Improvements to the Levenberg-Marquardt algorithm for nonlinear leastsquares minimization[J].Journal of Computational Physics,2012,11(1):1-32.
[8]RENKA R J.Nonlinear least squares and Sobolev gradients[J].Applied Numerical Mathematics,2013(65):91-104.
[9]KAZEMI P,RENKA R J.A Levenberg-Marquardt method based on sobolev gradients[J].Nonlinear Analy sis:Theory,Methods&Applications,2012,75(16):6170-6179.
[10]LAMPTON M.Damping-undamping strategies for the Levenberg-Marquardt nonlinear Least-Squares method[J].Computers in Physics Journal,1997,11(1):110-115.
[11]张鸿燕,耿征.Levenberg-Marquardt算法的一种新解释[J].计算机工程与应用,2009,45(3):5-8.
[12]UMBACH D,JONES K N.A few methods for fitting circles to data[J].IEEE Trans on Instrumentation and Measurement,2003,52(6):1181-1885.
[13]KANATANI K,SUGAYA Y.Performance evaluation of iterative geometric fitting algorithms[J].Computational Statistics&Data Analysis,2007,52(2):1208-1222.
[14]ALSHARADQAH A,CHERNOV N.Error analysis for circle fitting algorithms[J].Electronic Journal of Statistics,2009,21(3):886-911.
[15]CHERNOV N,LESORT C.Statistical efficiency of curve fitting algorithms[J].Computational Statistics and Data Analysis,2004,47(4):713-728.
[2]PROINOV P D.General local convergence theory for a class of iterative processes and its applications to newton’s method[J].Journal of Complexity,2009,25(1):38-62.
[3]MARQUARDT D W.An algorithm for the least-squares estimation of nonlinear parameters[J].Journal of the Society for Industrial and Applied Mathematics,1963,11(2):431-441.
[4]LEVENBERG K.A method for the solution of certain non-linear problems in least squares[J].Quarterly Journal of Applied Mathmatics,1944,2(2):164-168.
[5]魏荣,卢俊国,王执铨.基于Levenberg-Marquardt算法和最小二乘方法的小波网络混合学习算法[J].信息与控制,2001,30(5):440-442.
[6]TRANSTRUM M K,MACHTA B B,SETHNA J P,Why are nonlinear fits to data so challenging[J].Phys Rev Lett,2010(104):060201.
[7]TRANSTRUMA M K,SETHNA J P.Improvements to the Levenberg-Marquardt algorithm for nonlinear leastsquares minimization[J].Journal of Computational Physics,2012,11(1):1-32.
[8]RENKA R J.Nonlinear least squares and Sobolev gradients[J].Applied Numerical Mathematics,2013(65):91-104.
[9]KAZEMI P,RENKA R J.A Levenberg-Marquardt method based on sobolev gradients[J].Nonlinear Analy sis:Theory,Methods&Applications,2012,75(16):6170-6179.
[10]LAMPTON M.Damping-undamping strategies for the Levenberg-Marquardt nonlinear Least-Squares method[J].Computers in Physics Journal,1997,11(1):110-115.
[11]张鸿燕,耿征.Levenberg-Marquardt算法的一种新解释[J].计算机工程与应用,2009,45(3):5-8.
[12]UMBACH D,JONES K N.A few methods for fitting circles to data[J].IEEE Trans on Instrumentation and Measurement,2003,52(6):1181-1885.
[13]KANATANI K,SUGAYA Y.Performance evaluation of iterative geometric fitting algorithms[J].Computational Statistics&Data Analysis,2007,52(2):1208-1222.
[14]ALSHARADQAH A,CHERNOV N.Error analysis for circle fitting algorithms[J].Electronic Journal of Statistics,2009,21(3):886-911.
[15]CHERNOV N,LESORT C.Statistical efficiency of curve fitting algorithms[J].Computational Statistics and Data Analysis,2004,47(4):713-728.