- Farkas' lemma
Farkas' lemma is a result in
mathematics stating that a vector is either in a given cone or that there exists a (hyper)plane separating the vector from the cone, but not both. It was originally proved by harvtxt|Farkas|1902. It is used amongst other things in the proof of the Karush-Kuhn-Tucker theorem innonlinear programming .Farkas' lemma 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 or none.Statement of the lemma
Let "A" be an "m" × "n" matrix and "b" an "m"-dimensional vector. Then, exactly one of the following two statements is true:
# There exists an "x" ∈ R"n" such that "Ax" = "b" and "x" ≥ 0.
# There exists an "y" ∈ R"m" such that "ATy" ≥ 0 and "bTy" < 0.Here, the notation "x" ≥ 0 means that all components of the vector "x" are nonnegative.This formulation is due to
Albert W. Tucker in the 1950s.Geometric interpretation
Let "a"1, …, "a""n" ∈ R"m" denote the columns of "A". In terms of these vectors, Farkas' lemma states that exactly one of the following two statements is true:
# There exist non-negative coefficients "x"1, …, "x""n" ∈ R such that "b" = "x"1"a"1 + ··· + "x""n""a""n".
# There exists a vector "y" ∈ R"m" such that "a""i" · "y" ≥ 0 for "i" = 1, …, "n" and "b" · "y" < 0.The vectors "x"1"a"1 + ··· + "x""n""a""n" with nonnegative coefficients constitute the cone of the set {"a"1, …, "a""n"} so the first statement says that "b" is in this cone.
The second statement says that there exists a vector "y" such that the angle of "y" with the vectors "a""i" is at most 90° while the angle of "y" with the vector "b" is more than 90°. The hyperplane normal to this vector has the vectors "a""i" on one side and the vector "b" on the other side. Hence, this hyperplane separates the vectors in the cone of {"a"1, …, "a""n"} and the vector "b".
Farkas' lemma can thus be interpreted geometrically as follows: Given a cone and a vector, either the vector is in the cone or there is a hyperplane separating the vector from the cone, but not both.
Further implications
Farkas' lemma can be varied to many further theories of alternative by simple modifications, such as
Gordan's theorem .References
*.
*R. T. Rockafellar: "Convex Analysis", Princeton University Press, 1979 (See Page 200).
Wikimedia Foundation. 2010.
