Farkas's lemma
From Wikipedia, the free encyclopedia
Farkas's lemma is a result in mathematics which is 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 ; or
- for some such that .
The lemma was originally proved by Julius Farkas (Gyula Farkas) in 1902 (Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik 124, p1-27) in a slightly different form. The above formulation is due to Albert W. Tucker in the 1950's.
It is an example of a "theorem of the alternative", that is a theorem stating that of two equations, one or the other has a solution, but not both.
[edit] References
Julius Farkas. "Über die Theorie der Einfachen Ungleichungen". Journal für die Reine und Angewandte Mathematik 124. p1-27