Accession Number : ADA319597

Title :   Truncated-Newton Methods.

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Nash, Stephen G.

PDF Url : ADA319597

Report Date : MAY 1982

Pagination or Media Count : 122

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.

Descriptors :   *NUMERICAL METHODS AND PROCEDURES, *SIMULTANEOUS EQUATIONS, ALGORITHMS, THESES, VARIABLES, NONLINEAR SYSTEMS, QUADRATIC EQUATIONS.

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE