  


A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning
Renato D.C. Monteiro (monteiroisye.gatech.edu) Abstract: The conjugate gradient (CG) algorithm is wellknown 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 illconditioned 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 illconditioned 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 303320205, October 2004. Download: [Postscript][PDF] Entry Submitted: 10/06/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  