Optimierung - Algorithmen zur Optimierung

Algorithmen zur Optimierung

Bisher haben wir nur notwendige und hinreichende Bedingungen für lokale Extremstellen kennen gelernt. Bereits im Eindimensionalen war die aktuelle Berechnung der Stelle nicht immer einfach. Für die in der Praxis so wichtigen Funktionen mehrerer Veränderlicher ist dieses Problem häufig um ein Vielfaches komplizierter – schließlich muss in der Iteration in jedem Schritt die Richtung, in der weitergesucht wird, neu bestimmt werden. Man ist oft auf numerische Lösungsmethoden angewiesen. Dieses Gebiet ist ein aktiver Forschungszweig, und nach wie vor sind bei weitem nicht alle Fragestellungen gelöst. Wir wollen an dieser Stelle nur zwei grundlegende Verfahren besprechen. Eine Umsetzung dieser Verfahren mithilfe von R finden Sie in den Videos auf der Homepage erläutert.

Das Newton Verfahren in mehreren Dimensionen

Das in Abschnitt davor bereits erwähnte Newton-Verfahren kann recht einfach auf mehrere Dimensionen verallgemeinert werden. Die Grundidee bleibt dabei gleich, man sucht nach Nullstellen von ${\textstyle \mathrm {\nabla f} \left({\vec {x}}\right)}$ und ersetzt mit Hilfe dieses Gradienten die Funktion durch eine lineare Approximation. Man erhält das Iterationsverfahren

$${\begin{aligned}{\vec {x}}_{k+1}={\vec {x}}_{k}-\left[H_{f}\left({\vec {x}}_{k}\right)\right]^{-1}\mathrm {\nabla f} \left({\vec {x}}_{k}\right)\end{aligned}}$$

Verfolgen wir die Analogie zum bekannten eindimensionalen Fall: sucht man dort einen Extremwert, so kann mithilfe des eindimensionalen Newton-Verfahrens die Nullstellen der Ableitung bestimmen; dazu wird der Wert der ersten Ableitung an der Stelle ${\textstyle x_{i}}$ durch die zweite Ableitung dividiert, dieser Quotient gibt dann an, wie weit auf der x-Achse weitergegangen werden muss. Ist die Funktion, deren Extremwert gesucht wird, eine quadratische Funktion, dann ist das Verfahren nach einem Schritt am Ziel – dann ist nämlich die Ableitung eine lineare Funktion, deren Nullstelle in einem Schritt gefunden wird; für jede andere Funktion entspricht das Newton-Verfahren dann der Approximation durch quadratische Funktionen. Formal sieht die Iterationsvorschrift im Mehrdimensionalen genauso aus wie im eindimensionalen. Allerdings approximieren wir jetzt den Gradienten durch eine lineare Funktion, und die Division durch die zweite Ableitung im eindimensionalen entspricht der Multiplikation mit der Inversen der Hessematrix. Wenn die zu optimierende Funktion eine quadratische Funktion ist, so führt das Verfahren bereits in einem Schritt zum Ziel – wie im eindimensionalen. Die Hesse-Matrix muss im Allgemeinen nach jedem Iterationsschritt für jedes ${\textstyle {\vec {x}}_{k}}$ neu berechnet und invertiert werden, was bei großer Dimension n recht zeitaufwendig ist. In der Praxis wird dieses Update der Hesse-Matrix daher nicht in jedem Schritt durchgeführt, dies führt zu sogenannten Quasi-Newton Verfahren . Das Newtonverfahren konvergiert äußerst rasch, sobald man sich in der Nähe eines lokalen Minimums befindet. Allerdings ist es noch schwieriger als in einer Dimension, überhaupt in die Nähe eines Minimums zu kommen. Oft werden dazu Verfahren wie das folgende verwendet, die zwar nicht so rasch konvergieren, sich dafür aber mit Sicherheit in Richtung Minimum bewegen.

Das Gradientenverfahren

Die Idee hier ist, dass zunächst eine Suchrichtung festgelegt wird, und dann in diese Richtung ein eindimensionales Optimierungsverfahren angewendet wird. Bei der Suche nach einem Minimum ist es natürlich, dass man eine Richtung sucht, in der die Werte der Funktion ${\textstyle f}$ kleiner werden, eine sogenannte Abstiegsrichtung. Mathematisch gesprochen verringern sich die Werte der Funktion ${\textstyle f\left({\vec {x}}\right)}$ in Richtung des Vektors ${\textstyle {\vec {d}}}$, falls

$${\begin{aligned}f\left({\vec {x}}+c{\vec {d}}\right)<f\left({\vec {x}}\right)\end{aligned}}$$

für kleine Werte von c > 0. Dies hat zur Folge, dass

$${\begin{aligned}\left[\mathrm {\nabla f} \left({\vec {x}}\right)\right]^{T}{\vec {d}}<0\end{aligned}}$$

Das heißt wenn das innere Produkt des Gradienten mit einem Richtungsvektor ${\textstyle {\vec {d}}}$ negativ ist, so handelt es sich um eine Abstiegsrichtung. Wie man leicht zeigen kann erfolgt der steilste Abstieg gerade in die entgegengesetzte Richtung des Gradientenvektors, d.h.

$${\begin{aligned}{\vec {d}}=-{\frac {{\nabla f}({\vec {x}})}{||{{\nabla f}({\vec {x}})}||}}\end{aligned}}$$

ist der normierte Vektor, der die Richtung des optimalen Abstiegs angibt. Die Idee des Gradientenverfahrens besteht nun darin, dass man wieder mit einem beliebigen Startvektor ${\textstyle {\vec {x}}_{1}}$ beginnt und die Suchtrichtung

$${\begin{aligned}{\vec {d_{1}}}=-{\frac {{\nabla f}({\vec {x_{1}}})}{||{{\nabla f}({\vec {x_{1}}})}||}}\end{aligned}}$$

festlegt. (Für die Rechnung einfacher und im Ergebnis äquivalent ist es, wenn der Vektor nicht normiert wird; es ist zwar dann kein Richtungsvektor mehr – aber der nächste Iterationspunkt ist genau derselbe.) Definiere die eindimensionale Funktion

$${\begin{aligned}g\left(y\right)=f\left({\vec {x}}_{1}+y{\vec {d}}_{1}\right)\end{aligned}}$$

deren Minimum ${\textstyle y_{1}}$ nun zum Beispiel mit dem eindimensionalen Newtonverfahren bestimmt werden kann. Dieses liefert den nächsten Iterationspunkt

$${\begin{aligned}{\vec {x}}_{2}={\vec {x}}_{1}+y_{1}{\vec {d}}_{1}\end{aligned}}$$

Bestimme an ${\textstyle {\vec {x}}_{2}}$ eine neue Suchrichtung, und wiederhole das Verfahren so lange, bis ein lokales Minimum gefunden wurde. Dies ist dann der Fall, wenn der Gradient von ${\textstyle {\vec {x}}_{k}}$ sich kaum mehr vom Nullvektor unterscheidet. Das Gradientenverfahren konvergiert zwangsläufig gegen einen kritischen Punkt, d.h. gegen einen Punkt mit ${\textstyle \mathrm {\nabla f} \left({\vec {x}}\right)=0}$. Allerdings kann es in der Nähe eines Minimums zum sogenannten Zickzackphänomen kommen. Dabei ändert sich die Suchrichtung in jedem Iterationsschritt in drastischer Weise, während kaum mehr eine Verminderung des Wertes der Zielfunktion zu beobachten ist. Es empfiehlt sich häufig in der Nähe des Minimums zu anderen Verfahren überzugehen, etwa zu einem Quasi-Newton Verfahren. Für weitere Details sei hier wiederum auf die Literatur verwiesen (Bomze, Grossmann 1993, Nocedal, Wright 1999, etc.)