Fast ADMM for Semidefinite Programs with Chordal Sparsity

Abstract

Many problems in control theory can be formulated as semidefinite programs (SDPs). For large-scale SDPs, it is important to exploit the inherent sparsity to improve the scalability. This paper develops efficient first-order methods to solve SDPs with chordal sparsity based on the alternating direction method of multipliers (ADMM). We show that chordal decomposition can be applied to either the primal or the dual standard form of a sparse SDP, resulting in scaled versions of ADMM algorithms with the same computational cost. Each iteration of our algorithms consists of a projection on the product of small positive semidefinite cones, followed by a projection on an affine set, both of which can be carried out efficiently. Our techniques are implemented in CDCS, an open source add-on to MATLAB. Numerical experiments on large-scale sparse problems in SDPLIB and random SDPs with block-arrow sparse patterns show speedups compared to some common state-of-the-art software packages.

6 pages. Codes available from http://github.com/giofantuzzi/CDCS . Accepted in the American Control Conference, 2017 http://ieeexplore.ieee.org/abstract/document/7963462/

Cited by in corpus (14)

• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
• Exploiting Sparsity in the Coefficient Matching Conditions in Sum-of-Squares Programming using ADMM
• Fast ADMM for sum-of-squares programs using partial orthogonality
• Fast ADMM for homogeneous self-dual embedding of sparse SDPs
• Conic Optimization Theory: Convexification Techniques and Numerical Algorithms
• Optimization with affine homogeneous quadratic integral inequality constraints
• Decomposition and Completion of Sum-of-Squares Matrices
• Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
• Parallel Optimal Control for Cooperative Automation of Large-scale Connected Vehicles via ADMM
• Approximate Dynamic Programming For Linear Systems with State and Input Constraints
• Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations
• Chordal Decomposition for Spectral Coarsening