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. I know that in general I cannot claim that I have a polynomial time algorithm for my decision problem. But if I know that the feasible space of my SDP lies in the convex hull of a finite set of rank-$1$ matrices (having only rational entries), then does the situation improve in my favor or is it still as bad as the general case? Is it wishful thinking that the SDP in this case can be solved exactly?

  • 4
    $\begingroup$ the time is polynomial in input size and the logarithm of the precision value. if you know that in the feasible case the feasible region of the SDP contains a ball of radius at least $\exp(-\mathsf{poly}(n, m, L))$ ($n$ is number of variables, $m$ constraints, $L$ input size), you're fine. but i don't see how you can conclude that in your case $\endgroup$ – Sasho Nikolov May 3 '12 at 13:48
  • $\begingroup$ Thanks for the comment. It would help if you can give pointers to relevant literature. $\endgroup$ – Pawan Aurora May 3 '12 at 18:00
  • 3
    $\begingroup$ “I know that the feasible space of my SDP lies in the convex hull of a finite set of rank-1 matrices (having only rational entries)”: Isn’t this equivalent to the condition that the feasible set is bounded? I doubt that the semidefinite feasibility problem with a bounded feasible set is any easier than the general semidefinite feasibility problem. $\endgroup$ – Tsuyoshi Ito May 4 '12 at 10:35
  • $\begingroup$ for reference take any lecture notes or book chapter on the ellipsoid algorithm. nothing specific about SDP to what I said $\endgroup$ – Sasho Nikolov May 4 '12 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.