Farkas' Lemma

Given $A \in R^{m \times n}$ and $b \in R^n$, the Farkas Lemma states that exactly one of the following holds:

1. $\exists x \in R^n : Ax = b$, $x \ge 0$,
2. $\exists y \in R^m : y^T A \le 0$, $y^T b > 0$.

Geometrically, the first statements says that $b$ is a non-negative linear combination of columns of $A$. Denote the conic combination of columns of $A$ as $P = \{ Ax: \forall x \ge 0\} \subset R^m$. Note that it is a subset of the columns space of $A$.

If $b \notin P$, the second statement is equivalent to that

3. $\exists y \in R^m$, such that $y^T b > 0$ and $\forall z \in P$, we have $y^T z \le 0$.

When (3) holds, clearly (2) holds, as columns of $A$ belong to $P$. On the other hand, every element in $P$ is conic combination of columns of $A$, then $\forall z = Ax \in P$, then $y^T z = y^T (A x) = (y^T A) x \le 0$ by the fact that $y^T A \le 0 \wedge x \ge 0$.

The existence of $y$ is justified as follows: as $P$ is convex and closed, the Separation Theorem states that we can find a point $z^* = A x^*$ in $P$ that satisfies

Let $y = (b - z^*) \in R^m$. Note that $y > 0$ as $b \notin P$ and $P$ is closed. Consider the plane $y^T (x - z^*) = 0$. It has the following properties:

1. Points in $P$ lies on the negative side of the plane, that is $z \in P$, we have $y^T (z - z^*) \le 0$.
2. $b$ is on the positive side of the plane. As $y^T (b - z^*) = y^T y > 0$.
3. It holds that $y^T z^* = 0$, which implies that either $z^* = 0$ or $y$ is normal to $z^*$. To verify this, we move along the line that pass through the vector $z^*$ and note that for any $k \ge 0$, we have $kz^* \in P$, hence $y^T (kz^* - z^*) \le 0$. Replace $k$ with $0$ and $2$ respectively, we have the desired result.
4. It concludes that $z \in P$, $y^T z \le 0$ and $y^T b > 0$.

An equivalent form states that

1. $\exists x \in R^n : Ax \le b$
2. $\exists y \in R^m : y^T A = 0$, $y^T b > 0$, $y \le 0$.

We can prove this by converting statement (2) into an equivalent one:

3. $\exists y \in R^m : y^T A = 0$, $y^T b = 1$, $y \le 0$.

and hence

4. $\exists y \in R^m : (-y)^T [A, b] = [0, -1]$, $-y \ge 0$.

If this doesn't hold, by previous result, we have $\exists (x, \lambda) \in R^{n + 1}$, s,t., $[A, b] (x, \lambda) = Ax + \lambda b \le 0$ and $[0, 1](x, -\lambda) = -\lambda > 0$, which implies that$A \frac{x}{-\lambda} \le b$.

But this can also be verified via their geometrical meanings. We are not going to give all details here, just an example in $R^2$:

Another equivalent form of Farkas Lemma is written as

1. $\exists x \in R^n : Ax \le b$, $x \ge 0$.
2. $\exists y \in R^m : y^T A \le 0$, $y^T b > 0$, $y \le 0$.

Define $P = \{ z \mid \exists x \in R^n : z \ge Ax, x \ge 0\} \subset R^m$.

1. Statement 1 says $b \in Z$.
2. Otherwise, as $P$ is convex and closed

   • $z_1, z_2 \in P \rightarrow \exists x_1, x_2 \ge 0, z_1 \ge Ax_1, z_2 \ge Ax_2$, then $\mu_1 z_1 + \mu_2 z_2 \ge A(\mu_1 x_1 + \mu_2 x_2), \forall \mu_1, \mu_2 \ge 0, \mu_1 + \mu_2 = 1$,

   • Closeness follows from $\ge$ in the definition of $P$. There is a unique point $z^*$ that minimize $||z - b||$ for $z \in Z$. Let $y = (b - z^*) \neq 0$. Then it holds $y^T (b - z^*) = y^T y > 0$ and $y^T(z - z^*) \le 0$ for any $z \in Z$.

   • Similarly, $z^* \in P \rightarrow \exists x \ge 0, z^* \ge Ax \rightarrow k \ge 0, k z^* \ge A (kx) \rightarrow kz \in P$. Then $0 \in P$ and $2z^* \in P$, which implies $- y^T z^* \le 0$ and $y^T z^* \le 0$. Hence $y^T z^* = 0$ and $y^T b = y^T y + y^T z^* > 0$.

   • Further, the fact $z^* + e_i \in Z$ gives $y^T e_i \le 0$ for arbitrary $i$. Therefore $y \le 0$. The $y^T b < 0$ and $y^T A \le 0$ follow from the same proof given above.