Chordal decomposition in operator-splitting methods for sparse semidefinite programs
From MaRDI portal
Publication:2297655
DOI10.1007/S10107-019-01366-3zbMATH Open1434.90126arXiv1707.05058OpenAlexW3100916622WikidataQ120716813 ScholiaQ120716813MaRDI QIDQ2297655FDOQ2297655
Giovanni Fantuzzi, Yang Zheng, Paul J. Goulart, A. Wynn, Antonis Papachristodoulou
Publication date: 20 February 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1707.05058
Convex programming (90C25) Semidefinite programming (90C22) Decomposition methods (49M27) Numerical methods involving duality (49M29)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The university of Florida sparse matrix collection
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- SDPLIB 1.2, a library of semidefinite programming test problems
- Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
- Direct Methods for Sparse Linear Systems
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Linear Matrix Inequalities in System and Control Theory
- A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
- Regularization Methods for Semidefinite Programming
- Semidefinite Programming
- Parallel iterative methods for sparse linear systems
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- An Interior-Point Method for Semidefinite Programming
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Positive definite completions of partial Hermitian matrices
- Self Equivalence of the Alternating Direction Method of Multipliers
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Computing the Minimum Fill-In is NP-Complete
- Positive semidefinite matrices with a given sparsity pattern
- On the existence of convex decompositions of partially separable functions
- A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices
- Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- Decomposition Methods for Sparse Matrix Nearness Problems
- Decomposition in Conic Optimization with Partially Separable Structure
- SuperMann: A Superlinearly Convergent Algorithm for Finding Fixed Points of Nonexpansive Operators
Cited In (20)
- A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem
- 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
- Title not available (Why is that?)
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Distributed consensus-based solver for semi-definite programming: an optimization viewpoint
- CDCS
- Learning chordal extensions
- A proximal augmented method for semidefinite programming problems
- 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
- A new global algorithm for max-cut problem with chordal sparsity
- Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes
- COSMO: a conic operator splitting method for convex conic problems
- Efficient semidefinite programming with approximate ADMM
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)
