doi: 10.3934/jimo.2020068

Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound

1. 

School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai 200240, China

2. 

School of Mathematical Sciences, Shanghai Jiao Tong University, Key Lab of Scientific and Engineering Computing (Ministry of Education), Shanghai 200240, China

* Corresponding author: Jinyan Fan

Received  August 2019 Revised  November 2019 Published  March 2020

Fund Project: The authors are supported by Chinese NSF grants 11971309

In this paper, we study convergence properties of the inexact Levenberg-Marquardt method under the Hölderian local error bound condition and the Hölderian continuity of the Jacobian. The formula of the convergence rates are given, which are functions with respect to the Levenberg-Marquardt parameter, the perturbation vector, as well as the orders of the Hölderian local error bound and Hölderian continuity of the Jacobian.

Citation: Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020068
References:
[1]

M. Ahookhosh, F. J. Aragón, R. M. T. Fleming and P. T. Vuong, Local convergence of Levenberg-Marquardt methods under Hölderian metric subregularity, Adv. Comput. Math., 45 (2019), 2771–2806, arXiv: 1703.07461. doi: 10.1007/s10444-019-09708-7.  Google Scholar

[2]

H. DanN. Yamashita and M. Fukushima, Convergence properties of the inexact Levenberg-Marquardt method under local error bound, Optimization Methods and Software, 17 (2002), 605-626.  doi: 10.1080/1055678021000049345.  Google Scholar

[3]

F. Facchinei and C. Kanzow, A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems, Mathematical Programming, 76 (1997), 493-512.  doi: 10.1007/BF02614395.  Google Scholar

[4]

J. Y. Fan, A modified Levenberg-Marquardt algorithm for singular system of nonlinear equations, Journal of Computational Mathematics, 21 (2003), 625-636.   Google Scholar

[5]

J. Y. Fan, The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence, Mathematics of Computation, 81 (2012), 447-466.  doi: 10.1090/S0025-5718-2011-02496-8.  Google Scholar

[6]

J. Y. FanJ. C. Huang and J. Y. Pan, An adaptive multi-step Levenberg-Marquardt method, Journal of Scientific Computing, 78 (2019), 531-548.  doi: 10.1007/s10915-018-0777-8.  Google Scholar

[7]

J. Y. Fan and J. Y. Pan, Inexact Levenberg-Marquardt method for nonlinear equations, Discrete Continuous Dynamical System-Series B, 4 (2004), 1223-1232.  doi: 10.3934/dcdsb.2004.4.1223.  Google Scholar

[8]

J. Y. Fan and J. Y. Pan, A note on the Levenberg-Marquardt parameter, Applied Mathematics and Computation, 207 (2009), 351-359.  doi: 10.1016/j.amc.2008.10.056.  Google Scholar

[9]

J. Y. Fan and J. Y. Pan, On the convergence rate of the inexact Levenberg-Marquardt method, Industrial and Management Optimization, 7 (2011), 199-210.  doi: 10.3934/jimo.2011.7.199.  Google Scholar

[10]

J. Y. Fan and Y. X. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74 (2005), 23-39.  doi: 10.1007/s00607-004-0083-1.  Google Scholar

[11]

A. FischeraP. K. Shuklaa and M. Wang, On the inexactness level of robust Levenberg-Marquardt methods, Optimization, 59 (2010), 273-287.  doi: 10.1080/02331930801951256.  Google Scholar

[12]

C. T. Kelley, Solving Nonlinear Equations with Newton's Method, Fundamentals of Algorithms, SIAM, Philadelphia, 2003. doi: 10.1137/1.9780898718898.  Google Scholar

[13]

K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quart. Appl. Math., 2 (1944), 164-168.  doi: 10.1090/qam/10666.  Google Scholar

[14]

D. W. Marquardt, An algorithm for least-squares estimation of nonlinear inequalities, SIAM J. Appl. Math., 11 (1963), 431-441.  doi: 10.1137/0111030.  Google Scholar

[15]

J. J. Moré, The Levenberg-Marquardt algorithm: implementation and theory, In: G. A. Watson, ed., Lecture Notes in Mathematics 630: Numerical Analysis, Springer-Verlag, Berlin, 1978, 105–116.  Google Scholar

[16]

M. J. D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear Programming, 2 (1974), 1-27.   Google Scholar

[17]

G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory, (Computer Science and Scientific Computing), Academic Press Boston, 1990.  Google Scholar

[18]

H. Y. Wang and J. Y. Fan, Convergence rate of the Levenberg-Marquardt method under hölderian local error bound, Optimization Methods and Software, 2019. doi: 10.1080/10556788.2019.1694927.  Google Scholar

[19]

N. Yamashita and M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method, Computing, (15) (2001), 239-249.  doi: 10.1007/978-3-7091-6217-0_18.  Google Scholar

[20]

Y. X. Yuan, Recent advances in trust region algorithms, Math. Program., Ser. B, 151 (2015), 249–281. doi: 10.1007/s10107-015-0893-2.  Google Scholar

[21]

X. D. Zhu and G. H. Lin, Improved convergence results for a modified Levenberg-Marquardt method for nonlinear equations and applications in MPCC, Optimization Methods and Software, 31 (2016), 791-804.  doi: 10.1080/10556788.2016.1171863.  Google Scholar

show all references

References:
[1]

M. Ahookhosh, F. J. Aragón, R. M. T. Fleming and P. T. Vuong, Local convergence of Levenberg-Marquardt methods under Hölderian metric subregularity, Adv. Comput. Math., 45 (2019), 2771–2806, arXiv: 1703.07461. doi: 10.1007/s10444-019-09708-7.  Google Scholar

[2]

H. DanN. Yamashita and M. Fukushima, Convergence properties of the inexact Levenberg-Marquardt method under local error bound, Optimization Methods and Software, 17 (2002), 605-626.  doi: 10.1080/1055678021000049345.  Google Scholar

[3]

F. Facchinei and C. Kanzow, A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems, Mathematical Programming, 76 (1997), 493-512.  doi: 10.1007/BF02614395.  Google Scholar

[4]

J. Y. Fan, A modified Levenberg-Marquardt algorithm for singular system of nonlinear equations, Journal of Computational Mathematics, 21 (2003), 625-636.   Google Scholar

[5]

J. Y. Fan, The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence, Mathematics of Computation, 81 (2012), 447-466.  doi: 10.1090/S0025-5718-2011-02496-8.  Google Scholar

[6]

J. Y. FanJ. C. Huang and J. Y. Pan, An adaptive multi-step Levenberg-Marquardt method, Journal of Scientific Computing, 78 (2019), 531-548.  doi: 10.1007/s10915-018-0777-8.  Google Scholar

[7]

J. Y. Fan and J. Y. Pan, Inexact Levenberg-Marquardt method for nonlinear equations, Discrete Continuous Dynamical System-Series B, 4 (2004), 1223-1232.  doi: 10.3934/dcdsb.2004.4.1223.  Google Scholar

[8]

J. Y. Fan and J. Y. Pan, A note on the Levenberg-Marquardt parameter, Applied Mathematics and Computation, 207 (2009), 351-359.  doi: 10.1016/j.amc.2008.10.056.  Google Scholar

[9]

J. Y. Fan and J. Y. Pan, On the convergence rate of the inexact Levenberg-Marquardt method, Industrial and Management Optimization, 7 (2011), 199-210.  doi: 10.3934/jimo.2011.7.199.  Google Scholar

[10]

J. Y. Fan and Y. X. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74 (2005), 23-39.  doi: 10.1007/s00607-004-0083-1.  Google Scholar

[11]

A. FischeraP. K. Shuklaa and M. Wang, On the inexactness level of robust Levenberg-Marquardt methods, Optimization, 59 (2010), 273-287.  doi: 10.1080/02331930801951256.  Google Scholar

[12]

C. T. Kelley, Solving Nonlinear Equations with Newton's Method, Fundamentals of Algorithms, SIAM, Philadelphia, 2003. doi: 10.1137/1.9780898718898.  Google Scholar

[13]

K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quart. Appl. Math., 2 (1944), 164-168.  doi: 10.1090/qam/10666.  Google Scholar

[14]

D. W. Marquardt, An algorithm for least-squares estimation of nonlinear inequalities, SIAM J. Appl. Math., 11 (1963), 431-441.  doi: 10.1137/0111030.  Google Scholar

[15]

J. J. Moré, The Levenberg-Marquardt algorithm: implementation and theory, In: G. A. Watson, ed., Lecture Notes in Mathematics 630: Numerical Analysis, Springer-Verlag, Berlin, 1978, 105–116.  Google Scholar

[16]

M. J. D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear Programming, 2 (1974), 1-27.   Google Scholar

[17]

G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory, (Computer Science and Scientific Computing), Academic Press Boston, 1990.  Google Scholar

[18]

H. Y. Wang and J. Y. Fan, Convergence rate of the Levenberg-Marquardt method under hölderian local error bound, Optimization Methods and Software, 2019. doi: 10.1080/10556788.2019.1694927.  Google Scholar

[19]

N. Yamashita and M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method, Computing, (15) (2001), 239-249.  doi: 10.1007/978-3-7091-6217-0_18.  Google Scholar

[20]

Y. X. Yuan, Recent advances in trust region algorithms, Math. Program., Ser. B, 151 (2015), 249–281. doi: 10.1007/s10107-015-0893-2.  Google Scholar

[21]

X. D. Zhu and G. H. Lin, Improved convergence results for a modified Levenberg-Marquardt method for nonlinear equations and applications in MPCC, Optimization Methods and Software, 31 (2016), 791-804.  doi: 10.1080/10556788.2016.1171863.  Google Scholar

[1]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[2]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210

[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[4]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[5]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

[6]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[7]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[8]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[9]

Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294

[10]

Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190

[11]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034

[12]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[13]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053

[14]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[15]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[16]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[17]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267

[18]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933

[19]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206

[20]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (73)
  • HTML views (391)
  • Cited by (0)

Other articles
by authors

[Back to Top]