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.