SDP Feasibility - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T10:33:54Z http://mathoverflow.net/feeds/question/67152 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67152/sdp-feasibility SDP Feasibility Pawan Aurora 2011-06-07T16:07:46Z 2011-06-07T19:14:23Z <p>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?</p> http://mathoverflow.net/questions/67152/sdp-feasibility/67160#67160 Answer by alex o. for SDP Feasibility alex o. 2011-06-07T16:49:27Z 2011-06-07T16:49:27Z <p>No, you can't. If you could, then you would, among other things, have a solution to what is known as the <a href="http://garden.irmacs.sfu.ca/?q=op/complexity_of_square_root_sum" rel="nofollow">square root problem</a>: 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: </p> <p>$$\sum_{i=1}^n z_i \leq k, ~~~z_i \geq 0, ~~~~\left( \matrix{ 1 &amp; z_i \cr z_i &amp; a_i} \right) \preceq 0$$</p> <p>Finally, I suspect you would get better answers if you ask on <a href="http://cstheory.stackexchange.com/" rel="nofollow">cstheory.stackexchange.com</a>, which is visited by many of the experts on these sorts of questions. </p> http://mathoverflow.net/questions/67152/sdp-feasibility/67166#67166 Answer by Noah Stein for SDP Feasibility Noah Stein 2011-06-07T17:20:15Z 2011-06-07T17:41:40Z <p>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.</p> <p>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 &amp; z_i \\ z_i &amp; 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.</p> <p>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.</p> http://mathoverflow.net/questions/67152/sdp-feasibility/67176#67176 Answer by Steven Gortler for SDP Feasibility Steven Gortler 2011-06-07T19:14:23Z 2011-06-07T19:14:23Z <p>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.</p> <p>@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} }</p>