Farkas' lemma
From Wikimization
(→Geometrical Interpretation) |
|||
| Line 32: | Line 32: | ||
== Geometrical Interpretation == | == Geometrical Interpretation == | ||
| - | Farkas' lemma simply states that | + | Farkas' lemma simply states that either vector <math>\,b</math> belongs to convex cone <math>\mathcal{K}^*</math> or it does not. |
| - | either vector <math>\,b</math> belongs to convex cone <math>\mathcal{K}^*</math> | + | |
| - | or it does not. | + | When <math>b\notin\mathcal{K}^*</math>, then there is a vector <math>\,y\!\in\!\mathcal{K}</math> |
| + | normal to a hyperplane separating point <math>\,b</math> from cone <math>\mathcal{K}^*</math>. | ||
== References == | == References == | ||
* Gyula Farkas, Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik, volume 124, pages 1–27, 1902. | * Gyula Farkas, Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik, volume 124, pages 1–27, 1902. | ||
[http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364 http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364] | [http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364 http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364] | ||
Revision as of 13:42, 12 November 2008
Farkas' lemma is a result used in the proof of the Karush-Kuhn-Tucker (KKT) theorem from nonlinear programming.
It states that if is a matrix and
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
are nonnegative.
The lemma was originally proved by Farkas in 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.
Proof
(Dattorro) Define a convex cone
whose dual cone is
From the definition of dual cone,
rather,
Given some vector and
, then
can only mean
.
An alternative system is therefore simply
and so the stated result follows.
Geometrical Interpretation
Farkas' lemma simply states that either vector belongs to convex cone
or it does not.
When , then there is a vector
normal to a hyperplane separating point
from cone
.
References
- Gyula Farkas, Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik, volume 124, pages 1–27, 1902.
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364