Latest Version


4.12 (Build 81) Apr 18, 2014

download

Print

Levenberg - Marquardt

Levenberg-Marquardt [Levenberg44, Marquardt63] is a gradient descent method. It is a hybrid between the steepest descent and the Newton methods.

The Newton optimization method searches for the minimum of a nonlinear function by following descent directions determined from the function's first and second partial derivatives. The steepest descent method searches for a minimum based only on the first derivatives of the function. While the Newton method converges quadratically towards the minimum in its vicinity, it may not converge at all if it is far away from it. On the other hand the steepest descent method only converges linearly but is guaranteed to converge.

Levenberg first suggested an improvement to the Newton method in order to make it more robust, i.e. to overcome the problem of non-convergence. His suggestion was to add a factor to the diagonal elements of the Hessian matrix of second derivatives when not close to the minimum (this can be judged by how positive definite the matrix is). The effect when this factor is large compared to the elements of Hessian is that the method then becomes the steepest descent method. Later Marquardt suggested that the factor should be multiplicative rather than additive and also defined a heuristic to make this factor increase or decrease. The method known as Levenberg-Marquardt is thus an adaptive method that effectively changes between the steepest descent to the Newton method.

The original suggestions of Levenberg and Marquardt were effective to enhance the Gauss-Newton method, a variant of the Newton method specifically for minimizing least-squares functions. In this case the advantage is also that the second derivatives do not need to be calculated as they are estimated from the gradient of the residuals. Subsequently Goldfeld et al. [Goldfeld66] extended the method to the case of general non-linear functions.

Options for Levenberg - Marquardt

Iteration Limit
This parameter is positive integer determining the maximum number of iterations the algorithm shall perform. The default is '200'.

Tolerance
This parameter is a positive value determining the tolerance with which the solution shall be determined. If the improvement between two steps is less than the tolerance the algorithm stops. The default is '$10^{-5}$'.




Created by: system. Last Modification: Tuesday 17 of March, 2009 14:20:07 EDT by shoops.