Farkas' lemma

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(References)
Line 41: Line 41:
* 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/no_cache/dms/load/img/?IDDOC=261361 http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=261361]
 +
 +
 +
= Extended Farkas' lemma =
 +
 +
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>\mathcal 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''.
 +
 +
== 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
 +
 +
<center>
 +
<math>
 +
z=P_{\mathcal K}z+P_{\mathcal K^\circ}z
 +
</math>
 +
</center>
 +
 +
and
 +
 +
<center>
 +
<math>
 +
z=P_{\mathcal K^\circ}z+P_{\mathcal K^{\circ\circ}}z.
 +
</math>
 +
</center>
 +
 +
Therefore,
 +
 +
<center>
 +
<math>
 +
P_{\mathcal K^{\circ\circ}}z=P_{\mathcal K}z=z-P_{\mathcal K^\circ}z.
 +
</math>
 +
</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>.

Revision as of 19:31, 10 July 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.

Contents

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: \,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq\!0~~\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/no_cache/dms/load/img/?IDDOC=261361


Extended Farkas' lemma

For any closed convex cone LaTeX: \mathcal J in the Hilbert space LaTeX: (\mathcal H,\langle\cdot,\cdot\rangle), 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: \mathcal 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.

Proof of extended Farkas' lemma

(Sándor Zoltán Németh) Let LaTeX: z\in\mathcal 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^{\circ\circ}}z=P_{\mathcal K}z=z-P_{\mathcal K^\circ}z.

In particular, for any LaTeX: z\in K we have LaTeX: \mathcal K^{\circ\circ}\ni P_{\mathcal K^{\circ\circ}}z=z. Hence, LaTeX: \mathcal \mathcal K^{\circ\circ}\supset K. Similarly, for any LaTeX: z\in K^{\circ\circ} we have LaTeX: 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