So far, we have assumed that the Hessian matrix is available, but the algorithms are unchanged if the Hessian matrix is replaced by a reasonably accurate approximation. The most common method for obtaining such an approximation is to use differences of gradient values. If forward differences are used, then the ith column of the Hessian matrix is replaced by
for some suitable choice of difference parameter 
. Here, 
is the vector with 
in the ith position and zeros elsewhere.
Similarly, if central differences are used, the ith column is replaced by
An appropriate choice of the difference parameter can be difficult. Rounding errors
overwhelm the calculation if is too small, while truncation errors dominate if is too large.
Newton codes rely on forward differences, since they often yield sufficient accuracy for
reasonable values of . Central differences are more accurate but they require twice the work (
gradient evaluations against 
evaluations).
Variants of Newton's method for problems with a large number of variables cannot use
the above techniques to approximate the Hessian matrix because the cost of gradient
evaluations is prohibitive. For problems with a sparse Hessian matrix, however, it is
possible to use specialized techniques based on graph coloring that allow difference
approximations to the Hessian matrix to be computed efficiently. For example, if the
Hessian matrix has bandwidth 
,
then only 
gradient evaluations
are required.
VE08 is designed to solve optimization problems with a large number of variables where 
is a partially separable
function; that is, can be written in the form
where each function 
has an
invariant subspace
whose dimension is large relative to the number of variables . This is the case, in particular,
if 
depends only on a small
number (typically, fewer than ten) of the components of 
. Functions with sparse Hessian matrices are partially
separable. Indeed, most functions that arise in large-scale problems are partially
separable. An advantage of algorithms designed for these problems is that techniques for
approximating a dense Hessian matrix (for example, forward differences) can be used to
approximate the nontrivial part of the element Hessian matrix 
. Approximations to 
can be obtained by summing the approximations to .
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
