TY - GEN
T1 - Sparse Semidefinite Programs with Near-Linear Time Complexity
AU - Zhang, Richard Y.
AU - Lavaei, Javad
N1 - Funding Information:
This work was supported by NSF Award 1808859, DARPA Award D16AP00002, AFOSR Award FA9550-17-1-0163, and ONR YIP.
Publisher Copyright:
© 2018 IEEE.
PY - 2019/1/18
Y1 - 2019/1/18
N2 -
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.
AB -
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.
UR - http://www.scopus.com/inward/record.url?scp=85062186862&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062186862&partnerID=8YFLogxK
U2 - 10.1109/CDC.2018.8619478
DO - 10.1109/CDC.2018.8619478
M3 - Conference contribution
AN - SCOPUS:85062186862
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 1624
EP - 1631
BT - 2018 IEEE Conference on Decision and Control, CDC 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 57th IEEE Conference on Decision and Control, CDC 2018
Y2 - 17 December 2018 through 19 December 2018
ER -