Farkas' lemma

The lemma of Farkas is a mathematical lemma ( lemma). He was (then Austria - Hungary, now Romania) published in 1902 by Julius Farkas from Cluj as "the principle of simple inequalities ". One of the first statements about duality gained this lemma great importance for the development of linear programming and game theory.

The lemma of Farkas can be used to prove the strong duality theorem of linear programming and the set of Kuhn- Tucker. It further serves to treat financial arbitrage theoretical problems.

Set

For any real matrix and each real vector of both systems

Always exactly one solvable. It is well understood component-wise.

Derivation

This statement can be attributed to the geometric observation that two convex polyhedra are exactly then separable by a hyperplane if their intersection is empty.

It can ( 1) be interpreted as the statement that is in the convex cone. The latter has its point of origin and is spanned by the columns of the matrix. If this cone, it follows from always, statement ( 2) does not apply so.

Not in this cone, and is therefore (1 ) is false, then point and convex cone can be separated by a hyperplane. Such hyperplane is defined by an equation. The quality of separation can be specialized in that the cone are in the positive half- space, and in the negative half-space affine function. In particular, for the generating points of the cone and arbitrary positive multiples thereof

From which statement ( 2) follows.

Variants

• The inequality is solvable if and only if for each vector with.

• The inequality system has a solution if and only if for each vector.