The trust-region approach can be motivated by noting that the quadratic model 
is a useful model of the function 
only near 
. When the Hessian matrix is indefinite, the quadratic
function
is unbounded below, so is obviously a poor model of 
when 
is large. Therefore, it is reasonable to select the step
by solving the subproblem
for some 
and scaling matrix 
. The trust-region parameter, 
, is adjusted between iterations
according to the agreement between predicted and actual reduction in the function as measured by
the ratio
If there is good agreement, that is, 
, then is increased. If the agreement is
poor; i.e., 
is small or
negative, then is decreased. The decision to accept the step is also based on . Usually,
if 
, where 
is small (typically, 
); otherwise 
.
The following Newton codes use trust-region methods with different algorithms for
choosing the step :
Most of these algorithms rely on the observation that there is a 
such that
where either 
and 
, or 
and 
. An appropriate 
is determined by an iterative process in which (1.1) is solved for each trial value of .
The algorithm implemented in the TENMIN package extends Newton's method by forming low-rank approximations to the third- and fourth-order terms in the Taylor series approximation. These approximations are formed by using matching conditions that require storage of the gradient (but not the Hessian) on a number of previous iterations.
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
