Lemma von Farkas

mathematischer Satz
(Weitergeleitet von Farkas’ Lemma)

Das Lemma von Farkas ist ein mathematischer Hilfssatz (Lemma). Er wurde 1902 von Julius Farkas aus 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 linearen Optimierung und 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.

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

Bearbeiten

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

Bearbeiten
  • 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

Bearbeiten
  • 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.