Farkas’ Lemma

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.

Inhaltsverzeichnis

Satz

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

(1) A x = b,~x \geq 0
(2) y^\top A \geq 0,~y^\top b < 0

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

Herleitung

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

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

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

-d\ge 0,~y^\top ta_1-d\ge 0,\dots,~y^\top ta_1-d\ge 0 und gleichzeitig y^\top b<d,

woraus Aussage (2) folgt.

Varianten

  • Das Ungleichungssystem Ax\le b ist genau dann lösbar, wenn y^\top b\ge 0 für jeden Vektor  y\ge0 mit y^\top A=0 gilt
  • Das Ungleichungssystem Ax\le b hat genau dann eine Lösung x\ge0, wenn y^\top b\ge 0 für jeden Vektor  y\ge0 mit y^\top A\ge0 gilt.

Literatur

  • Julius Farkas: Über die Theorie der Einfachen Ungleichungen. In: Journal für die Reine und Angewandte Mathematik. Band 124, Seiten 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.

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Farkas' lemma — is a result in mathematics stating that a vector is either in a given cone or that there exists a (hyper)plane separating the vector from the cone, but not both. It was originally proved by harvtxt|Farkas|1902. It is used amongst other things in… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • Farkas — ist ein ungarischer Familienname, entstanden aus einem Spitznamen, mit der Bedeutung „Wolf“.[1] Als männlicher Vorname entspricht Farkas dem Vornamen Wolfgang. Inhaltsverzeichnis 1 Namensträger 1.1 Vorname …   Deutsch Wikipedia

  • Farkas — ( King Wolf in Hungarian) is a Hungarian surname or a given name (the last corresponds in the Catholic tradition to the German name Wolfgang). The surname may refer to: * Andy Farkas, former American football player, who, along with 9 other… …   Wikipedia

  • Lemma von Farkas — 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… …   Deutsch Wikipedia

  • Gyula Farkas (natural scientist) — Farkas Gyula, or Julius Farkas (March 28, 1847, Sárosd, Fejér megye December 27, 1930, Pestszentlőrinc) was a Jewish Hungarian mathematician and physicist.He attended the gymnasium at Győr (Raab), and studied law and philosophy at Budapest. After …   Wikipedia

  • Gyula Farkas — ([ˈɟula fɒrkɒʃ], auch Julius Farkas) (* 28. März 1847 in Sárosd; † 27. Dezember 1930 in Pestszentlőrinc) war ein ungarischer Physiker und Mathematiker. Nach ihm wurde das Farkas Lemma benannt, ein zentraler Satz in der Dualitätstheorie der… …   Deutsch Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Duales Problem — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Linear programming — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”