# What is the use/significance of Farkas' lemma?

I worked on an exercise to prove Farkas' lemma, which states that for $A \in \mathbb{R}^{m,n}$ and $b \in \mathbb{R}^n$ exactly one of the following is true:

• There exists $x \ge 0$ such that $Ax=b$.
• There exists $y$ such that $A^T y \ge 0$ and $y^T b < 0$.

This is simply a trivial fact about the separation between two closed convex sets: $S_1 = \{ b \}$ and $S_2 = \{ Ax \mid x \ge 0 \}$.

Given its simplicity, there must be some broader significance or application of this fact. Can anyone enlighten me as to what it is?

• Farkas lemma is the geometric interpretation of Duality in linear programming . – Red shoes Mar 1 '18 at 7:03

$$\{x| x \ge 0, Ax=b\}$$
What Farkas' lemma has promised you is that if you can find such a $y$ such that $A^Ty \ge 0$ and $y^Tb <0$, then you have proven that the set is empty. Farkas lemma has promised us the existence of a certificate $y$ to show that the set is empty.
• Thanks. That sounds useful. Do solvers return a certificate $y$ in cases where the feasible set is empty? And if so, does it give you any other information over and above the fact that the feasible set is empty? Also, is it computationally as easy to search for $y$ as it is to search for $x$? – ted Mar 1 '18 at 7:09
• I can't speak for all solvers, but Cplex does. Looking for $y$ is just another linear programming problem where the feasible region is a subset of $\mathbb{R}^m$. – Siong Thye Goh Mar 1 '18 at 7:24