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
- 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
- A Newton-CG augmented Lagrangian method for semidefinite programming
- 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
- 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?)
- 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
(29)- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Learning chordal extensions
- A proximal augmented method for semidefinite programming problems
- Bregman primal-dual first-order method and application to sparse semidefinite programming
- Decomposed structured subsets for semidefinite and sum-of-squares optimization
- Efficient semidefinite programming with approximate ADMM
- COSMO: a conic operator splitting method for convex conic problems
- Decomposition of arrow type positive semidefinite matrices with application to topology optimization
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Distributed consensus-based solver for semi-definite programming: an optimization viewpoint
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes
- CDCS
- Decomposition in conic optimization with partially separable structure
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- scientific article; zbMATH DE number 7306855 (Why is no real title available?)
- A bilevel approach for identifying the worst contingencies for nonconvex alternating current power systems
- A new global algorithm for max-cut problem with chordal sparsity
- 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 graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem
- IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming
- Distributed nonlinear conic optimization with partially separable structure
- Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods
- Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices
- Complexity of chordal conversion for sparse semidefinite programs with small treewidth
- Solving low-rank semidefinite programs via manifold optimization
- A semismooth Newton based augmented Lagrangian algorithm for Lovász theta SDP problem
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)
