Farkas' lemma

From Wikimization

Revision as of 23:57, 1 November 2007 by Dattorro (Talk | contribs)

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

Farkas' lemma is a result in mathematics used amongst other things in the proof of the Karush-Kuhn-Tucker theorem in 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:

$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 x are nonnegative.

The lemma was originally proved by Template:Harvtxt. 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: 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}^*$ .