previous up next contents index
previous: Eine graphische Methode up: Kuhn-Tucker next: Der Satz von Kuhn-Tucker

Die Kuhn-Tucker Bedingung  



Wir untersuchen zuerst die Auswirkung der Nichtnegativitätsbedingung auf das Maximum einer Funktion in einer Variablen. Für ein (lokales) Maximum $\bar{x}$ gibt es drei Möglichkeiten

Zusammengefaßt:

\begin{displaymath}
f'(\bar{x})\leq 0,\qquad 
\bar{x}\geq 0\qquad{und}\qquad
\bar{x}\,f'(\bar{x})=0\end{displaymath}


\begin{figure}
\setlength {\unitlength}{1.5mm}
 
\begin{tabular}[t]
{ccccc}
 \be...
 ... \spline(5,22)(10,15)(15,12)(20,11)(25,10)\end{picture}\end{tabular}\end{figure}



Im Falle einer Funktion $f(\mathsfbf{x})$ in mehreren Variablen erhalten wir für jede Variable $x_j$ so eine Bedingung:

\begin{displaymath}
f_{x_j}(\bar{\mathsfbf{x}})\leq 0 \qquad
\bar{x}_j\geq 0\qquad{und}\qquad
\bar{x}_j\,f_{x_j}(\bar{\mathsfbf{x}})=0\end{displaymath}




Wir können die Nebenbedingungen unseres usprünglichen Problems durch Einfügen von Schlupfvariablen in ein System von Gleichungen mit Nichtnegativitätsbedingung überführen (vgl. Simplex-Algorithmus).

\begin{displaymath}
\begin{array}
{rl}
 \mbox{Maximiere} & f(x_1,\ldots,x_n) \\ ...
 ...,\, s_i\geq 0\\  &(j=1,\ldots,n,\, i=1,\ldots,m)\\  \end{array}\end{displaymath}



Verwenden wieder die Lagrange-Funktion:

\begin{displaymath}
L^\ast=f(x_1,\ldots,x_n)
+ \sum_{i=1}^m\lambda_i (c_i-g_i(x_1,\ldots,x_n)-s_i)\end{displaymath}

Berücksichtigen der Nichtnegativitätsbedingung:

\begin{displaymath}
\begin{array}
{llll}
 \displaystyle\frac{\partial L^\ast}{\p...
 ...e\frac{\partial L^\ast}{\partial\lambda_i}=0 &&& \\ \end{array}\end{displaymath}




Die Schlupfvariablen lassen sich wieder eliminieren:

Wegen $\frac{\partial L^\ast}{\partial s_i}=-\lambda_i$, wird zweite Zeile zu

\begin{displaymath}
\lambda_i\geq 0,\qquad s_i\geq 0 \qquad{und}\qquad \lambda_i s_i=0\end{displaymath}

Wegen $0=\frac{\partial L^\ast}{\partial\lambda_i}=
c_i-g_i(x_1,\ldots,x_n)-s_i\quad\Leftrightarrow$
$s_i=c_i-g_i(x_1,\ldots,x_n)$erhalten wir daraus:

\begin{displaymath}
\lambda_i\geq 0,\qquad 
c_i-g_i(x_1,\ldots,x_n)\geq 0\quad{und}\end{displaymath}

\begin{displaymath}
\lambda_i(c_i-g^i(x_1,\ldots,x_n))=0\end{displaymath}

Jetzt brauchen wir die Schlupfvariablen nicht mehr.

Verwenden statt $L^\ast$ direkt die Lagrange-Funktion

\begin{displaymath}
L=f(x_1,\ldots,x_n)
+ \sum_{i=1}^m\lambda_i (c_i-g_i(x_1,\ldots,x_n))\end{displaymath}

Wegen

\begin{displaymath}
\frac{\partial L}{\partial x_j} = \frac{\partial L^\ast}{\pa...
 ...d
\frac{\partial L}{\partial \lambda_i}=c_i-g_i(x_1,\ldots,x_n)\end{displaymath}

können wir obige Bedingungen für ein lokales Maximum unter Nebenbedingungen schreiben als




$\mbox{\ovalbox{$\begin{Beqnarray*}
\frac{\partial L}{\partial x_j}\leq 0, \quad...
 ...& \quad
 \lambda_i\,\frac{\partial L}{\partial\lambda_i} = 0\end{Beqnarray*}$}}$


Dieses Kriterium für das lokale Maximum einer Funktion unter Nebenbedingungen heißt  Kuhn-Tucker Bedingung.



 

BEISPIEL
Wir suchen das Maximum von

\begin{displaymath}
f(x,y)=-(x-1)^2-(y-1)^2
 \end{displaymath}

unter den Nebenbedingungen

\begin{displaymath}
x+y\leq 1,\qquad x,y\geq 0
 \end{displaymath}


Durch die Lagrange-Funktion

\begin{displaymath}
L(x,y;\lambda) = -(x-1)^2-(y-1)^2 + \lambda (1-x-y)
 \end{displaymath}

erhalten wir die Kuhn-Tucker-Bedingung:

\begin{displaymath}
\begin{array}
{lrcll}
 (A)&L_x &=& -2(x-1)-\lambda &\leq 0\\...
 ...) & \lambda\, L_\lambda &=& \lambda(1-x-y) &= 0\\  \end{array} \end{displaymath}

Schreiben $(I)$-$(III)$ an als

\begin{displaymath}
\begin{array}
{llcl}
 (I)\quad & x=0 &\quad\vee\quad& 2(x-1)...
 ...lambda=0 \\  (III) & \lambda=0 &\vee & 1-x-y=0 \\  \end{array} \end{displaymath}

Müssen nun alle 8 Möglichkeiten ausrechnen, und überprüfen ob die entsprechenden Lösungen die Bedingungen $(A)$, $(B)$, $(C)$ und $(N)$ erfüllen:

Die Kuhn-Tucker-Bedingung wird daher nur vom Punkt

\begin{displaymath}
(x,y;\lambda)=\left(\frac{1}{2},\frac{1}{2},1\right)
 \end{displaymath}

erfüllt.


previous up next contents index

© 1997, Josef Leydold
Abteilung für angewandte Statistik und Datenverarbeitung