# Fastest way to check existence of solution for a linear system of inequalities

What is the fastest way to check if there exists a solution to the inequality $A x \leq b$, with $A \in \mathbb R^{n \times m}$?

I know this can be checked through the phase 1 of a linear programming algorithm, but I would like to know if there exists a faster method. Please note that I do not actually need a feasible point, but I only need to know if there exists one.

If it helps, in my particular case, the set $\{ x : A x \leq b \}$ is a polytope (i.e. it is bounded) and $n > m$.

Thank you very much!

• Maybe you could try $\displaystyle\min_x\|Ax-b-k1\|_2$ where 1 is the vector full of ones and $k$ is a real positive constant. I suppose if it would be faster than phase 1 of your linear programming method would depend a lot of how the matrix $A$ looks. Sep 29, 2017 at 18:53
• Assuming for each line $A_i$ of $A$ the system $A_ix\leq b_i$ has a solution (i.e. whenever $A_i=0$ then $b_i\geq 0$), your question is equivalent to the following: check, whether or not the intersection of a given set of semi-spaces (the solutions of $A_ix\leq b_i$) is empty. are you searching for exact criteria or speed ups that only work in certain special cases?
– Max
Sep 29, 2017 at 19:07
• I'm not sure about the least squares approach: how am I supposed to understand if the polytope is empty from that? I get a zero residual only if there exists a point that is "distant $k$" from each facet, but this is a very particular case... Sep 29, 2017 at 20:22
• Yes, I worked a lot on orthogonal projections of polytopes. But it's not clear to me how can I use Fourier-Motzkin here. Eliminating variables until I find a trivially unfeasible inequality? Thanks. Sep 30, 2017 at 14:28
• @TobiaMarcucci Fourier-Motzkin is also how we (maths students) were introduced to linear optimization. We had to check whether a given polyhedron contains at least one point, and the solution was always Fourier-Motzkin. Of course, you can add a break for the contradiction case. Oct 9, 2017 at 3:24