Consider the following Theorem of Alternatives:
Let $A \in \mathbb{R}^{n}, b \in \mathbb{R}^{m}.$ Then exactly one of the following statements is true:
(1) $\exists x \in \mathbb{R}^{n} : Ax \leq b$
(2) $\exists p \in \mathbb{R}^{m} : p \geq 0, p^TA = 0, p^Tb < 0.$
Also, Consider Farkas Lemma:
(1) $\exists x \in \mathbb{R}^{n} : Ax = b, x \geq 0$
(2) $\exists p \in \mathbb{R}^{m} : p^TA \geq 0^T, p^Tb < 0.$
Prove Farkas Lemma using the Theorem of Alternatives.
Note: It is possible, and potentially much easier, to prove Farkas Lemma using strong and weak duality, but I am looking for a proof that takes advantage of the Theorem of Alternatives, rather than the duality of Linear Programs.
Best Answer
To prove Farkas' lemma, we must show $\neg (1)\Leftrightarrow (2)$.
[$\neg (1)\Rightarrow (2)$] Note that the system $Ax=b,x\geq 0$ can be written as
$$\begin{bmatrix}A\\-A\\I\end{bmatrix}x\leq\begin{bmatrix}b\\-b\\0\end{bmatrix}.$$
This system is in the form given in the first theorem of the alternative (TOA). Thus, by that TOA, $\exists\ p_1,p_2,p_3\in\mathbb{R}^m_+$ such that
$$(p_1-p_2)^\text{T}A = p_3^\text{T} \quad\text{and}\quad (p_1-p_2)^\text{T}b<0$$
Take $p:=p_1-p_2$ and use that $p_3\geq 0$ to conclude.
[$(2)\Rightarrow\neg(1)$] Suppose (2), and for contradiction suppose (1) as well. Then $p^\text{T}A\geq0^\text{T}$ and $x\geq 0$ imply $p^\text{T}Ax\geq 0$. But $Ax=b$ implies $p^\text{T}Ax=p^\text{T}b\geq 0$, which is a contradiction.