In mathematics and computing, the Levenberg–Marquardt algorithm (LMA or just LM), also known as the damped least-squares (DLS) method, is used to solve non-linear least squares problems. These minimization problems arise especially in least squares curve fitting. The LMA interpolates between the Gauss–Newton algorithm (GNA) and the method of gradient descent. The LMA is more robust than the GNA, which means that in many cases it finds a solution even if it starts very far off the final minimum. For well-behaved functions and reasonable starting parameters, the LMA tends to be slower than the GNA. LMA can also be viewed as Gauss–Newton using a trust region approach. The algorithm was first published in 1944 by Kenneth Levenberg, while working at the Frankford Army Arsenal. It was rediscovered in 1963 by Donald Marquardt, who worked as a statistician at DuPont, and independently by Girard, Wynne and Morrison. The LMA is used in many software applications for solving generic curve-fitting problems. By using the Gauss–Newton algorithm it often converges faster than first-order methods. However, like other iterative optimization algorithms, the LMA finds only a local minimum, which is not necessarily the global minimum.
The problem The primary application of the Levenberg–Marquardt algorithm is in the least-squares curve fitting problem: given a set of m {\displaystyle m} empirical pairs ( x i , y i ) {\displaystyle \left(x_{i},y_{i}\right)} of independent and dependent variables, find the parameters β {\displaystyle {\boldsymbol {\beta }}} of the model curve f ( x , β ) {\displaystyle f{\left(x,{\boldsymbol {\beta }}\right)}} so that the sum of the squares of the deviations S ( β ) {\displaystyle S{\left({\boldsymbol {\beta }}\right)}} is minimized:
β ^ ∈ argmin β S ( β ) ≡ argmin β ∑ i = 1 m [ y i − f ( x i , β ) ] 2 , {\displaystyle {\hat {\boldsymbol {\beta }}}\in \mathop {\operatorname {argmin} } _{\boldsymbol {\beta }}S{\left({\boldsymbol {\beta }}\right)}\equiv \mathop {\operatorname {argmin} } _{\boldsymbol {\beta }}\sum _{i=1}^{m}\left[y_{i}-f{\left(x_{i},{\boldsymbol {\beta }}\right)}\right]^{2},} which is assumed to be non-empty.
The solution Like other numeric minimization algorithms, the Levenberg–Marquardt algorithm is an iterative procedure. To start a minimization, the user has to provide an initial guess for the parameter vector β {\displaystyle {\boldsymbol {\beta }}} . In cases with only one minimum, an uninformed standard guess like β T = ( 1 , 1 , … , 1 ) {\displaystyle {\boldsymbol {\beta }}^{\text{T}}={\begin{pmatrix}1,\ 1,\ \dots ,\ 1\end{pmatrix}}} will work fine; in cases with multiple minima, the algorithm converges to the global minimum only if the initial guess is already somewhat close to the final solution. In each iteration step, the parameter vector β {\displaystyle {\boldsymbol {\beta }}} is replaced by a new estimate β + δ {\displaystyle {\boldsymbol {\beta }}+{\boldsymbol {\delta }}} . To determine δ {\displaystyle {\boldsymbol {\delta }}} , the function f ( x i , β + δ ) {\displaystyle f{\left(x_{i},{\boldsymbol {\beta }}+{\boldsymbol {\delta }}\right)}} is approximated by its linearization:
… excerpt ends here. Continue reading the full article.
