Lemma of Farkas

The Farkas' lemma is a mathematical lemma (Lemma). It was published in 1902 by Julius Farkas from Klausenburg (then Austria-Hungary , now Romania ) as the "Principle of Simple Inequalities". As one of the first statements about duality, this lemma gained great importance for the development of linear optimization and game theory .

Farkas' lemma can be used to prove the strong duality theorem of linear optimization and Kuhn-Tucker 's theorem. It is also used to deal with arbitrage problems based on finance theory.

sentence

For every real matrix and every real vector is of both systems ${\ displaystyle A}$ ${\ displaystyle b}$

(1)

{\ displaystyle Ax = b, ~ x \ geq 0}

(2)

{\ displaystyle A ^ {\ top} y \ geq 0, ~ b ^ {\ top} y <0}

always exactly one solvable. It is to be understood as component-wise. ${\ displaystyle x \ geq 0}$ ${\ displaystyle A ^ {\ top} y \ geq 0}$

Derivation

This statement can be attributed to the geometric observation that two convex polyhedra by if and hyperplane separable , if their intersection is empty. ${\ displaystyle P, Q}$ ${\ displaystyle P \ cap Q}$

(1) can be interpreted as the statement that lies in the convex cone . This has its point at the origin and is spanned by the columns of the matrix . If it lies in this cone, it always follows that statement (2) does not apply. ${\ displaystyle b}$ ${\ displaystyle C = \ {z = Ax: \; x \ geq 0 \}}$ ${\ displaystyle A}$ ${\ displaystyle b}$ ${\ displaystyle y ^ {\ top} A \ geq 0}$ ${\ displaystyle y ^ {\ top} b \ geq 0}$

If (1) is not located in this cone , then the point and the convex cone can be separated by a hyperplane. Such a hyperplane is defined by an equation . The separation property can be specialized so that the cone lies in the positive half-space and in the negative half-space of the affine function . In particular, applies to the generating points of the cone and any positive multiples thereof ${\ displaystyle b}$ ${\ displaystyle C}$ ${\ displaystyle y ^ {\ top} zd = 0}$ ${\ displaystyle C}$ ${\ displaystyle b}$ ${\ displaystyle y ^ {\ top} zd = 0}$ ${\ displaystyle 0, a_ {1}, \ dots, a_ {n}}$

{\ displaystyle -d \ geq 0, ~ y ^ {\ top} ta_ {1} -d \ geq 0, \ dots, ~ y ^ {\ top} ta_ {n} -d \ geq 0}

and at the same time ,

{\ displaystyle y ^ {\ top} b <d}

from which statement (2) follows.

variants

The inequality is solvable if for each vector with valid. ${\ displaystyle Ax \ leq b}$ ${\ displaystyle y ^ {\ top} b \ geq 0}$ ${\ displaystyle y \ geq 0}$ ${\ displaystyle y ^ {\ top} A = 0}$

The system of inequalities has a solution if and only if for every vector with holds. ${\ displaystyle Ax \ leq b}$ ${\ displaystyle x \ geq 0}$ ${\ displaystyle y ^ {\ top} b \ geq 0}$ ${\ displaystyle y \ geq 0}$ ${\ displaystyle y ^ {\ top} A \ geq 0}$

literature

Julius Farkas: Theory of Simple Inequalities. In: Journal for Pure and Applied Mathematics. Volume 124, pp. 1-27.
Alexander Schrijver: Theory of Linear and Integer Programming. In: Wiley Interscience Series in Discrete Mathematics and Optimization. Wiley, 1994, pp. 89ff, ISBN 978-0471982326 .