# Farkas' lemma

(Difference between revisions)
 Revision as of 05:47, 11 July 2009 (edit)m (→Extended Farkas' lemma)← Previous diff Revision as of 05:49, 11 July 2009 (edit) (undo)m (→Extended Farkas' lemma)Next diff → Line 45: Line 45: = Extended Farkas' lemma = = Extended Farkas' lemma = - For any closed convex cone $\mathcal J$ (for definition see [http://en.wikipedia.org/wiki/Convex_cone Convex cone, Wikipedia] or for finite dimension [[Convex cones | Convex cones, Wikimization]] in the Hilbert space $(\mathcal H,\langle\cdot,\cdot\rangle)$, denote by $\mathcal J^\circ$ the polar cone of $\mathcal J$ (for definition see [http://www.convexoptimization.com/wikimization/index.php/Moreau%27s_decomposition_theorem#Moreau.27s_theorem Moreau's theorem] or for finite dimension [http://en.wikipedia.org/wiki/Dual_cone_and_polar_cone Dual cone and polar cone]). + For any closed convex cone $\mathcal J$ (for definition see [http://en.wikipedia.org/wiki/Convex_cone Convex cone, Wikipedia] or for finite dimension [[Convex cones | Convex cones, Wikimization]] in the Hilbert space $(\mathcal H,\langle\cdot,\cdot\rangle)$, denote by $\mathcal J^\circ$ the polar cone of $\mathcal J$ (for definition see [[Moreau%27s_decomposition_theorem#Moreau.27s_theorem | Moreau's theorem]] or for finite dimension [http://en.wikipedia.org/wiki/Dual_cone_and_polar_cone Dual cone and polar cone]). Let $\mathcal K$ be an arbitrary closed convex cone in $\mathcal H$. Let $\mathcal K$ be an arbitrary closed convex cone in $\mathcal H$.

## Revision as of 05:49, 11 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.

## 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: b$ vector and $LaTeX: y\!\in\!\mathcal{K}~$, then $LaTeX: 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$ (for definition see Convex cone, Wikipedia or for finite dimension Convex cones, Wikimization in the Hilbert space $LaTeX: (\mathcal H,\langle\cdot,\cdot\rangle)$, denote by $LaTeX: \mathcal J^\circ$ the polar cone of $LaTeX: \mathcal J$ (for definition see Moreau's theorem or for finite dimension Dual cone and polar cone).

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