9
$\begingroup$

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?

$\endgroup$
0

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What if we work in the Real RAM model - where the registers can store arbitrary-precision real numbers, and each action on real numbers can be done in unit time: is the problem still hard? $\endgroup$ Dec 31, 2023 at 18:23
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @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? $\endgroup$ May 3, 2012 at 13:11
2
$\begingroup$

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

$\endgroup$

Your Answer

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

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