3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Simply put the linear inequalities of the polyhedron on the diagonal of a matrix. $\endgroup$ – Johan Löfberg Jun 12 '18 at 19:25
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.