2

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 $?

DevinY
  • 31
  • 3
  • 2
    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". – Rahul Savani Aug 22 '19 at 05:53
  • @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 – DevinY Aug 22 '19 at 07:09
  • 1
    Checking feasibility of linear programs is as hard as optimizing an objective. See e.g. https://cstheory.stackexchange.com/questions/20723/equivalence-of-feasibility-checking-and-optimization-for-linear-systems . – Emil Jeřábek Aug 22 '19 at 08:30
  • @Emil Jeřábek I get the point. Thx – DevinY Aug 22 '19 at 08:33
  • 1
    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$ – Sasho Nikolov Aug 22 '19 at 13:28
  • @Sasho Nikolov I get your point. Thx. But why the solver like CPLEX can determine whether a set is empty or not quickly, e.g., output the 'none' solution, by setting the objective as a constant. – DevinY Aug 28 '19 at 13:55
  • Because there are algorithms that work quite well most of the time in practice. This is not the same as being able to prove a theoretical bound in the worst case. – Sasho Nikolov Aug 28 '19 at 14:03
  • @Sasho Nikolov For some relative simple convex sets, e.g., quadratic or some 2-norm constraints, do we have polynomial algorithm to check feasibility? Books in optimization usually focus on solving an objective assuming a nonempty feasible set is given. When we do not know too much about the feasible set, the feasibility problem really confuses me. Any clues or references provided will be much appreciated! – DevinY Aug 28 '19 at 15:15

0 Answers0