Computing modified Newton directions using a partial Cholesky factorization

The effectiveness of Newton's method for finding an unconstrained minimizer of a strictly convex twice continuously differentiable function has prompted the proposal of various modified Newton methods for the nonconvex case.

Line search modified Newton methods utilize a linear combination of a descent direction and a direction of negative curvature. If these directions are sufficient in a certain sense, and a suitable line search is used, the resulting method will generate limit points that satisfy the second-order necessary conditions for optimality.

We propose an efficient method for computing a descent direction and a direction of negative curvature that is based on a partial Cholesky factorization of the Hessian. This factorization not only gives theoretically satisfactory directions, but also requires only a partial pivoting strategy, i.e., the equivalent of only two rows of the Schur complement need be examined at each step.

Return To PEG's Home Page.