Optimierung: Existenz einer Optimallösung

24.01.2011, 23:48

toasten

Optimierung: Existenz einer Optimallösung

Hallo,

ich komme bei folgender Aufgabe gerade nicht weiter:

Seien $\begin{eqnarray*} A \in \mathbb{R}^{m,n} \end{eqnarray*}$ und $\begin{eqnarray*} b\in \mathbb{R}^m \end{eqnarray*}$ , so dass

$\begin{eqnarray*} min \, c^Tx \qquad \text{ u.d.N. } Ax \geq b \end{eqnarray*}$

eine zulässige Lösung besitzt.

Nun soll mittels des Dualitätssatzes gezeigt werden, dass die Existenz einer Optimallösung äquivalent zu $\begin{eqnarray*} c \in \left\{ A^Ty | y \geq 0 \right\} \end{eqnarray*}$ ist.

Bisher habe ich für " $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ ":
$\begin{eqnarray*} c^Tx = (A^Ty)^Tx = y^TAx \geq y^Tb = b^Ty \end{eqnarray*}$
wobei das Ungleichheitszeichen wegen der Existenz einer zulässigen Lösung gilt.

Damit habe ich jetzt zwar die schwache Dualität.... aber so wirklich komme ich nicht auf den richtigen Schluss. und auch für die Hinrichtung...

Vielleicht kann mir ja jemand helfen?

Vielen Dank im Voraus.
toasten

25.01.2011, 00:40

tigerbine

Auf diesen Beitrag antworten »

RE: Optimierung: Existenz einer Optimallösung
Hallo,

ich kenne das Primal nur mit "=", also Polyeder in Normalform. Du sollst wohl die starke Dualität verwenden ?). Die besagt:

Primal hat Lösung x* <=> Dual hat Lösung y*

Die Dualitätslücke ist 0, d.h. $\begin{eqnarray*} c^Tx^* = b^Ty^* \end{eqnarray*}$ . Ansatz wäre dann

$\begin{eqnarray*} 0 &&= c^Tx^* - b^Ty^* &&=c^Tx^*-(y^*)^Tb &&=c^Tx^*-(y^*)^TAx^* &&=\left(c-A^Ty^*\right)^Tx^* \end{eqnarray*}$

Das liefert sicher, dass die Bedingung hinreichend ist. Wie sieht bei euch das Duale Problem aus? Also die dortige Zulässigkeit? Es existiert ja eine Lösung des Duals, diese ist zulässig und es gilt was? Habt ihr da Gleichheit oder Ungleichheitsforderung?

25.01.2011, 10:48

toasten

Auf diesen Beitrag antworten »

RE: Optimierung: Existenz einer Optimallösung
Hi,

Zitat:

Original von tigerbine
ich kenne das Primal nur mit "=", also Polyeder in Normalform.

Ja, ich eigentlich auch nur. Das Problem könnte man dann ja mit einer Schlupfvariablen s in Normalform bringen:

$\begin{eqnarray*} min \, c^Tx \qquad \text{ u.d.N. } Ax-s=b \, , \, s \geq 0 \end{eqnarray*}$

Zitat:

Du sollst wohl die starke Dualität verwenden? Die besagt:

Primal hat Lösung x* <=> Dual hat Lösung y*

Die Dualitätslücke ist 0, d.h. $\begin{eqnarray*} c^Tx^* = b^Ty^* \end{eqnarray*}$ .

Zitat:

Ansatz wäre dann

$\begin{eqnarray*} 0 &&= c^Tx^* - b^Ty^* &&=c^Tx^*-(y^*)^Tb &&=c^Tx^*-(y^*)^TAx^* &&=\left(c-A^Ty^*\right)^Tx^* \end{eqnarray*}$

Das liefert sicher, dass die Bedingung hinreichend ist. Wie sieht bei euch das Duale Problem aus? Also die dortige Zulässigkeit? Es existiert ja eine Lösung des Duals, diese ist zulässig und es gilt was? Habt ihr da Gleichheit oder Ungleichheitsforderung

Wir haben das duale Problem wie folgt definiert

$\begin{eqnarray*} max \, b^Ty \qquad \text{ u.d.N. } A^Ty + \hat{s} = c \, , \, \hat{s} \geq 0 \end{eqnarray*}$

Mein Ansatz für " $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ wäre jetzt:

Mit der schwachen Dualität gilt
$\begin{eqnarray*} y^Tb = b^T y &&\leq c^Tx && = (A^Ty)^Tx && = y^TAx \end{eqnarray*}$
Also $\begin{eqnarray*} b \leq Ax \end{eqnarray*}$ , was aber nach der Nebenbedingung aus der Aufgabenstellung nur mit echt = richtig ist. Daraus folgt
$\begin{eqnarray*} b^Ty = c^Tx \Rightarrow \end{eqnarray*}$ starke Dualität und somit Existenz einer optimalen Lösung.

Kann man das so folgern?

Vielen Dank
Grüße

26.01.2011, 03:25

tigerbine

Auf diesen Beitrag antworten »

RE: Optimierung: Existenz einer Optimallösung
Kennst du KKT-Bedingungen?

Damit die Forderungen an c gelten, muss imho noch die Komplementarität rein.

Ich schreibe morgen mehr.

26.01.2011, 14:57

tigerbine

Auf diesen Beitrag antworten »

RE: Optimierung: Existenz einer Optimallösung

Zitat:

Primal hat Lösung x* <=> Dual hat Lösung (y*,s*)

Es ist ja schon mal wichtig, dass es y* überhaupt gibt. Es gilt für x* und y*:

Zitat:

Die Dualitätslücke ist 0, d.h. $\begin{eqnarray*} c^Tx^* = b^Ty^* \end{eqnarray*}$ .

Des weiteren wissen wir über x*,( y*,s*)

$\begin{eqnarray*} Ax^*=b,~x^* \geq 0 \end{eqnarray*}$ (zulässig primal)

$\begin{eqnarray*} A^Ty^*+s^*=c,~s^* \geq 0 \end{eqnarray*}$ (zulässig dual)

Zitat:

$\begin{eqnarray*} 0 &&= c^Tx^* - b^Ty^* &&=c^Tx^*-(y^*)^Tb &&=c^Tx^*-(y^*)^TAx^* &&=\left(c-A^Ty^*\right)^Tx^* &&=(s^*)^Tx^* \end{eqnarray*}$

Man kann also notieren

Zitat:

Primal hat Lösung x* <=> Dual hat Lösung (y*,s*) <=> siehe unten (KKT-Bedingungen)

$\begin{eqnarray*} A^Ty^*+s^*=c \end{eqnarray*}$
$\begin{eqnarray*} Ax^*=b \end{eqnarray*}$
$\begin{eqnarray*} (s^*)^Tx^* \end{eqnarray*}$ (#)
$\begin{eqnarray*} s^* \geq 0 \end{eqnarray*}$
$\begin{eqnarray*} x^* \geq 0 \end{eqnarray*}$

Das war nun für Primal mit "=" und Dual (inkl. Schlupvariable) mit "=". Vielleicht kommt die Formulierung $\begin{eqnarray*} c \in \left\{ A^Ty | y \geq 0 \right\} \end{eqnarray*}$ daher, dass das Primal hier anders aussieht. Denn bei den KKT ergibt sich alles (#) einfach aus der Zulässigkeit.

edit:

Also ich mal für dein Primal (Ungleichheiten ) das Dual gebildet. Dann löst sich das, mit dem was wir schon erarbeiten haben, auch in Wohlgefallen auf. Denke daran, x muss aufgespalten werden und eine Schlupvariable eingeführt werden.

Vielleicht hattet ihr schon die Rechnung zu "Dual von Dual ist Primal" Ideen solltest du übertragen.

Wink

30.01.2011, 20:45

toasten

Auf diesen Beitrag antworten »

Hi,

sorry, dass ich erst jetzt wieder schreibe...

Also die KKT-Bedingungen hatten wir bis dato nicht - zumindest nicht bewusst.

An sich waren unsere Überlegungen alle gut. Der Vollständigkeit halber kann ich ja noch mal die Lösung eines Kommilitonen schreiben, die unser Prof abgesegnet hat:

" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ ":
(P) hat Optimallösung ==> (D) ist zulässig und hat eine Lösung
$\begin{eqnarray*} min \left\{ c^Tx | Ax \geq b \right\} &=& -max \left\{ -c^Tx | Ax - s = b, s \geq 0 \right\} &=& -max\left\{ -c^Tx | -Ax+s=-b , s\geq 0\right\} &=& -min\left\{-b^Ty | -A^Ty=-c , y\geq 0 \right\} &=& -min \left\{ -b^Ty | A^Ty = c, y \geq 0 \right\} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow c \in A^Ty \end{eqnarray*}$

" $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ ":
Es ist
$\begin{eqnarray*} min \left\{ c^Tx | Ax \geq b \right\} = min \left\{ y^TAx | Ax \geq b \right\} \end{eqnarray*}$ .

Nun ist:
$\begin{eqnarray*} c^Tx = y^TAx= \sum_{i=1}^n y_i (Ax)_i \geq \sum_{i=1}^n y_ib_i=y^tb \end{eqnarray*}$
(Beschränktheit gezeigt)

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ (P) hat eine Lösung.

Viele Grüße und noch mal vielen Dank.

Toasten

30.01.2011, 20:52

tigerbine

Auf diesen Beitrag antworten »

Das ist das, was ich mit "Bilde das dual" angesprochen hatte. Hoffe du hast ein paar Punkte bekommen. Danke für die Rückmeldung. Wink

Neue Frage »

Antworten »

Optimierung: Existenz einer Optimallösung

Verwandte Themen