Farkas' lemma

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(→Proof)
Line 11: Line 11:
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.
-
== Proof ==
+
m5q7Jx <a href="http://ziiqzqflxkvi.com/">ziiqzqflxkvi</a>, [url=http://yizopuiuroex.com/]yizopuiuroex[/url], [link=http://cyejujpgader.com/]cyejujpgader[/link], http://fqxxafgrxjex.com/
-
 
+
-
'''('''Dattorro''')''' Define a convex cone
+
-
* <math>\mathcal{K}=\{y~|~A^Ty\succeq0\}\quad</math>
+
-
whose dual cone is
+
-
* <math>\quad\mathcal{K}^*=\{A_{}x~|~x\succeq0\}</math>
+
-
 
+
-
From the definition of dual cone
+
-
<math>\,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq\!0~~\forall~y\!\in_{}\!\mathcal{K}\}</math> we get
+
-
 
+
-
<math>y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*</math>
+
-
 
+
-
rather,
+
-
 
+
-
<math>A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~|~x\succeq0\}</math>
+
-
 
+
-
Given some <math>{\displaystyle b}</math> vector and <math>y\!\in\!\mathcal{K}~</math>, then <math>{\displaystyle b^Ty\!<\!0}</math> can only mean <math>b\notin\mathcal{K}^*</math>.
+
-
 
+
-
An alternative system is therefore simply <math>b\in\mathcal{K}^*</math>
+
-
and so the stated result follows.
+
== Geometrical Interpretation ==
== Geometrical Interpretation ==

Revision as of 05:08, 9 January 2009

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.

m5q7Jx <a href="http://ziiqzqflxkvi.com/">ziiqzqflxkvi</a>, [url=http://yizopuiuroex.com/]yizopuiuroex[/url], [link=http://cyejujpgader.com/]cyejujpgader[/link], http://fqxxafgrxjex.com/

Geometrical Interpretation

Farkas' lemma simply states that either vector LaTeX: \,b belongs to convex cone LaTeX: \mathcal{K}^* or it does not.

When LaTeX: b\notin\mathcal{K}^*, then there is a vector LaTeX: \,y\!\in\!\mathcal{K} normal to a hyperplane separating point LaTeX: \,b from cone LaTeX: \mathcal{K}^*.

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

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Farkas%27_lemma"
Personal tools