<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. 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?</p>

CC BY-SA 3.0
2012-05-03T13:48:30.440Z
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
Sasho Nikolov
CC BY-SA 3.0
2012-05-03T18:00:12.883Z
Thanks for the comment. It would help if you can give pointers to relevant literature.
Pawan Aurora
CC BY-SA 3.0
2012-05-04T10:35:15.703Z
“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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-04T21:11:27.777Z
for reference take any lecture notes or book chapter on the ellipsoid algorithm. nothing specific about SDP to what I said
Sasho Nikolov
<ds.algorithms><semidefinite-programming>
SDP Feasibility
Pawan Aurora
# SDP Feasibility

(Asked by: username_0 on 2012-05-03)

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?

**Tags:** ds.algorithms, semidefinite-programming

> **Comments:**
> **username_1**: 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  
> **username_0**: Thanks for the comment. It would help if you can give pointers to relevant literature.  
> **username_2**: “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.  
> **username_1**: for reference take any lecture notes or book chapter on the ellipsoid algorithm. nothing specific about SDP to what I said  

---

## 0 answers

