Newton-Type Minimization via the Lanczos Method

This paper discusses the use of the linear conjugate-gradient method (developed via the Lanczos method) in the solution of large-scale unconstrained minimization problems. At each iteration of a Newton-type method, the direction of search is defined as the solution of a quadratic subproblem. When the number of variables is very large, this subproblem may be solved using the linear conjugate-gradient method of Hestenes and Stiefel. We show how the equivalent Lanczos characterization of the linear conjugate-gradient method may be exploited to define a modified Newton method which can be applied to problems that do not necessarily have positive-definite Hessian matrices at all points of the region of interest. This derivation also makes it possible to compute a negative-curvature direction at a stationary point. The idea of a truncated Newton method is to perform only a limited number of iterations of the quadratic subproblem. This effectively gives a search direction that interpolates between the steepest-descent direction and the Newton direction. We describe a preconditioned linear conjugate-gradient method that defines a search direction which interpolates between the direction defined by a nonlinear conjugate-gradient-type algorithm and a modified Newton direction.