Optimierung - Lokale Extrema von reellen Funktionen

Lokale Extrema von reellen Funktionen

Wir erinnern uns, dass für Funktionen mit einer Veränderlichen eine notwendige Bedingung für lokale Extrema darin besteht, dass die erste Ableitung verschwindet, i.e. durch Lösen der Gleichung ${\textstyle f^{\prime }\left(x\right)=0}$ erhält man mögliche Kandidaten für ein Maximum bzw. ein Minimum einer Funktion.
Beispiel 6: Betrachte das Polynom aus Beispiel 4:
${\textstyle p(x)=-x^{4}+x^{3}+4x^{2}-4x+2}$
Ableitung liefert
${\textstyle p^{\prime }(x)=-4x^{3}+3x^{2}+8x-4}$
Die Suche nach Nullstellen von ${\textstyle p^{\prime }(x)}$ liefert potenzielle Kandidaten für lokale Maxima und Minima. Für ein Polynom dritten Grades gibt es geschlossene Formeln, um die Nullstellen zu bestimmen, man erhält näherungsweise
${\textstyle x_{1}=-1.3263,x_{2}=1.6073,x_{3}=0.4691}$ Der Vergleich lässt erkennen, dass an der Stelle ${\textstyle x_{1}}$ das absolute Maximum der Funktion liegt, während es sich bei ${\textstyle x_{2}}$ um ein lokales Minimum und bei ${\textstyle x_{3}}$ um ein lokales Maximum handelt.
Bereits für eine solch einfache Funktion wie ein Polynom dritten Grades ist die Bestimmung der Nullstellen nicht ganz trivial. Für die meisten Funktionen ist eine explizite Lösung überhaupt nicht möglich, und man ist auf numerische Methoden angewiesen. Die wichtigste wird im folgenden Abschnitt vorgestellt:

Das Newton Verfahren

Wir wollen die Nullstelle einer Funktion ${\textstyle g(x)}$ finden. (In Zusammenhang mit den Optimierungsaufgaben dieses Kapitels ist ${\textstyle g\left(x\right)=f^{\prime }\left(x\right)}$ die Ableitung der Funktion, deren Extremwerte gesucht werden; das Verfahren kann aber selbstverständlich für beliebige einmal differenzierbare Funktionen angewandt werden.) Das Newton-Verfahren ist ein Iterationsverfahren. Wir beginnen mit einer Stelle ${\textstyle x_{1}}$, die hoffentlich bereits in der Nähe der Nullstelle liegt. Grundidee ist nun die Funktion ${\textstyle g(x)}$ durch ihre Tangente an der Stelle ${\textstyle x_{1})}$ zu ersetzen, ${\textstyle t(x)=g(x_{1})+g\prime (x_{1})(x-x_{1})}$ und anschließend die Nullstelle der Tangente zu suchen. Die Lösung liefert den nächsten Punkt der Iteration:

$${\begin{aligned}x_{2}=x_{1}-{\frac {g\left(x_{1}\right)}{g^{\prime }\left(x_{1}\right)}}\end{aligned}}$$

Anschließend wird diese Prozedur so lange wiederholt, bis das Verfahren konvergiert, d.h. (bis auf numerische Genauigkeit) eine Nullstelle gefunden wurde. Es kann gezeigt werden, dass das Newton Verfahren extrem rasch (quadratisch) konvergiert, sobald man sich in der Nähe einer Nullstelle befindet. Die deutsche Wikipedia Seite bietet eine sehr schöne Animation, die verdeutlich wie das Newton Verfahren in der Praxis funktioniert. Um Kandidaten für lokale Extrema von ${\textstyle f(x)}$ zu erhalten sucht man Nullstellen der Ableitung von f, und das Iterationsverfahren hat daher die Gestalt

$${\begin{aligned}x_{k+1}=x_{k}-{\frac {f^{\prime }\left(x_{k}\right)}{f^{\prime \prime }\left(x_{k}\right)}}\end{aligned}}$$

Das bedeutet eine Funktion muss mindestens zweimal differenzierbar sein, damit diese Methode verwendet werden kann. In der Literatur findet man eine Unzahl an weiteren Methoden zur numerischen Bestimmung von Nullstellen.
Aufgabe 5:
Berechne für das Polynom ${\textstyle p^{\prime }(x)}$ aus Beispiel 6 die ersten beiden Newtonschritte mit Startwert ${\textstyle x_{1}=0}$. Schreib ein kleines Programm in der Programmiersprache deiner Wahl. Versuche auch andere Startwerte und beobachte wie sich das Verfahren verhält.

Die Bestimmung von globalen Extrema ist typischerweise wesentlich komplizierter als die Suche nach lokalen Extrema. Auch müssen diese nicht zwangsläufig existieren; die Funktion ${\textstyle f(x)=sin(x)}$ besitzt unendlich lokale Minima und Maxima, die gleichzeitig globale Extremwerte sind, die Funktion ${\textstyle f(x)=xsin(x)}$ besitzt unendlich viele lokale Extremwerte, aber keinen globalen. Plotten Sie die beiden Funktionen, um sich diese Tatsache vor Augen zu führen! Für eine gewisse Klasse von Funktionen kann man jedoch von lokaler Optimalität auf globale Optimalität schließen. Speziell nennt man eine Funktion f konvex (konkav), falls die Funktionswerte zwischen zwei Werten x und y jeweils unterhalb der Verbindungsgeraden der beiden Funktionswerte an x und y – der sogenannten Sekante - liegen. D.h. für jede Zahl t zwischen 0 und 1 gilt

$${\begin{aligned}&f(tx+(1-t)y)\leq tf(x)+(1-t)f(y){\text{ (konvex) }}\\&f(tx+(1-t)y)\geq tf(x)+(1-t)f(y)({\text{ konkav) }}\end{aligned}}$$

Konvexe Funktion

Die Abbildung zeigt eine konvexe Funktion und deren Sekante für zwei ausgewählte Werte ${\textstyle x_{1}}$ und ${\textstyle x_{2}}$. Die Sekante liegt oberhalb des Graphen der Funktion. Falls die zweite Ableitung existiert so gilt für eine konvexe Funktion

$${\begin{aligned}f^{\prime \prime }\left(x\right)\geq 0\end{aligned}}$$

und für eine konkave Funktion

$${\begin{aligned}f^{\prime \prime }\left(x\right)\leq 0\end{aligned}}$$

Für eine konvexe (konkave) Funktion gibt es höchstens ein lokales Extremum, und dies ist dann das globale Minimum (Maximum).