Farkas' lemma

From Wikimization

Jump to: navigation, search

Farkas' lemma is a result used in the proof of the Karush-Kuhn-Tucker (KKT) theorem from nonlinear programming.

It states that if \,A\, is a matrix and \,b a vector, then exactly one of the following two systems has a solution:

  • A^Ty\succeq0 for some y\, such that b^Ty<0~~

or in the alternative

  • Ax=b\, for some x\succeq0

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.

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.

[edit] Proof

(Dattorro) Define a convex cone

  • \mathcal{K}=\{y~|~A^Ty\succeq0\}\quad

whose dual cone is

  • \quad\mathcal{K}^*=\{A_{}x~|~x\succeq0\}

From the definition of dual cone \,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq\!0~~\forall~y\!\in_{}\!\mathcal{K}\} we get

y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*

rather,

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}^*.

An alternative system is therefore simply b\in\mathcal{K}^* and so the stated result follows.

[edit] Geometrical Interpretation

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} normal to a hyperplane separating point \,b from cone \mathcal{K}^*.

[edit] References

  • Gyula Farkas, Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik, volume 124, pages 1–27, 1902.

http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Farkas%27_lemma"
Personal tools