<p>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. </p>

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

<p>Now let's look at $S_3$. Write</p>

<p>$$
X = \left(
\begin{array}{ccc}
1 &amp; x &amp; y\\
x &amp; 1 &amp; z\\
y &amp; z &amp; 1
\end{array}
\right)
$$</p>

<p>By <a href="http://matthewhr.wordpress.com/2013/09/08/sylvesters-criterion-for-positive-semidefinite-matrices-i/" rel="noreferrer">Sylvester's criterion</a>, $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 &amp;\leq 1\\
x^2 + y^2 + z^2 &amp;\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$.</p>

<p>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.</p>

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

<p>For illustration, here is the set $T$:
<img src="https://i.sstatic.net/UeqY1.jpg" alt="enter image description here"></p>

<p>And here you can see that $U$ is a disc:</p>

<p><img src="https://i.sstatic.net/MypN8.jpg" alt="enter image description here"></p>

CC BY-SA 3.0
2014-06-16T21:30:23.753Z
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
CC BY-SA 3.0
2014-06-17T02:27:14.210Z
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
CC BY-SA 3.0
2014-06-17T03:01:43.677Z
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
CC BY-SA 3.0
2014-06-17T03:36:06.287Z
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
CC BY-SA 3.0
2014-06-17T03:51:57.523Z
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
CC BY-SA 3.0
2014-06-17T13:03:03.567Z
Btw isn't sylvester's criterion for positive definiteness ? I thought that for p.S.d you needed to check all principal minors to get an iff.
Suresh Venkat
CC BY-SA 3.0
2014-06-17T14:16:23.973Z
@SureshVenkat Thanks, you are right! I have fixed the answer.
Sasho Nikolov
CC BY-SA 3.0
2014-06-16T18:55:10.650Z
2014-06-17T14:31:54.063Z
2014-06-17T14:31:54.063Z
Sasho Nikolov
<p>We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral? </p>

<p>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.</p>

<p>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?</p>

<convex-optimization><semidefinite-programming><polytope>
Is the feasible region of this SDP polyhedral?
Pawan Aurora
# Is the feasible region of this SDP polyhedral?

(Asked by: username_0 on 2014-06-16)

We have a semidefinite program (SDP) whose feasible region contains 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?

**Tags:** convex-optimization, semidefinite-programming, polytope


---

## 1 answers

### Answer by username_1 on 2014-06-16. Score: 15 | Accepted answer

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](http://matthewhr.wordpress.com/2013/09/08/sylvesters-criterion-for-positive-semidefinite-matrices-i/), $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$:
![enter image description here](https://i.sstatic.net/UeqY1.jpg)

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

![enter image description here](https://i.sstatic.net/MypN8.jpg)

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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}]$.  
> **username_2**: Btw isn't sylvester's criterion for positive definiteness ? I thought that for p.S.d you needed to check all principal minors to get an iff.  
> **username_1**: @SureshVenkat Thanks, you are right! I have fixed the answer.  

---

