Nichtlineare Optimierung - Karush Kuhn Tucker

28.07.2012, 17:31	Fealy	Auf diesen Beitrag antworten »
Nichtlineare Optimierung - Karush Kuhn Tucker Edit: Ich glaube das Thema muss nach Sonstiges verschoben werden. Hey, ich bin gerade dabei mich auf eine Prüfung im Operations Research (BWL) vorzubereiten. Es geht hierbei um Nichtlineare Optimierungsaufgaben mittels KKT. Nun soll eine Funktion F(x) maximiert werden, unter der Nebenbedingung: $\begin{eqnarray} F(x)= 8x1-x1² + 4x2 - x2² \end{eqnarray}$ $\begin{eqnarray} x1+x2 <= 2 ; x1,x2 >= 0 \end{eqnarray}$ Dazu muss ich nun die Lagrangefunktion und die KKT-Bedingungen aufstellen: Lagrange: $\begin{eqnarray} L=8x1-x1²+4x2-x2²+u(2-x1-x2) \end{eqnarray}$ Hierbei komme ich auf folgende Bedingungen: (1a) $\begin{eqnarray} 8-2x1 -u <= 0 \end{eqnarray}$ (1b) $\begin{eqnarray} 4-2x2-u <= 0 \end{eqnarray}$ (2a) $\begin{eqnarray} x1(8-2x1-u) = 0 \end{eqnarray}$ (2b) $\begin{eqnarray} x2(4-2x2-u) = 0 \end{eqnarray}$ (3) $\begin{eqnarray} x1+x2 <= 2 \end{eqnarray}$ (4) $\begin{eqnarray} u(2-x1-x2)=0 \end{eqnarray}$ (5) $\begin{eqnarray} x1,x2 >= 0 \end{eqnarray}$ (6) $\begin{eqnarray} u>=0 \end{eqnarray}$ Genau an diesem Punkt habe ich nun erhebliche Schwierigkeiten. Laut meinem aktuellen Verständnis muss ich nun die Kandidaten für das Maximum finden, aber wie genau gehe ich da vor? Laut Musterlösung erfüllen x=(2,0) mit u=4 die KKT-Bedingungen. Ich würde gerne wissen, wie ich dies systematisch errechnen kann (Auch wenn evtl die Methode des scharfen hinsehens möglich wäre, hätte ich hierfür gerne ein 'Allgemeinrezept'). _______________________________________________________ Ich habe eine zweite Aufgabe, die mich vor dasselbe Problem stellt: Die Daten: $\begin{eqnarray} F(x)=x²+y²+y-1 \end{eqnarray}$ udN.: $\begin{eqnarray} x²+y²<=1 \end{eqnarray}$ Lagrangefunktion: $\begin{eqnarray} x²+y²+y-1+u(1-x²-y²) \end{eqnarray}$ KKT-Bedingungen: (1a) $\begin{eqnarray} 2x-2ux <= 0 \end{eqnarray}$ (1b) $\begin{eqnarray} 2y+1-2uy <= 0 \end{eqnarray}$ (2a) $\begin{eqnarray} x(2x-2ux) = 0 \end{eqnarray}$ (2b) $\begin{eqnarray} y(2y+1-2uy) = 0 \end{eqnarray}$ (3) $\begin{eqnarray} x²+y² <=1 \end{eqnarray}$ (4) $\begin{eqnarray} u(1-x²-y²) = 0 \end{eqnarray}$ (5) $\begin{eqnarray} x,y >= 0 \end{eqnarray}$ (6) $\begin{eqnarray} u >= 0 \end{eqnarray}$ Die Bedingungen sind korrekt, oder? Habe hierfür leider keine Musterlösung. Auch hier habe ich dasselbe Problem. Gibt es hier nicht ne Möglichkeit, irgendwie die Formeln umzustellen und irgendwie ineinander einzusetzen, oder sowas ähnliches? Würde mich über jede Hilfe sehr sehr freuen! Lg,
28.07.2012, 18:34	Kasen75	Auf diesen Beitrag antworten »
Hallo, bei Kuhn-Tucker untersuchst man immer bestimmte Fälle: Bei dir wäre es, dass u=0 oder $\begin{eqnarray} u \neq 0 \end{eqnarray}$ ist. Ich nehm jetzt einfach mal den Fall $\begin{eqnarray} u \neq 0 \end{eqnarray}$ bei Aufgabe 1. Wenn man jetzt zur Bedingung 4 geht, sieht man, dass $\begin{eqnarray} x_1=2-x_2 \end{eqnarray}$ sein muss. Man bedenke, dass wir im Fall $\begin{eqnarray} u \neq 0 \end{eqnarray}$ sind. Jetzt habe ich die Bedingung 2 von Bedingung 1 abgezogen und für $\begin{eqnarray} x_1 \end{eqnarray}$ den obigen Ausdruck eingesetzt. Variable u fällt weg. Nach Umformungen kommt raus: $\begin{eqnarray} 2\cdot x_2 \leq 0 \end{eqnarray}$ . Was ja $\begin{eqnarray} x_2 \leq 0 \end{eqnarray}$ entspricht. Schaut man sich jetzt Bedingung 5 an, ist klar was $\begin{eqnarray} x_2 \end{eqnarray}$ für einen Wert annimmt. Wäre hier irgendwo ein Widerspruch herausgekommen, dann hätte man den Fall u = 0 untersuchen müssen. Beim Auffinden von Lösungen bzw. Widersprüchen kann man nicht sehr schematisch vorgehen. Man muss Stück für Stück schauen, welche (UN-)Gleichung einem die Lösung näher bringt. Bei mir funktionierts. Übung und scharfes Überlegen bringt den Erfolg. Mit freundlichen Grüßen. Wenn jemand doch ein "Schema" hat, bitte posten.
28.07.2012, 19:30	Fealy	Auf diesen Beitrag antworten »
Ich komm irgendwie nicht auf Habe folgendes gemacht: $\begin{eqnarray} 4-2x2-u-(8-2x1-u) \end{eqnarray}$ <=> $\begin{eqnarray} 4-2x2 -u -8 +2x1 +u \end{eqnarray}$ <=> $\begin{eqnarray} -4 -2x2 +2(2-x2) \end{eqnarray}$ <=> $\begin{eqnarray} -4 -2x2 +4 -2x2 \end{eqnarray}$ <=> $\begin{eqnarray} -4x2 <= 0 \end{eqnarray}$ ?? Gruß
28.07.2012, 19:39	Kasen75	Auf diesen Beitrag antworten »
Ich habe natürlich Bedingung 1b von Bedingung 1a abgezogen. Jetzt müsste es klappen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »