Optimization Online


A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

Renato D.C. Monteiro (monteiro***at***isye.gatech.edu)
Jerome W. O'Neal (joneal***at***isye.gatech.edu)
Arkadi Nemirovski (nemirovs***at***ie.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society