Farkas' lemma

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(New page: '''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 t...)
Line 1: Line 1:
-
'''Farkas' lemma''' is a result in [[mathematics]] used amongst other things in the proof of the [[Karush-Kuhn-Tucker|Karush-Kuhn-Tucker theorem]] in [[nonlinear programming]]. It states that if ''A'' is a [[matrix (mathematics)|matrix]] and ''b'' a [[vector space|vector]], then exactly one of the following two systems has a solution:
+
'''Farkas' lemma''' is a result used in the proof of the Karush-Kuhn-Tucker (KKT) theorem from nonlinear programming.
 +
 
 +
It states that if <math>A</math> is a matrix and <math>b</math> a vector, then exactly one of the following two systems has a solution:
* <math>A^Ty\succeq0</math> for some <math>y\,</math> such that <math>b^Ty<0~~</math>
* <math>A^Ty\succeq0</math> for some <math>y\,</math> such that <math>b^Ty<0~~</math>
or in the alternative
or in the alternative
* <math>Ax=b\,</math> for some <math>x\succeq0</math>
* <math>Ax=b\,</math> for some <math>x\succeq0</math>
-
where the notation <math>x\succeq0</math> means that all components of the vector ''x'' are nonnegative.
+
where the notation <math>x\succeq0</math> means that all components of the vector <math>x</math> are nonnegative.
-
The lemma was originally proved by {{harvtxt|Farkas|1902}}. The above formulation is due to [[Albert W. Tucker]] in the 1950s.
+
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.
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.
Line 13: Line 15:
'''('''Dattorro''')''' Define a convex cone
'''('''Dattorro''')''' Define a convex cone
* <math>\mathcal{K}=\{y~|~A^Ty\succeq0\}\quad</math>
* <math>\mathcal{K}=\{y~|~A^Ty\succeq0\}\quad</math>
-
whose [[Dual cone and polar cone|dual cone]] is
+
whose dual cone is
* <math>\quad\mathcal{K}^*=\{A_{}x~|~x\succeq0\}</math>
* <math>\quad\mathcal{K}^*=\{A_{}x~|~x\succeq0\}</math>
-
From the definition of [[Dual cone and polar cone|dual cone]],
+
From the definition of dual cone,
<math>y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*</math>
<math>y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*</math>
Line 30: Line 32:
== References ==
== References ==
-
* {{citation | first1 = Julius (Gulya) | last1 = Farkas | author1-link = Gyula Farkas (natural scientist) | year = 1902 | title = Über die Theorie der Einfachen Ungleichungen | url = http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364 | journal = Journal für die Reine und Angewandte Mathematik | volume = 124 | pages = 1–27 }}.
+
* 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]
-
*R. T. Rockafellar: ''Convex Analysis'', Princeton University Press, 1979 (See Page 200).
+
-
 
+
-
[[Category:Optimization]]
+
-
[[Category:Lemmas]]
+
-
[[de:Farkas’ Lemma]]
+
*R. T. Rockafellar: ''Convex Analysis'', Princeton University Press, 1979 (Page 200).
-
[[fr:Lemme de Farkas]]
+
-
<!--
+
-
[[ja:ファルカシュの定理]][[ja:ファルカシュの補題]]-->
+

Revision as of 00:49, 9 November 2007

Farkas' lemma is a result used in the proof of the Karush-Kuhn-Tucker (KKT) theorem from nonlinear programming.

It states that if LaTeX: A is a matrix and LaTeX: b a vector, then exactly one of the following two systems has a solution:

  • LaTeX: A^Ty\succeq0 for some LaTeX: y\, such that LaTeX: b^Ty<0~~

or in the alternative

  • LaTeX: Ax=b\, for some LaTeX: x\succeq0

where the notation LaTeX: x\succeq0 means that all components of the vector LaTeX: x 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

  • LaTeX: \mathcal{K}=\{y~|~A^Ty\succeq0\}\quad

whose dual cone is

  • LaTeX: \quad\mathcal{K}^*=\{A_{}x~|~x\succeq0\}

From the definition of dual cone,

LaTeX: y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*

rather,

LaTeX: A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~|~x\succeq0\}

Given some LaTeX: {\displaystyle b} vector and LaTeX: y\!\in\!\mathcal{K}~, then LaTeX: {\displaystyle b^Ty\!<\!0} can only mean LaTeX: b\notin\mathcal{K}^*.

An alternative system is therefore simply LaTeX: b\in\mathcal{K}^* and so the stated result follows.

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

  • R. T. Rockafellar: Convex Analysis, Princeton University Press, 1979 (Page 200).
Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Farkas%27_lemma"
Personal tools