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 and therefore is well-suited to problems with a sparse dual matrix. 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 constraint matrices 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.

An inexact dual logarithmic barrier method for solving sparse semidefinite programs / Stefania Bellavia, Jacek Gondzio, Margherita Porcelli. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - STAMPA. - 178:(2019), pp. 109-143. [10.1007/s10107-018-1281-5]

An inexact dual logarithmic barrier method for solving sparse semidefinite programs

Stefania Bellavia;Margherita Porcelli
2019

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 and therefore is well-suited to problems with a sparse dual matrix. 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 constraint matrices 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.
2019
178
109
143
Stefania Bellavia, Jacek Gondzio, Margherita Porcelli
File in questo prodotto:
File Dimensione Formato  
SDP_math_prog.pdf

Accesso chiuso

Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 879 kB
Formato Adobe PDF
879 kB Adobe PDF   Richiedi una copia
SDP_mathprog_preprint.pdf

accesso aperto

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Open Access
Dimensione 534 kB
Formato Adobe PDF
534 kB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1126647
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact