Lemma von Farkas

Das Lemma v​on Farkas i​st ein mathematischer Hilfssatz (Lemma). Er w​urde 1902 v​on Julius Farkas a​us Klausenburg (damals Österreich-Ungarn, h​eute Rumänien) a​ls „Grundsatz d​er einfachen Ungleichungen“ veröffentlicht. Als e​ine der ersten Aussagen über Dualität erlangte dieses Lemma große Bedeutung für d​ie Entwicklung d​er linearen Optimierung u​nd die Spieltheorie.

Das Lemma von Farkas kann verwendet werden, um den starken Dualitätssatz der linearen Optimierung und den Satz von Kuhn-Tucker zu beweisen. Es dient weiter dazu, finanztheoretische Arbitrageprobleme zu behandeln.

Satz

Für jede reelle Matrix und jeden reellen Vektor ist von beiden Systemen

(1)
(2)

stets genau eines lösbar. Dabei ist sowie komponentenweise zu verstehen.

Herleitung

Diese Aussage lässt sich auf die geometrische Beobachtung zurückführen, dass zwei konvexe Polyeder genau dann durch eine Hyperebene trennbar sind, wenn ihr Durchschnitt leer ist.

Dabei kann (1) als die Aussage interpretiert werden, dass im konvexen Kegel liegt. Dieser hat seine Spitze im Ursprung und wird von den Spalten der Matrix aufgespannt. Liegt in diesem Kegel, so folgt aus immer schon , Aussage (2) gilt also nicht.

Liegt nicht in diesem Kegel , ist also (1) falsch, dann können Punkt und konvexer Kegel durch eine Hyperebene getrennt werden. Eine solche Hyperebene ist durch eine Gleichung definiert. Die Trennungseigenschaft kann so spezialisiert werden, dass der Kegel im positiven Halbraum und im negativen Halbraum der affinen Funktion liegen. Insbesondere gilt für die erzeugenden Punkte des Kegels und beliebige positive Vielfache davon

und gleichzeitig ,

woraus Aussage (2) folgt.

Varianten

  • Das Ungleichungssystem ist genau dann lösbar, wenn für jeden Vektor mit gilt.
  • Das Ungleichungssystem hat genau dann eine Lösung , wenn für jeden Vektor mit gilt.

Literatur

  • Julius Farkas: 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.