SDP Feasibility

Question

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?

Answer 1

No, you can't. If you could, then you would, among other things, have a solution to what is known as the square-root sum 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.

Answer 2

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.

Answer 3

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} }