TY - JOUR

T1 - Successive preconditioned conjugate gradient method for the minimization of quadratic and nonlinear functions

AU - Davey, K.

AU - Ward, M.J.

PY - 2000/10

Y1 - 2000/10

N2 - This paper is concerned with a conjugate gradient method that utilizes a successive set of preconditioner matrices. The method is developed for the solution of min{f (x): x ∈ Rn}, where f is a nonlinear function that is sufficiently smooth to possess a Hessian matrix that is continuous. The theory underpinning the method is developed for quadratic polynomials of the form p(x) = 12 (xTAx − 2xTb) where A is an arbitrary n × n matrix that is symmetric and positive definite. The minimization of p is achieved by the successive minimization of hi (ui) = p ◦ gi (ui ) where gi (ui ) = Kiui , i = 0, 1, . . . , n − 1, and where Ki are invertible matrices designed to accelerate the convergence of the conjugate gradient method. It is shown that quadratic termination is achievable for an arbitrary set, {K: i = 0, 1, . . . , n − 1}, of nonsingular matrices. This remarkable property provides for a very general formulation, where the preconditioned conjugate gradient method (PCGM) and quasi-Newton method are just special cases. The method is extended to nonlinear functions by means of an inexact Newton method. The method is tested on some simple functions to demonstrate the flexibility and computational effectiveness of the new approach. Systems of nonlinear equations generated from a finite element flow formulation are tested to illustrate the practical usefulness of the method.

AB - This paper is concerned with a conjugate gradient method that utilizes a successive set of preconditioner matrices. The method is developed for the solution of min{f (x): x ∈ Rn}, where f is a nonlinear function that is sufficiently smooth to possess a Hessian matrix that is continuous. The theory underpinning the method is developed for quadratic polynomials of the form p(x) = 12 (xTAx − 2xTb) where A is an arbitrary n × n matrix that is symmetric and positive definite. The minimization of p is achieved by the successive minimization of hi (ui) = p ◦ gi (ui ) where gi (ui ) = Kiui , i = 0, 1, . . . , n − 1, and where Ki are invertible matrices designed to accelerate the convergence of the conjugate gradient method. It is shown that quadratic termination is achievable for an arbitrary set, {K: i = 0, 1, . . . , n − 1}, of nonsingular matrices. This remarkable property provides for a very general formulation, where the preconditioned conjugate gradient method (PCGM) and quasi-Newton method are just special cases. The method is extended to nonlinear functions by means of an inexact Newton method. The method is tested on some simple functions to demonstrate the flexibility and computational effectiveness of the new approach. Systems of nonlinear equations generated from a finite element flow formulation are tested to illustrate the practical usefulness of the method.

KW - Preconditioners

KW - Conjugate gradients

KW - Optimization

KW - Quasi-Newton

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-0034299715&partnerID=MN8TOARS

U2 - 10.1016/S0168-9274(99)00053-7

DO - 10.1016/S0168-9274(99)00053-7

M3 - Article

SN - 0168-9274

VL - 35

SP - 129

EP - 156

JO - Applied Numerical Mathematics

JF - Applied Numerical Mathematics

IS - 2

ER -