Maximum Semidefinite and Linear Extension Complexity of Families of Polytopes

Gennadiy Averkov, Volker Kaibel, Stefan Weltge

TL;DR

This paper introduces a new, geometrically intuitive method to derive lower bounds on the "extension complexity" of families of polytopes. This complexity measures how efficiently a polytope can be represented using linear matrix inequalities (LMIs). The authors show that these bounds are directly related to the number of polytopes in the family and their pairwise distances, offering a simpler proof for existing results and opening doors for new insights.

What Problem Does This Paper Address?

In optimization and computer science, we often represent complex sets (like polytopes) using simpler mathematical descriptions. "Extended formulations" are a way to represent a polytope $P$ in a higher-dimensional space using a simpler set $Q$ (a "spectrahedron" defined by linear matrix inequalities) and then projecting $Q$ back to get $P$. The "semidefinite extension complexity" ($sxc(P)$) is the minimum size of the LMI needed for such a representation, and the "linear extension complexity" ($xc(P)$) is the minimum number of linear inequalities.

Finding the maximum extension complexity for a family of polytopes is crucial for understanding the inherent difficulty of certain optimization problems. Existing lower bounds for these maximum complexities (especially for 0/1-polytopes and polygons) were derived using complex combinatorial arguments. This paper aims to provide a simpler, more geometric approach to establish these bounds and explore their implications.

Methods

The core of the paper's contribution lies in a new theorem that relates the maximum semidefinite and linear extension complexity of a family of polytopes to its size (cardinality) and the minimum pairwise Hausdorff distance between its members. The proof is notably geometric, relying on a fundamental property of maximum volume inscribed ellipsoids of convex bodies. This approach avoids the intricate factorization techniques and balancing procedures used in prior work.

The authors also introduce the concept of "normalized extended formulations," which simplifies the representation of polytopes without affecting their extension complexity. This normalization is achieved through a series of lemmas that manipulate the defining equations of spectrahedra and projected spectrahedra.

Datasets

Not discussed in the paper. The paper focuses on theoretical bounds for families of polytopes, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Geometric Simplicity: The paper demonstrates that complex bounds on extension complexity can be derived from simple geometric properties, specifically the relationship between a convex body and its maximum volume inscribed ellipsoid. This offers a more intuitive understanding of the phenomenon.
  • Unified Approach: The new theorem provides a single, powerful tool to derive lower bounds for both semidefinite and linear extension complexities, simplifying previous separate proofs.
  • Direct Link to Family Properties: The bounds are directly tied to the number of polytopes in a family and their geometric separation (Hausdorff distance), offering a clear intuition for why certain families might require complex representations.
  • Improved Bounds for Polygons: The framework is shown to improve existing bounds for polygons with integer vertices.
  • New Upper Bound for 0/1-Polytopes: The paper establishes a new upper bound on the linear extension complexity of $d$-dimensional 0/1-polytopes, showing it's at most $O(2^d/d)$, which is a significant improvement over previous trivial bounds.

Key Results

  • Theorem 1: For a family of $N$ polytopes in $\mathbb{R}^d$ with minimum pairwise Hausdorff distance $\Delta$, contained in a ball of radius $p$, the maximum semidefinite extension complexity $l$ and linear extension complexity $k$ satisfy: $l^2m^2 \gtrsim \frac{\log N}{d(1 + \log(2p/\Delta) + \log \log N)}$, where $m$ is the LMI size. This implies lower bounds on $sxc(P)$ and $xc(P)$ for individual polytopes $P$ in the family.

  • Corollary 8: For a random 0/1-polytope in $\mathbb{R}^d$ ($d \ge 3$), the probability of having a semidefinite extension complexity less than $2^{d/4}$ or a linear extension complexity less than $2^{d/2}$ is exponentially small in $d$.

  • Corollary 9: For integral polygons with $n$ vertices, the paper shows that there exist such polygons with linear and semidefinite extension complexities of order $\Omega(\sqrt{n})$.
  • Theorem 10: For any $d$-dimensional 0/1-polytope $P$ ($d \ge 4$), its linear extension complexity is at most $O(2^d/d)$.

Limitations and Future Work

  • "Vast Majority" vs. Explicit Examples: While the paper (and prior work) shows that the vast majority of 0/1-polytopes have high extension complexity, finding explicit examples of polytopes that achieve these lower bounds remains an open challenge. The current bounds are derived from counting arguments.
  • Generalization of Theorem 1: The paper mentions that Theorem 1 can be generalized to handle extended formulations with multiple LMIs of potentially different sizes, but the full details are not elaborated.
  • Upper Bound for Semidefinite Complexity of 0/1-Polytopes: The paper provides an upper bound for linear extension complexity of 0/1-polytopes. An analogous, tight upper bound for semidefinite extension complexity is not presented.
  • Future Work: The authors hope their geometric proof of Theorem 1 will "open doors for further results." The new framework could potentially be applied to other families of polytopes or lead to tighter bounds in various settings. The explicit construction of polytopes achieving the derived lower bounds is a clear avenue for future research.

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 [Briet, Dadush & Pokutta 2015]. We hope that revealing the geometry behind the phenomenon opens doors for further results. Moreover, we show that the linear extension complexity of every d-dimensional 0/1-polytope is bounded from above by O(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},
}

Loading related content...

Figure