Chordal decomposition in operator-splitting methods for sparse semidefinite programs
From MaRDI portal
Abstract: We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller positive semidefinite (PSD) constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order operator-splitting methods, enabling the development of efficient and scalable algorithms. In particular, we apply the alternating direction method of multipliers (ADMM) to solve decomposed primal- and dual-standard-form SDPs. Each iteration of such ADMM algorithms requires a projection onto an affine subspace, and a set of projections onto small PSD cones that can be computed in parallel. We also formulate the homogeneous self-dual embedding (HSDE) of a primal-dual pair of decomposed SDPs, and extend a recent ADMM-based algorithm to exploit the structure of our HSDE. The resulting HSDE algorithm has the same leading-order computational cost as those for the primal or dual problems only, with the advantage of being able to identify infeasible problems and produce an infeasibility certificate. All algorithms are implemented in the open-source MATLAB solver CDCS. Numerical experiments on a range of large-scale SDPs demonstrate the computational advantages of the proposed methods compared to common state-of-the-art solvers.
Recommendations
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- COSMO: a conic operator splitting method for convex conic problems
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Exploiting structured sparsity in large scale semidefinite programming problems
- Algorithm 925, parallel solver for semidefinite programming problem having sparse Schur complement matrix
Cites work
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- Alternating direction augmented Lagrangian methods for semidefinite programming
- An Interior-Point Method for Semidefinite Programming
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Computing the Minimum Fill-In is NP-Complete
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Decomposition in conic optimization with partially separable structure
- Decomposition methods for sparse matrix nearness problems
- Direct Methods for Sparse Linear Systems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Linear Matrix Inequalities in System and Control Theory
- On the existence of convex decompositions of partially separable functions
- Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems
- Parallel iterative methods for sparse linear systems
- Positive definite completions of partial Hermitian matrices
- Positive semidefinite matrices with a given sparsity pattern
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- Regularization methods for semidefinite programming
- SDPLIB 1.2, a library of semidefinite programming test problems
- Self equivalence of the alternating direction method of multipliers
- Semidefinite Programming
- Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- SuperMann: A Superlinearly Convergent Algorithm for Finding Fixed Points of Nonexpansive Operators
- The University of Florida sparse matrix collection
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(23)- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Decomposition of arrow type positive semidefinite matrices with application to topology optimization
- Decomposition in conic optimization with partially separable structure
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- Sparse conic reformulation of structured QCQPs based on copositive optimization with applications in stochastic optimization
- A bilevel approach for identifying the worst contingencies for nonconvex alternating current power systems
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- scientific article; zbMATH DE number 7306855 (Why is no real title available?)
- A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem
- CDCS
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Distributed consensus-based solver for semi-definite programming: an optimization viewpoint
- Learning chordal extensions
- A proximal augmented method for semidefinite programming problems
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Bregman primal-dual first-order method and application to sparse semidefinite programming
- IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Decomposed structured subsets for semidefinite and sum-of-squares optimization
- A new global algorithm for max-cut problem with chordal sparsity
- COSMO: a conic operator splitting method for convex conic problems
- Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes
- Efficient semidefinite programming with approximate ADMM
Describes a project that uses
Uses Software
This page was built for publication: Chordal decomposition in operator-splitting methods for sparse semidefinite programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297655)
