<p>The general convex set should be represented by a set of (generalized) inequalities <span class="math-container">$f_{i}(x)\leq 0 $</span> with <span class="math-container">$ f_{i}(x) $</span> being convex in <span class="math-container">$ x $</span>.</p>

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

<p>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 <span class="math-container">$c=0$</span> in the objective <span class="math-container">$c^{\top}x $</span>?</p>

CC BY-SA 4.0
2019-08-22T05:53:40.713Z
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
CC BY-SA 4.0
2019-08-22T07:09:30.573Z
@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
CC BY-SA 4.0
2019-08-22T08:30:29.100Z
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
CC BY-SA 4.0
2019-08-22T08:33:20.147Z
@Emil Jeřábek I get the point. Thx
DevinY
CC BY-SA 4.0
2019-08-22T13:28:18.223Z
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
CC BY-SA 4.0
2019-08-28T13:55:40.093Z
@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
CC BY-SA 4.0
2019-08-28T14:03:16.383Z
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
CC BY-SA 4.0
2019-08-28T15:15:05.943Z
@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
<cc.complexity-theory><time-complexity><polynomial-time>
How to prove a general convex set is nonempty or empty in polynomial time?
DevinY
# How to prove a general convex set is nonempty or empty in polynomial time?

(Asked by: username_0 on 2019-08-22)

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

**Tags:** cc.complexity-theory, time-complexity, polynomial-time

> **Comments:**
> **username_1**: 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".  
> **username_0**: @username_1 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  
> **username_2**: 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 .  
> **username_0**: @username_2 I get the point. Thx  
> **username_3**: 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$  
> **username_0**: @username_3 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.  
> **username_3**: 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.  
> **username_0**: @username_3  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!  

---

## 0 answers

