Feasible solution existence

Question

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.

Answer 1

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.