Decomposition in conic optimization with partially separable structure
From MaRDI portal
Publication:3192107
DOI10.1137/130926924zbMATH Open1297.90111arXiv1306.0057OpenAlexW2014495508MaRDI QIDQ3192107FDOQ3192107
Authors: Yi-Fan Sun, Martin S. Andersen, Lieven Vandenberghe 
Publication date: 26 September 2014
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: Decomposition techniques for linear programming are difficult to extend to conic optimization problems with general non-polyhedral convex cones because the conic inequalities introduce an additional nonlinear coupling between the variables. However in many applications the convex cones have a partially separable structure that allows them to be characterized in terms of simpler lower-dimensional cones. The most important example is sparse semidefinite programming with a chordal sparsity pattern. Here partial separability derives from the clique decomposition theorems that characterize positive semidefinite and positive-semidefinite-completable matrices with chordal sparsity patterns. The paper describes a decomposition method that exploits partial separability in conic linear optimization. The method is based on Spingarn's method for equality constrained convex optimization, combined with a fast interior-point method for evaluating proximal operators.
Full work available at URL: https://arxiv.org/abs/1306.0057
Recommendations
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
- Applications of the method of partial inverses to convex programming: Decomposition
- On Decomposition Methods for a Class of Partially Separable Nonlinear Programs
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- On the existence of convex decompositions of partially separable functions
Cited In (14)
- Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Decomposition methods for sparse matrix nearness problems
- A survey on conic relaxations of optimal power flow problem
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Distributed consensus-based solver for semi-definite programming: an optimization viewpoint
- On the existence of convex decompositions of partially separable functions
- Bounds on heat transfer for Bénard–Marangoni convection at infinite Prandtl number
- Bregman primal-dual first-order method and application to sparse semidefinite programming
- Title not available (Why is that?)
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes
- COSMO: a conic operator splitting method for convex conic problems
- On Decomposition Methods for a Class of Partially Separable Nonlinear Programs
Uses Software
This page was built for publication: Decomposition in conic optimization with partially separable structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192107)
