Farkas-Lemma

[n***@strunk-online.net]

Hi!

Ich beschäftige mich gerade mit Polyedern und da habe ich folgendes
Farkas-Lemma:

Lemma: Sei A eine Matrix im R^(m x n), b in R^m. Dann trifft genau eine der
Alternativen zu:

(i) Ax <= b, x >= 0, x in R^n ist lösbar
(ii) A^T y >= 0, y >= 0, b^T <= 0, y in R^m ist lösbar.


Und jetzt meine Frage: Wie darf ich das Farkas-Lemma anschaulich(!)
verstehen? Gibt es irgendwie eine (geometrische) Beschreibung, was dieses
Lemma in Bezug auf Polyeder zu bedeuten hat? Für Hilfe wäre ich echt
dankbar!

Und weiß hier jemand, wo ich einen Beweis zu obigem Lemma finden kann? Dass
das beides Alternativen sind, ist klar. Aber wie beweise ich z.B. aus
nicht(i) folgt (ii)?
Ich habe hier zwar einen Beweis stehen, der auf einem anderen Farkas-Lemma
(Ax = b usw.) basiert, aber den verstehe ich nicht.

Schönen Tag noch!

Karsten

[Horst Kraemer]

Post by n***@strunk-online.net
Hi!
Ich beschäftige mich gerade mit Polyedern und da habe ich folgendes
Lemma: Sei A eine Matrix im R^(m x n), b in R^m. Dann trifft genau eine der
(i) Ax <= b, x >= 0, x in R^n ist lösbar
(ii) A^T y >= 0, y >= 0, b^T <= 0, y in R^m ist lösbar.

Hier hast Du aber nicht das originale Farkas-Lemma erwischt, sondern
eine etwas elaborierte Folgerung.

Das Lemma von Farkas wird ueblicherweise so formuliert:

Es sind aequivalent (ich schreibe ' fuer ^T)

i) A'y=c, y>=0 ist loesbar

ii) Fuer jedes x mit Ax <=0 gilt c'x <=0

Post by n***@strunk-online.net
Und jetzt meine Frage: Wie darf ich das Farkas-Lemma anschaulich(!)
verstehen? Gibt es irgendwie eine (geometrische) Beschreibung, was dieses
Lemma in Bezug auf Polyeder zu bedeuten hat? Für Hilfe wäre ich echt
dankbar!

Eine Veranschaulichung im R^3. Stelle Dir den Ursprung (0,0,0) als
Ecke eines konvexen Polyeders vor. Hier treffen also 3 oder mehr
Ebenen zusammen. Wir vergessen jetzt den Rest des Polyeders und
betrachten nur die Punktmenge die innerhalb des von den Ebenen
definierten Gebiets liegen.

Diese Punkte erfuellen ein System Ax<=0. Die Zeilen dieser Matrix, die
ja Koeffizieten fuer jeweils eine Halbraum-Ungleichung sind, kann man
als Normalvektoren der Ebenen interpretieren. Wenn Du Dir nun die
Normalvektoren alle im Urprung angeheftet vorstellst, entspricht den
sich im Ursprung schneidenden Flaechen ein Buendel von Normalvektoren,
die in die entgegengesetzte Richtung zeigen, also nach aussen
bezueglich des polyedrischen Punktmenge.

Nun legen wir eine beliebige Ebene durch 0 und betrachten den Halbraum
c'x<=0. Es gibt nun zwei Faelle, wenn 0 eine konvexe Ecke der durch
Ax<=0 definierten polyedrischen Menge ist. Die Ebene bildet einen
"Deckel" auf der Ecke, oder sie geht durch die Menge Ax<=0.

Wenn die Ebene c'x=0 die Ecke "deckelt", und der Normalvektor c der
Ebene nach "aussen" bezueglich P zeigt, ist offenbar ii) erfuellt.

Damit liest sich das Lemma so. Der Halbraum mit mit nach aussen
zeigendem Normalvektor c deckelt P genau dann, wenn c eine positive
Linearkombination der Zeilen von A sind (diese sind ja jeweils nach
aussen zeigenden Normalvektoren der in 0 zusammenstossenden
Halbraueme/Ebenen), d.h. dann wenn c in dem von diesen Normalvektoren
aufgespannten konvexen Kegel liegt. Ist intuitiv wohl klar, oder ?

Post by n***@strunk-online.net
Und weiß hier jemand, wo ich einen Beweis zu obigem Lemma finden kann? Dass
das beides Alternativen sind, ist klar. Aber wie beweise ich z.B. aus
nicht(i) folgt (ii)?
Ich habe hier zwar einen Beweis stehen, der auf einem anderen Farkas-Lemma
(Ax = b usw.) basiert, aber den verstehe ich nicht.

Beweise dieser Gewichtsklasse findest Du in jedem Lehrbuch der
linearen Optimierung.