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

  1. either belongs to the cone OR

  2. 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?

  • 1
    $\begingroup$ I cannot remember any reeealy easy and intuitive proof of that part. Maybe one proof will be of interest to you -- Matousek and Gartner, in their book, "Understanding and Using Linear Programming", include a couple of demonstrations, including one using Fourier-Motzkin elimination, which is quite straightforward. $\endgroup$
    – Jay
    Apr 7, 2016 at 16:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.