SCCM, Gates Bldg. 2B

Stanford University

Stanford, CA 94305-9025

Co-author: Walter Murray, Stanford

Abstract

When solving a nonconvex optimization problem using
a modified Newton type algorithm, a descent direction
may not exist near a first order optimality point.
In these cases it is important to find a direction
of negative curvature, i.e. a direction *d*
such that *dHd<0*, where *H* is the Hessian
of the objective function. Such a *d*
exists if and only if *H* has at least one negative
eigenvalue. A good direction of negative curvature
has negative curvature bounded away from zero, and
should preferably be close to the smallest eigenvalue.

Forsgren, Gill, and Murray (1995) showed how to obtain
a provably satisfactory direction of negative curvature
using a partial Cholesky factorization of *H*.
This algorithm requires partial pivoting. We suggest
instead an iterative method. First we consider
the case where some type of approximate Cholesky factorization
is needed for other purposes. We propose
to compute a modified Cholesky factorization,
which requires no pivoting. From this, we can always
find a direction of negative curvature (if one exists),
but it may be very poor.
To remedy this we use an iterative method to improve
the direction we found initially.
The best candidates for this iterative process are
Lanczos, Chebyshev iteration, and the Jacobi-Davidson method. We show
empirically that in most cases, after a small number of iterations
(typically 2-10) a good direction of negative curvature is obtained.
Which method is the better depends on the distribution of
the eigenvalues of *H*. One interesting feature
of the Jacobi-Davidson method is we can use the modified
Cholesky factorization we already have computed as a preconditioner
in the inner iteration.

The second scenario is when it is impractical to form the Hessian matrix explicitly. In such cases, we need to use a purely iterative method which only requires matrix-vector products. We start with a random initial vector and iterate using one of the methods described above. Obviously, more iterations are now required to get a good direction since initially the curvature is most likely positive.