Every convex polyhedron is a spectrahedron

Question

I'm trying to show that convex polyhedra are special cases of spectrahedra. This was left as an exercise to the reader in a convex optimization text that I'm reading. I'm not sure how standard the definitions and notation in this book are, so I'll include them below.

---

Notation: Letting $A, B \in \mathbb{R}^{m \times m}$ be symmetric matrices, write $B \succeq A$ if $B - A \succeq 0$, i.e., $B-A$ is positive semidefinite. For vectors $a, b \in \mathbb{R}^n$, write $a \geq b$ if $ a_i \geq b_i \forall i \in \{1, 2, \dots, n\}$.

---

Definition: Given symmetric matrices $A_1, A_2, \dots, A_n, B \in \mathbb{R}^{m \times m}$, the following convex set $$\left\{ x \in \mathbb{R}^n \,\,\middle|\,\, \sum_{i = 1}^n x_i A_i \preceq B \right\}$$ is called a spectrahedron.

---

Definition: Given $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, $\left\{ x \in \mathbb{R}^n \mid Ax \leq b \right\}$ is called a convex polyhedron.

---

My attempt so far:

I've been trying to come up with a representation of a spectrahedron, probably with $B = bb^T$. I was thinking of $AA^T = A_i$ for $i = 1, \dots, n$. But I haven't made much progress with this approach. I figure making a solid guess on the form and then showing "$\subseteq$" and "$\supseteq$" is the best way to prove this.

Answer 1

Given $\mathrm A \in \mathbb{R}^{m \times n}$ and $\mathrm b \in \mathbb{R}^m$, let

$$\mathcal P := \{ \mathrm x \in \mathbb{R}^n \mid \rm A x \leq b \}$$

which is a (convex) $\mathcal H$-polytope (i.e., defined by the intersection of closed half-spaces). Let

$$p_i (\mathrm x) := b_i - a_{i1} x_1 - a_{i2} x_2 - \dots - a_{in} x_n$$

where $i \in \{1, 2, \dots, m\}$, be $n$-variate polynomials of degree $1$. Hence,

$$\mathcal P = \{ \mathrm x \in \mathbb{R}^n \mid p_1 (\mathrm x) \geq 0 \land p_2 (\mathrm x) \geq 0 \land \cdots \land p_m (\mathrm x) \geq 0 \}$$

The conjunction of the $m$ non-strict linear inequalities is equivalent to the following linear matrix inequality (LMI)

$$\mathrm M (\mathrm x) := \mathrm M_0 + x_1 \mathrm M_1 + x_2 \mathrm M_2 + \dots + x_n \mathrm M_n = \begin{bmatrix} p_1 (\mathrm x) & 0 & \ldots & 0\\ 0 & p_2 (\mathrm x) & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & p_m (\mathrm x)\end{bmatrix} \succeq \mathrm O_m$$

where the $m \times m$ diagonal matrices $\mathrm M_0, \mathrm M_1, \dots, \mathrm M_n$ are given by

$$\mathrm M_0 := \begin{bmatrix} b_1 & 0 & \ldots & 0\\ 0 & b_2 & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & b_m\end{bmatrix} \qquad \qquad \mathrm M_j := \begin{bmatrix} -a_{1j} & 0 & \ldots & 0\\ 0 & -a_{2j} & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & -a_{m j}\end{bmatrix}$$

for $j \in \{1, 2,\dots, n\}$. Thus, convex polytope $\mathcal P$ can be defined using an LMI

$$\mathcal P = \{ \mathrm x \in \mathbb{R}^n \mid \mathrm M (\mathrm x) \succeq \mathrm O_m \}$$

and, thus, is a (convex) spectrahedron.

---

convex-analysis discrete-geometry polyhedra polytopes linear-matrix-inequality spectrahedra

Answer 2

I was able to solve this using Johan's hint. Rodrigo's answer is sleeker than mine (albeit the same idea), but I thought that I'd post this as well, since it may be easier to understand for someone with my background or less in this area of math.

---

Let $P$ be a convex polyhedron, defined as $$ P := \left\{ x \in \mathbb{R}^n \middle| Ax \leq b \right\}, $$ where $A = \begin{pmatrix} \vec{a}_1^T \\ \vdots \\ \vec{a}_m^T \end{pmatrix} = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix} \in \mathbb{R}^{m \times n}$ and $b = \begin{pmatrix} b_1 \\ \vdots \\ b_m \end{pmatrix}$.

Define $B := \begin{pmatrix} b_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & b_m \end{pmatrix}$ and $Q_i := \begin{pmatrix} a_{1i} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & a_{mi} \end{pmatrix}$, $i = 1, \cdots, n$.

Note: \begin{align*} \sum_{i=1}^n x_i Q_i = \sum_{i=1}^n x_i \begin{pmatrix} a_{1i} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & a_{mi} \end{pmatrix} &= \begin{pmatrix} \sum_{i=1}^n a_{1i} x_i & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \sum_{i=1}^n a_{mi} x_i \end{pmatrix} \\ &= \begin{pmatrix} \vec{a}_1^T x & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \vec{a}_m^T x \end{pmatrix} \\ &= \begin{pmatrix} \left( Ax \right)_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \left( Ax \right)_m \end{pmatrix}. \end{align*}

Now define the spectrahedron $$ P' := \left\{ x \in \mathbb{R}^n \middle| \sum_{i = 1}^n x_i Q_i \preceq B \right\}. $$

Claim: $P = P'$.

Proof:

"$\subseteq$":

Let $x \in P$, i.e. $Ax \leq b \iff b_i - (Ax)_i \geq 0$ for all $i \in \{1, \cdots, n\}$.

Let $z \in \mathbb{R}^m$. $$ z^T \left(B - \sum_{i=1}^n x_i Q_i \right)z = \sum_{j=1}^m z_j^2 \left( b_j - \left( \sum_{i=1}^n x_i Q_i \right)_{jj} \right), $$ since $B - \sum_{i=1}^n x_i Q_i$ is a diagonal matrix. From the the note above, we have $$ z^T \left(B - \sum_{i=1}^n x_i Q_i \right)z = \sum_{j=1}^m z_j^2 \underbrace{\left( b_j - (Ax)_j \right)}_{\geq 0 \text{ since } x \in P} \geq 0. $$ Hence $B - \sum_{i=1}^n x_i Q_i \succeq 0$ and $x \in P'$.

"$\supseteq$":

Let $x \in P'$, i.e. $z^T \left( B - \sum_{i=1}^n x_i Q_i \right) z \geq 0$ $\forall z \in \mathbb{R}^m$.

Suppose that $Ax \nleq b$.

Define the index set $J := \left\{ j \in \{1, \cdots, m\} \middle| (Ax)_j > b_j \right\}$, which is nonempty by hypothesis.

Define $z \in \mathbb{R}^m$ by $z_j = 1$ if $j \in J$, $z_j = 0$ otherwise. Then \begin{align*} z^T \left( B - \sum_{i=1}^n x_i Q_i \right) z &= \sum_{j \in J} z_j^2 \left( b_j - \left( \sum_{i=1}^n x_i Q_i \right)_{jj} \right) \\ &= \sum_{j \in J} \underbrace{z_j^2}_{=1} \underbrace{ \left( b_j - \left( Ax \right)_j \right) }_{ < 0 \text{ since } j \in J} < 0, \end{align*} which contradicts $x \in P'$. Hence $Ax \leq b$, so $x \in P$.