5.4 Farkas’ lemma
Duality gives a short proof of the classical theorem of the alternative.
Theorem 5.4.1 (Farkas’ lemma). Exactly one of the following has a solution: (a) \(Ax \leq b\); (b) \(y \geq 0\) with \(A^{\mathsf T}y = 0\) and \(b^{\mathsf T}y < 0\).
Proof. Both cannot hold: \(0 = (A^{\mathsf T}y)^{\mathsf T}x = y^{\mathsf T}Ax \leq y^{\mathsf T}b < 0\). Suppose (a) fails. The LP “maximise \(0\) subject to \(Ax \leq b\)” (with \(x\) free) is infeasible, so its dual “minimise \(b^{\mathsf T}y\) subject to \(A^{\mathsf T}y = 0\), \(y \geq 0\)” is either infeasible or unbounded. It is feasible (\(y = 0\)), so it is unbounded, and some feasible \(y\) has \(b^{\mathsf T}y < 0\). □
A solution of (b) is a certificate of infeasibility: a non-negative combination of the constraints that reads \(0 \leq \) (a negative number). Solvers return such certificates, and they are easy to check. For \(x_1 + x_2 \leq 2\) and \(x_1 + x_2 \geq 3\), the combination with weights \((\frac 12, \frac 12)\) of \(x_1 + x_2 \leq 2\) and \(-x_1 - x_2 \leq -3\) gives \(0 \leq -\frac 12\) (Software 5.6.3).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.