4
$\begingroup$

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?

$\endgroup$
  • 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 '16 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.