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?
The feasible set of the optimization is usually written as
$$\{x| x \ge 0, Ax=b\}$$
We might construct the above feasible set by asking a client what do they desire and we included that criteria in the set above. A natural question to ask is whether the set is non-empty, i.e. whether the optimization problem is infeasible.
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.