I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states:
For any convex cone generated by vectors $a_1, a_2, ...a_m \in \mathbb R^n, C=\{x: x=\sum_{i=1}^m \alpha_ia_i,\alpha_i \geq 0\}$, any point $y \in \mathbb R^n$ in the space
either belongs to the cone OR
there is a halfspace through the origin that contains the cone and does not contain $y$, i.e. there is a vector $w \in \mathbb R^n$ such that $w^Ta_i \geq 0$ for all $1 \leq i \leq m$ and $w^Ty < 0$.
I think I understand the first part of the proof -- namely that if (1) if true, then (2) cannot be true, because if both were true, then it means all of the following is true: $Ax=y$, $w^TAx < 0$, and $w^TAx \geq 0$ the latter of which is a contradiction. Please let me know if I've made any errors here.
The second part of the proof -- namely, if (1) is false then (2) must be true -- is where I'm having issues. I've read a few proofs, but most of them either appeal to a different theorem (i.e. separation lemma) or have explanations / notations that are too confusing. Is it possible to come up with a nice, self-contained, intuitive proof for Farkas' Lemma?
