S. Bellavia, J. Gondzio and M. Porcelli
Abstract
A dual logarithmic barrier method for solving large, sparse semidefinite
programs is proposed in this paper. The method avoids any explicit use
of the primal variable $X$ and therefore is well-suited to problems
with a sparse dual matrix $S$. It relies on inexact Newton steps
in dual space which are computed by the conjugate gradient method
applied to the Schur complement of the reduced KKT system.
The method may take advantage of low-rank representations of matrices
A_i to perform implicit matrix-vector products with the Schur complement
matrix and to compute only specific parts of this matrix.
This allows the construction of the partial Cholesky factorization
of the Schur complement matrix which serves as a good preconditioner
for it and permits the method to be run in a matrix-free scheme.
Convergence properties of the method are studied and a polynomial
complexity result is extended to the case when inexact Newton
steps are employed.
A MATLAB-based implementation is developed and preliminary computational
results of applying the method to maximum cut and matrix completion
problems are reported.
Key words: Semidefinite programming, dual logarithmic barrier method, inexact Newton method, preconditioning