The Levenberg–Marquardt method: an overview of modern convergence theories and more
Pages 33 - 67
Abstract
The Levenberg–Marquardt method is a fundamental regularization technique for the Newton method applied to nonlinear equations, possibly constrained, and possibly with singular or even nonisolated solutions. We review the literature on the subject, in particular relating to each other various convergence frameworks and results. In this process, the analysis is performed from a unified perspective, and some new results are obtained as well. We discuss smooth and piecewise smooth equations, inexact solution of subproblems, and globalization techniques. Attention is also paid to the LP-Newton method, because of its relations to the Levenberg–Marquardt method.
References
[1]
Ahookhosh M, Fleming RMT, and Vuong PT Finding zeros of Hölder metrically subregular mappings via globally convergent Levenberg-Marquardt methods Optim. Methods Softw. 2022 37 113-149
[2]
Amini K, Rostami F, and Caristi F An efficient Levenberg-Marquardt method with a new LM parameter for systems of nonlinear equations Optimization 2018 67 637-650
[3]
Ariizumi S, Yamakawa Y, and Yamashita N Convergence properties of Levenberg-Marquardt methods with generalized regularization terms Appl. Math. Comput. 2024 463 128365
[4]
Bao J, Yu CKW, Wang J, Hu Y, and Yao J-C Modified inexact Levenberg-Marquardt methods for solving nonlinear least squares problems Comput. Optim. Appl. 2019 74 547-582
[5]
Becher L, Fernández D, and Ramos A A trust-region LP-Newton method for constrained nonsmooth equations under Hölder metric subregularity Comput. Optim. Appl. 2023 86 711-743
[6]
Behling, R.: The method and the trajectory of Levenberg–Marquardt. PhD thesis. IMPA - Instituto Nacional de Matemática Pura e Aplicada, Rio de Janeiro, Brazil (2011). https://impa.br/wp-content/uploads/2017/08/tese_dout_roger_behling.pdf
[7]
Behling R and Iusem A The effect of calmness on the solution set of systems of nonlinear equations Math. Program. 2013 137 155-165
[8]
Behling R and Fischer A A unified local convergence analysis of inexact constrained Levenberg-Marquardt methods Optim. Lett. 2012 6 927-940
[9]
Behling R, Fischer A, Haeser G, Ramos A, and Schönefeld K On the constrained error bound condition and the projected Levenberg-Marquardt method Optimization 2017 66 1397-1411
[10]
Behling R, Fischer A, Herrich M, Iusem A, and Ye Y A Levenberg-Marquardt method with approximate projections Comput. Optim. Appl. 2014 59 5-26
[11]
Behling R, Fischer A, Schönefeld K, and Strasdat N A special complementarity function revisited Optimization 2019 68 65-79
[12]
Behling R, Gonçalves DS, and Santos SA Local convergence analysis of the Levenberg-Marquardt framework for nonzero-residue nonlinear least-squares problems under an error bound condition J. Optim. Theory Appl. 2019 183 1099-1122
[13]
Bergou EH, Diouane Y, and Kungurtsev V Convergence and complexity analysis of a Levenberg-Marquardt algorithm for inverse problems J. Optim. Theory Appl. 2020 185 927-944
[14]
Bergou EH, Diouane Y, Kungurtsev V, and Royer CW A nonmonotone matrix-free algorithm for nonlinear equality-constrained least-squares problems SIAM J. Sci. Comput. 2021 43 S743-S766
[15]
Bertsekas DP Nonlinear Programming 1999 2 Belmont Athena
[16]
Bonnans JF, Gilbert JC, Lemaréchal C, and Sagastizábal CA Numerical Optimization: Theoretical and Practical Aspects 2006 Berlin Springer-Verlag
[17]
Dan H, Yamashita N, and Fukushima M Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions Optim. Methods Softw. 2002 17 605-626
[19]
Dennis JE and Schnabel RB Numerical Methods for Unconstrained Optimization and Nonlinear Equations 1983 Englewood Cliffs Prentice-Hall Inc
[20]
Dreves A, Facchinei F, Fischer A, and Herrich M A new error bound result for Generalized Nash Equilibrium Problems and its algorithmic application Comput. Optim. Appl. 2014 59 63-84
[21]
Dreves A, Facchinei F, Kanzow C, and Sagratella S On the solution of the KKT conditions of generalized Nash equilibrium problems SIAM J. Optim. 2011 21 1082-1108
[22]
Facchinei F, Fischer A, and Herrich M A family of Newton methods for nonsmooth constrained systems with nonisolated solutions Math. Methods Oper. Res. 2013 77 433-443
[23]
Facchinei F, Fischer A, and Herrich M An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions Math. Program. 2014 146 1-36
[24]
Facchinei F, Fischer A, and Piccialli V Generalized Nash equilibrium problems and Newton methods Math. Program. 2009 117 163-194
[25]
Facchinei F and Kanzow C A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems Math. Program. 1997 76 493-512
[26]
Fan J-Y A modified Levenberg-Marquardt algorithm for singular systems of nonlinear equations J. Comput. Math. 2003 21 625-636
[27]
Fan J-Y On the Levenberg-Marquardt methods for convex constrained nonlinear equations J. Ind. Manag. Optim. 2013 9 227-241
[28]
Fan J-Y and Pan J-Y Inexact Levenberg-Marquardt method for nonlinear equations Discrete Contin. Dyn. Syst. Ser. B. 2004 4 1223-1232
[29]
Fan J-Y and Pan J-Y Convergence properties of a self-adaptive Levenberg-Marquardt algorithm under local error bound condition Comput. Optim. Appl. 2006 34 47-62
[30]
Fan J-Y and Pan J-Y On the convergence rate of the inexact Levenberg-Marquardt method J. Ind. Manag. Optim. 2011 7 199-210
[31]
Fan J-Y and Yuan Y-X On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption Computing 2005 74 23-39
[32]
Fischer A Local behavior of an iterative framework for generalized equations with nonisolated solutions Math. Program. 2002 94 91-124
[33]
Fischer A, Herrich M, Izmailov AF, and Solodov MV A globally convergent LP-Newton method SIAM J. Optim. 2016 26 2012-2033
[34]
Fischer A, Herrich M, Izmailov AF, and Solodov MV Convergence conditions for Newton-type methods applied to complementarity systems with nonisolated solutions Comput. Optim. Appl. 2016 63 425-459
[35]
Fischer A, Herrich M, Izmailov AF, Scheck W, and Solodov MV A globally convergent LP-Newton method for piecewise smooth constrained equations: escaping nonstationary accumulation points Comput. Optim. Appl. 2018 69 325-349
[36]
Fischer A and Shukla PK A Levenberg-Marquardt algorithm for unconstrained multicriteria optimization Oper. Res. Lett. 2008 36 643-646
[37]
Fischer A, Shukla PK, and Wang M On the inexactness level of robust Levenberg-Marquardt methods Optimization 2010 59 273-287
[38]
Fischer A and Strasdat N An extended convergence framework applied to complementarity systems with degenerate and nonisolated solutions Pure Appl. Funct. Anal. 2023 8 1039-1054
[39]
Frank M and Wolfe P An algorithm for quadratic programming Naval Res. Logist. 1956 3 95-110
[40]
Golubitsky M and Schaeffer DG Singularities and Groups in Bifurcation Theory 1985 New York Springer-Verlag
[41]
Griewank A Starlike domains of convergence for Newton’s method at singularities Numer. Math. 1980 35 95-111
[42]
Hager WW Lipschitz continuity for constrained processes SIAM J. Control Optim. 1979 17 321-338
[43]
Izmailov AF, Kurennoy AS, and Solodov MV Critical solutions of nonlinear equations: local attraction for Newton-type methods Math. Program. 2018 167 355-379
[44]
Izmailov AF, Kurennoy AS, and Solodov MV Critical solutions of nonlinear equations: stability issues Math. Program. 2018 168 475-507
[45]
Izmailov AF and Solodov MV Newton-Type Methods for Optimization and Variational Problems. Springer Series in Operations Research and Financial Engineering 2014 Cham Springer
[46]
Izmailov AF, Solodov MV, and Uskov EI A globally convergent Levenberg-Marquardt method for equality-constrained optimization Comput. Optim. Appl. 2019 72 215-239
[47]
Jolaoso LO, Mehlitz P, and Zemkoho AB A fresh look at nonsmooth Levenberg-Marquardt methods with applications to bilevel optimization Optimization 2024
[48]
Kanzow C and Petra S On a semismooth least squares formulation of complementarity problems with gap reduction Optim. Methods Softw. 2004 19 507-525
[49]
Kanzow C and Petra S Projected filter trust region methods for a semismooth least squares formulation of mixed complementarity problems Optim. Methods Softw. 2007 22 713-735
[50]
Kanzow C, Yamashita N, and Fukushima M Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints J. Comput. Appl. Math. 2004 172 375-397
[51]
Karas EW, Santos SA, and Svaiter BF Algebraic rules for computing the regularization parameter of the Levenberg-Marquardt method Comput. Optim. Appl. 2016 65 723-751
[52]
Levenberg K A method for the solution of certain non-linear problems in least squares Quart. Appl. Math. 1944 2 164-168
[53]
Macconi M, Morini B, and Porcelli M Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities Appl. Numer. Math. 2009 59 859-876
[54]
Martínez MA and Fernández D A quasi-Newton modified LP-Newton method Optim. Methods Softw. 2019 34 634-649
[55]
Martínez MA and Fernández D On the local and superlinear convergence of a secant modified linear-programming-Newton method J. Optim. Theory Appl. 2019 180 993-1010
[56]
Marquardt DW An algorithm for least-squares estimation of nonlinear parameters SIAM J. 1963 11 431-441
[57]
Marumo N, Okuno T, and Takeda A Majorization-minimization-based Levenberg-Marquardt method for constrained nonlinear least squares Comput. Optim. Appl. 2023 84 833-874
[58]
Monteiro RDC and Pang J-S A potential reduction Newton method for constrained equations SIAM J. Optim. 1999 9 729-754
[59]
Nocedal J and Wright SJ Numerical Optimization 2006 2 New York Springer-Verlag
[60]
de Oliveira FR and de Oliveira FR A locally convergent inexact projected Levenberg-Marquardt-type algorithm for large-scale constrained nonsmooth equations J. Comput. Appl. Math. 2023 427 115-121
[61]
Riccietti, E.: Levenberg–Marquardt methods for the solution of noisy nonlinear least squares problems. Ph.D. thesis. University of Florence, Italy (2017)
[62]
Tin A and Zemkoho AB Levenberg-Marquardt method and partial exact penalty parameter selection in bilevel optimization Optim. Eng. 2023 24 1343-1385
[63]
Yamashita N and Fukushima M Alefeld G and Chen X On the rate of convergence of the Levenberg-Marquardt method Topics in Numerical Analysis. Computing Supplementa 2001 Vienna Springer
[64]
Yin J, Jian J, and Ma G A modified inexact Levenberg-Marquardt method with the descent property for solving nonlinear equations Comput. Optim. Appl. 2024 87 289-322
[65]
Zhang J-L On the convergence properties of the Levenberg-Marquardt method Optimization 2003 52 739-756
Index Terms
- The Levenberg–Marquardt method: an overview of modern convergence theories and more
Index terms have been assigned to the content through auto-classification.
Recommendations
Local Attractors of Newton-Type Methods for Constrained Equations and Complementarity Problems with Nonisolated Solutions
AbstractFor constrained equations with nonisolated solutions, we show that if the equation mapping is 2-regular at a given solution with respect to a direction in the null space of the Jacobian, and this direction is interior feasible, then there is an ...
A globally convergent LP-Newton method for piecewise smooth constrained equations: escaping nonstationary accumulation points
The LP-Newton method for constrained equations, introduced some years ago, has powerful properties of local superlinear convergence, covering both possibly nonisolated solutions and possibly nonsmooth equation mappings. A related globally convergent ...
Quadratic convergence analysis of a nonmonotone Levenberg–Marquardt type method for the weighted nonlinear complementarity problem
AbstractIn this paper we consider the weighted nonlinear complementarity problem (denoted by wNCP) which contains a wide class of optimization problems. We introduce a family of new weighted complementarity functions and show that it is continuously ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 11 June 2024
Accepted: 31 May 2024
Received: 27 November 2023
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
- Volkswagen Foundation
- Russian Science Foundation
- CNPq
- FAPERJ
- PRONEX-Optimization
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Dec 2024