Optimization Online


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

Michal Kocvara (kocvara***at***utia.cas.cz)
Michael Stingl (stingl***at***am.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

  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