# Farkas' lemma

### From Wikimization

(→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ándor Zoltán Né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 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**)** 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/no_cache/dms/load/img/?IDDOC=261361

# Extended Farkas' lemma

For any closed convex cone in the Hilbert space , 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*.

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