Newton-Type Minimization via the Lanczos Method

TLDR

The paper examines using the linear conjugate‑gradient method, derived via the Lanczos process, to solve large‑scale unconstrained minimization problems by iteratively solving quadratic subproblems, and discusses truncated Newton approaches that interpolate between steepest‑descent and Newton directions. The authors aim to develop a modified Newton method that exploits the Lanczos characterization of linear conjugate‑gradient to handle problems with indefinite Hessians, and to design a preconditioned CG scheme that interpolates between nonlinear conjugate‑gradient and modified Newton search directions. They achieve this by applying the Lanczos‑based linear conjugate‑gradient framework to construct search directions and by incorporating preconditioning to blend nonlinear conjugate‑gradient and modified Newton steps. The resulting derivation enables computation of a negative‑curvature direction at a stationary point.

Abstract

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.