On the solution of large-scale SDP problems by the modified barrier method using iterative solvers

Michal Kocvara (kocvarautia.cas.cz)
Michael Stingl (stinglam.uni-erlangen.de)

Abstract: When solving large-scale semidefinite programming problems by second-order methods, the storage and factorization of the Newton matrix are the limiting factors. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable alternative for problems with large number of variables and modest size of the constrained matrix. We further propose to approximate the Newton matrix in the matrix-vector product by a finite-difference formula. This leads to huge savings in memory requirements and, for certain problems, to further speed-up of the algorithm.

Keywords: semidefinite programming, conjugate gradient method, modified barrier method

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Research Report 304, Institute of Applied Mathematics, University of Erlangen, 2005

Download: [PDF]

Entry Submitted: 03/02/2005
Entry Accepted: 03/02/2005
Entry Last Modified: 01/25/2006

Modify/Update this entry