Farkas' lemma
From Wikipedia, the free encyclopedia
Farkas' lemma is a result in mathematics used amongst other things in the proof of the Karush-Kuhn-Tucker theorem in nonlinear programming. It states that if A is a matrix and b a vector, then exactly one of the following two systems has a solution:
for some 
such that 
or in the alternative
for some 
where the notation means that all components of the vector x are nonnegative.
The lemma was originally proved by Farkas (1902). The above formulation is due to Albert W. Tucker in the 1950s.
It is an example of a theorem of the alternative; a theorem stating that of two systems, one or the other has a solution, but not both.
[edit] References
- Farkas, Julius (Gyula) (1902), “Über die Theorie der Einfachen Ungleichungen”, Journal für die Reine und Angewandte Mathematik 124: 1–27, <http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364>.
- R. T. Rockafellar: Convex Analysis, Princeton University Press, 1979 (See Page 200).
