imported>부고: /* Literatur */

2016-08-30T13:55:27Z

Literatur

Neue Seite

Das '''Lemma von Farkas''' ist ein mathematischer [[Hilfssatz]] (Lemma). Er wurde 1902 von [[Gyula Farkas|Julius Farkas]] aus [[Cluj-Napoca|Klausenburg]] (damals [[Österreich-Ungarn]], heute [[Rumänien]]) als „Grundsatz der einfachen Ungleichungen“ veröffentlicht. Als eine der ersten Aussagen über Dualität erlangte dieses Lemma große Bedeutung für die Entwicklung der [[Lineare Optimierung|linearen Optimierung]] und die [[Spieltheorie]].

Das Lemma von Farkas kann verwendet werden, um den starken Dualitätssatz der [[lineare Optimierung|linearen Optimierung]] und den [[Karush-Kuhn-Tucker-Bedingungen|Satz von Kuhn-Tucker]] zu beweisen.
Es dient weiter dazu, finanztheoretische [[Arbitrage]]probleme zu behandeln.

== Satz ==
Für jede reelle [[Matrix (Mathematik)|Matrix]] <math>A</math> und jeden reellen [[Vektor]] <math>b</math> ist von beiden Systemen
:(1) <math>A x = b,~x \geq 0</math>
:(2) <math>A^\top y \geq 0,~b^\top y < 0</math>
stets genau eines lösbar. Dabei ist <math>x \geq 0</math> sowie <math>A^\top y \geq 0</math> komponentenweise zu verstehen.

== Herleitung ==
Diese Aussage lässt sich auf die geometrische Beobachtung zurückführen, dass zwei konvexe [[Polyeder]] <math>P, Q</math> genau dann durch eine [[Hyperebene]] [[Trennungssatz|trennbar]] sind, wenn ihr Durchschnitt <math>P\cap Q</math> leer ist.

Dabei kann (1) als die Aussage interpretiert werden, dass <math>b</math> im konvexen Kegel <math>C=\{z=Ax:\;x\ge0\}</math> liegt. Dieser hat seine Spitze im Ursprung und wird von den Spalten der Matrix <math>A</math> aufgespannt. Liegt <math>b</math> in diesem Kegel, so folgt aus <math>y^\top A\ge0</math> immer schon <math>y^\top b\ge 0</math>, Aussage (2) gilt also nicht.

Liegt <math>b</math> nicht in diesem Kegel <math>C</math>, ist also (1) falsch, dann können Punkt und konvexer Kegel durch eine Hyperebene getrennt werden. Eine solche Hyperebene ist durch eine Gleichung <math>y^\top z-d=0</math> definiert. Die Trennungseigenschaft kann so spezialisiert werden, dass der Kegel <math>C</math> im positiven Halbraum und <math>b</math> im negativen Halbraum der affinen Funktion <math>y^\top z-d=0</math> liegen. Insbesondere gilt für die erzeugenden Punkte <math>0,a_1,\dots, a_n</math> des Kegels und beliebige positive Vielfache davon
::<math>-d\ge 0,~y^\top ta_1-d\ge 0,\dots,~y^\top ta_n-d\ge 0</math> und gleichzeitig <math>y^\top b<d</math>,
woraus Aussage (2) folgt.

== Varianten ==

* Das Ungleichungssystem <math>Ax\le b</math> ist genau dann lösbar, wenn <math>y^\top b\ge 0</math> für jeden Vektor <math> y\ge0</math> mit <math>y^\top A=0</math> gilt.

* Das Ungleichungssystem <math>Ax\le b</math> hat genau dann eine Lösung <math>x\ge0</math>, wenn <math>y^\top b\ge 0</math> für jeden Vektor <math> y\ge0</math> mit <math>y^\top A\ge0</math> gilt.

== Literatur ==

* Julius Farkas: [http://gdz.sub.uni-goettingen.de/en/dms/load/img/?PPN=PPN243919689_0124&DMDID=dmdlog4 ''Theorie der einfachen Ungleichungen.''] In: ''Journal für die Reine und Angewandte Mathematik.'' Band 124, S. 1–27.
* Alexander Schrijver: ''Theory of Linear and Integer Programming.'' In: ''Wiley Interscience Series in Discrete Mathematics and Optimization.'' Wiley, 1994, Seiten 89ff, ISBN 978-0471982326.

[[Kategorie:Lineare Optimierung]]
[[Kategorie:Satz (Mathematik)|Farkas]]

Lemma von Farkas - Versionsgeschichte

imported>부고: /* Literatur */