Decomposition in conic optimization with partially separable structure

Yifan Sun, Martin Skovgaard Andersen, Lieven Vandenberghe

Research output: Contribution to journalJournal articleResearchpeer-review

280 Downloads (Pure)

Abstract

Decomposition techniques for linear programming are difficult to extend to conic optimization problems with general nonpolyhedral 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.
Original languageEnglish
JournalS I A M Journal on Optimization
Volume24
Issue number2
Pages (from-to)873-897
ISSN1052-6234
DOIs
Publication statusPublished - 2014

Keywords

  • DECOMPOSITION (Mathematics)
  • MATHEMATICS,
  • POSITIVE SEMIDEFINITE MATRICES
  • EXPLOITING SPARSITY
  • ALGORITHM
  • OPERATOR
  • CONES
  • SDP
  • semidefinite programming
  • decomposition
  • interior-point algorithms

Fingerprint

Dive into the research topics of 'Decomposition in conic optimization with partially separable structure'. Together they form a unique fingerprint.

Cite this