Majorization-minimization-based Levenberg–Marquardt method for constrained nonlinear least squares
Authors:
Open Access
- 17 January 2023
- journal article
- research article
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 84 (3) , 833-874
Abstract
A new Levenberg–Marquardt (LM) method for solving nonlinear least squares problems with convex constraints is described. Various versions of the LM method have been proposed, their main differences being in the choice of a damping parameter. In this paper, we propose a new rule for updating the parameter so as to achieve both global and local convergence even under the presence of a convex constraint set. The key to our results is a new perspective of the LM method from majorization-minimization methods. Specifically, we show that if the damping parameter is set in a specific way, the objective function of the standard subproblem in LM methods becomes an upper bound on the original objective function under certain standard assumptions. Our method solves a sequence of the subproblems approximately using an (accelerated) projected gradient method. It finds an $$\varepsilon$$ -stationary point after $$O(\varepsilon ^{-2})$$ computation and achieves local quadratic convergence for zero-residual problems under a local error bound condition. Numerical results on compressed sensing and matrix factorization show that our method converges faster in many cases than existing methods.
Keywords
All Related Versions
Funding Information
- Japan Society for the Promotion of Science
- Exploratory Research for Advanced Technology
- University of Tokyo
This publication has 55 references indexed in Scilit:
- Iteration-complexity of first-order penalty methods for convex programmingMathematical Programming, 2012
- The modified Levenberg-Marquardt method for nonlinear equations with cubic convergenceMathematics of Computation, 2011
- On the convergence rate of the inexact Levenberg-Marquardt methodJournal of Industrial and Management Optimization, 2011
- Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexityMathematical Programming, 2010
- Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical resultsMathematical Programming, 2009
- An improved trust region algorithm for nonlinear equationsComputational Optimization and Applications, 2009
- Cubic regularization of Newton method and its global performanceMathematical Programming, 2006
- Convergence Rate of The Trust Region Method for Nonlinear Equations Under Local Error Bound ConditionComputational Optimization and Applications, 2006
- On the Quadratic Convergence of the Levenberg-Marquardt Method without Nonsingularity AssumptionComputing, 2005
- An Automatic Method for Finding the Greatest or Least Value of a FunctionThe Computer Journal, 1960