1
$\begingroup$

I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty.

Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is any feasible solution to a linear program constrained with a lot of linear inequalities. Is it possible to perform the feasibility check without actually optimizing an objective function? I know that there are polynomial time optimization algorithms in O(n^3.5), but is it possible to reduce the time even more by skipping the linear optimization part?

In particular an iterative algorithm may be very beneficial for me, since I'm adding and removing inequalities to the system all the time and after each addition, I'm checking the feasibility again. Thus, the best would be a king of inductive approach which (using some previously collected information) quickly determines if the set stays feasible after addition of a new inequality.

I would prefer to write my own piece of code for this problem instead of using a 3rd party solver library.

I have seen a related post, but my question targets a general set of equations.

$\endgroup$
  • $\begingroup$ Exactly that's what I mean :) $\endgroup$ – Isolin Aug 3 '14 at 20:11
  • $\begingroup$ Yes, based on your comment I improved the question even before you suggested to do so :) $\endgroup$ – Isolin Aug 4 '14 at 18:58
0
$\begingroup$

Theory

There's a simple argument to show you can't help to do that much better. In particular, testing for feasibility of a set of linear inequalities can't be too much easier than optimizing a linear objective function subject to a set of linear inequalities.

Why? If we want to optimize the objective function $\Psi$ subject to a set $\mathcal{S}$ of inequalities, one way to do that is to use binary search on the value of the objective function. This can be done by repeated feasibility testing of a set of linear inequalities of the form $\mathcal{S} \land \Psi \ge c$, where $c$ is a constant. In particular, you use binary search to find the largest value of $c$ such that $\mathcal{S} \land \Psi \ge c$ is feasible.

Very roughly speaking, binary search can be expected to succeed within $O(\lg n)$ iterations. Therefore, testing for feasibility can't be more than $O(\lg n)$ times faster than maximizing an objective function.

Practice

I don't know of any more efficient way to test for feasibility of a set of linear inequalities, than simply to solve a linear program using standard linear solvers. Basically, you pick any old objective function, and use the linear solver to maximize it subject to the set of linear inequalities. I don't know of any procedure that is faster in practice than this straightforward approach.

$\endgroup$
  • $\begingroup$ How to choose the initial $c$ to start the binary search process? $\endgroup$ – hengxin Feb 13 '17 at 12:29
  • $\begingroup$ @hengxin, good point! Is it true that if there is a maximum, then its size is polynomial in the size of the problem? If so, you can start with $c=1$ (the starting point is not critical). Maybe the reduction in the first three paragraphs is invalid.... $\endgroup$ – D.W. Feb 13 '17 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.