Farkas' lemma
From Wikimization
(→References) |
|||
(25 intermediate revisions not shown.) | |||
Line 7: | Line 7: | ||
where the notation <math>x\succeq0</math> means that all components of the vector <math>x</math> 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 Farkas in 1902. The above formulation is due to Albert W. Tucker in the 1950s. | + | The lemma was originally proved by [http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=261361 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 13: | ||
== Proof == | == Proof == | ||
- | '''('''Dattorro''')''' Define a convex cone | + | '''('''[http://ccrma.stanford.edu/~dattorro/mybook.html Dattorro, ch.2.13]''')''' 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 is | whose dual cone is | ||
Line 19: | Line 19: | ||
From the definition of dual cone | From the definition of dual cone | ||
- | <math>\,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\ | + | <math>\,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq0~~\forall~y\!\in\mathcal{K}\}</math> we get |
<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 27: | Line 27: | ||
<math>A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~|~x\succeq0\}</math> | <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 | + | 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> | An alternative system is therefore simply <math>b\in\mathcal{K}^*</math> | ||
Line 35: | Line 35: | ||
Farkas' lemma simply states that either vector <math>\,b</math> belongs to convex cone <math>\mathcal{K}^*</math> or it does not. | Farkas' lemma simply states that 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 | + | 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>. | 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://gdz.sub.uni-goettingen.de | + | [http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002165023&physid=PHYS_0006 http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002165023&physid=PHYS_0006] |
- | + | ||
= Extended Farkas' lemma = | = Extended Farkas' lemma = | ||
+ | For any closed convex cone <math>\mathcal{J}</math> in the Hilbert space <math>(\mathbb{H},\langle\cdot,\cdot\rangle)</math> (in particular we can have <math>\mathbb{H}=\mathbb{R}^n)</math>, denote by <math>\mathcal{J}^\circ</math> the polar cone of <math>\mathcal{J}.</math> | ||
- | + | Let <math>\mathcal{K}</math> be an arbitrary closed convex cone in <math>\mathbb{H}.</math> | |
- | + | Then, the extended Farkas' lemma asserts that <math>\mathcal{K}^{\circ\circ}=\mathcal{K}.</math> | |
- | + | Hence, denoting <math>\mathcal{L}=\mathcal{K}^\circ,</math> it follows that <math>\mathcal{L}^\circ=\mathcal{K}.</math> | |
- | + | Therefore, the cones <math>\mathcal{K}</math> and <math>\mathcal{L}</math> are called ''mutually polar pair of cones''. | |
- | + | === notes === | |
+ | For definition of ''convex cone'' see in finite dimension see [[Convex cones | Convex cones, Wikimization]]. | ||
+ | |||
+ | For definition of ''polar cone'' see [[Moreau%27s_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]]. | ||
== Proof of extended Farkas' lemma == | == Proof of extended Farkas' lemma == | ||
- | (S | + | ([http://web.mat.bham.ac.uk/S.Z.Nemeth/ Sándor Zoltán Németh]) Let <math>z\in\mathbb H</math> be arbitrary. Then, by [[Moreau's decomposition theorem | Moreau's theorem]] we have |
<center> | <center> | ||
Line 75: | Line 78: | ||
<center> | <center> | ||
- | <math> | + | <math>P_{\mathcal K}z=P_{\mathcal K^{\circ\circ}}z=z-P_{\mathcal K^\circ}z. |
- | P_{\mathcal K | + | |
</math> | </math> | ||
</center> | </center> | ||
- | In particular, for any <math>z\in K</math> we have <math>\mathcal K^{\circ\circ}\ | + | In particular, for any <math>z\in K</math> we have <math>z=P_{\mathcal K}z=P_{\mathcal K^{\circ\circ}}z\in\mathcal K^{\circ\circ}.</math> Hence, <math>\mathcal K \subset \mathcal K^{\circ\circ}.</math> Similarly, for any <math>z\in K^{\circ\circ}</math> we have <math>z=P_{\mathcal K^{\circ\circ}}z= P_{\mathcal K}z\in\mathcal K.</math> Hence, <math>\mathcal K^{\circ\circ}\subset\mathcal K.</math> Therefore, <math>\mathcal K^{\circ\circ}=\mathcal K.</math> |
Current revision
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.
Contents |
Proof
(Dattorro, ch.2.13) Define a convex cone
whose dual cone is
From the definition of dual cone we get
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://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002165023&physid=PHYS_0006
Extended Farkas' lemma
For any closed convex cone in the Hilbert space (in particular we can have , denote by the polar cone of
Let be an arbitrary closed convex cone in
Then, the extended Farkas' lemma asserts that
Hence, denoting it follows that
Therefore, the cones and are called mutually polar pair of cones.
notes
For definition of convex cone see in finite dimension see Convex cones, Wikimization.
For definition of polar cone see Moreau's theorem.
Proof of extended Farkas' lemma
(Sándor Zoltán Németh) Let be arbitrary. Then, by Moreau's theorem we have
and
Therefore,
In particular, for any we have Hence, Similarly, for any we have Hence, Therefore,