How do you tell if a system of linear inequalities has a solution?

A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.

• You can compute the optimum of a linear program by using binary search on feasibility of the program together with an added linear constraint, hence feasibility testing is computationally about as complicated as full-blown linear programming. – Emil Jeřábek Apr 1 '12 at 10:15
• I almost put that comment into my response, but then I started thinking about getting estimates on the biggest possible size of optimum, and decided that it is a little trickier than it looks... – Igor Rivin Apr 1 '12 at 15:19
• @Igor: The optimum is attained at a vertex of the polytope defined by the program, which is a solution of a linear system consisting of a subset of the inequalities turned into equalities. As such, it is polynomially bounded (in terms of bit-length of the numerator and denominator, i.e., logarithmic height). – Emil Jeřábek Apr 1 '12 at 15:39