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 are m functions f₁, ..., f_m of n parameters p₁, ..., p_n with m≥n. It is convenient to use vector notation for both the functions and the parameters,

f^T=(f₁, ..., f_m), and p^T=(p₁, ..., p_n).

The least squares problem consists in finding the parameter vector p for which the cost function

S(p) = f^Tf=${\displaystyle \sum _{i=1}^{m}}$  [f_i(p)]²

becomes minimal.

The main application is in the least squares curve fitting problem: given a set of empirical data pairs (t_i,y_i), optimize the parameters p of the model curve c(t|p) so that the sum of the squares of the deviations

f_i(p)=y_i - c(t_i|p)

becomes minimal.

(A word on notation: we avoid the letter x because it is used sometimes in the place of our p, sometimes in the place of our t).

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