An inexact dual logarithmic barrier method for solving sparse semidefinite programs

Stefania Bellavia, Jacek Gondzio, Margherita Porcelli

Research output: Contribution to journalArticlepeer-review

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 Ai 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.
Original languageEnglish
Pages (from-to)109-143
Number of pages34
JournalMathematical programming
Volume178
Early online date28 Apr 2018
DOIs
Publication statusPublished - Nov 2019

Fingerprint

Dive into the research topics of 'An inexact dual logarithmic barrier method for solving sparse semidefinite programs'. Together they form a unique fingerprint.

Cite this