Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to arbitrary precision in time that is polynomial in the input size as well as the precision value. Now can I claim that I have a polynomial time algorithm for my decision problem?

share|improve this question

3 Answers 3

up vote 6 down vote accepted

No, you can't. If you could, then you would, among other things, have a solution to what is known as the square root problem: given $a_1, \ldots, a_n,k$ determine whether $ \sum_{i=1}^n \sqrt{a_i} \leq k.$ This looks like a solvable problem - just compute the square roots- but is actually difficult, because its unclear to what precision the square roots need to be computed. Now observe that this is equivalent to asking whether there is a point $(z_1, \ldots, z_n)$ that makes the following SDP feasible:

$$ \sum_{i=1}^n z_i \leq k, ~~~z_i \geq 0, ~~~~\left( \matrix{ 1 & z_i \cr z_i & a_i} \right) \preceq 0$$

Finally, I suspect you would get better answers if you ask on cstheory.stackexchange.com, which is visited by many of the experts on these sorts of questions.

share|improve this answer

Alex gave a good answer, but I would just like to highlight a subtle problem with your claim about polynomial time solvability of SDPs. This depends on having inner and outer bounding balls to the feasible sets as part of the input. As Alex showed, without the inner ball it can be hard to tell whether the feasible set is infeasible or just extremely small.

Similarly, without the outer bounding ball it can be hard to tell whether the problem is infeasible or only admits extremely large feasible solutions. An example is the problem: \[ \text{minimize}\quad z_n \] \[ \text{subject to}\quad z_0 \geq 2, \quad \begin{bmatrix}1 & z_i \\\ z_i & z_{i+1}\end{bmatrix}\succeq 0. \] The optimal solution has $z_0 = 2$ and $z_{i+1} = z_i^2$ for all $i$, so $z_n = 2^{2^n}$. Even writing down the optimal objective value takes exponentially many bits in binary. It is conceivable that there is some other more compact but still useful encoding scheme (clearly there is for this particular problem, but this is just a toy example). However, I am not aware of any reasonable proposals for such an encoding.

The moral of the story is that the complexity of solving general semidefinite programs is a much more subtle issue than the case of linear programs, a fact which is often downplayed.

share|improve this answer
    
@Noah Stein, I am hoping you get to read this comment (not sure if MO would send you an alert or something), does the situation change if I know that the feasible space is the convex hull of a finite set of rank-$1$ matrices? –  Pawan Aurora May 3 '12 at 13:11

As already answered, the complexity of the SDP feasibility problem is unknown. Some interesting complexity results on this problem are contained in the following paper.

@article{ramana1997exact, title={An exact duality theory for semidefinite programming and its complexity implications}, author={Ramana, M.V.}, journal={Mathematical Programming}, volume={77}, number={1}, pages={129--162}, year={1997}, publisher={Springer} }

share|improve this answer

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.