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 ${\displaystyle A}$ und jeden reellen Vektor ${\displaystyle b}$ ist von beiden Systemen

(1) ${\displaystyle Ax=b,~x\geq 0}$

(2) ${\displaystyle A^{\top }y\geq 0,~b^{\top }y<0}$

stets genau eines lösbar. Dabei ist ${\displaystyle x\geq 0}$ sowie ${\displaystyle A^{\top }y\geq 0}$ komponentenweise zu verstehen.

Herleitung

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

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

Liegt ${\displaystyle b}$ nicht in diesem Kegel ${\displaystyle C}$, ist also (1) falsch, dann können Punkt und konvexer Kegel durch eine Hyperebene getrennt werden. Eine solche Hyperebene ist durch eine Gleichung ${\displaystyle y^{\top }z-d=0}$ definiert. Die Trennungseigenschaft kann so spezialisiert werden, dass der Kegel ${\displaystyle C}$ im positiven Halbraum und ${\displaystyle b}$ im negativen Halbraum der affinen Funktion ${\displaystyle y^{\top }z-d=0}$ liegen. Insbesondere gilt für die erzeugenden Punkte ${\displaystyle 0,a_{1},\dots ,a_{n}}$ des Kegels und beliebige positive Vielfache davon

${\displaystyle -d\geq 0,~y^{\top }ta_{1}-d\geq 0,\dots ,~y^{\top }ta_{n}-d\geq 0}$ und gleichzeitig ${\displaystyle y^{\top }b<d}$,

woraus Aussage (2) folgt.

Varianten

• Das Ungleichungssystem ${\displaystyle Ax\leq b}$ ist genau dann lösbar, wenn ${\displaystyle y^{\top }b\geq 0}$ für jeden Vektor ${\displaystyle y\geq 0}$ mit ${\displaystyle y^{\top }A=0}$ gilt.

• Das Ungleichungssystem ${\displaystyle Ax\leq b}$ hat genau dann eine Lösung ${\displaystyle x\geq 0}$, wenn ${\displaystyle y^{\top }b\geq 0}$ für jeden Vektor ${\displaystyle y\geq 0}$ mit ${\displaystyle y^{\top }A\geq 0}$ 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.