Farkas' lemma

Farkas' lemma is a solvability theorem for a finite system of linear inequalities in mathematics. It was originally proven by the Hungarian mathematician Gyula Farkas. Farkas' lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization ( alternatively, mathematical programming). It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming.

Generalizations of the Farkas' lemma are about the solvability theorem for convex inequalities, i.e., infinite system of linear inequalities. Farkas' lemma belongs to a class of statements called "theorems of the alternative": a theorem stating that exactly one of two systems has a solution.

There are a number of slightly different (but equivalent) formulations of the lemma in the literature. The one given here is due to Gale, Kuhn & Tucker (1951).

Farkas' lemma —  Let ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}}$ and ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}$ . Then exactly one of the following two statements is true:

...
Wikipedia