A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

Renato D.C. Monteiro (monteiroisye.gatech.edu)
Jerome W. O'Neal (jonealisye.gatech.edu)
Arkadi Nemirovski (nemirovsie.technion.ac.il)

Abstract: The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the performance of the CG algorithm on extremely ill-conditioned systems. We introduce the preconditioning procedure by applying it first to the steepest descent algorithm. Then, the same techniques are extended to the CG algorithm, and convergence to an $\epsilon$-solution in $\O(\log\det(A) + \sqrt{n}\log\epsilon^{-1})$ iterations is proven, where $\det(A)$ is the determinant of the matrix.

Keywords: Conjugate gradient algorithm, steepest descent algorithm, ellipsoid method, condition number, linear systems of equations, convergence rate, polynomial algorithms.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Linear, Cone and Semidefinite Programming (Other )

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, October 2004.

Download: [Postscript][PDF]

Entry Submitted: 10/06/2004
Entry Accepted: 10/06/2004
Entry Last Modified: 10/06/2004

Modify/Update this entry