# Is the feasible region of this SDP polyhedral?

We have a semidefinite program (SDP) with feasible region containing only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to be true since the 'circular' portion of the cone of semidefinite matrices is due to the extreme rank-$1$ matrices. Any 'curved' boundary of the feasible region must occur from an infinite number of extreme rays.

As a consequence can we claim that this SDP can be solved exactly in polynomial time just like linear programs which too have a polyhedral feasible region?

-

No, even if there is a finite number of feasible rank-1 matrices, the feasible region of an SDP does not have to be polyhedral.

A spectrahedron you see all the time in applications is $S_n = \{X: X \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$, i.e. the set of Gram matrices of $n$ unit vectors. This is, for example, the feasible region for the Goemans-Williamson SDP relaxation for MaxCut. There can be no more than $2^n$ rank-1 matrices in $S_n$, because $xx^T \in S_n$ implies $x_i^2 = 1$ for all $i$, and therefore $x \in \{-1, 1\}^n$.

Now let's look at $S_3$. Write

$$X = \left( \begin{array}{ccc} 1 & x & y\\ x & 1 & z\\ y & z & 1 \end{array} \right)$$

By Sylvester's criterion, $X \succeq 0$ if and only if all principal minors are non-negative. This gives the following inequalities: \begin{align} x^2, y^2, z^2 &\leq 1\\ x^2 + y^2 + z^2 &\leq 1 + 2xyz \end{align} The first three inequalities come from writing the 2-by-2 minors, and the last comes from writing the determinant of $X$.

It's now easy to see this set is not polyhedral. For example, let the set $T$ be the projection of $S_3$ onto the free variables $x, y, z$, and consider $U = T \cap \{(x, y, z): z = 0\}$. Polyhedral sets remain polyhedral after orthogonal projection and intersection with halfspaces, so if $S_3$ is polyhedral, then $U$ is as well. But $U = \{(x, y, 0): x^2 + y^2 \leq 1\}$ is a disc.

In fact there is also a direct geometric argument that $U$ is a disc. If $X$ is the Gram matrix of the vectors $u, v, w$, then setting $z = 0$ means $v \perp w$, and $(x, y)$ are the coordinates of the projection of $u$ onto the plane spanned by $v$ and $w$, expressed in the orthonormal basis given by $v$ and $w$. Since $u$ can be any unit vector, $(x,y)$ can be any vector of length at most $1$.

For illustration, here is the set $T$:

And here you can see that $U$ is a disc:

-
I should say I never tried to visualize this spectrahedron before, and I find it interesting that it simply looks like a slightly inflated version of the tetrahedron formed by the legal rank-1 points. The section which is here shown as a circle, is a square in the tetrahedron. –  Sasho Nikolov Jun 16 at 21:30
Just curious about the second part of my question. Let's say there exists a SDP with polyhedral feasible region. What do you think about its exact polynomial time solvability? Btw thanks for the nice explanation. –  Pawan Aurora Jun 17 at 2:27
Pawan, apriori it is not clear to me that if an SDP is polyhedral, it would have rational vertices, and that seems necessary for exact solvability. But I am having trouble imagining an example. Maybe in all polyhedral examples the PSD constraints don't matter. –  Sasho Nikolov Jun 17 at 3:01
I came across this paper titled 'Polyhedra, Spectrahedra, and Semidefinite Programming' by Motakuri Ramana. From what I understand on skimming through this paper is that there are cases where PSD constraints do matter. I guess it is the possibility of irrational vertices that can make exact solvability hard. –  Pawan Aurora Jun 17 at 3:36
Ya, actually there is a simple example: if for the matrix $X$ above you add the constraints $z = 0$ and $x = y$, then for $x$ you get the segment $[-1/\sqrt{2}, 1/\sqrt{2}]$. –  Sasho Nikolov Jun 17 at 3:51