Trust Region and Line-search Methods

A trust-region version of Newton's method takes the view that the linear model

of is valid only when is not too large, and thus places a restriction on the size of the step. In a general trust-region method, the Jacobian matrix is replaced by an approximation, and the step is obtained as an approximate solution of the subproblem

where is a scaling matrix and is the trust-region radius. The step is accepted if the ratio

of the actual-to-predicted decrease in is greater than some constant . (Typically .0001.). If the step is not accepted, the trust region radius is decreased and the ratio is recomputed. The trust-region radius may also be updated between iterations according to how close the ratio is to its ideal value of 1. Trust-region techniques are used in the IMSL , LANCELOT , MINPACK-1 , NAG(FORTRAN) and NAG(C) codes.

Given an approximation to the Jacobian matrix, a line-search method obtains a search direction by solving the system of linear equations

The next iterate is then defined as

,

where the line search parameter is chosen by the line-search procedure so that

.

When the "approximate" Jacobian is "exact", as in Newton's method, is a downhill direction 2-norm, so there is certain to be an such that

.

This descent property does not necessarily hold for other choices of the approximate Jacobian, so line-search methods are used only when is either the exact Jacobian or a close approximation to it.

In an ideal line-search Newton method, we would compute the search direction by solving

and choose the line-search parameter to minimize the scalar function

However, since it is usually too time-consuming to find the that exactly minimizes , we usually settle for an approximate solution that satisfies the conditions

where and are two constants with . Typical values are

,

The first of these conditions ensures that decreases by a significant amount, while the second condition ensures that we move far enough along the search direction by insisting on a significant reduction in the size of the gradient. Line-search techniques are implemented in the GAUSS, MATLAB, OPTIMA, and TENSOLVE codes.

Up To:

Systems of Nonlinear Equations .

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

Updated 28 March 1996