Efficient sampling in spectrahedra and volume approximation

Apostolos Chalkis, Ioannis Z. Emiris, Vissarion Fisikopoulos, Panagiotis Repouskos, Elias TsigaridasLinear 2022 · DOI

Abstract

This paper introduces a high-performance framework for sampling points and approximating volumes within spectrahedra—the complex, non-linear shapes that define the feasible regions of semidefinite programs. By reducing geometric operations to efficient linear algebra and implementing advanced random walks in C++, the authors demonstrate the ability to handle dimensions as high as 200, significantly pushing the boundaries of what was previously computationally feasible.

Introduction

In the world of optimization and geometry, polytopes (shapes with flat sides, like cubes or pyramids) are well-understood. However, many real-world problems in control theory and optimization involve spectrahedra. These are generalizations of polytopes that have curved boundaries defined by Linear Matrix Inequalities (LMIs).

Visual representations of spectrahedra, showing their characteristic curved boundaries.

While mature tools exist for sampling and measuring the volume of polytopes, spectrahedra are much harder to handle because their boundaries are non-linear. Existing methods often struggle to scale beyond very low dimensions (e.g., $n \leq 10$). This paper tackles the challenge of making sampling and volume estimation efficient and scalable for these "curvy" high-dimensional shapes.

Methodology

The authors develop a "toolbox" of three primitive geometric operations:

  1. Membership: Determining if a point is inside the shape.
  2. Intersection: Calculating where a curve (like a line or a parabola) hits the boundary.
  3. Reflection: Computing how a trajectory "bounces" off the curved boundary.

The key innovation is reducing these geometric queries to Polynomial Eigenvalue Problems (PEP). By solving these using optimized linear algebra libraries (like Eigen and Spectra), the authors can perform these operations very quickly. They integrate these primitives into several geometric random walks:

  • Hit-and-Run (W-HnR): Moves along random lines.
  • Billiard Walk (W-Billard): Mimics a gas particle bouncing inside a container.
  • Hamiltonian Monte Carlo with Reflections (W-HMC-r): Uses "physics-inspired" trajectories (curves) to explore the space, reflecting when it hits the boundary.

Experimental Evaluation

The researchers evaluated their methods using two primary types of data:

  • Randomly Generated Spectrahedra: Created using a specific stochastic process to ensure they are bounded and have interior points.
  • Elliptopes: A special class of spectrahedra where the exact volume is known analytically, allowing the authors to measure the precision and error of their approximation algorithms.

Key Insights

  • PEP Reduction: The realization that finding the boundary intersection of a polynomial trajectory is equivalent to solving a Polynomial Eigenvalue Problem allows the use of highly optimized numerical solvers.
  • Billiard Superiority: Experimentally, the Billiard Walk mixed much faster and produced more stable results (lower variance) than the traditional Hit-and-Run walk.
  • Exploiting Structure: By using C++ and leveraging state-of-the-art linear algebra libraries, they achieved a $20\times$ speedup over default eigenvalue computations.

Results

  • High-Dimensional Scaling: The implementation (available in the open-source volesti library) successfully sampled from spectrahedra in up to 200 dimensions.
  • Volume Approximation: They approximated the volume of 100-dimensional spectrahedra within a 0.1 relative error in just a few minutes.
  • Optimization via Sampling: They demonstrated that their W-HMC-r walk could be used to solve semidefinite programs (SDPs) by sampling from a "cooling" Boltzmann distribution, showing that sampling-based optimization is a viable alternative to interior-point methods in certain settings.

Discussion and Future Work

While the algorithms perform exceptionally well in practice, there is still a "gap" in the theoretical understanding of the worst-case mixing times for Billiard and HMC-r walks on spectrahedra. Furthermore, the current reflection logic assumes the boundary is "smooth" at the point of impact; handling singularities or non-smooth points more robustly remains an area for refinement. The authors suggest a more detailed practical study on the mixing times of these walks to provide better heuristics for how many steps are needed for a "perfect" sample.

Summary updated

BibTeX
@inproceedings{chalkis2022efficient,
  author = {Apostolos Chalkis and Ioannis Z. Emiris and Vissarion Fisikopoulos and Panagiotis Repouskos and Elias Tsigaridas},
  title = {{Efficient sampling in spectrahedra and volume approximation}},
  booktitle = {Linear},
  year = {2022},
  doi = {10.1016/j.laa.2022.04.002},
}
Figure