Sparse Semidefinite Programs with Near-Linear Time Complexity

Richard Y. Zhang, Javad Lavaei

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Some of the strongest polynomial-time relaxations to NP-hard combinatorial optimization problems are semidefinite programs (SDPs), but their solution complexity of up to O(n 6. 5 L) time and O(n 4 ) memory for L accurate digits limits their use in all but the smallest problems. Given that combinatorial SDP relaxations are often sparse, a technique known as chordal conversion can sometimes reduce complexity substantially. In this paper, we describe a modification of chordal conversion that allows any general-purpose interior-point method to solve a certain class of sparse SDPs with a guaranteed complexity of O(n l. 5 L) time and O(n) memory. To illustrate the use of this technique, we solve the MAX k- CUT relaxation and the Lovasz Theta problem on power system models with up to n = 13659 nodes in 5 minutes, using SeDuMi v1.32 on a 1.7 GHz CPU with 16 GB of RAM. The empirical time complexity for attaining L decimal digits of accuracy is ≈ 0.001n l. l L seconds.

Original languageEnglish (US)
Title of host publication2018 IEEE Conference on Decision and Control, CDC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781538613955
StatePublished - Jan 18 2019
Externally publishedYes
Event57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States
Duration: Dec 17 2018Dec 19 2018

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546


Conference57th IEEE Conference on Decision and Control, CDC 2018
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Sparse Semidefinite Programs with Near-Linear Time Complexity'. Together they form a unique fingerprint.

Cite this