Farkas' lemma

(Difference between revisions)
 Revision as of 04:08, 9 January 2009 (edit) (→Proof)← Previous diff Revision as of 13:45, 9 January 2009 (edit) (undo)m (Reverted edits by 92.48.203.116 (Talk); changed back to last version by Ranjelin)Next diff → Line 11: Line 11: 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. - m5q7Jx ziiqzqflxkvi, [url=http://yizopuiuroex.com/]yizopuiuroex[/url], [link=http://cyejujpgader.com/]cyejujpgader[/link], http://fqxxafgrxjex.com/ + == Proof == + + '''('''Dattorro''')''' Define a convex cone + * [itex]\mathcal{K}=\{y~|~A^Ty\succeq0\}\quad + whose dual cone is + * [itex]\quad\mathcal{K}^*=\{A_{}x~|~x\succeq0\} + + From the definition of dual cone + [itex]\,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq\!0~~\forall~y\!\in_{}\!\mathcal{K}\} we get + + [itex]y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^* + + rather, + + [itex]A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~|~x\succeq0\} + + Given some [itex]{\displaystyle b} vector and [itex]y\!\in\!\mathcal{K}~, then [itex]{\displaystyle b^Ty\!<\!0} can only mean [itex]b\notin\mathcal{K}^*. + + An alternative system is therefore simply [itex]b\in\mathcal{K}^* + and so the stated result follows. == Geometrical Interpretation == == Geometrical Interpretation ==

Revision as of 13:45, 9 January 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: {\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.