The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0 $ with $ f_{i}(x) $ being convex in $ x $.

I know ellipsoid method and interior method, but I do not find specific theorems to explain my question.

Can I use the theorem of equivalence of optimization and separation problems in ellipsoid method by setting the objective as a constant e.g. take $c=0$ in the objective $c^{\top}x $?

  • 2
    $\begingroup$ How is the set specified, i.e., what is the input to the problem? You need to be much more precise. The text of the question suggests that you might be talking about intersections of half spaces, i.e., polyhedra given in the "H-representation", in which case checking emptiness is in P (check any standard text on the ellipsoid method for Linear Programming), but your title just refers to a "convex set". $\endgroup$ – Rahul Savani Aug 22 at 5:53
  • $\begingroup$ @Rahul Savani Yes, my concern is on the general convex set represented by set of inequalities like f_i(x)<=0. I will refine the description. Thx $\endgroup$ – IronMan Aug 22 at 7:09
  • $\begingroup$ Checking feasibility of linear programs is as hard as optimizing an objective. See e.g. cstheory.stackexchange.com/questions/20723/… . $\endgroup$ – Emil Jeřábek Aug 22 at 8:30
  • $\begingroup$ @Emil Jeřábek I get the point. Thx $\endgroup$ – IronMan Aug 22 at 8:33
  • 1
    $\begingroup$ I think this is not known to be in polynomial time in general: for example, I think testing the feasibility of an arbitrary SDP is not known to be in P. The ellipsoid method allows you to distinguish between two cases that may not be mutually exclusive: that the convex set contains a ball of some radius $r$, and that the convex set is empty. The running time depends on $\log 1/r$ $\endgroup$ – Sasho Nikolov Aug 22 at 13:28

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.