Optimization Online


An inexact dual logarithmic barrier method for solving sparse semidefinite programs

Stefania Bellavia (stefania.bellavia***at***unifi.it)
Jacek Gondzio (j.gondzio***at***ed.ac.uk)
Margherita Porcelli (margherita.porcelli***at***unifi.it)

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 linear system is preconditioned by the partial Cholesky factorization of the Schur complement matrix and this allows for 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 problems are reported.

Keywords: Semidefinite programming Dual logarithmic barrier method Inexact Newton method Maximum cut problem

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Nonlinear Optimization

Citation: Technical Report ERGO-16-004, School of Mathematics, The University of Edinburgh, July 29, 2016

Download: [PDF]

Entry Submitted: 07/29/2016
Entry Accepted: 07/29/2016
Entry Last Modified: 03/31/2017

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 Optimization Society