Tight Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packing

Tianqi Zheng, James Guthrie, Enrique MalladaarXiv 2021 · OpenReview

TL;DR

This paper introduces a novel framework for approximating the computationally expensive positive-semidefinite (PSD) cone by decomposing it into conic combinations of smaller sub-cones. By connecting this problem to Grassmannian packing, they develop a method to arrange these sub-cones to maximize their separation, leading to tighter and more efficient inner approximations for solving large-scale semidefinite programs.

What Problem Does This Paper Address?

Semidefinite programs (SDPs) are powerful optimization tools with wide applications, but their computational cost grows significantly with the dimension of the PSD cone. Solving large SDPs becomes impractical due to memory and time constraints. Existing methods to alleviate this often involve approximating the PSD cone with simpler structures, but these can be overly conservative or limited in scalability. This paper aims to address this by developing a more flexible and accurate approach to inner approximating the PSD cone, enabling more efficient solution of large-scale SDPs.

Methods

The core of the paper is a novel decomposition framework for the PSD cone. They show that many existing inner approximation techniques (like diagonally dominant matrices and factor-width matrices) can be unified under this framework, which expresses the PSD cone as a conic hull of smaller sub-cones.

The key innovation is the development of a flexible family of inner approximations. This is achieved by framing the problem of arranging sub-cones as a packing problem in Grassmannian manifolds. Specifically, they demonstrate that finding maximally distant sub-cones within the PSD cone is equivalent to packing k-dimensional subspaces in an n-dimensional Euclidean space. They leverage existing computational methods for Grassmannian packing (like alternating projection) to construct these maximally separated sub-cones, leading to tighter approximations that occupy a larger fraction of the PSD cone's volume.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments using synthetic data generated for testing the approximation quality.

Key Insights and Ideas

  • Unifying Framework: Existing PSD cone approximation techniques can be viewed as special cases of a more general decomposition framework based on conic combinations of sub-cones.
  • Grassmannian Connection: The problem of finding optimally separated sub-cones within the PSD cone is mathematically equivalent to a classical packing problem in Grassmannian manifolds. This connection is crucial for leveraging existing geometric packing algorithms.
  • Maximally Separated Sub-cones: Arranging sub-cones to be maximally distant from each other leads to significantly tighter inner approximations of the PSD cone, improving accuracy.
  • Trade-off: The proposed approach offers a way to balance approximation accuracy with computational complexity by controlling the number and dimension of the sub-cones used.

Key Results

  • The paper provides a theoretical framework that unifies several existing inner approximation methods for the PSD cone.
  • They demonstrate that their proposed method, based on Grassmannian packing, can achieve comparable or better approximation accuracy with fewer sub-cones compared to traditional methods like scaled diagonally dominant (SDD) or factor-width (FW) matrices.
  • Numerical experiments show that for a PSD cone of size n=20, their "FRAME" approach can achieve near-perfect approximations with only 30 sub-cones of dimension s=10, whereas SDD requires 190 sub-cones and FW3 requires 1140 sub-cones of smaller dimensions.
  • The study also indicates that the number of sub-cones required for a tight approximation grows exponentially with the dimension of the ambient PSD cone, a finding consistent with prior theoretical work.

Limitations and Future Work

  • Alternating Projection Algorithm Limitations: The paper notes that the alternating projection algorithm used for constructing Grassmannian packings has limitations: it lacks a theoretical convergence proof, can require many iterations (up to 5000), and its performance flags for a large number of subspaces (approaching 20). This could impact the scalability of their method for very large numbers of sub-cones.
  • Computational Cost of Packing: While the resulting approximations are tighter, the process of finding optimal Grassmannian packings itself can be computationally intensive, especially for a large number of sub-cones.
  • Future Work: The authors suggest that establishing these connections to Grassmannian packing could inspire new research into better approximations by leveraging tools from information theory and other related fields. They also implicitly point towards the need for more efficient algorithms for constructing these packings.

Summary updated

Abstract

We investigate the problem of finding inner ap-proximations of positive semidefinite (PSD) cones. We developa novel decomposition framework of the PSD cone by meansof conical combinations of smaller dimensional sub-cones. Weshow that many inner approximation techniques could besummarized within this framework, including the set of (scaled)diagonally dominant matrices, Factor-widthkmatrices, andChordal Sparse matrices. Furthermore, we provide a moreflexible family of inner approximations of the PSD cone, wherewe aim to arrange the sub-cones so that they are maximallyseparated from each other. In doing so, these approximationstend to occupy large fractions of the volume of the PSD cone.The proposed approach is connected to a classical packingproblem in Riemannian Geometry. Precisely, we show thatthe problem of finding maximally distant sub-cones in anambient PSD cone is equivalent to the problem of packingsub-spaces in a Grassmannian Manifold. We further leverageexisting computational method for constructing packings inGrassmannian manifolds to build tighter approximations ofthe PSD cone. Numerical experiments show how the proposedframework can balance between accuracy and computationalcomplexity, to efficiently solve positive-semidefinite programs.
BibTeX
@misc{zheng2021tight,
  author = {Tianqi Zheng and James Guthrie and Enrique Mallada},
  title = {{Tight Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packing}},
  year = {2021},
  eprint = {2105.12021},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.12021},
}
Figure