Why is the Farkas Lemma so popular?

Question

When studying optimization, the Farkas Lemma is a very common occurrence. It is used in order to obtain a solvability criterion for linear programs, since it states that exactly one of two problems is solvable. Currently I am doing some research on linear programs and I am a little bit confused on why it is that popular.

Why can I not always project out all variables with Fourier-Motzkin elimination and verify if the inequality of the form $b\geq 0$ holds, with the known vector $b$? This seems to be simpler for me.

Can anyone please enlighten me? Thanks in advance!

Answer 1

I also found the following answers: Linear prorams can be solved with cutting plane algorithms. Many of those are based on the Farkas Lemma. In the integer vase the Farkas Lemma has to be modifies. But even this modiefied version can be used for the prove of the algorithms terminating in finite time. Furthermore, is the Farkas Lemma important for the theory of so called totally dual integral systems. A technic that is very helpful for developing solution algorithms for integer programs.

Answer 2

Farkas' Lemma comes in different variants. I prefer the following variant.

The system (1) $A\mathbf x \leq \mathbf b$ has no solution if and only if (2) there exists some $\mathbf u \geq \mathbf 0$ with $\mathbf u^TA = \mathbf 0^T$ and $\mathbf b^T\mathbf u < 0$.

But what does this lemma say? It says that (1) has no solution if and only if it implies the inequality $0 < 0$.

Explanation: The vector $\mathbf u$ consists of non-negative coefficients and (3) $\mathbf u^TA\mathbf x \leq \mathbf u^T\mathbf b$ is a non-negative combination of the inequalities of (1). Moreover (3) is implied by (1) as any solution of (1) is also a solution of (3). In (2) we additionally stipulate that $\mathbf u^TA = \mathbf 0$ and $\mathbf u^T\mathbf b < 0$. Hence, we have $\mathbf 0^T\mathbf x < 0$. Moreover, since $\mathbf 0^T\mathbf x = 0$, we have shown that (1) implies the inequality $0 < 0$.

--- Addition

In practice, one uses the following linear program to check for the solvability of $A \mathbf x \leq \mathbf b$: $$\text{maximize } \mathbf 0^T\mathbf x \text{ s.t. } A\mathbf x \leq \mathbf b.$$ By duality this linear program is infeasible if and only if the dual program $$\text{minimize } \mathbf b^T\mathbf u \text{ s.t. } A^T\mathbf u = \mathbf 0 \text{ and } \mathbf u \geq \mathbf 0$$ is unbounded. But the later is equivalent to Farkas' Lemma as a simple exercise shows.