Maximum semidefinite and linear extension complexity of families of polytopes

Gennadiy Averkov, Volker Kaibel, Stefan Weltge

Abstract

This paper introduces a geometric tool to establish lower bounds on the extension complexity of polytopes. By moving from algebraic factorizations to metric geometry—specifically the Hausdorff distance—the authors simplify existing proofs and provide a new upper bound for the linear extension complexity of $0/1$-polytopes.

Introduction: The Extension Complexity Problem

In mathematical optimization, a complex polytope $P$ is often represented as the projection of a simpler set $Q$ in a higher-dimensional space. A linear extension occurs when $Q$ is a higher-dimensional polytope with few facets. Conversely, a semidefinite extension occurs when $Q$ is a spectrahedron, defined by linear matrix inequalities.

A spectrahedron $Q$ in $\mathbb{R}^3$ defined by a semidefinite constraint. Such sets are used in semidefinite extensions of polytopes.

The "extension complexity" is the minimum size of such a $Q$. Proving lower bounds—demonstrating that a shape cannot be represented simply—is a significant challenge. While previous methods relied on complex algebraic "slack matrix factorizations," this work proposes a more intuitive geometric approach.

Methodology: Metric Geometry and Hausdorff Distance

The authors utilize metric geometry and the Hausdorff distance to measure the separation between sets in space. The core of their method involves:

  1. Normalization via John-Löwner Ellipsoids: Every extended formulation is normalized using the unique maximum-volume ellipsoid inscribed in a convex body, placing all representations into a comparable geometric frame.
  2. Volume Counting and Packing: By treating the space of normalized representations as a high-dimensional metric space, the authors show that if a family of polytopes is "well-separated," there is insufficient "room" in low-complexity representation spaces to accommodate all members.
  3. General Lower Bound Formula: Theorem 1 links the cardinality of a polytope family and their minimum pairwise distance to a lower bound on extension complexity.

Key Insights

  • Geometric Packing: Extension complexity is fundamentally constrained by how shapes are packed in space. Distinct geometric shapes require higher-dimensional representations to be distinguished.
  • Simplified Normalization: Using John-Löwner ellipsoids eliminates the need for the complex matrix balancing required in earlier proofs.
  • Addressing the 0/1-Polytope Gap: The authors adapted techniques from boolean circuit theory to establish a previously missing non-trivial upper bound for $0/1$-polytopes.

Key Results

  • General Lower Bounds: A concrete formula for lower bounds based on family cardinality and spatial separation.
  • 0/1-Polytopes: A simpler proof that most $0/1$-polytopes require exponential extension complexity. Additionally, a new upper bound for the linear extension complexity of any $d$-dimensional $0/1$-polytope was established at $O(2^d/d)$, specifically $9 \frac{2^d}{d}$ for $d \ge 4$.
  • Improved Polygon Bounds: For $n$-gons on specific integer grids, the lower bound for semidefinite extension complexity was improved to $\Omega(\sqrt[4]{n})$.

Conclusion and Future Work

While these results provide powerful tools for bounding the maximum complexity within a family, they do not yet allow for the calculation of the exact complexity of a specific, individual polytope. The method's power also depends on the "well-separatedness" of the family. Future research remains focused on the exact asymptotics of extension complexity for $n$-gons.

Summary updated

Abstract

We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance of its members. This result directly implies a known lower bound on the maximum semidefinite extension complexity of 0/1-polytopes. We further show how our result can be used to improve on the corresponding bounds known for polygons with integer vertices. Our geometric proof builds upon nothing else than a simple well-known property of maximum volume inscribed ellipsoids of convex bodies. In particular, it does not rely on factorizations over the semidefinite cone and thus avoids involved procedures of balancing them as required, e.g., in Briët et al. (Math Program 153(1):179–199, 2015). Moreover, we show that the linear extension complexity of every d-dimensional 0/1-polytope is bounded from above by \( O(\frac{2^d}{d}) \).
BibTeX
@article{averkov2018maximum,
  author = {Gennadiy Averkov and Volker Kaibel and Stefan Weltge},
  title = {{Maximum semidefinite and linear extension complexity of families of polytopes}},
  journal = {Math. Program.},
  year = {2018},
  doi = {10.1007/s10107-017-1134-7},
}
Figure