Why is the feasible set of solutions to an SDP a spectrahedron?

Question

A spectrahedron is the set $$ S = \left\lbrace (x_1,\cdots,x_m)\in \mathbb{R}^m \quad|\quad A_0+ A_ix_i \succeq 0 \quad i\in [m] \right\rbrace$$

for some given symmetric matrices $A_0, A_1,\cdots, A_m$. An SDP problem is \begin{align*} \text{minimize }& \langle C,X\rangle \\ \langle A_i,X \rangle &= b_i \;\; i=\{1,\cdots m\} \\ X &\succeq 0 \end{align*} where $C,A_i$ are symmetric and $\langle A,X \rangle= Tr(A^TX)=\sum_{ij}A_{ij}X_{ij}$.

How do I see the feasible set of X as in the condition given in the definition of $S$?

Answer 1

The definition of spectrahedron that you've given simply isn't one of the standard definitions of a spectrahedron. The two commonly used definitions are

1. A spectrahedron is a set of matrices in $S^{n}$ (symmetric $n$ by $n$ matrices) such that

$\mbox{tr} (A_{i}X)=b_{i}\;\; i=1, 2, \ldots, m$

$X \succeq 0$.

The feasible set of your SDP is a spectrahedron under this definition.

2. A spectrahedron is a set of vectors $x \in R^{k}$ such that

$A_{0} + \sum_{i=1}^{k} x_{i}A_{i} \succeq 0$

(Note that there is only one $\succeq$ inequality here rather than $m$ as given in the question, but there is a sum of $x_{i}A_{i}$ terms lacking in the definition given in the question.)

An important point is that the Lagrangian dual of the SDP based on definition 1 is an optimization problem over a definition 2 spectrahedron.

Since the second definition says that the spectrahedron is a set of vectors in $R^{k}$ and the first says that the spectrahedron is a set of matrices in $S^{n}$, they clearly aren't exactly the same. However, it turns out that these two definitions are essentially equivalent in that any spectrahedron under definition 1 is related to a definition 2 spectrahedron as shown by the following construction.

To find a definition 2 spectrahedron from a definition 1 spectrahedron,

1. Find a symmetric matrix $B_{0}$ such that

$\mbox{tr}(A_{i}B_{0})=b_{i}\;\; i=1, 2, \ldots, m$

If no such matrix exists, then the original SDP is infeasible and the spectrahedron is the empty set.

2. Find a basis (of symmetric matrices) for the null space of the linear system of equations

$V=\left\{ X\in S^{n} |\; \mbox{tr}(A_{i}X)=0 \;\; i=1, 2, \ldots, m \right\}$

Call this basis $B_{1}$, $B_{2}$, $\ldots$, $B_{k}$

3. Then

$\left\{ X \in S^{n} |\; \mbox{tr}(A_{i}X)=b_{i}\;\; i=1, 2, \ldots, m,\; X \succeq 0 \right\}= \left\{B \in S^{n} | B=B_{0}+x_{1}B_{1}+\ldots +x_{k}B_{k},\; B \succeq 0 \right\}$.

The set on the right is a set of matrices in $S^{n}$ rather than a definition 2 spectrahedron, but the coefficients $x_{i}$ are the elements of a definition 2 spectrahedron with matrices $B_{0}$, $B_{1}$, $\ldots$, $B_{k}$.

This construction is sometimes useful in modeling with semidefinite programming. If you have a very highly constrained SDP problem, then it can sometimes be useful to switch from the definition 1 spectrahedral constraints to definition 2 spectrahedral constraints.