Optimization Online


Degeneracy in Maximal Clique Decomposition for Semidefinite Programs

Arvind Raghunathan(raghunathan***at***merl.com)
Andrew Knyazev(knyazev***at***merl.com)

Abstract: Exploiting sparsity in Semidefinite Programs (SDP) is critical to solving large-scale problems. The chordal completion based maximal clique decomposition is the preferred approach for exploiting sparsity in SDPs. In this paper, we show that the maximal clique-based SDP decomposition is primal degenerate when the SDP has a low rank solution. We also derive conditions under which the multipliers in the maximal clique-based SDP formulation is not unique. Numerical experiments demonstrate that the SDP decomposition results in the schur-complement matrix of the Interior Point Method (IPM) having higher condition number than for the original SDP formulation.

Keywords: semidefinite programming, primal degeneracy, dual multiplicity, ill-conditioning, IPM

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

Category 2: Convex and Nonsmooth Optimization

Citation: arXiv:1509.08021v1 (http://arxiv.org/abs/1509.08021)

Download: [PDF]

Entry Submitted: 09/28/2015
Entry Accepted: 09/28/2015
Entry Last Modified: 09/28/2015

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