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. Linesearch 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 linesearch 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.... Unconstrained minimization, Modified Newton method, Descent direction, Negative curvature, Cholesky factorization.