Farkas' lemma

Solvability theorem for finite systems of linear inequalities

In mathematics, Farkas' lemma is a solvability theorem for a finite system of linear inequalities. 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. Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden variable theory, given data from any specific set of measurements. 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 and Tucker (1951). Here, the notation means that all components of the vector are nonnegative.

A particularly suggestive and easy to remember version is the following: if a set of linear inequalities has no solution, then a contradiction can be produced from it by linear combination with nonnegative coefficients. In formulas: if is unsolvable then has a solution. Note that is a combination of the left hand sides, a combination of the right hand side of the inequalities. Since the positive combination produces a zero vector on the left and a −1 on the right, the contradiction is apparent. Thus, Farkas' lemma can be viewed as a theorem of logical completeness: is a set of "axioms", the linear combinations are the "derivation rules", and the lemma says that, if the set of axioms is inconsistent, then it can be refuted using the derivation rules.

Farkas's lemma can be varied to many further theorems of alternative by simple modifications, such as Gordan's theorem: Either has a solution 'x', or has a nonzero solution 'y' with 'y' ≥ 0. Common applications of Farkas' lemma include proving the strong duality theorem associated with linear programming and the Karush–Kuhn–Tucker conditions. An extension of Farkas' lemma can be used to analyze the strong duality conditions for and construct the dual of a semidefinite program. It is sufficient to prove the existence of the Karush–Kuhn–Tucker conditions using the Fredholm alternative but for the condition to be necessary, one must apply von Neumann's minimax theorem to show the equations derived by Cauchy are not violated.