previous up next contents index
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

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

unter den Nebenbedingungen

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


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

\begin{displaymath}
\mathsfbf{H}_f=\pmatrix{ -2 & 0 \cr 0 & -2 }
 \qquad\qquad
 \mathsfbf{H}_g=\pmatrix{ 0 & 0 \cr 0 & 0 }
 \end{displaymath}

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.


previous up next contents index

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