Gauss-Newton Method

An algorithm that is particularly suited to the small-residual case is the Gauss-Newton algorithm, in which the Hessian is approximated by its first term. In a line-search version of the Gauss-Newton algorithm, the search direction from the current iterate satisfies the linear system

Any solution of (1.1) is a descent direction for, since

unless .

Gauss-Newton codes perform a line search along the direction to obtain the new iterate. The suitability of a candidate's step length can be determined, as in the case of unconstrained minimization, by enforcing the sufficient decrease condition and the curvature condition.

When the Jacobian of f has rank less than n, the system (1.1) has a multiplicity of solutions. In these circumstances, Gauss-Newton algorithms choose a particular solution. For example, the choice

where, in general, the matrix denotes the Moore-Penrose pseudo-inverse of the matrix , corresponds to the solution of least 2-norm. Since this choice is expensive to compute and requires the determination of the rank of the Jacobian, codes tend to obtain a direction that satisfies (1.1) by using less expensive techniques.

The Gauss-Newton algorithm is used, usually with enhancements, in much of the software for nonlinear least squares. It is a component of the algorithms used by DFNLP , MATLAB , NAG(FORTRAN) , NAG(C) , OPTIMA , and TENSOLVE . In many of these codes the Gauss-Newton model is augmented by a matrix ; as a consequence the search direction satisfies

The purpose of is to guarantee fast local convergence while retaining the global convergence properties of the Gauss-Newton method.

The NAG routines use a Gauss-Newton search direction whenever a sufficiently large decrease in is obtained at the previous iteration. Otherwise, second-derivative information is obtained from user-supplied function evaluation routines, quasi-Newton approximations, or difference approximations. Using this information, the software attempts to find a more accurate approximation to the Newton direction than the Gauss-Newton direction is able to provide.

The TENSOLVE software augments the Gauss-Newton model with a low-rank tensor approximation to the second-order term. It has been observed to converge faster than standard Gauss-Newton on many problems, particularly when the Jacobian matrix is rank deficient at the solution.

Up To:

Nonlinear Least Squares.

[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]

Updated 28 March 1996