Sparse Semidefinite Programs with Near-Linear Time Complexity

Richard Y. Zhang, Javad Lavaei

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

Abstract

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.
Pages1624-1631
Number of pages8
ISBN (Electronic)9781538613955
DOIs
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
Volume2018-December
ISSN (Print)0743-1546

Conference

Conference57th IEEE Conference on Decision and Control, CDC 2018
Country/TerritoryUnited States
CityMiami
Period12/17/1812/19/18

ASJC Scopus subject areas

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

Fingerprint

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

Cite this