previous: Die Kuhn-Tucker Bedingung up: Kuhn-Tucker next: Dynamische Analyse

Der Satz von Kuhn-Tucker  

Wir brauchen nun noch ein Werkzeug, um festzustellen, ob ein Punkt, der die Kuhn-Tucker-Bedingung erfüllt, tatsächlich ein (globales) Maximum ist. Das ist aber nicht immer leicht.

Der  Satz von Kuhn-Tucker gibt für einen Spezialfall eine hinreichende Bedingung:

(1)

Die Zielfunktion $f(x_1,\ldots,x_n)$ sei differenzierbar und eine konkave Funktion für alle $\mathsfbf{x}$ mit $x_j\geq 0$.

(2)

Die Funktionen der Nebenbedingungen $g_i(x_1,\ldots,x_n)$ seien alle differenzierbar und konvex für alle $\mathsfbf{x}$ mit $x_j\geq 0$.

(3)

Der Punkt $\bar{\mathsfbf{x}}$ erfüllt die Kuhn-Tucker-Bedingung.

Dann ist $\bar{\mathsfbf{x}}$ ein globales Maximum von $f$ unter den Nebenbedingungen $g_i\leq c_i$.

Das Extremum ist eindeutig, wenn die Funktion $f$streng konkav ist.

BEISPIEL TEX2HTML_CR_MARK>#BSP:KUHN-TUCKER_1#15984><TEX2HTML_CR_MARK>
Wir betrachten wieder das Optimierungsproblem

$$f(x,y)=-(x-1)^2-(y-1)^2\quad\rightarrow\quad\max$$

unter den Nebenbedingungen

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

Die Hessematrizen von $f(x,y)$ und $g(x,y)=x+y$ lauten

$$\mathsfbf{H}_f=\pmatrix{ -2 & 0 \cr 0 & -2 } \qquad\qquad \mathsfbf{H}_g=\pmatrix{ 0 & 0 \cr 0 & 0 }$$

Die Hauptminoren von $\mathsfbf{H}_f$ sind: $\vert\mathsfbf{H}_1\vert = -2 < 0$ und $\vert\mathsfbf{H}_2\vert = 4 \gt 0$ $\quad\Rightarrow\quad$ $f$ ist konkav.

Alle allgemeinen Hauptminoren von $\mathsfbf{H}_g$ sind gleich Null und daher auch $\geq 0$ $\quad\Rightarrow\quad$ $g$ ist konvex.

$(x,y)=(\frac{1}{2},\frac{1}{2})$ erfüllt die Kuhn-Tucker-Bedingung.

Daher ist nach dem Satz von Kuhn-Tucker $\bar{\mathsfbf{x}}=(\frac{1}{2},\frac{1}{2})$ das gesuchte globale Maximum.