8
$\begingroup$

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?

$\endgroup$

1 Answer 1

15
$\begingroup$

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$: enter image description here

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

enter image description here

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 16, 2014 at 21:30
  • $\begingroup$ 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. $\endgroup$ Jun 17, 2014 at 2:27
  • $\begingroup$ 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. $\endgroup$ Jun 17, 2014 at 3:01
  • 2
    $\begingroup$ 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}]$. $\endgroup$ Jun 17, 2014 at 3:51
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 17, 2014 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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