2.1.1 Algorithm Description



next up previous contents index
Next: 2.1.2 Calculation of the Up: 2.1 Nonlinear Least Squares Previous: 2.1 Nonlinear Least Squares

2.1.1 Algorithm Description

A Taylor series expansion of (2.7) around a nominal point in can be written as:

 

where

is the gradient of the objective function, and H is an matrix of second derivatives called the Hessian matrix whose elements are   given by:

An intuitive iterative solution scheme consists of taking a step in the negative gradient direction:

When the size of the step () is chosen appropriately, a monotonic decrease in the objective function is ensured. At each iteration, the size of the step can be determined via a line search along the negative gradient direction using a one-dimensional optimization technique (e.g. Brent's parabolic [84]). The new values of the parameters are then calculated as:

 

This procedure is called steepest descent. It is a reliable and inherently stable method that will always lead to a minimum of F. Its disadvantage is that the step often has to be so small that it results in a very slow convergence especially as the minimum is approached.

An alternative solution technique is the Gauß -Newton method which is based on the premise that a quadratic approximation is an accurate representation of F at . In this case, the terms in (2.10) are dropped, and the necessary condition for the minimum of F, namely that the gradient must be zero, can be written as:

which yields the following equation for :

In the case of the least-squares objective F, the elements of the gradient and the Hessian matrix can be expressed as:

 

and

 

For sufficiently small residuals, the second term in (2.18) can be neglected and the elements of the Hessian matrix are approximated as:

 

By introducing the Jacobian matrix J whose elements are   the partial derivative of the individual residual with respect to the parameters:

(2.17) and (2.19) can be written in vector form as:

The above equations are the basis of the Gauß -Newton iteration scheme:

 

Given an initial iterate sufficiently close to the solution, the Gauss-Newton method has a quadratic convergence rate. However, a poor starting vector could cause the method to diverge due to the size of the neglected second term in (2.18). Furthermore, the method always fails when the Hessian matrix becomes singular or ill-conditionned. Several modifications have been proposed [22][5] to the basic scheme to ensure convergence.

In the Levenberg-Marquardt method, the approximate Hessian matrix is replaced by:

and the iteration scheme becomes:

 

where is a conditioning factor and is a diagonal matrix with entries equal to the diagonal elements of . The essence of the Levenberg-Marquardt compromise is that the step direction is intermediate between the steepest descent and the Gauß -Newton directions. As the search direction approaches the Gauß -Newton direction. Alternatively when , the method reduces to a steepest descent minimum search. A simple strategy to update the values of consists of decreasing its value when an iteration is successful in reducing the sum of squares fit criterion, and increasing it when the iteration fails:

where is a user defined parameter (default of 5).



next up previous contents index
Next: 2.1.2 Calculation of the Up: 2.1 Nonlinear Least Squares Previous: 2.1 Nonlinear Least Squares



Martin Stiftinger
Tue Aug 1 19:07:20 MET DST 1995