= Solution
One form of <Farkas lemma> states that exactly one of the following holds:
$$
\boxed{\exists z\geq0:\ Az=b,\qquad
\exists y:\ A^Ty\geq0,\ b^Ty<0.}
$$
Their mutual exclusion is immediate: if both held, $b^Ty=z^TA^Ty\geq0$.
For existence of the alternative certificate, let $C=\{Az:z\geq0\}$, 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_jd_ja_j=0$ with at least one $d_j>0$. Subtract
$$
t d,\qquad t=\min_{d_j>0}\frac{\lambda_j}{d_j}
$$
from 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> is
$$
\delta_C^*(w)=
\begin{cases}
0,&A^Tw\leq0,\\
+\infty,&\text{otherwise}.
\end{cases}
$$
Indeed a positive pairing with a cone generator can be scaled arbitrarily, while all nonpositive pairings give supremum zero. The <Fenchel-Moreau theorem> now gives
$$
\delta_C(b)=\delta_C^{**}(b)=\sup_{A^Tw\leq0}\langle w,b\rangle.
$$
If $b\notin C$, the left side is infinite, so some feasible $w$ has $\langle w,b\rangle>0$. Taking $y=-w$ gives $A^Ty\geq0$ and $b^Ty<0$. If $b\in C$, the first alternative holds. \b[The biconjugation theorem applied to a closed finitely generated cone proves the alternative.]
For inequalities $Cx\leq d$ with unrestricted $x$, split $x=x_+-x_-$ and add nonnegative slack:
$$
[C,-C,I]\begin{pmatrix}x_+\\x_-\\s\end{pmatrix}=d.
$$
The equivalent <Farkas certificate for linear inequalities> is
$$
y\geq0,\qquad C^Ty=0,\qquad d^Ty<0.
$$
Back to article page
