Truncated-Newton Methods.
Abstract
The problem of minimizing a real valued function F of n variables arises in many contexts. Most methods for solving this problem have their roots in Newton's method, i.e. they are based on approximating F by a quadratic function Q. If the number of variables n is large, then Newton's method can be problematic since it requires the computation and storage of the Hessian matrix of second derivatives. Use of finite differencing and sparse matrix techniques has overcome some of these problems but not all. In this thesis, we examine a flexible class of methods, called truncated-Newton methods. They are based on approximately minimizing the quadratic function Q using an iterative scheme such as the linear conjugate gradient algorithm. A truncated-Newton algorithm is made up of two sub-algorithms: an outer non-linear algorithm controlling the entire minimization, and an inner linear algorithm for approximately minimizing Q. The most important choice is the selection of the inner algorithm. When the Hessian matrix is known to be positive definite everywhere, then the basic linear conjugate gradient algorithm can be used. If not, Q may not have a minimum. We have used the correspondence between the linear conjugate gradient algorithm and the Lanezos algorithm for tridiagonalizing a symmetric matrix to develop methods for the indefinite case. The performance of the inner algorithm can be greatly improved through the use of preconditioning strategies. Preconditionings can be developed using either the outer nonlinear algorithm or using information computed during the inner algorithm. A number of diagonal and tridiagonal preconditioning strategies are derived here. Numerical tests show that a carefully chosen truncated-Newton method can perform significantly better than the best nonlinear conjugate gradient algorithms available today.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1982
- Accession Number
- ADA319597
Entities
People
- Stephen G. Nash
Organizations
- Stanford University