The Gauss-Newton and Levenberg-Marquardt algorithms usually exhibit quadratic
convergence for zero-residual (r(x*)=0) problems. Otherwise, the convergence is
only linear. It would seem that something could be gained by treating a nonlinear least
squares problem as a general unconstrained minimization problem and applying quasi-Newton
algorithms to it, since quasi-Newton algorithms are superlinearly convergent. A simple
hybrid strategy, implemented in the PROC NLP algorithms, combines the
Gauss-Newton and BFGS quasi-Newton algorithms. In this approach, the Gauss-Newton step is
used if it decreases the value of
by a factor of 5. If not, the BFGS step is taken. The initial approximate Hessian for BFGS
is taken to be the initial Gauss-Newton matrix
. For zero-residual problems, Gauss-Newton steps are
always eventually taken, and the iterates converge quadratically. For other problems, BFGS
steps are eventually used and superlinear convergence is obtained.
Another combination of the Gauss-Newton and quasi-Newton approaches appears in the
algorithm implemented in the PORT 3
library. A trust-region approach is used with an approximate Hessian matrix of the form where
is a quasi-Newton approximation to the second term in
the true Hessian. Low-rank corrections are applied to
at each iteration, together with
a scaling strategy that ensures that this matrix stays small when the residuals are small.
At each iteration, a decision is made whether to take the Gauss-Newton step or the step
that is computed by including the
term.
Other codes that use a quasi-Newton approach that takes advantage of the structure in nonlinear least squares problems in some way are DFNLP , LANCELOT , NLSSOL , and VE10 .
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
