# Farkas' lemma

(Difference between revisions)
 Revision as of 20:38, 10 July 2009 (edit) (→Extended Farkas' lemma)← Previous diff Current revision (14:50, 28 September 2016) (edit) (undo) (→References) (24 intermediate revisions not shown.) Line 7: Line 7: where the notation $x\succeq0$ means that all components of the vector $x$ are nonnegative. where the notation $x\succeq0$ means that all components of the vector $x$ 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 * $\mathcal{K}=\{y~|~A^Ty\succeq0\}\quad$ * $\mathcal{K}=\{y~|~A^Ty\succeq0\}\quad$ whose dual cone is whose dual cone is Line 19: Line 19: From the definition of dual cone From the definition of dual cone - $\,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq\!0~~\forall~y\!\in_{}\!\mathcal{K}\}$ we get + $\,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq0~~\forall~y\!\in\mathcal{K}\}$ we get $y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*$ $y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*$ Line 27: Line 27: $A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~|~x\succeq0\}$ $A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~|~x\succeq0\}$ - Given some ${\displaystyle b}$ vector and $y\!\in\!\mathcal{K}~$, then ${\displaystyle b^Ty\!<\!0}$ can only mean $b\notin\mathcal{K}^*$. + Given some ${\displaystyle b}$ vector and $y\!\in\mathcal{K}~$, then ${\displaystyle b^Ty\!<0}$ can only mean $b\notin\mathcal{K}^*$. An alternative system is therefore simply $b\in\mathcal{K}^*$ An alternative system is therefore simply $b\in\mathcal{K}^*$ Line 35: Line 35: Farkas' lemma simply states that either vector $\,b$ belongs to convex cone $\mathcal{K}^*$ or it does not. Farkas' lemma simply states that either vector $\,b$ belongs to convex cone $\mathcal{K}^*$ or it does not. - When $b\notin\mathcal{K}^*$, then there is a vector $\,y\!\in\!\mathcal{K}$ + When $b\notin\mathcal{K}^*$, then there is a vector $\,y\!\in\mathcal{K}$ normal to a hyperplane separating point $\,b$ from cone $\mathcal{K}^*$. normal to a hyperplane separating point $\,b$ from cone $\mathcal{K}^*$. == 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 $\mathcal{J}$ in the Hilbert space $(\mathbb{H},\langle\cdot,\cdot\rangle)$ (in particular we can have $\mathbb{H}=\mathbb{R}^n)$, denote by $\mathcal{J}^\circ$ the polar cone of $\mathcal{J}.$ - For any closed convex cone $\mathcal J$ in the Hilbert space $(\mathcal H,\langle\cdot,\cdot\rangle)$, denote by $\mathcal J^\circ$ the polar cone of $\mathcal J$. + Let $\mathcal{K}$ be an arbitrary closed convex cone in $\mathbb{H}.$ - Let $\mathcal K$ be an arbitrary closed convex cone in $\mathcal H$. + Then, the extended Farkas' lemma asserts that $\mathcal{K}^{\circ\circ}=\mathcal{K}.$ - Then, the extended Farkas' lemma asserts that $\mathcal K^{\circ\circ}=\mathcal K$. + Hence, denoting $\mathcal{L}=\mathcal{K}^\circ,$ it follows that $\mathcal{L}^\circ=\mathcal{K}.$ - Hence, denoting $\mathcal L=\mathcal K^\circ,$ it follows that $\mathcal L^\circ=\mathcal K$. + Therefore, the cones $\mathcal{K}$ and $\mathcal{L}$ are called ''mutually polar pair of cones''. - Therefore, the cones $\mathcal K$ and $\mathcal L$ 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ándor Zoltán Németh) Let $z\in\mathcal H$ 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 $z\in\mathbb H$ be arbitrary. Then, by [[Moreau's decomposition theorem | Moreau's theorem]] we have
Line 75: Line 78:
- $+ [itex]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. +$ [/itex]
- In particular, for any $z\in K$ we have $\mathcal K^{\circ\circ}\ni P_{\mathcal K^{\circ\circ}}z=z$. Hence, $\mathcal \mathcal K^{\circ\circ}\supset K$. Similarly, for any $z\in K^{\circ\circ}$ we have $z= P_{\mathcal K}z\in\mathcal K$. Hence, $\mathcal K^{\circ\circ}\subset\mathcal K$. Therefore, $\mathcal K^{\circ\circ}=\mathcal K$. + In particular, for any $z\in K$ we have $z=P_{\mathcal K}z=P_{\mathcal K^{\circ\circ}}z\in\mathcal K^{\circ\circ}.$ Hence, $\mathcal K \subset \mathcal K^{\circ\circ}.$ Similarly, for any $z\in K^{\circ\circ}$ we have $z=P_{\mathcal K^{\circ\circ}}z= P_{\mathcal K}z\in\mathcal K.$ Hence, $\mathcal K^{\circ\circ}\subset\mathcal K.$ Therefore, $\mathcal K^{\circ\circ}=\mathcal K.$

## 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.

## 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.

# 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.$