TY - JOUR
T1 - A Low-Complexity Parallelizable Numerical Algorithm for Sparse Semidefinite Programming
AU - Madani, Ramtin
AU - Kalbat, Abdulrahman
AU - Lavaei, Javad
N1 - Funding Information:
Manuscript received June 12, 2017; revised June 13, 2017, June 14, 2017, and September 30, 2017; accepted October 25, 2017. Date of publication November 15, 2017; date of current version December 14, 2018. This work was supported in part by the ONR YIP Award, in part by the DARPA Young Faculty Award, in part by the AFOSR YIP Award, in part by the NSF CAREER Award 1351279, and in part by the NSF EECS Award 1552096. This paper was presented in part at the 54th IEEE Conference on Decision and Control, Osaka, Japan, December 2015. Recommended by Associate Editor M. Rabbat. (Corresponding author: Javad Lavaei.) R. Madani is with the Department of Electrical Engineering, University of Texas at Arlington, Arlington, TX 76019 USA (e-mail: ramtin. madani@uta.edu).
Publisher Copyright:
© 2017 IEEE.
PY - 2018/12
Y1 - 2018/12
N2 - In the past two decades, the semidefinite programming (SDP) technique has been proven to be extremely successful in the convexification of hard optimization problems appearing in graph theory, control theory, polynomial optimization theory, and many areas in engineering. In particular, major power optimization problems, such as optimal power flow, state estimation, and unit commitment, can be formulated or well approximated as SDPs. However, the inability to efficiently solve large-scale SDPs is an impediment to the deployment of such formulations in practice. Motivated by the significant role of SDPs in revolutionizing the decision-making process for real-world systems, this paper designs a low-complexity numerical algorithm for solving sparse SDPs, using the alternating direction method of multipliers and the notion of tree decomposition in graph theory. The iterations of the designed algorithm are highly parallelizable and enjoy closed-form solutions, whose most expensive computation amounts to eigenvalue decompositions over certain submatrices of the SDP matrix. The proposed algorithm is a general-purpose parallelizable SDP solver for sparse SDPs, and its performance is demonstrated on the SDP relaxation of the optimal power flow problem for real-world benchmark systems with more than 13 600 nodes.
AB - In the past two decades, the semidefinite programming (SDP) technique has been proven to be extremely successful in the convexification of hard optimization problems appearing in graph theory, control theory, polynomial optimization theory, and many areas in engineering. In particular, major power optimization problems, such as optimal power flow, state estimation, and unit commitment, can be formulated or well approximated as SDPs. However, the inability to efficiently solve large-scale SDPs is an impediment to the deployment of such formulations in practice. Motivated by the significant role of SDPs in revolutionizing the decision-making process for real-world systems, this paper designs a low-complexity numerical algorithm for solving sparse SDPs, using the alternating direction method of multipliers and the notion of tree decomposition in graph theory. The iterations of the designed algorithm are highly parallelizable and enjoy closed-form solutions, whose most expensive computation amounts to eigenvalue decompositions over certain submatrices of the SDP matrix. The proposed algorithm is a general-purpose parallelizable SDP solver for sparse SDPs, and its performance is demonstrated on the SDP relaxation of the optimal power flow problem for real-world benchmark systems with more than 13 600 nodes.
KW - Large-scale optimization
KW - numerical algorithms
KW - power systems
KW - semidefinite programming
KW - tree decomposition
UR - http://www.scopus.com/inward/record.url?scp=85035137793&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85035137793&partnerID=8YFLogxK
U2 - 10.1109/TCNS.2017.2774008
DO - 10.1109/TCNS.2017.2774008
M3 - Article
AN - SCOPUS:85035137793
SN - 2325-5870
VL - 5
SP - 1898
EP - 1909
JO - IEEE Transactions on Control of Network Systems
JF - IEEE Transactions on Control of Network Systems
IS - 4
M1 - 8110723
ER -