Check whether a polyhedron is empty or not

Question

I have a polyhedron of the form $$ P=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Ax}\leq\mathbf{b}\}.$$ This polyhedron is an intersection of two other polyhedra, and I want to know if the intersection exists or not, i.e. how can I check if this polyhedron is an empty set or not? I am looking for an algorithm that is computationally inexpensive.

In my problem, I have more inequalities than the dimension $\mathbf{x}$, so the matrix $\mathbf{A}$ is a tall matrix.

I have already done some research, and I think that maybe the Farka's lemma is helpful, but I have not yet found a proper solution for my problem.

Answer 1

Yes, you can use Farkas' Lemma. One of its variants is

Either the system $Ax\leq b$ for $x\in \mathbb{R}^n$ has a solution, or the system $A^Ty=0$, $b^Ty<0$ for $y\geq 0$ has a solution.

and you can use any linear programming software to solve the latter system.