§ Farkas Lemma

• Reference: Advanced Algorithms by Michael X Goemans

§ Statement

• Either $Ax = b$, $x \geq 0$ has a solution, or
• There exists $y$ such that $A^T y \geq 0$, and $y^T b < 0$. (separating hyperplane).

§ Why both cannot occur at the same time

• See that $y^T Ax = y^T b$, so if $y^T A \geq 0$, and there is a solution vector $x \geq 0$ such that $Ax = b$, then $y^T b = y^T (Ax) = (y^T A) x \geq 0$.
• This contradicts $y^T b < 0$.

§ Geometric Proof

§ Geometric Lemma

• Let $K$ be a closed covex nonempty set in $R^n$.
• Let $b \in R^n$, $b \not \in K$.
• Define a projection $p_b$ of $b$ onto $K$ as the point $x \in K$ such that $||b - x||$ is minimized.
• Then, for all $z \in K$, $(b - p_b)^T (z - p_b) \leq 0$.
• That is, for any point outside the convex set, the vector pointing to the point outside makes a non-acute angle with any vector pointing from the projection to a point in the convex set.

§ Proof of Farkas Lemma

• Assume $Ax = b$, $x \geq 0$ has no solution.
• Let $K = \{ Ax : x \geq 0 \}$ be the "positive cone" generated by the columns of $A$.
• These are, intuitively, all linear combinations of the hyperplanes that define the polytope.
• Note that $b \not in k$ (since $Ax = b$, $x \geq 0$ has no solution).
• Let $p_b$ be the projection of $b$ onto $K$. This has a vector $w$ such that $p = Aw$, for some $w \geq 0$.
• Now, we know by the geometric lemma that $(b - p_b)^T (z - p_b) \leq 0$ for all $z \in K$.
• We can rewrite this as $(b - Aw)^T (Ax - Aw) \leq 0$ for all $x \geq 0$. (substitute $z = Ax$, $x \geq 0$).
• TODO

§ Farkas as Interpolant