In nearly all convex optimization methods that I read about, it is assumed that the problem satisfies [Slater's condition][1], that is, there is a point that strictly satisfies all constraints (the interior of the feasible region is non-empty). What if Slater's condition does not hold - is there a proof that, in this case, convex optimization cannot be solved in polynomial time unless P=NP? In other words: is Slater's condition a necessary condition for solving convex optimization problems in polynomial time? [1]: https://en.wikipedia.org/wiki/Slater%27s_condition