Accelerating the modified Levenberg-Marquardt method for nonlinear equations

Fan, Jinyan

doi:10.1090/S0025-5718-2013-02752-4

Accelerating the modified Levenberg-Marquardt method for nonlinear equations
HTML articles powered by AMS MathViewer

by Jinyan Fan;

Math. Comp. 83 (2014), 1173-1187

DOI: https://doi.org/10.1090/S0025-5718-2013-02752-4

Published electronically: August 8, 2013

PDF | Request permission

Abstract:

In this paper we propose an accelerated version of the modified Levenberg-Marquardt method for nonlinear equations (see Jinyan Fan, Mathematics of Computation 81 (2012), no. 277, 447–466). The original version uses the addition of the LM step and the approximate LM step as the trial step at every iteration, and achieves the cubic convergence under the local error bound condition which is weaker than nonsingularity. The notable differences of the accelerated modified LM method from the modified LM method are that we introduce the line search for the approximate LM step and extend the LM parameter to more general cases. The convergence order of the new method is shown to be a continuous function with respect to the LM parameter. We compare it with both the LM method and the modified LM method; on the benchmark problems we observe competitive performance.

References

Roger Behling and Alfredo Iusem, The effect of calmness on the solution set of systems of nonlinear equations, Math. Program. 137 (2013), no. 1-2, Ser. A, 155–165. MR 3010423, DOI 10.1007/s10107-011-0486-7
Jinyan Fan and Jianyu Pan, Convergence properties of a self-adaptive Levenberg-Marquardt algorithm under local error bound condition, Comput. Optim. Appl. 34 (2006), no. 1, 47–62. MR 2224974, DOI 10.1007/s10589-005-3074-z
Jinyan Fan, The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence, Math. Comp. 81 (2012), no. 277, 447–466. MR 2833503, DOI 10.1090/S0025-5718-2011-02496-8
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
Andreas Fischer, Local behavior of an iterative framework for generalized equations with nonisolated solutions, Math. Program. 94 (2002), no. 1, Ser. A, 91–124. MR 1953167, DOI 10.1007/s10107-002-0364-4
Andreas Fischer and Pradyumn K. Shukla, A Levenberg-Marquardt algorithm for unconstrained multicriteria optimization, Oper. Res. Lett. 36 (2008), no. 5, 643–646. MR 2459519, DOI 10.1016/j.orl.2008.02.006
A. Fischer, P. K. Shukla, and M. Wang, On the inexactness level of robust Levenberg-Marquardt methods, Optimization 59 (2010), no. 2, 273–287. MR 2765461, DOI 10.1080/02331930801951256
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, DOI 10.1137/0111030
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, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numer. Algebra Control Optim. 1 (2011), no. 1, 15–34. MR 2806290, DOI 10.3934/naco.2011.1.15