Startseite    
MathematikPoolNRW Projekt Hintergründe Kontakt


Optimalitätskriterien

Man nennt ein Tupel $(x_1^*,x_2^*)$ ein strenges lokales Minimum (bzw. ein strenges lokales Maximum), falls eine Zahl $\epsilon > 0$ existiert, so dass gilt
$f(x_1^*,x_2^*) \le (\mbox{ bzw. } \ge ) f(x_1,x_2)$
für alle $x_1 \in [x_1^*-\epsilon ,x_1^*+\epsilon ]$ und $ x_2 \in [x_2^*-\epsilon ,x_2^*+\epsilon]$.

Eine $2 \times 2$-Matrix
$ Q= \left( \begin{array}{cc} q_{11}& q_{12}\cr q_{21}& q_{22} \end{array} \right) $
ist positiv definit, falls für jedes $\vec{x} \ne (0,0)$ die Bedingung
$\vec{x}Q\vec{x}^{\ T} > 0$
erfüllt ist.
Dies ist der Fall, falls
$q_{11} > 0$ und $q_{11}\cdot q_{22}- q_{12}\cdot q_{21} > 0$ gilt.

Notwendiges Kriterium:
Ist $(x_1^*,x_2^*)$ ein lokales Minimum bzw. ein lokales Maximum, so muss gelten
$\nabla_f(x_1^*,x_2^*) = (0,0)$.
D.h. $(x_1^*,x_2^*)$ muss ein sogenannter kritischer Punkt von $f$ sein.

Hinreichendes Kriterium:
Ist $(x_1^*,x_2^*)$ ein kritischer Punkt der Funktion $f$, und die Hessematrix $H_f (x_1^*,x_2^*)$ an dieser Stelle positiv definit, so ist $(x_1^*,x_2^*)$ ein strenges lokales Minimum.

Die hinreichenden Bedingungen für ein strenges lokales Minimum sind jedoch nicht notwendig. Der kritische Punkt $(0,0)$ beispielsweise ist ein strenges lokales Minimum der Funktion $f(x_1,x_2) = x_1^{\ 2} + x_2^{\ 4}$, obwohl die Hessematrix an dieser Stelle nicht positiv definit ist.

Beispiel:
Für die Funktion

         $f(x,y)=y^2-\sin x$
hat der Gradient $\nabla_f(x,y)=(\cos x,2y)$ eine Nullstelle im Punkt $(\frac{\pi}{2},0)$.
Die Hessematrix
         $ H_f (\frac{\pi}{2},0)= \left( \begin{array}{cc} \sin(\frac{\pi}{2})& 0\cr ... ...} \right) = \left( \begin{array}{cc} 1& 0\cr 0 &2 \end{array} \right) $
ist an diesem kritischen Punkt wegen $1>0$ und $1\cdot2-0>0$ positiv definit,
folglich ist $(\frac{\pi}{2},0)$ ein strenges lokales Minimum von $f$.


Bemerkung:
Für den Fall von nur einer Veränderlichen entsprechen diese Optimalitätskriterien denen der aus der Differentialrechnung bei einer Veränderlichen bekannten: "$x^*$ ist genau dann ein strenges lokales Minimum der Funktion $f(x)$, wenn die erste Ableitung $f'(x^*) = 0$ und die zweite Ableitung $f''(x^*) > 0$ ist. Diese Bedingungen sind jedoch nicht notwendig (z.B. $f(x)=x^4$)."

Da im Fall einer quadratischen Funktion
$f(\vec{x}) = \frac{1}{2} \vec{x} Q \vec{x}^{\ T}- \vec{a} \vec{x}^{\ T} + c_1$
sich der Gradient als
$\nabla_f(\vec{x}) = \vec{x}Q - \vec{a}$
und die Hessematrix als
$H_f(\vec{x})= Q$
errechnen, existiert im Fall einer positiv definiten Matrix $Q$ genau ein strenges Minimum $\vec{x}^{\ *}$ an der kritischen Stelle $\vec{x}^{\ *}=Q^{-1} \vec{a}$, der Nullstelle des Gradienten.

Beispiel:
Die quadratische Funktion

         $f(x,y)=x^2+y^2+xy+2x-1$
mit positiv definiter Matrix
        $Q = \left( \begin{array}{cc} 2& 1\cr 1& 2 \end{array} \right) $
besitzt ein strenges Minimum an der kritischen Stelle
        \begin{eqnarray*} (\vec{x}^{\ *},\vec{y}^{\ *}) &=& \left( \begin{array}{cc} ... ...}{3} (-4,2) \\ &=& \left( -\frac{4}{3},\frac{2}{3} \right) \end{eqnarray*}


Wir werden zeigen, wie man mit dem konjugierten Gradientenverfahren das strenge Minimum $\vec{x}^{\ *}$ in nur zwei Iterationsschritten bestimmen kann.
Auf diese Weise kann die bei mehreren Veränderlichen aufwendige Berechnung der inversen Matrix $Q^{-1}$ umgangen werden.