Farkas Lemma

05.11.2012, 15:57

Theend9219

Auf diesen Beitrag antworten »

Farkas Lemma

Meine Frage:
Guten Tag ich habe eine Frage bzgl. mathematischer Optimierung.
Folgende Aufgabe:
Beweisen Sie folgenden Teil aus dem Farkas Lemma
[latex] Für A \el R^(mxn) und b \el R^m gilt: Entweder es gibt x \el R^n mit Ax = b und x>= 0_n oder es gibt ein y \el R^m mit y^T A>= 0_n und y^T b = -1 (aber nicht beides)[\latex]

Meine Ideen:
Ich weiß leider nicht wie ich vorgehen soll .. ich weiß nur das y^T b ein transponierter Vektor ist von v. Und das man das umschreiben kann als <y,b> als Skalarprodukt..
Ich hoffe mir kann jemand helfen

05.11.2012, 17:16

Theend9219

Auf diesen Beitrag antworten »

RE: Farkas Lemma
Guten Tag ich habe eine Frage bzgl. mathematischer Optimierung.
Folgende Aufgabe:
Beweisen Sie folgenden Teil aus dem Farkas Lemma
Für $\begin{eqnarray*} A in R^(mxn) \end{eqnarray*}$ und $\begin{eqnarray*} b in R^m \end{eqnarray*}$ gilt: Entweder es gibt $\begin{eqnarray*} x in R^n \end{eqnarray*}$ mit $\begin{eqnarray*} Ax = b \end{eqnarray*}$ und $\begin{eqnarray*} x>= 0_n \end{eqnarray*}$ oder es gibt ein $\begin{eqnarray*} y in R^m \end{eqnarray*}$ mit $\begin{eqnarray*} y^T A>= 0_n \end{eqnarray*}$ und $\begin{eqnarray*} y^T b = -1 \end{eqnarray*}$ (aber nicht beides)

noch einmal mathematischer geschrieben

05.11.2012, 17:26

magic_hero

Auf diesen Beitrag antworten »

Zeige zunächst, dass beide Aussagen gleichzeitig nicht gelten können, indem du annimmst, beide Aussagen würden gleichzeitig gelten und du das zu einem Widerspruch führst.

Dann hängt es ein wenig von den "Vorkenntnissen" ab: Kennst du den Satz von Weyl und den Trennungssatz? Dann kannst du annehmen, dass die erste Aussage nicht gilt und mithilfe der beiden Sätze zeigen, dass dann die zweite Aussage gilt.

PS: An deiner LaTeX-Formatierung solltest du auch noch arbeiten Augenzwinkern

Augenzwinkern

05.11.2012, 17:38

Theend9219

Auf diesen Beitrag antworten »

Also ich hätte das folgendermaßen gemacht:
$\begin{eqnarray*} "=>" \end{eqnarray*}$ $\begin{eqnarray*} y^T b = y^{T}A x \geq 0 \end{eqnarray*}$
$\begin{eqnarray*} "<=" \end{eqnarray*}$ Angenommen es gibt ein $\begin{eqnarray*} x\geq 0 \end{eqnarray*}$ mit $\begin{eqnarray*} Ax = b => b \in \!\!\!/\ cone (a_1, ... ,a_n) \end{eqnarray*}$ ( $\begin{eqnarray*} a_i \end{eqnarray*}$ Spalten von $\begin{eqnarray*} A \end{eqnarray*}$ ) =>
$\begin{eqnarray*} => \exists y \in R^{m} \end{eqnarray*}$ mit $\begin{eqnarray*} y^{T}b <0 \end{eqnarray*}$
und $\begin{eqnarray*} y^{t} a_i \geq 0 \forall i=1, ... ,n \end{eqnarray*}$
Aber das ist ja bei mir blöd weil das $\begin{eqnarray*} y^{T}b = -1 \end{eqnarray*}$ (negativ ist)

05.11.2012, 17:42

magic_hero

Auf diesen Beitrag antworten »

Ich verstehe nicht, was überhaupt die Folgepfeile besagen sollen, also welche Aussage sie beweisen. Wir haben hier ja keine äquivalente Aussage.

05.11.2012, 17:42

Theend9219

Auf diesen Beitrag antworten »

Das führt zum Widerspruch weil das
y^{T}A \geq 0 ist . Das hatte ich vergessen

Anzeige

05.11.2012, 17:43

Theend9219

Auf diesen Beitrag antworten »

Dann lass ich sie weg Big Laugh

Big Laugh

05.11.2012, 17:44

magic_hero

Auf diesen Beitrag antworten »

Sag doch einfach mal, was für ein Aussage in "=>" beweisen werden soll und was für eine in "<=". (Das meinte ich mit meinem Einwand eben.)

05.11.2012, 17:46

Theend9219

Auf diesen Beitrag antworten »

Ich wollte es von rechts nach links und einmal von links nach rechts zeigen ..
oder ich steh gerade auf dem Schlauch ...

05.11.2012, 17:51

Theend9219

Auf diesen Beitrag antworten »

http://www.math.kit.edu/ianm3/lehre/opti...inklausur07.pdf

Ist auf Seite 2 mein Beweis?

05.11.2012, 17:55

magic_hero

Auf diesen Beitrag antworten »

Im Prinzip ja. Ist bei dir halt etwas spezieller.

05.11.2012, 17:58

Theend9219

Auf diesen Beitrag antworten »

Inwiefern schreibe ich dann bei mir hin
-1 \leq y^{T}b = y^{T} Ax = (A^{T}y)^{T} x \leq 0 Daher widerspruch ?

05.11.2012, 17:58

Theend9219

Auf diesen Beitrag antworten »

Inwiefern schreibe ich dann bei mir hin
$\begin{eqnarray*} -1 \leq y^{T}b = y^{T} Ax = (A^{T}y)^{T} x \leq 0 \end{eqnarray*}$ Daher widerspruch ?

05.11.2012, 18:04

magic_hero

Auf diesen Beitrag antworten »

Bei dir sind die Voraussetzungen anders, aufpassen!

Es gilt u.a.:
$\begin{eqnarray*} y^Tb=-1<br /> (A^Ty)^T=y^TA\geq0_n \end{eqnarray*}$
Setze diese Eigenschaften ein!

( $\begin{eqnarray*} -1\leq0 \end{eqnarray*}$ ist ja eine wahre Aussage und kein Widerspruch!)

05.11.2012, 18:14

Theend9219

Auf diesen Beitrag antworten »

Danke... du bist mir echt eine Hilfe ..

$\begin{eqnarray*} 0 = x^{T}A^{T}b = (Ax)^{T}b = (wegen (Ax=b, x \in R^n) =y^{T}b = -1 \end{eqnarray*}$ Widerspruch ..
Hab ich das nun richtig?

05.11.2012, 18:18

magic_hero

Auf diesen Beitrag antworten »

Wieso sollte die erste Gleichheit gelten? Du weißt nichts über $\begin{eqnarray*} x^TA^Tb \end{eqnarray*}$ , aber wohl über $\begin{eqnarray*} y^TAx \end{eqnarray*}$ , wenn beide Voraussetzungen gelten.
Es sollte am Ende so etwas wie $\begin{eqnarray*} 0 \leq -1 \end{eqnarray*}$ da stehen, das ist der Widerspruch, den man auf diese Weise findet!

05.11.2012, 18:24

Theend9219

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 0 \leq y^{T} b = y^{T}Ax = (A^{T}y)^{T} x \leq -1 \end{eqnarray*}$

05.11.2012, 18:29

magic_hero

Auf diesen Beitrag antworten »

verwirrt

Es gilt doch $\begin{eqnarray*} y^Tb=-1 \end{eqnarray*}$ , dann kann das doch nicht größer gleich 0 sein.... außerdem sind $\begin{eqnarray*} y^TA\geq0 ~und ~x\geq0 \end{eqnarray*}$ nach unserer Annahme, dass beide Aussagen gleichzeitig gelten.

05.11.2012, 18:35

Theend9219

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 0 \leq y^{T}A \leq (A^{T}y)^{T} \leq .... \leq y^{T}b \leq y^{T}Ax \leq -1 \end{eqnarray*}$
Nun weiß ich nicht was dort steht bei den ...

05.11.2012, 18:38

magic_hero

Auf diesen Beitrag antworten »

Jetzt hast du links einen Vektor und rechts eine Zahl.... das ist schlecht (denn die größer-Relation zwischen diesen ist erst mal nicht definiert, sondern grundsätzlich nur zwischen Zahlen). Eigentlich stand in diesem Thread schon mal fast das Richtige:

Zitat:

Original von Theend9219
Inwiefern schreibe ich dann bei mir hin
$\begin{eqnarray*} -1 \leq y^{T}b = y^{T} Ax = (A^{T}y)^{T} x \leq 0 \end{eqnarray*}$ Daher widerspruch ?

Jetzt entferne zunächst mal die beiden Zahlen und Ungleichungszeichen links und rechts (du erhältst $\begin{eqnarray*} y^{T}b = y^{T} Ax = (A^{T}y)^{T} x \end{eqnarray*}$ ) und nutze anschließend aus, was ich gesagt hatte, nämlich $\begin{eqnarray*} y^Tb=-1 \end{eqnarray*}$ (auf der linken Seite) und $\begin{eqnarray*} y^TA\geq0 ~und ~x\geq0 \end{eqnarray*}$ (auf der rechten Seite). Dann steht doch alles da...

05.11.2012, 18:45

Theend9219

Auf diesen Beitrag antworten »

Ich blicke da echt nicht durch .. und danke dir das du dir die Zeit nimmst ...
-1 = y^{T} b = y^{T} Ax (wegen y^{T} \geq 0 und x\geq 0) \geq 0

05.11.2012, 18:45

Theend9219

Auf diesen Beitrag antworten »

Ich blicke da echt nicht durch .. und danke dir das du dir die Zeit nimmst ...
$\begin{eqnarray*} -1 = y^{T} b = y^{T} Ax (wegen y^{T} \geq 0 und x\geq 0) \geq 0 \end{eqnarray*}$

05.11.2012, 18:57

magic_hero

Auf diesen Beitrag antworten »

Die (Un-)Gleichung stimmt, die Begründung nicht ganz. Es ist $\begin{eqnarray*} y^TAx\geq0, ~weil ~y^TA\geq0 ~und ~x\geq0 \end{eqnarray*}$ , weil wir ja angenommen haben, dass beide Aussagen stimmen. Jetzt hast du den gewünschten Widerspruch.

(Noch mal, um das deutlich zu machen: $\begin{eqnarray*} y^TA ~und ~x \end{eqnarray*}$ sind "Vektoren" aus dem $\begin{eqnarray*} \mathbb{R}^n \end{eqnarray*}$ !)

05.11.2012, 18:58

Theend9219

Auf diesen Beitrag antworten »

Dankeschön ... Ich bin dir sehr dankbar ...
Muss ich nun noch irgendetwas zeigen wenn ich den widerspruch habe?

05.11.2012, 19:01

magic_hero

Auf diesen Beitrag antworten »

Bisher hast du nur gezeigt, dass beide Aussagen nicht gleichzeitig stimmen können. Daher bleibt noch zu zeigen, dass, falls eine von beiden Aussagen nicht gilt, die andere gilt!

05.11.2012, 19:07

Theend9219

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} A' = ( A b), c=(0,...,0,-1)^{T} \in R^{m+1}. U = Lin(a^1, ... , a^n), U' = Lin(a'_1,...a'_m,a'_{m+1}), a^{i} \end{eqnarray*}$ ist i-ter Spaltenvektor von $\begin{eqnarray*} A, a'_{i} \end{eqnarray*}$ ist i-ter Zeilenvektor von $\begin{eqnarray*} A' \end{eqnarray*}$ .
Falls $\begin{eqnarray*} Ax = b \end{eqnarray*}$ nicht gilt, d.h das $\begin{eqnarray*} Ax = b \end{eqnarray*}$ nicht lösbar ist, so gilt:
$\begin{eqnarray*} rang (A') = rang (A) +1 \end{eqnarray*}$ und $\begin{eqnarray*} c \in U' \end{eqnarray*}$ (genau dann wenn $\begin{eqnarray*} y^{T}A \end{eqnarray*}$ gilt)

so??

05.11.2012, 19:24

magic_hero

Auf diesen Beitrag antworten »

Du nimmst also an, dass Ax=b, x>=0 nicht lösbar ist. Wie aber aus dem, was du geschrieben hast, folgen soll, dass die andere Aussage gilt, wird mir nicht klar.
A' ist als Produkt von Matrix und Vektor schon mal keine Matrix, sondern ein (Spalten-)Vektor.

05.11.2012, 19:27

Theend9219

Auf diesen Beitrag antworten »

Danke für deine Antwort....
Ja ich weiß auch nicht ... die Aufgabe macht mir sehr zu schaffen .. brauche bei der Aufgabe die 4 Punkte um den Schein zu bekommen .. und im Internet finde ich nichts brauchbares . =( kannst du mir vielleicht nochmal einen denkstoß geben ?

Danke das du mich schon mal so weit gebracht hast ..

05.11.2012, 19:32

magic_hero

Auf diesen Beitrag antworten »

Es ist seltsam, dass du behauptest, du würdest im Internet nichts Brauchbares finden, du aber auch der vorigen Seite was Entsprechendes gepostet hast.... und das ist ziemlich genau das, an das ich gedacht hatte, weil wir das "damals" (ist ein knappes halbes Jahr her) mithilfe vom Satz von Weyl und Trennungssatz bewiesen haben. In deiner Aufgabenstellung sind nur ein paar kleine Änderungen, die leichte Anpassungen an den Beweis erforderlich machen, aber nichts Besonderes. Natürlich funktioniert das aber nur, wenn du den Satz von Weyl und den Trennungssatz kennst... ansonsten musst du halt was anderes benutzen, wie z.B. den starken Dualitätssatz. Das hängt dann aber von deinen Vorkenntnissen ab.

05.11.2012, 19:45

Theend9219

Auf diesen Beitrag antworten »

Ja ich hatte da einen Post gefunden .. brauchbar ja aber anwenden kann ichs dann nicht ..Ich kenn den starken Dualitätssatz ...
$\begin{eqnarray*} M := {x \in R^n : Ax = b, x \geq 0} \end{eqnarray*}$ das f. Lemma kann ich dann äquivalent schreiben als
$\begin{eqnarray*} M\neq \end{eqnarray*}$ leere Menge $\begin{eqnarray*} <=> \end{eqnarray*}$ $\begin{eqnarray*} \forall y \in R^m mit y^{T}A \leq 0_n gilt b^{T}y \leq 0<br /> => \end{eqnarray*}$ Sei M \neq leere Menge . Dann besitzt das primale Problem
$\begin{eqnarray*} (P) Min c^{T}x mit x \in M \end{eqnarray*}$ für $\begin{eqnarray*} x = 0_n \end{eqnarray*}$ eine Lösung $\begin{eqnarray*} x* \in M \end{eqnarray*}$ , da $\begin{eqnarray*} -oo <0 = min(P). \end{eqnarray*}$ Nach dem starken Dualitätssatz folgt dann das duale Problem
(D) $\begin{eqnarray*} Max b^{T}y mit y \in N := {Y \in R^m : A^{T}y \leq c = 0_n} \end{eqnarray*}$

eine Lösung $\begin{eqnarray*} y* \in N \end{eqnarray*}$ hat ( $\begin{eqnarray*} N \neq \end{eqnarray*}$ leere Menge, da $\begin{eqnarray*} 0_m \in N \end{eqnarray*}$ ) Weiter gilt $\begin{eqnarray*} min(P) = max(D) \end{eqnarray*}$ nach dem starken DUalitätssatz
$\begin{eqnarray*} b^{T}y \leq b^{T}y* = max(D) = min(P) = 0^{T}_n x* = 0 \end{eqnarray*}$

also so hab ich das gelernt

05.11.2012, 19:56

magic_hero

Auf diesen Beitrag antworten »

Das ist ja (teilweise) genau das, was auch in dem von dir verlinkten pdf als Beweis steht. Das Problem ist eben, dass deine Aufgabe eine andere Version vom Farkas-Lemma beinhaltet. Du kannst das demnach nicht eins zu eins übernehmen, sondern musst gewisse Anpassungen vornehmen, da bei dir ja z.B. $\begin{eqnarray*} y^Tb=-1 \end{eqnarray*}$ gilt. Aber eigentlich steckt sonst dann nicht mehr etwas Besonderes dahinter. Die Eigenleistung musst du nun schon selbst bringen!

05.11.2012, 20:01

Theend9219

Auf diesen Beitrag antworten »

Ich bin dir sehr dankbar für deine Antworten ...
Kannst du mir das bitte nicht einmal kurz hinschreiben ... hast ja selbst mitbekommen wie lange ich schon an dieser ... Aufgabe hänge.. das würde mich in der Uni retten ... du hast mir so super geholfen . ich bin dir so dankbar ..

muss ich einfach statts $\begin{eqnarray*} b^{T} y \leq 0 \end{eqnarray*}$ immer =-1 schreiben?

05.11.2012, 20:08

magic_hero

Auf diesen Beitrag antworten »

Es wird sich sicherlich das ein oder andere ändern, weil auch noch $\begin{eqnarray*} y^TA\geq0 \end{eqnarray*}$ gilt. ABer ich vermute, dass der Beweis dann trotzdem sehr ähnlich, wenn nicht gar gleich geführt werden kann.

Vormachen kann ich ihn für dich aber nicht, da mir zum einen dazu gerade die Zeit fehlt (ich bin dann gleich auch offline) und du außerdem auch selbst etwas leisten solltest. Und jetzt hast du ja schon eine Vorstellung, wie man an die Aufgabe herangeht und musst nur noch ein paar Kleinigkeiten beachten....

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »