[Artikel] Optimierung mit Lagrange und Karush-Kuhn-Tucker

16.09.2010, 18:41

tigerbine

[Artikel] Optimierung mit Lagrange und Karush-Kuhn-Tucker

In diesem Workshop wollen wir die Ideen aus [WS] Extremwertaufgaben mit Nebenbedingungen noch einmal aufgreifen und anhand verschiedener Aufgaben aus dem Board die Ansatz mit Lagrange und die KKT-Bedingungen prüfen. Für die Theorie sei auf ein Analysisskript/Optimierungsskript verwiesen.

28.12.2010, 21:11

tigerbine

Auf diesen Beitrag antworten »

Beispiel 1

Zitat:

Quelle

Man bestimme den Kürzesten Abstand des Punktes $\begin{eqnarray*} P_0\left(2,2\sqrt 7,\frac 1 2\right) \end{eqnarray*}$ vom Rotationsparaboloid $\begin{eqnarray*} z=x^2+y^2 \end{eqnarray*}$

Den Abstand interpretieren wir hier mal in der euklidischen Norm ||.||. Nun kann man sich überlegen, dass es keinen Einfluss auf die Lösung hat, wenn man das Problem bzgl. ||.||² löst. Wir erhalten also

$\begin{eqnarray*} \min f(x)~\text{ u.d.N. } h(x)=0 \end{eqnarray*}$

mit

$\begin{eqnarray*} f(x):=\left(x_1-2\right)^2+\left(x_2-2\sqrt{7}\right)^2 + \left(x_3-0.5\right)^2 \end{eqnarray*}$

$\begin{eqnarray*} h(x):=x_1^2+x_2^2-x_3 \end{eqnarray*}$

Für die Lösung mittels Lagrange suchen wir $\begin{eqnarray*} (x^*,\mu*),~\mu \in \mathbb R \end{eqnarray*}$ mit:

$\begin{eqnarray*} \nabla f(x^*) + \mu^* \cdot \nabla h(x^*)=0 \end{eqnarray*}$ ,

$\begin{eqnarray*} h(x^*)=0 \end{eqnarray*}$ .

Dazu lösen wir die Gradientengleichung in Abhängigkeit von $\begin{eqnarray*} \mu \end{eqnarray*}$ und ermitteln $\begin{eqnarray*} \mu^* \end{eqnarray*}$ aus der Zulässigkeitsforderung.
Achtung bei der entstehenden Division! Lösung $\begin{eqnarray*} \mu^*=-1 \end{eqnarray*}$ ausschließen!
Am Ende erhalten wir $\begin{eqnarray*} \mu^*=3 \end{eqnarray*}$ und den Lösungspunkt $\begin{eqnarray*} x^*=\left(0.5, 0.5\sqrt{7}, 2\right)^T \end{eqnarray*}$

28.12.2010, 21:42

tigerbine

Auf diesen Beitrag antworten »

Beispiel 2

Zitat:

Quelle

Ich soll Extrema der Funktion $\begin{eqnarray*} f(x,y)=x-y^2 \end{eqnarray*}$ mit der Nebenbedingung $\begin{eqnarray*} x^2+y^2=1 \end{eqnarray*}$ bestimmen.

Wieder notieren wir das in Standardnotation.

$\begin{eqnarray*} \min~f(x)~\text{u.d.N.}~h(x)=0 \end{eqnarray*}$

mit

$\begin{eqnarray*} f(x):=x_1-x_2^2 \end{eqnarray*}$

$\begin{eqnarray*} h(x):=x_1^2+x_2^2-1 \end{eqnarray*}$

Für die Lösung mittels Lagrange suchen wir $\begin{eqnarray*} (x^*,\mu^*),~\mu \in \mathbb R \end{eqnarray*}$ mit:

$\begin{eqnarray*} \nabla f(x^*) + \mu^* \cdot \nabla h(x^*)=0 \end{eqnarray*}$ ,

$\begin{eqnarray*} h(x^*)=0 \end{eqnarray*}$ .

Dazu lösen wir die Gradientengleichung in Abhängigkeit von $\begin{eqnarray*} \mu \end{eqnarray*}$ und ermitteln $\begin{eqnarray*} \mu^* \end{eqnarray*}$ aus der Zulässigkeitsforderung.
Achtung bei der entstehenden Division! Lösung $\begin{eqnarray*} \mu^*=0 \end{eqnarray*}$ ausschließen!
Am Ende erhalten wir $\begin{eqnarray*} \mu^*=-1 \end{eqnarray*}$ und den Lösungspunkt $\begin{eqnarray*} x^*=\left(-\frac{1}{2}, \frac{\sqrt{3}}{2} \right)^T \end{eqnarray*}$

15.01.2011, 12:55

tigerbine

Auf diesen Beitrag antworten »

Beispiel 3

Zitat:

Quelle

Seien $\begin{eqnarray*} f(x)=4x_1^{2} -3x_1x_2 \end{eqnarray*}$ und $\begin{eqnarray*} K:=\left\{ x \in \mathbb R ^{2}: x_1^{2} +x_2^{2}\leq 1 \right\} \end{eqnarray*}$ . Bestimmen Sie die Extremstellen von f in K.

Wir wollen hier 2 Wege bestreiten. Die zulässige Menge ist (offensichtlich) ein Kreis mit Radius 1.

Wir können nun das unrestringierte Problem betrachten und schauen, ob wir (lokale) Minima finden, die den NB genügen. Anschließend betrachten wir das Problem nur auf der Kreislinie. Klassischer Fall für Lagrange.

$\begin{eqnarray*} f(x)=4x_1^{2} -3x_1x_2 \end{eqnarray*}$ , $\begin{eqnarray*} \nabla f(x)= \begin{pmatrix} 8x_1 - 3x_2 \\ -3x_1 \end{pmatrix} \end{eqnarray*}$

Im unrestringierten Fall, also ohne NB, muss dann notwendigerweise gelten $\begin{eqnarray*} \nabla f(x)= \begin{pmatrix} 0 \\0\end{pmatrix} \end{eqnarray*}$ . Da sehe ich nur eine Lösung für: $\begin{eqnarray*} x^*=(0,0)^T \end{eqnarray*}$ . Ist dies nun aber auch ein lokales Minimum?

Die Hessematrix lautet, sogar unabhängig von x, $\begin{eqnarray*} H_f(x)= \begin{pmatrix} 8 & -3 \\ -3 & 0 \end{pmatrix} \end{eqnarray*}$

Diese Matrix ist jedoch indefinit. Somit liegt hier ein Sattelpunkt vor.

--------------------
Zur Übung wollen wir uns dennoch fragen: Wie sieht ein Beispiel für einen Weg Richtung x* aus, auf dem gilt $\begin{eqnarray*} f(x)<0 \end{eqnarray*}$ ?

Betrachten wir einmal die Punkte $\begin{eqnarray*} \tilde x:=(x_1,2x_1) \end{eqnarray*}$ . Für $\begin{eqnarray*} x_1 \end{eqnarray*}$ hinreichend klein liegen sie im zulässigen Bereich und es gilt $\begin{eqnarray*} \lim_{x_1\to 0}~\tilde x =x^* \end{eqnarray*}$ , sowie

$\begin{eqnarray*} f(\tilde x) = 4x_1^{2} -3x_1\cdot 2x_1 = 4x_1^2 - 6x_1^2 = -2x_1 < 0,~\forall x_1 \neq 0 \end{eqnarray*}$

---------------------

Untersuchen wir nun also den Kreisrand mit Lagrange, so erhalten wir die Forderungen an ein neues x*

$\begin{eqnarray*} \nabla f(x^*) + \lambda^* \cdot \nabla g(x^*)=0 \end{eqnarray*}$ ,

$\begin{eqnarray*} g(x^*)=0 \end{eqnarray*}$ .

Dies führt uns - nach Auflösen der zweiten Bedingung - auf zwei Fälle und auf die Multiplikatoren: $\begin{eqnarray*} \lambda_1=0.5,~\lambda_2=-4.5 \end{eqnarray*}$ . Da die Kreislinie eine kompakte Menge ist und f stetig, finden wir auf jeden Fall ein Min und ein Max. Weitere Rechnungen mit den Multiplikatoren führen auf:

$\begin{eqnarray*} x^{*,0.5,1}=\left(\sqrt{\frac{1}{10}}, \sqrt{\frac{9}{10}}\right)^T \end{eqnarray*}$ , $\begin{eqnarray*} x^{*,0.5,2}=\left(-\sqrt{\frac{1}{10}}, -\sqrt{\frac{9}{10}}\right)^T \end{eqnarray*}$ mit $\begin{eqnarray*} f\left(x^{*,0.5,1}\right)=f\left(x^{*,0.5,2}\right) = -0.5 \end{eqnarray*}$ und

$\begin{eqnarray*} x^{*,-4.5,1}=\left(\sqrt{\frac{9}{10}}, -\sqrt{\frac{1}{10}}\right)^T \end{eqnarray*}$ , $\begin{eqnarray*} x^{*-4.5,2}=\left(-\sqrt{\frac{9}{10}}, \sqrt{\frac{1}{10}}\right)^T \end{eqnarray*}$ mit $\begin{eqnarray*} f\left(x^{*,-4.5,1}\right)=f\left(x^{*,-4.5,2}\right) =4.5 \end{eqnarray*}$ .

Durch das Auftreten einer Ungleichheitsrestriktion sollte man hier aber auch mal die KKT-Bedingungen durchspielen (Prüfen auf CQ! nicht vergessen). Da wir hier nur eine Nebenbedingung, ergo nur einen Gradienten haben, ist auf der Kreislinie (Aktivitätsbereich der Ungleichheitsrestriktion, Gradient dort ungleich dem Nullvektor!) jedoch die LICQ erfüllt.

Für die Rechnungen sehen wir sofort, dass die Minima aus der vorherigen Rechnung auch diese Bedingungen erfüllen. Gradientengleichung ist klar, positiver Multiplikator und Komplementarität ein mal checken.

Die Maxima fallen wegen des neg. Multiplikators raus. Der Punkt (0,0) erfüllt jedoch auch mit $\begin{eqnarray*} \lambda=0 \end{eqnarray*}$ die KKT-Bedingungen. Dies verdeutlicht noch einmal, dass es sich auch hier nur um notwendige und i.A. nicht hinreichende Bedingungen handelt. Die Überprüfung gestaltet sich analog zu Lagrange, da (0,0) ein innerer Punkt ist.

Neue Frage »

Antworten »

[Artikel] Optimierung mit Lagrange und Karush-Kuhn-Tucker

Verwandte Themen