Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 62 / 3

One form of Farkas lemma states that exactly one of the following holds:Their mutual exclusion is immediate: if both held, $b^{T}y=z^T{A}^{T}y\ge 0$.

For existence of the alternative certificate, let $C=\{Az:z\ge 0\}$, the finitely generated cone of the columns of $A$. It is convex. It is also closed, a fact that must be justified rather than assumed for arbitrary linear images of closed cones. In a representation with dependent active generators, choose a nonzero dependence ${\sum }_j{d}_j{a}_j=0$ with at least one $d_j>0$. Subtractfrom the nonnegative coefficient vector. The represented point is unchanged, all coefficients remain nonnegative, and at least one active coefficient disappears. Iteration produces a representation with independent active columns. For a convergent sequence in $C$, pass to a subsequence using the same independent set, possible because there are finitely many sets. Its coefficients converge through a fixed left inverse, and their limits remain nonnegative. This proves closedness of finitely generated cones.

The indicator functional ${\delta }_C$ is therefore proper, lower semicontinuous and convex. Its Legendre-Fenchel transform isIndeed a positive pairing with a cone generator can be scaled arbitrarily, while all nonpositive pairings give supremum zero. The Fenchel-Moreau theorem now givesIf $b\notin C$, the left side is infinite, so some feasible $w$ has $⟨w,b⟩>0$. Taking $y=-w$ gives $A^{T}y\ge 0$ and $b^{T}y<0$. If $b\in C$, the first alternative holds. The biconjugation theorem applied to a closed finitely generated cone proves the alternative.

For inequalities $Cx\le d$ with unrestricted $x$, split $x=x_{+}-x_{-}$ and add nonnegative slack:The equivalent Farkas certificate for linear inequalities is

Use the standard form $Cz\le d$ with unrestricted $z=(x,y{)}^T$:The nonnegative multipliersatisfies $C^{T}w=0$ and $d^{T}w=-1<0$. This is a Farkas certificate for linear inequalities, so the system is infeasible by Farkas lemma. In scalar form, adding twice the first inequality to the other two produceswhich directly exhibits the contradiction.