\
Hallo,


ich betrachte gerade den folgenden Satz:

\big\Satz__
Sei V(X) := menge(v^1, ..., v^q) die Menge der Ecken von X. Wenn das Problem
lex-max menge(Cx: Ax=b, x>=0)
ein lex-Maximum hat, dann gilt
lex-max menge(Cx: x \in X) = lex-max menge(Cx: x \in V(X))

Beweis__:
Sei v_j \in V(X), so dass
C v^j = lex-max menge(Cx: x \in V(X)).
.
.
.

Warum sollte es so eins geben? Das steht ja nicht in der Voraussetzung.

Edit: X:=menge(x: Ax=b,x>=0)

Liebe Grüße
Chris

\
lex-max menge(Cx: x \in X)

\
Vielleicht schildere ich das Problem noch genauer:

Seien X eine (möglicherweise unbeschränkte) polyedrische Menge in \IR^n und C eine k \cross n - Matrix. Zeigen Sie, wenn Problem 
lex - max menge(Cx: x \in X) ein lexikografisches Maximum hat, dann gilt
lex - max menge(Cx: x \in X) = lex - max menge(Cx: x \in V(X),
wobei V(X) = menge(v^1, ..., v^q) die Menge aller Ecken von X ist.

Kann vielleicht jetzt jemand helfen?

Liebe Grüße
Chris

\
Hallo und vielen lieben Dank für deine Antwort.

Ich habe eine halbe Stunde darüber nachgedacht und kam zu folgendem. Ist es korrekt, dass jede zulässige Lösung schon eine Seite__ von X ist?

Liebe Grüße
Chris

Edit: Nein, bisher ist mir noch nicht klar geworden worauf du hinaus möchtest.

\
Ok. Hier ist eine Ecke dadurch charakterisiert, dass sie nicht als echte Konvexkombination zweier Punkte aus X dargestellt werden kann.

Der Beweis beginnt also wie folgt.

Ann__.: z ist keine Ecke von X.
=> \exists u, v != z aus X so, dass
z = \lambda u + (1-\lambda) v, \lambda \in intervall(0,1).

\
Hm, wieso?

Die Frage ist doch ob die Optimallösung von

\
lex-max menge(Cx: x \in X)

\
Tippfehler gemeint ist in beiden Fällen das große C aus der Aufgabe.
C kann man als Abbildung interpretieren C(x)=C*x. Es ist üblich solche Abbildungen auf Mengen zu verallgemeinern, nämlich: C(X):=menge(C(x) : x\in X). Zur Abkürzung schreibt man für C(X) auch C*X oder CX (analog zu C*x und Cx).

Kitaktus

\
Mir fällt gerade auf, dass die Beweisidee eine kleine Lücke hat. Die schauen wir uns später an.

x ist eine Konvexkombination von r und s. Da C eine lineare Abbildung ist, ist auc C*x eine Konvexkombination von C*r und C*s. Es gibt zwei Möglichkeiten: C*x!=C*r oder C*x=C*r. Im ersten Fall suchen wir die erste Komponente k, in der sich Cx und Cr unterscheiden. Wenn Cx und Cr in den ersten k-1 Komponenten übereinstimmen, dann stimmen dort auch Cx und Cs überein. In der k\-ten Komponente kann aber nicht gleichzeitig (Cx)_k>(Cr)_k und (Cx)_k>=(Cs)_k gelten. Folglich ist entweder Cr oder Cs lexikographisch größer als Cx.

Es bleibt noch der etwas lästige Fall Cx=Cr=Cs \(das ist die Lücke von der ich sprach\).
Am einfachsten kann man den erledigen, wenn man für r eine Ecke wählt. Wenn Cx das lexikographische Maximum ist, weiß man dann sofort, dass es auch eine Ecke (nämlich r) mit selben Wert Cr=Cx gibt, die also ebenfalls lexikographisches Maximum ist.
Wie kann man so eine Ecke r finden? Liegt x im (relativen) Inneren von X, dann geht jede Ecke.
Liegt x allerdings auf einer Seitenfläche von X, dann ist mehr Sorgfalt nötig. Man sucht sich zunächst beliebige r' und s', deren Konvexkombination x ist und wählt dann die kleinste Seitenfläche, die x, r' und s' enthält. x muss dann im relativen Inneren dieser Seitenfläche liegen und man wählt für r einen Eckpunkt, der ebenfalls in dieser Seitenfläche liegt.

Jetzt kommt der Knalleffekt. Gibt es denn immer einen solchen Eckpunkt? Die Antwort ist leider ''nein''. Können wir den Beweis trotzdem retten? Leider auch nicht. Ein Beispiel:
Wir nehmen den \IR^2 und als X die Menge aller Punkte (x,y) mit x<=0.
C ist (1,0;0,0), ordnet also jedem Punkt (x,y) den Punkt (x,0) zu.
C*X hat ein lex. Maximum nämlich (0,0). X selbst hat aber gar keine Ecken. Die Aussage in \#7 ist also in der Form wie sie dort steht falsch.

Tut mir leid.

Kitaktus

\
Gut, dann zeige ich dir einmal unseren Beweis aus der Übung.

Zunächste einen Satz den wir brauchen werden.

\big\ (Satz 1)__
Sei K der asymptotische Kegel von X. Falls es eine asymptotische Richtung d \in K gibt, so dass Cd (>)_lex 0, dann gibt es kein lex-max für Problem 
lex-max menge(Cx: Ax=b,x>=0).

Nun zum eigentlichen Beweis:
Sei v^j \in V(X), so dass
Cv^j = lex-max menge(Cx: x \in V(X))
Weiter sei V die konvexe Hülle von V(X), d.h.
V = menge(x \in X: x = sum(\alpha_i v^i,i=1,q), sum(\alpha_i,i=1,q)=1, \alpha_i >= 0, \forall i)
Dann gilt für alle x \in V
\lr(*) Cv^j = sum(\alpha_i Cv^i,i=1,q) (>=)_lex sum(\alpha_i Cv^i,i=1,q)=Cx

Für x \in X\\V gilt nach Satz von Minkowski
x=v+\lambda d, v \in V, d \in K, \lambda >=0

Daraus folgt
Cx - Cv = \lambda Cd

Da das Problem ein lex-max hat, folgt aus Satz 1, dass gilt
Cd (<)_lex 0, \forall d \in K.

\lr(**)Das bedeutet Cx ist nicht__ lexikografisch größer als Cv.

Aus \ref(*) und \ref(**) folgt die Behauptung.

Was sagst du dazu?

Liebe Grüße
Chris

\
Hallo Kitaktus,


kein Problem, dem kommen wir bestimmmt noch auf die Schliche.

\big\Definition__
Sei P = menge(x \in \IR^n: (a^i)^T x <= b_i, i = 1, ..., m)
(a^i \in \IR^n, b_i \in \IR \forall i)
Polyeder mit dim P = k (k<=n).

(a) Eine Teilmenge S \subset P heißt Seite__ von P, wenn entweder S = P, oder eine affine Menge der Form
M = menge(x \in \IR^n: (a^i)^T x = b_i, i \in I \ subset menge(1, ..., m))
existiert, so dass S = P \cut M.
Seite S heißt (p-Seite)__ (p<=k), wenn dim S = p.
(b) 0-Seiten heißen Extrempunkte__ oder Ecken__.
1-Seiten heißen Kanten__
(k-1)-Seiten heißen Facetten__.

\big\ (Satz von Minkowski)__
Seien P = menge(x \in \IR^n: Bx <= b), B \in \IR^(m \cross n), b \in \IR^m ein Polyeder mit 
V(P) = menge(v^1, ..., v^k) Menge aller Ecken und U(P)=menge(u^1, ..., u^l) Menge der unbeschränkten Kanten. Sei
Q = menge(x \in \IR^n: x=sum(\lambda_i v^i,i=1,k)+sum(\mue_j u^j,j=1,l), sum(\lambda_i,i=1,k)=1, \lambda_i>=0 \forall i, \mue_j >=0 \forall j), dann gilt P = Q.

Beweis__:
zu Q \subset P:
Man kann zunächst zeigen, dass gilt:
Bu^j <= 0, \forall j=1, ..., l \lr(*)
Sei nun x \in Q, d.h.
x = sum(\lambda_i v^i,i=1,k) + sum(\mue_j u^j,j=1,l), sum(\lambda_i,i=1,k)=1, \lambda_i >=0 \forall i, \mue_j >= 0 \forall j. Dann gilt nach \ref(*):
Bx = sum(\lambda_i B v^i,i=1,k) + sum(\mue_j B u^j,j=1,l) <= sum(\lambda_i b) = b

zu P \subset Q:
Man nimmt an, dass P \nosubset\ Q und kann sich dann mit Hilfe des Lemma von Farkas überlegen, dass z^T u^j > 0 gilt, was ein Widerspruch ist.

Willst du diese Richtung noch genauer sehen? Sie ist etwa eine Seite lang, deswegen habe ich sie erst einmal nicht abgetippt.

Liebe Grüße
Chris

\
Hallo,

ich glaube, dass das Problem bei diesem ''Satz von Minkowski'' liegt.
Ich habe folgendes Beispiel im Hinterkopf:
n=2
m=1
a_1=(1;0);
b_1=1;

Zu P gehören also alle Punkte (x_1;x_2)\in\IR^2 mit x_1<=1.
I hat nur zwei Teilmengen, also hat P auch nur zwei Seiten.
Das sind P selbst und die Menge K=\menge((x_1;x_2)\in\IR^2 : x_1=1) mit den Dimensionen 2 bzw. 1. K ist also die einzige Kante von P. Ecken hat P überhaupt nicht.

Für dieses Beispiel sehe ich keine geeignete Interpretation der verwendeten Begriffe, für die die Behauptung Q=P wahr wäre, da Q nur eindimensional und P zweidimensional ist.
Man kann jetzt weiter in den zweiten Teil des Beweises einsteigen, um ganz genau auf die Stelle zeigen zu können, wo der Fehler ist, aber aus meiner Sicht ist jetzt schon klar, dass der Beweis nicht funktionieren kann.

Ich würde an Deiner Stelle Deinen Prof. ansprechen, was er dazu meint, oder arbeitest Du allein mit einem Buch?

Ich möchte nochmal betonen, dass ich mich mit dem Farkas-Lemma, der Zerlegung in Polyeder und Kegel und ähnlichem zwar mal beschäftigt habe, dass das aber nicht mein Spezialgebiet ist. 

Es würde mich nicht überraschen, wenn als Auflösung etwas in der Art herauskäme ''Auf Seite xy wurde festgelegt, dass wir unsere Untersuchungen auf Mengen mit der Eigenschaft E beschränken und deshalb ist dieser Fall gar nicht möglich.''

Kitaktus

\
Hallo Kitaktus,


ich habe noch einen kleinen Schreibfehler entdeckt. Es muss heißen
''...und U(P)=menge(u^1, ..., u^l) Menge (der Richtungen)__ der unbeschränkten Kanten.''

Das ändert aber nichts, da du das sowieso so interpretiert hast, richtig?

Gut, da der Satz scheinbar falsch ist, muss auch der Beweis falsch sein, oder zumindest Aufschluss darüber geben, was zur Richtigkeit des Satzes noch angenommen werden muss.

Also dann:

Wir brauchen zunächst eine alternative Darstellung des Farkas-Lemmas.

\Lemma__
Entweder hat das System Ax <= 0, c^T x >0 eine Lösung, oder das System A^T u = c, u >= 0 hat eine Lösung (aber nicht beide). \bigbox

Beweis__: (Minkowski)
(i) Q \subset P:
Man kann zeigen, dass gilt
Bu^j <= 0, \forall j = 1, ..., l \lr(*).
Sei nun x \in Q, d.h.
x = sum(\lambda_i v^i,i=1,k)+sum(\mue_j u^j,j=1,k), sum(\lambda_i,i=1,k)=1, \lambda_i >= 0, \forall i, \mue_j >= 0, \forall j.
Dann gilt nach \ref(*):
Bx__ = sum(\lambda_i B v^i,i=1,k)+sum(\mue_j B u^j,j=1,l) <= 
(da Bv^i <= b und Bu^j <= 0)
<= sum(\lambda_i b,i=1,k) = b__.

(ii) P \subset Q:
Ann__: P \nosubset Q, d.h. es ex. y \in P, y \notin Q.
Das bedeutet: Es gibt keine \lambda \in \IR^k und \mue \in \IR^l, so dass gilt
sum(\lambda_i v^i,i=1,k)+sum(\mue_j u^j,j=1,l) = y, sum(\lambda_i,i=1,k)=1, \lambda_i >= 0, \forall i, \mue_j >= 0, \forall j.

Setze: c = (y;-1), u=(\lambda_1, ..., \lambda_k, \mue_1, ..., \mue_l)^T, A^T = (v^1,.,.,.,v^k,u^1,.,.,.,u^l;-1,.,.,.,-1,0,.,.,.,0).

Dann haben wir das System A^T u = c, u >= 0, was keine Lösung hat.

Nach obigem Lemma
\exists x = (z;z_0) \in \IR^(n+1), so dass das System Ax = A(z;z_0) <= 0 und c^T x = c^T (z;z_0) = z^T y - z_0 > 0, d.h.
sesac(z^T v^i - z_0 <= 0 (i=1\,...\,k);z^T u^j <= 0 (j=1\,...\,l);y^T - z_0> 0) \lr(**)
eine Lösung (z;z_0) hat.

Nun betrachte das (LP) max menge(z^T x: x\in P). Wenn dieses LP eine OL hat, dann gibt es eine optimale Ecke. Da aber z^T y > z_0 >= z^T v^i, \forall i = 1, ..., k, folgt:
Es gibt keine Ecke von P, die eine OL ist.
Das bedeutet LP hat keine beschränkte OL, d.h. z^T x ist nach oben unbeschränkt auf einer Kante K_j mit der Richtung u^j.
Das bedeutet
z^T (w + \mue_j u^j) = z^T w + \mue_j z^T u^j -> +\inf für w \in K_j und \mue_j -> +\inf.
Daraus folgt: Es muss gelten, dass z^T u^j > 0 \blitz \bigbox.

Liebe Grüße
Chris

\
Hallo Kitaktus,


also ich war heute bei meinem Professor, er meinte zu mir, dass X in dem Satz immer eine Ecke haben muss. Das werde durch
''V(P) = menge(v^1, ..., v^k) Menge aller Ecken''
impliziert.

Meine Frage aus dem Eingangspost ist jetzt auch klar.
Man hat eine endliche Menge von Vektoren, dort gibt es immer ein lexikographisches Maximum.

Vielen Dank für deine Hilfe.
Liebe Grüße
Chris