A Low-Complexity Parallelizable Numerical Algorithm for Sparse Semidefinite Programming

Ramtin Madani, Abdulrahman Kalbat, Javad Lavaei

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


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.

Original languageEnglish
Article number8110723
Pages (from-to)1898-1909
Number of pages12
JournalIEEE Transactions on Control of Network Systems
Issue number4
Publication statusPublished - Dec 2018


  • Large-scale optimization
  • numerical algorithms
  • power systems
  • semidefinite programming
  • tree decomposition

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization


Dive into the research topics of 'A Low-Complexity Parallelizable Numerical Algorithm for Sparse Semidefinite Programming'. Together they form a unique fingerprint.

Cite this