Levenberg–Marquardt algorithm

The Levenberg-Marquardt algorithm provides a numerical solution to the mathematical problem of minimizing a sum of squares of several, generally nonlinear functions that depend on a common set of parameters.

This minimization problem arises especially in least squares curve fitting (see also: nonlinear programming).

The Levenberg-Marquardt algorithm (LMA) interpolates between the Gauss-Newton algorithm (GNA) and the method of steepest descent. The LMA is robuster than the GNA, which means that in many cases it finds a solution even if it starts very far off the final minimum. On the other hand, for well-behaved functions and reasonable starting parameters, the LMA tends to be a bit slower than the GNA. The LMA is the most popular curve-fitting algorithm; it is used in almost any software that provides a generic curve-fitting tool; few users will ever need another curve-fitting algorithm.

The problem

Given is the problem: minimize the sum

${\displaystyle S({\vec {x}})=\sum _{i=1}^{m}[f_{i}({\vec {x}})]^{2}}$ 

where

${\displaystyle f_{i}({\vec {x}})}$ 

represent the components of the function

${\displaystyle {\vec {f}}}$ .

The solution

The LMA solves the minimization problem according to

${\displaystyle (J^{T}J+\lambda I){\vec {q}}=-J^{T}{\vec {f}}}$ .

Here ${\displaystyle J}$  represents the Jacobian of the function ${\displaystyle {\vec {f}}}$ , ${\displaystyle \lambda }$  the damping factor, which is altered at every iteration, ${\displaystyle I}$  the identity matrix, and ${\displaystyle {\vec {q}}}$  the solution to an iteration step.

Weblinks

history of the algorithm

Public ___domain implementations:

• minpack::lmdif in FORTRAN
• sourceforge::lmfit in C