Line-search methods generate the iterates by setting
where 
is a search direction and 
is chosen so that
.
Most line-search versions of the basic Newton method generate the direction by modifying
the Hessian matrix 
to ensure
that the quadratic model 
of the
function has a unique minimizer. The modified Cholesky decomposition approach
adds positive quantities to the diagonal of during the Cholesky
factorization. As a result, a diagonal matrix, 
, with nonnegative diagonal entries is generated such
that
is positive definite. Given this decomposition, the search direction is obtained by solving 
After is
found, a line-search procedure is used to choose an that approximately minimizes 
along the ray
.
The following Newton codes use line-search methods:
GAUSS, NAG(FORTRAN) , NAG(C) , and OPTIMA .
The algorithms used in these codes for determining 
rely on quadratic or cubic interpolation of the
univariate function
in their search for a suitable . An elegant and practical criterion for a suitable is to require to satisfy the sufficient
decrease condition: 
and the
curvature condition: 
where 
and 
are two constants with 
. The sufficient decrease condition guarantees, in
particular, that 
, while the
curvature condition requires that be not too far from a minimizer of 
. Requiring an accurate minimizer is generally wasteful
of function and gradient evaluations, so codes typically use 
and 
in these conditions.
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
