Levenberg-Marquardt algorithm

The Levenberg-Marquardt algorithm , named after Kenneth Levenberg and Donald Marquardt , is a numerical optimization algorithm for solving nonlinear compensation problems using the least squares method . The method combines the Gauss-Newton method with a regularization technique that enforces descending function values.

The Levenberg-Marquardt algorithm is significantly more robust than the Gauss-Newton method, that is, it converges with a high probability even under poor starting conditions, but convergence is not guaranteed here either. Furthermore, it is often somewhat slower at initial values ​​that are close to the minimum.

description

For the nonlinear function , the least squares minimization problem (with a smaller number of independent variables compared to the number of function components) ${\displaystyle F:\mathbb {R} ^{m}\to \mathbb {R} ^{n},\;m<n,}$

${\displaystyle \min _{x\in \mathbb {R} ^{m}}\|F(x)\|_{2}^{2}}$

based on a starting approach . ${\displaystyle x_{0}}$

As with the Gauss-Newton method, F (x) is replaced by a linearization in each step and the replacement problem:

${\displaystyle \min _{x\in \mathbb {R} ^{m}}\|F(x_{k})+J(x_{k})(x-x_{k})\|_{2}^{2}}$

considered. Here J is the Jacobi matrix of the function F.

In addition, the Levenberg-Marquardt algorithm demands that . With this additional condition you can force a reduction of in each step. To do this, the parameter is adjusted accordingly. ${\displaystyle \|x-x_{k}\|_{2}^{2}<r_{k}}$ ${\displaystyle \|F(x_{k})\|_{2}^{2}}$ ${\displaystyle r_{k}}$

convergence

The Levenberg-Marquardt method changes locally into the Gauss-Newton method . The convergence is locally linear and, close to the optimum, even quadratic.

literature

• K. Levenberg: A Method for the Solution of Certain Problems in Least Squares , Quart. Appl. Math. 2, 164-168, 1944.
• D. Marquardt: An Algorithm for Least-Squares Estimation of Nonlinear Parameters , SIAM J. Appl. Math. 11, 431-441, 1963.
• Jorge J. Moré: The Levenberg-Marquardt algorithm: Implementation and theory. In GA Watson (ed.): Numerical Analysis. Dundee 1977 , Lecture Notes Math. 630, 1978, pp. 105-116
• P. Gill, W. Murray and M. Wright: Practical Optimization , Academic Press 1981
• JE Dennis, Jr., and RB Schnabel: Numerical methods for unconstrained optimization and nonlinear equations. Prentice-Hall Series in Computational Mathematics, Englewood Cliffs 1983

Web links

Freely available implementations of the Levenberg-Marquardt algorithm :

• gnuplot , free graphics program
• lmdif , in Fortran , classic implementation from Netlib / Minpack . License: Public Domain
  • lmfit , self-contained C library based on Netlib :: Minpack :: lmfid , for general minimization and for curve fitting using the least squares method. FreeBSD license
• levmar , in C / C ++ , with interfaces for Matlab , Perl and Python . License: GPL
• mpfit , implementation in IDL
• csmpfit , C # port of mpfit