Farkas' lemma

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Current revision (14:50, 28 September 2016) (edit) (undo)
(References)
 
(23 intermediate revisions not shown.)
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\!\geq\!0~~\forall~y\!\in_{}\!\mathcal{K}\}</math> we get
+
<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\!\mathcal{K}~</math>, then <math>{\displaystyle b^Ty\!<\!0}</math> can only mean <math>b\notin\mathcal{K}^*</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>
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\!\mathcal{K}</math>
+
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/no_cache/dms/load/img/?IDDOC=261361 http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=261361]
+
[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>
-
For any closed convex cone <math>\mathcal J</math> in the Hilbert space <math>(\mathcal H,\langle\cdot,\cdot\rangle)</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>
-
Let <math>\mathcal K</math> be an arbitrary closed convex cone in <math>\mathcal H</math>.
+
Then, the extended Farkas' lemma asserts that <math>\mathcal{K}^{\circ\circ}=\mathcal{K}.</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>
-
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''.
-
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&aacute;ndor Zolt&aacute;n N&eacute;meth) Let <math>z\in\mathcal H</math> be arbitrary. Then, by [[Moreau's decomposition theorem | Moreau's theorem]] we have
+
([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^{\circ\circ}}z=P_{\mathcal K}z=z-P_{\mathcal K^\circ}z.
+
</math>
</math>
</center>
</center>
-
In particular, for any <math>z\in K</math> we have <math>\mathcal K^{\circ\circ}\ni P_{\mathcal K^{\circ\circ}}z=z</math>. Hence, <math>\mathcal \mathcal K^{\circ\circ}\supset K</math>. Similarly, for any <math>z\in K^{\circ\circ}</math> we have <math>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>.
+
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 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.

Contents

Proof

(Dattorro, ch.2.13) 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: \,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq0~~\forall~y\!\in\mathcal{K}\} we get

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.

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://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002165023&physid=PHYS_0006

Extended Farkas' lemma

For any closed convex cone LaTeX: \mathcal{J} in the Hilbert space LaTeX: (\mathbb{H},\langle\cdot,\cdot\rangle) (in particular we can have LaTeX: \mathbb{H}=\mathbb{R}^n), denote by LaTeX: \mathcal{J}^\circ the polar cone of LaTeX: \mathcal{J}.

Let LaTeX: \mathcal{K} be an arbitrary closed convex cone in LaTeX: \mathbb{H}.

Then, the extended Farkas' lemma asserts that LaTeX: \mathcal{K}^{\circ\circ}=\mathcal{K}.

Hence, denoting LaTeX: \mathcal{L}=\mathcal{K}^\circ, it follows that LaTeX: \mathcal{L}^\circ=\mathcal{K}.

Therefore, the cones LaTeX: \mathcal{K} and LaTeX: \mathcal{L} 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 LaTeX: z\in\mathbb H be arbitrary. Then, by Moreau's theorem we have

LaTeX: 
z=P_{\mathcal K}z+P_{\mathcal K^\circ}z

and

LaTeX: 
z=P_{\mathcal K^\circ}z+P_{\mathcal K^{\circ\circ}}z.

Therefore,

LaTeX: P_{\mathcal K}z=P_{\mathcal K^{\circ\circ}}z=z-P_{\mathcal K^\circ}z.

In particular, for any LaTeX: z\in K we have LaTeX: z=P_{\mathcal K}z=P_{\mathcal K^{\circ\circ}}z\in\mathcal K^{\circ\circ}. Hence, LaTeX: \mathcal K \subset \mathcal K^{\circ\circ}. Similarly, for any LaTeX: z\in K^{\circ\circ} we have LaTeX: z=P_{\mathcal K^{\circ\circ}}z= P_{\mathcal K}z\in\mathcal K. Hence, LaTeX: \mathcal K^{\circ\circ}\subset\mathcal K. Therefore, LaTeX: \mathcal K^{\circ\circ}=\mathcal K.

Personal tools