Decomposition in conic optimization with partially separable structure

Understand

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.