# Farkas' lemma

### From Wikimization

Line 1: | Line 1: | ||

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

- | It states that if <math>A</math> is a matrix and <math>b</math> a vector, then exactly one of the following two systems has a solution: | + | It states that if <math>\,A\,</math> is a matrix and <math>\,b</math> a vector, then exactly one of the following two systems has a solution: |

* <math>A^Ty\succeq0</math> for some <math>y\,</math> such that <math>b^Ty<0~~</math> | * <math>A^Ty\succeq0</math> for some <math>y\,</math> such that <math>b^Ty<0~~</math> | ||

or in the alternative | or in the alternative | ||

Line 30: | Line 30: | ||

An alternative system is therefore simply <math>b\in\mathcal{K}^*</math> | An alternative system is therefore simply <math>b\in\mathcal{K}^*</math> | ||

and so the stated result follows. | and so the stated result follows. | ||

+ | |||

+ | == Geometrical Interpretation == | ||

+ | Given vector <math>\,b\,</math>, then Farkas' lemma is simply a statement that | ||

+ | either <math>\,b</math> belongs to the convex cone <math>\mathcal{K}^*</math> | ||

+ | or it does not. | ||

== References == | == References == | ||

* 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://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364 http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364] | [http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364 http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D261364] |

## Revision as of 20:07, 10 November 2008

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

## Proof

**(**Dattorro**)** Define a convex cone

whose dual cone is

From the definition of dual cone,

rather,

Given some vector and , then can only mean .

An alternative system is therefore simply and so the stated result follows.

## Geometrical Interpretation

Given vector , then Farkas' lemma is simply a statement that either belongs to the convex cone or it does not.

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