Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Accelerating the modified Levenberg-Marquardt method for nonlinear equations


Author: Jinyan Fan
Journal: Math. Comp. 83 (2014), 1173-1187
MSC (2010): Primary 65K05, 90C30
DOI: https://doi.org/10.1090/S0025-5718-2013-02752-4
Published electronically: August 8, 2013
MathSciNet review: 3167454
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, DOI: 10.1007/s10107-011-0486-7. MR 3010423
  • [2] 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 (2007d:65054), https://doi.org/10.1007/s10589-005-3074-z
  • [3] Jinyan Fan, The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence, Math. Comp. 81 (2012), no. 277, 447-466. MR 2833503 (2012e:65091), https://doi.org/10.1090/S0025-5718-2011-02496-8
  • [4] 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 (2006a:65079), https://doi.org/10.1007/s00607-004-0083-1
  • [5] 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 (2004b:90116), https://doi.org/10.1007/s10107-002-0364-4
  • [6] 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 (2009i:90119), https://doi.org/10.1016/j.orl.2008.02.006
  • [7] 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 (2011k:65074), https://doi.org/10.1080/02331930801951256
  • [8] 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 (2000h:90003)
  • [9] Kenneth Levenberg, A method for the solution of certain nonlinear problems in least squares, Quart. Appl. Math. 2 (1944), 164-168. MR 0010666 (6,52a)
  • [10] Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431-441. MR 0153071 (27 #3040)
  • [11] Jorge J. Moré, The Levenberg-Marquardt algorithm: implementation and theory, Numerical analysis (Proc. 7th Biennial Conf., Univ. Dundee, Dundee, 1977), Springer, Berlin, 1978, pp. 105-116. Lecture Notes in Math., Vol. 630. MR 0483445 (58 #3446)
  • [12] 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 (85b:90066)
  • [13] 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 (83b:90144), https://doi.org/10.1145/355934.355936
  • [14] M. J. D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear programming, 2 (Proc. Sympos. Special Interest Group on Math. Programming, Univ. Wisconsin, Madison, Wis., 1974), Academic Press, New York, 1974, pp. 1-27. MR 0386270 (52 #7128)
  • [15] Robert B. Schnabel and Paul D. Frank, Tensor methods for nonlinear equations, SIAM J. Numer. Anal. 21 (1984), no. 5, 815-843. MR 760620 (86d:65066), https://doi.org/10.1137/0721054
  • [16] G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press Inc., Boston, MA, 1990. MR 1061154 (92a:65017)
  • [17] Wenyu Sun and Ya-Xiang Yuan, Optimization theory and methods: Nonlinear programming, Springer Optimization and Its Applications, vol. 1, Springer, New York, 2006. MR 2232297 (2007c:90002)
  • [18] 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 (2002k:65088), https://doi.org/10.1007/978-3-7091-6217-0_18
  • [19] Ya-xiang Yuan, Trust region algorithms for nonlinear equations, Information 1 (1998), no. 1, 7-20. MR 1645695 (2000d:65090)
  • [20] 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 (2012e:65112), https://doi.org/10.3934/naco.2011.1.15

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65K05, 90C30

Retrieve articles in all journals with MSC (2010): 65K05, 90C30


Additional Information

Jinyan Fan
Affiliation: Department of Mathematics, and MOE-LSC, Shanghai Jiao Tong University, Shanghai 200240, People’s Republic of China
Email: jyfan@sjtu.edu.cn

DOI: https://doi.org/10.1090/S0025-5718-2013-02752-4
Keywords: Nonlinear equations, Levenberg-Marquardt method, local error bound
Received by editor(s): February 6, 2012
Received by editor(s) in revised form: August 8, 2012
Published electronically: August 8, 2013
Additional Notes: The author was supported by Chinese NSF grants 10871127 and 11171217
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society