Home Notes Research Fun Stuffs

13 January 2022

Farkas' Lemma

This short exposition is about Farkas’ lemma, a byproduct of the Fourier-Motzkin elimination. Under the same title multiple variants exist, but all of them have a “binary choice” nature. The lemma plays a key role in the theory of linear programming amongst many others.

Farkas’ lemma I. For a linear system of inequalities \(A \vec{x} \leq \vec{b}\), exactly one of the two choices is true:

• either the system is feasible;
• or there exists a “witness of infeasibility” \(\vec{h} \geq \vec{0}\) with \(\vec{h}^\T A = \vec{0}^\T\) but \(\vec{h}^\T \vec{b} = -1\).

The mysterious formulas just mean the following: “We can derive the contradicting inequality \(0 \leq -1\) by appropriate, non-negative weighted sum of the original inequalities (rows).” So at its core, the lemma states a logically stimulating fact: Solving linear system of inequalities via the operation of “non-negative weighted sum” is not only sound but also complete.

Proof of Farkas’ lemma I. Firstly, the choices cannot be simultaneously true; otherwise we come to the absurdity

\[0 = (\vec{h}^\T A) \vec{x} = \vec{h}^\T (A \vec{x}) \leq \vec{h}^\T \vec{b} = -1.\]

Next assume that the first choice is false (i.e. the system is infeasible) and show that the second choice must be true. This basically comes for free from Fourier-Motzkin elimination. Recall that during elimination of \(x_k\) we group the inequalities into three blocks, depending on the coefficient of \(x_k\) being 1, -1 or 0 (no loss of generality up to positive scaling). The “1” and “-1” blocks give rise to upper and lower bounds on \(x_k\), respectively. Then we generate all inequalities of the form “lower ≤ upper” and copy the “0” block. After some thoughts you realise that the procedure is just (inductively) adding non-negative weighted rows of the initial system. Eventually we eliminated all variables, left with a list of comparisons on real numbers. This final system is infeasible since the initial system is infeasible. But then, with proper positive scaling, we must spot a \(0 \leq -1\) in our list. To put it differently, we can generate \(0 \leq -1\) via non-negative weighted sum of the initial system. ∎

Next we provide another variant of Farkas’ lemma.

Farkas’ lemma II. For a linear system of inequalities \(A \vec{x} = \vec{b}, ~\vec{x} \geq \vec{0}^\T\), exactly one of the choices occurs:

• either it is feasible;
• or there exists a witness \(\vec{h}: ~\vec{h}^\T A \geq \vec{0}\) but \(\vec{h}^\T \vec{b} < 0\).

This version has a very nice geometric restatement: Given \(A = \set{ \vec{a}_1, \dots, \vec{a}_n }\) and a vector \(\vec{b}\),

• either \(\vec{b} \in \cone(A)\);
• or there exists a hyperplane \(H: \vec{h}^\T \vec{x} = 0\) such that \(\cone(A) \subseteq H^+\) and \(\vec{b} \in H^-\).

As you might have noticed, it is a special type of separation theorem for convex sets (with slightly different conditions because neither a cone nor a hyperplane is compact).

Proof of Farkas’ lemma II. Note that

\[\begin{align*} A \vec{x} = \vec{b}, ~\vec{x} \geq \vec{0} &\iff \begin{pmatrix} A \\ -A \\ -I \end{pmatrix} \vec{x} \leq \begin{pmatrix} \vec{b} \\ -\vec{b} \\ \vec{0} \end{pmatrix}, \end{align*}\]

so by Farkas’ lemma I we see

\[\begin{align*} \text{feasible} &\iff \exists (\vec{u}, \vec{v}, \vec{w}) \geq \vec{0}: ~(\vec{u}^\T - \vec{v}^\T) A = \vec{w}^\T, ~(\vec{u}^\T - \vec{v}^\T) \vec{b} = -1 \\ &\iff \exists \vec{h}: ~\vec{h}^\T A \geq \vec{0}, ~\vec{h}^\T \vec{b} = -1 \end{align*}\]

as desired. ∎