U 02.1 & U 02.2 – Bestimmung von Minimum und Maximum mit dem Satz von Kuhn-Tucker

 

Es seien

f:{\mathbb{R}^2} \to \mathbb{R},\quad f\left( {x,y} \right) = {x^2}-y

und

S: = \left\{ {\left( {x,y} \right) \in {\mathbb{R}^2};\quad {y^2}-x \leq 0,\quad {x^2}+{y^2}-2 \leq 0} \right\}

Bestimmen Sie mit Hilfe des Satzes von Kuhn-Tucker

\min \left\{ {f\left( {x,y} \right);\quad x \in S} \right\}

bzw.

\max \left\{ {f\left( {x,y} \right);\quad x \in S} \right\}

Hinweis: \max \left\{ {f\left( {x,y} \right);\quad x \in S} \right\} = \min \left\{ {-f\left( {x,y} \right);\quad x \in S} \right\}.

Lösung

Satz von Kuhn-Tucker

Es sei U \subseteq {\mathbb{R}^n} offen. f:U \to \mathbb{R},\quad g = \left( {{g_1},\: \ldots \:,{g_k}} \right):{\mathbb{R}^n} \to {\mathbb{R}^k} und h = \left( {{h_1},\: \ldots \:,{h_p}} \right):{\mathbb{R}^n} \to {\mathbb{R}^p} seien {\mathcal{C}^1}-Funktionen. Es sei weiterhin S: = \left\{ {\vec x \in U;\quad g\left( {\vec x} \right) = 0\quad und\quad h\left( {\vec x} \right) \leq 0} \right\}.

Es sei \hat {\vec x} eine lokale Minimalstelle von f auf S, die regulär ist. Dann gibt es \lambda \in {\mathbb{R}^k} und \mu \in {\mathbb{R}^p} so, dass

\nabla f\left( {\hat {\vec x}} \right)+\sum\limits_{i = 1}^k {{\lambda _i}\nabla {g_i}\left( {\hat {\vec x}} \right)} +\sum\limits_{j = 1}^p {{\mu _j}\nabla {h_j}\left( {\hat {\vec x}} \right)} = 0

und

{\mu _j} \geq 0,\quad {\mu _j}{h_j} = 0,\quad j = q,\; \ldots \;,p.

Auf unsere Aufgabe bezogen bedeutet dies:

f\left( {x,y} \right) = {x^2}-y,\quad S: = \left\{ {\left( {x,y} \right) \in {\mathbb{R}^2},\quad \underbrace {{y^2}-x}_{{h_1}\left( {x,y} \right)} \leq 0,\quad \underbrace {{x^2}+{y^2}-2}_{{h_2}\left( {x,y} \right)} \leq 0} \right\}

Die Funktion f sieht dabei wie folgt aus:

u02-funktionsplot

Unter Einbeziehung der Restriktionen ergibt sich folgendes Bild:

u02-funktionsplot-mit-restriktionen

Gesucht: \min \left\{ {f\left( {x,y} \right):\left( {x,y} \right) \in S} \right\}

bzw: \max \left\{ {f\left( {x,y} \right):\left( {x,y} \right) \in S} \right\} = \min \left\{ {-f\left( {x,y} \right):\left( {x,y} \right) \in S} \right\}

Nach dem Satz von Kuhn-Tucker muss für eine lokale Minimalstelle (bzw. lokale Maximalstelle) \hat x \in S gelten:

\nabla f\left( {\hat x} \right)+{\mu _1}\nabla {h_1}\left( {\hat x} \right)+{\mu _2}\nabla {h_2}\left( {\hat x} \right) = 0\quad \quad \quad \quad \left( * \right)

{\mu _1},{\mu _2} \geq 0,\quad {\mu _1}{h_1}\left( {\hat x} \right) = 0,\quad {\mu _2}{h_2}\left( {\hat x} \right) = 0

Bei der Maximierung gilt statt {\mu _1},{\mu _2} \geq 0 die Bedingung {\mu _1},{\mu _2} \leq 0.

In \left( * \right) gibt es maximal vier Möglichkeiten für die Werte von {\mu _i}.

Fall 1:

{\mu _1} = 0,\quad {\mu _2} = 0\quad \mathop \Rightarrow \limits^{\left( * \right)} \quad \nabla f\left( {x,y} \right) = 0\quad \Rightarrow \quad \left( {\begin{array}{*{20}{c}}{2x} \\ {-1}  \end{array}} \right) = 0

Diese Bedingung kann nicht erfüllt werden.

Fall 2:

{\mu _1} \ne 0,\quad {\mu _2} = 0\quad \Rightarrow \quad {h_1}\left( {x,y} \right) = 0,\quad \nabla f\left( {x,y} \right)+{\mu _1}\nabla {h_1}\left( {x,y} \right) = 0

Daraus ergibt sich:

{y^2} = x,\quad \left( {\begin{array}{*{20}{c}}{2x} \\ {-1}  \end{array}} \right)+{\mu _1}\left( {\begin{array}{*{20}{c}}{-1} \\ {2y}  \end{array}} \right) = 0\quad \Rightarrow \quad {y^2} = x,\quad 2x-{\mu _1} = 0,\quad -1+2{\mu _1}y = 0

Dies sind drei Gleichungen für drei Unbekannte. Wir lösen die zweite Gleichung nach x und die dritte Gleichung nach y auf und setzen beide in die erste Gleichung ein:

{\left( {\frac{1}{{2{\mu _1}}}} \right)^2} = \frac{{{\mu _1}}}{2}\quad \Rightarrow \quad \frac{1}{{4\mu _1^2}} = \frac{{{\mu _1}}}{2}\quad \Rightarrow \quad \mu _1^3 = \frac{1}{2}\quad \Rightarrow \quad {\mu _1} = \sqrt[3]{{\frac{1}{2}}} > 0

Daraus erhalten wir die Werte für x und y:

x = \frac{1}{2}\sqrt[3]{{\frac{1}{2}}},\quad y = \frac{1}{{2\sqrt[3]{{\frac{1}{2}}}}} = \frac{{\sqrt[3]{2}}}{2}\quad \Rightarrow \quad \hat {\vec x} = \left( {\begin{array}{*{20}{c}}{\frac{1}{2}\sqrt[3]{{\frac{1}{2}}}} \\ {\frac{{\sqrt[3]{2}}}{2}}  \end{array}} \right)

Wegen {\mu _1} > 0,\quad {\mu _2} = 0 kommt der Punkt als Minimum in Frage. Wir müssen noch überprüfen, ob der gefundene Kandidat \hat {\vec x} tatsächlich in S liegt:

{h_1}\left( {x,y} \right) = {y^2}-x = \frac{{\sqrt[3]{4}}}{4}-\frac{1}{2}\sqrt[3]{{\frac{1}{2}}}\mathop = \limits^{Bedingung} 0

{h_2}\left( {x,y} \right):\quad {x^2}+{y^2} = \frac{1}{4}\sqrt[3]{{\frac{1}{4}}}+\frac{{\sqrt[3]{4}}}{4} = \frac{1}{4}\left( {\sqrt[3]{{\frac{1}{4}}}+\sqrt[3]{4}} \right) = 0,554\mathop < \limits^{Bedingung} 2

Die Beiden Bedingungen sind tatsächlich erfüllt, also liegt \hat {\vec x} in S und wir haben ein lokales Minimum gefunden.

Als Funktionswert ergibt sich:

f\left( {\hat x} \right) = -\frac{3}{{4\sqrt[3]{4}}}

Fall 3:

{\mu _1} = 0,\quad {\mu _2} \ne 0\quad \Rightarrow \quad {h_2}\left( {x,y} \right) = 0,\quad \nabla f\left( {x,y} \right)+{\mu _2}\nabla {h_2}\left( {x,y} \right) = 0

\quad \Rightarrow \quad {x^2}+{y^2} = 2,\quad \left( {\begin{array}{*{20}{c}}{2x} \\ {-1}  \end{array}} \right)+{\mu _2}\left( {\begin{array}{*{20}{c}}{2x} \\ {2y}  \end{array}} \right) = 0

\quad \Rightarrow \quad 2x\left( {1+{\mu _2}} \right) = 0,\quad -1+{\mu _2}2y = 0,\quad {x^2}+{y^2} = 2

Damit folgt nun entweder:

x = 0,\quad y = \pm \sqrt 2 \quad \Rightarrow \quad \hat {\vec x} = \left( {\begin{array}{*{20}{c}}  0 \\ { \pm \sqrt 2 }  \end{array}} \right) \notin S

oder:

1+{\mu _2} = 0\quad \Rightarrow \quad {\mu _2} = -1 < 0\quad \Rightarrow \quad y = -\frac{1}{2}\quad \Rightarrow \quad {x^2} = \frac{7}{4}\quad \Rightarrow \quad x = \pm \frac{{\sqrt 7 }}{2}

\quad \Rightarrow \quad \hat {\vec x} = \left( {\begin{array}{*{20}{c}}{\frac{{\sqrt 7 }}{2}} \\ {-\frac{1}{2}}  \end{array}} \right)\quad \vee \quad \hat {\vec x} = \underbrace {\left( {\begin{array}{*{20}{c}}{-\frac{{\sqrt 7 }}{2}} \\ {-\frac{1}{2}}  \end{array}} \right)}_{ \notin S}\quad \Rightarrow \quad \hat {\vec x} = \left( {\begin{array}{*{20}{c}}{\frac{{\sqrt 7 }}{2}} \\ {-\frac{1}{2}}  \end{array}} \right)

Als Funktionswert ergäbe sich dann:

f\left( {\hat x} \right) = {x^2}-y = \frac{7}{4}+\frac{1}{2} = \frac{9}{4}

Da {\mu _2} = -1 < 0 ist dies ein lokales Maximum.

Fall 4:

{\mu _1} \ne 0,\quad {\mu _2} \ne 0\quad \Rightarrow \quad \nabla f+{\mu _1}\nabla {h_1}+{\mu _2}\nabla {h_2} = 0,\quad {h_1} = 0,\quad {h_2} = 0

\quad \Rightarrow \quad \left( {\begin{array}{*{20}{c}}{2x} \\ {-1}  \end{array}} \right)+{\mu _1}\left( {\begin{array}{*{20}{c}}{-1} \\ {2y}  \end{array}} \right)+{\mu _2}\left( {\begin{array}{*{20}{c}}{2x} \\ {2y}  \end{array}} \right) = 0,\quad {y^2} = x,\quad {x^2}+{y^2} = 2

\quad \Rightarrow \quad {x^2}+x-2 = 0\quad \Rightarrow \quad \left( {x-1} \right)\left( {x+2} \right) = 0\quad \Rightarrow \quad x = 1\quad \vee \quad x = -2

Negative Werte für x sind nicht möglich, da die erste Nebenbedingung verletzt wird. Daher müssen wir nur den Wert x = 1 weiter prüfen.

x = 1\quad \Rightarrow \quad {y^2} = 1\quad \Rightarrow \quad y = \pm 1\quad \Rightarrow \quad \hat {\vec x} = \left( {\begin{array}{*{20}{c}}  1 \\   1  \end{array}} \right)\quad \vee \quad \hat {\vec x} = \left( {\begin{array}{*{20}{c}}  1 \\ {-1}  \end{array}} \right)

Überprüfung des ersten Kandidaten liefert:

\hat {\vec x} = \left( {\begin{array}{*{20}{c}}  1 \\   1  \end{array}} \right)\quad \Rightarrow \quad \left( {\begin{array}{*{20}{c}}  2 \\ {-1}  \end{array}} \right)+{\mu _1}\left( {\begin{array}{*{20}{c}}{-1} \\   2  \end{array}} \right)+{\mu _2}\left( {\begin{array}{*{20}{c}}  2 \\   2  \end{array}} \right) = 0

\quad \Rightarrow \quad 3-3{\mu _1} = 0\quad \Rightarrow \quad {\mu _1} = 1 > 0

\quad \Rightarrow \quad -1+2+2{\mu _2} = 0\quad \Rightarrow \quad {\mu _2} = -\frac{1}{2} < 0

Da die Vorzeichen von {\mu _1} und {\mu _2} unterschiedlich sind, kommt dieses \hat {\vec x} weder als Maximum noch als Minimum in Frage.

Überprüfung des zweiten Kandidaten liefert:

\hat x = \left( {\begin{array}{*{20}{c}}  1 \\ {-1}  \end{array}} \right)\quad \Rightarrow \quad {\mu _1} = \frac{1}{3} > 0,\quad {\mu _2} = -\frac{5}{6} < 0

Auch dies ist kein Kandidat für ein Extremum.

Die Menge S kann in 2D wie folgt veranschaulicht werden:

u02-graphische-darstellung

Dabei sind:

Blaue Funktion.: {y^2}-x = 0

Schwarzer Kreis: {x^2}+{y^2} = 2

Rote Funktion: f\left( {x,y} \right) = {x^2}-y = -\frac{3}{{4\sqrt[3]{4}}}

Grüne Funktion: f\left( {x,y} \right) = {x^2}-y = \frac{9}{4}