Convex Geometry

Polyhedral Structural Results

Definition: A polyhedron is a set defined by finitely many linear inequalities (and equalities). A polytope is a bounded polyhedron.

It may be the case that a polyhedron has exponentially many vertices but it has only polynomially many facets, for instance this is the case with the bipartite matching polytope.

For a permutation $\sigma \in S_n$, let $1_\sigma \in \mathbb{R}^{n^2}$ be the matrix whose entries of the form $(i, \sigma(i))$ are equal to one, and all other entries are zero. $$BP(n) := \text{conv}\{ 1_\sigma \mid \sigma \in S_n \}$$ We know that $BP(n)$ is given by the following polytope: $$P(n) := \{ X \in \mathbb{R}^{n^2} \mid \sum_{j} x_{i,j} = 1, \sum_i x_{i,j} = 1, 0 \leq x_{i,j} \leq 1 \}. $$

Minkowski-Weyl Theorem: every polyhedron $P$ is finitely generated, i.e., can be written as $$ P = \text{conv}(a_1, \ldots, a_r) + \text{cone}(b_1,\ ldots, b_s)$$ where $a_i$’s are the vertices and $b_i$’s are the extreme rays of $P$.

Spectrahedral Structural Results

Notation for this section: $\mathcal{S}^n$ is the space of symmetric $n \times n$ matrices. $\mathcal{S}^n_+$ is the cone of positive semidefinite matrices, and $\mathcal{S}^n_{++}$ is the cone of positive definite matrices.

Definition: A linear matrix inequality (LMI) is any inequality of the form: $$ A_0 + \sum_{i=1}^m A_i x_i \succeq 0, \ \ A_i \in \mathcal{S}^n. $$

Definition: A spectrahedron is a set defined as the solution set of a LMI. That is, there exist matrices $A_0, \ldots, A_m \in \mathcal{S}^n$ such that $$ S = \{ (b_1, \ldots, b_m) \in \mathbb{R}^m \mid A_0 + \sum_{i=1}^m A_i x_i \succeq 0 \}. $$

Projections of Spectrahedra (Spectrahedral Shadows)

Example 2.9 in [BPT'12] is a simple example of a spectrahedral shadow that is not a spectrahedron.