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.
Citation
Research Report 304, Institute of Applied Mathematics, University of Erlangen, 2005