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

• Entweder liegt $\bar{x}$ im Inneren des zulässigen Bereichs (d.h. $\bar{x}\gt 0$), dann ist $f'(\bar{x})=0$.
• Oder $\bar{x}$ liegt am Rand (d.h. $\bar{x}=0$) und $f'(\bar{x})=0$.
• Oder $\bar{x}=0$ und $f'(\bar{x})< 0$.

Zusammengefaßt:

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

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

$$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$$

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{array} {rl} \mbox{Maximiere} & f(x_1,\ldots,x_n) \\ ... ...,\, s_i\geq 0\\ &(j=1,\ldots,n,\, i=1,\ldots,m)\\ \end{array}$$

Verwenden wieder die Lagrange-Funktion:

$$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)$$

Berücksichtigen der Nichtnegativitätsbedingung:

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

Die Schlupfvariablen lassen sich wieder eliminieren:

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

$$\lambda_i\geq 0,\qquad s_i\geq 0 \qquad{und}\qquad \lambda_i s_i=0$$

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:

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

$$\lambda_i(c_i-g^i(x_1,\ldots,x_n))=0$$

Jetzt brauchen wir die Schlupfvariablen nicht mehr.

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

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

Wegen

$$\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)$$

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

$$f(x,y)=-(x-1)^2-(y-1)^2$$

unter den Nebenbedingungen

$$x+y\leq 1,\qquad x,y\geq 0$$

Durch die Lagrange-Funktion

$$L(x,y;\lambda) = -(x-1)^2-(y-1)^2 + \lambda (1-x-y)$$

erhalten wir die Kuhn-Tucker-Bedingung:

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

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

$$\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}$$

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:

• Wenn $\lambda=0$ $(III,\mbox{links})$, dann gibt es wegen $(I)$ und $(II)$ vier Möglichkeiten für $(x,y;\lambda)$:

  $(0,0;0)$, $(1,0;0)$, $(0,1;0)$ und $(1,1;0)$.

  Keiner dieser Fälle erfüllt alle Nebenbedingungen $(A)$, $(B)$ und $(C)$.

• Wenn $\lambda\not=0$, dann gilt wegen $(III,\mbox{rechts})$,

  $1-x-y=0\Leftrightarrow y=1-x$.

  • Wenn nun $\lambda\not=0$ und $x=0$, dann ist $y=1$ und wegen $(II,\mbox{rechts})$, $\lambda=0$. Ein Widerspruch.
  • Genauso kann nicht $\lambda\not=0$ und $y=0$ sein.
  • Es müssen daher alle drei Variablen ungleich 0 sein.

    Wir erhalten daher durch

    $(I,\mbox{rechts}) - (II,\mbox{rechts})$: $x-y=0$.

    Zusammen mit $1-x-y=0$ erhalten wir daraus $x=y=\frac{1}{2}$ und aus $(I,\mbox{rechts})$, $\lambda=1$.

Die Kuhn-Tucker-Bedingung wird daher nur vom Punkt

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

erfüllt.