The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence

Fan, Jinyan

doi:10.1090/S0025-5718-2011-02496-8

The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence
HTML articles powered by AMS MathViewer

by Jinyan Fan;

Math. Comp. 81 (2012), 447-466

DOI: https://doi.org/10.1090/S0025-5718-2011-02496-8

Published electronically: June 23, 2011

PDF | Request permission

Abstract:

We propose a modified Levenberg-Marquardt method for nonlinear equations, in which not only a LM step but also an approximate LM step are computed at every iteration. To ensure the global convergence of the new method, a new kind of predicted reduction is introduced for the merit function when using the trust region technique. The cubic convergence of the modified LM method is proved under the local error bound condition which is weaker than nonsingularity. Numerical results show that the new method is very efficient and could save many calculations of the Jacobian.

References

Jin-yan Fan, A modified Levenberg-Marquardt algorithm for singular system of nonlinear equations, J. Comput. Math. 21 (2003), no. 5, 625–636. MR 1999973
Jinyan Fan and Jianyu Pan, A note on the Levenberg-Marquardt parameter, Appl. Math. Comput. 207 (2009), no. 2, 351–359. MR 2489105, DOI 10.1016/j.amc.2008.10.056
Jin-yan Fan and Ya-xiang Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing 74 (2005), no. 1, 23–39. MR 2127319, DOI 10.1007/s00607-004-0083-1
C. T. Kelley, Iterative methods for optimization, Frontiers in Applied Mathematics, vol. 18, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. MR 1678201, DOI 10.1137/1.9781611970920
Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 10666, DOI 10.1090/S0033-569X-1944-10666-0
Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 153071
Jorge J. Moré, The Levenberg-Marquardt algorithm: implementation and theory, Numerical analysis (Proc. 7th Biennial Conf., Univ. Dundee, Dundee, 1977) Lecture Notes in Math., Vol. 630, Springer, Berlin-New York, 1978, pp. 105–116. MR 483445
J. J. Moré, Recent developments in algorithms and software for trust region methods, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 258–287. MR 717404
Jorge J. Moré, Burton S. Garbow, and Kenneth E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software 7 (1981), no. 1, 17–41. MR 607350, DOI 10.1145/355934.355936
M. J. D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear programming, 2 (Proc. Special Interest Group on Math. Programming Sympos., Univ. Wisconsin, Madison, Wis., 1974) Academic Press, New York-London, 1975, pp. 1–27. MR 386270
Robert B. Schnabel and Paul D. Frank, Tensor methods for nonlinear equations, SIAM J. Numer. Anal. 21 (1984), no. 5, 815–843. MR 760620, DOI 10.1137/0721054
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
Wenyu Sun and Ya-Xiang Yuan, Optimization theory and methods, Springer Optimization and Its Applications, vol. 1, Springer, New York, 2006. Nonlinear programming. MR 2232297
N. Yamashita and M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method, Topics in numerical analysis, Comput. Suppl., vol. 15, Springer, Vienna, 2001, pp. 239–249. MR 1874516, DOI 10.1007/978-3-7091-6217-0_{1}8
Ya-xiang Yuan, Trust region algorithms for nonlinear equations, Information 1 (1998), no. 1, 7–20. MR 1645695
Ya-xiang Yuan, A review of trust region algorithms for optimization, ICIAM 99 (Edinburgh), Oxford Univ. Press, Oxford, 2000, pp. 271–282. MR 1824450