Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 12 down vote accepted

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

share|improve this answer
2  
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
2  
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
1  
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 Jun 17 at 13:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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