7 Optimierung
Einige Optimierungsprobleme haben wir schon kennengelernt und zwar
- bei der linearen Regression (vgl. besonders Kapitel 2.3) bei der die Parameter der Ansatzfunktion bestmöglich an die Daten gefittet wurden
- bei der Hauptkomponentenanalyse (vgl. besonders Kapitel 4.3) als wir die Hauptrichtungen so ermittelt, dass in ihrer Richtung die Varianz maximal wurde.
Hier lag in beiden Fällen ein sogenanntes linear-quadratisches Optimierungsproblem vor, für welche die Existenz der Lösungen bewiesen werden kann und die mit Methoden aus der linearen Algebra direkt gelöst werden können.
Sogenannte nichtlineare Optimierungsprobleme liegen vor, wenn die zu erfüllenden Ziele wirklich nichtlineare Gleichungen enthalten. Zum Bespiel sind gängige Elemente von Neuronalen Netzen als \[\begin{equation*} f(x) = \tanh(a\, x + b) \end{equation*}\] gegeben, mit Parametern \(a\), \(b\) die aus der Minimierung eines mean square error Terms der Form \[\begin{equation*} \frac 1N \sum_{k=1}^N|y_k - \tanh(a\, x_k + b)|^2 \end{equation*}\] für gegebene Trainingsdaten \((x_k, y_k)\) bestimmt werden.
Wir sehen, dass die Optimierung ein ganz wesentlicher Teil der Data Science ist (und ganz unabhängig davon ein eigenes Forschungsgebiet ist und quasi überall in der Praxis mittel– oder unmittelbar benutzt wird).
Nachfolgend ein paar Begriffe aus der Optimierung
- glatte Optimierung – das Modell beinhaltet ausreichend stetige (bzw. differenzierbare) Funktionen. Ein Optimum könnte durch Bestimmung von Ableitungen berechnet werden.
- nichtglatte Optimierung – das Modell beinhaltet Teile, die nicht differenzierbar sind. Das kann am Problem selbst liegen oder, was bei machine learning im Speziellen und Data Science an sich eine Rolle spielt, dass die Daten verrauscht sind. Jetzt ist eine (klassische) Ableitung nicht mehr möglich aber es existieren diverse Ansätze zur Abhilfe.
- diskrete Optimierung – in obigen Fällen sind wir implizit davon ausgegangen, dass die Lösung und die Gleichungen auf den reellen oder komplexen Zahlen leben. Denkbar ist aber auch, dass diskrete Lösungen (z.B. Anzahlen oder binäre Zustände) gesucht werden.
- kombinatorische Optimierung – hier ergeben sich die möglichen Lösungen als Kombination von Möglichkeiten. Oft ist die Anzahl möglicher Lösungen endlich aber sehr groß.
- restringierte Optimierung – zusätzlich zu einem Optimalitätskriterium sind noch Nebenbedingungen zu erfüllen.
Hier werden wir uns erstmal mit glatter Optimierung ohne Nebenbedingungen beschäftigen.
7.1 Multivariable Funktionen
Um unsere Optimierungsprobleme in allgemeiner Form zu formulieren und auch um allgemeine Lösungsansätze herzuleiten, brauchen wir erstmal ein paar Begriffe aus der Analysis von multivariablen Funktionen.
Es sei also eine Funktion \[\begin{equation*} f\colon \mathbb R^{n}\to \mathbb R^{}, \quad f \colon (x_1,x_2, \dots, x_n) \mapsto f(x_1, x_2, \dotsc, x_n) \end{equation*}\] gegeben, die ein \(n\)-tupel von Variablen auf einen reellen Wert abbildet. Ein Beispiel wäre \[\begin{equation*} g(x_1, x_2, x_3) = \sin(x_1) + x_3\cos(x_2) + x_1^2 x_2^2 x_3^2 - 2x_2. \end{equation*}\]
Hier verwenden wir jetzt \(x_i\) für die \(i\)-te Variable der multivariablen Funktion. Bitte nicht verwechseln mit der Bezeichnung für den \(i\)-ten Datenpunkt zum Beispiel in Kapitel 2.
Außerdem wäre es besser wir würden die Funktion mit einem Definitionsbereich \(D(f)\) angeben, also schreiben \[\begin{equation*} f\colon D(f) \subset \mathbb R^{n}\to \mathbb R^{} \end{equation*}\] da eine Funktion eventuell nicht überall definiert ist (bzw. definiert sein muss). Im Sinne der besseren Lesbarkeit, ersparen wir uns dieses Detail.
7.2 Partielle Ableitungen und der Gradient
Wenn wir alle Variablen bis auf die \(i\)-te für einen Augenblick einfrieren (also auf einen konstanten Wert \(\bar x_j\) festlegen und nicht verändern), können wir die Teilfunktion \[\begin{equation*} \bar f_{(i)}\colon \mathbb R^{}\to \mathbb R^{}, \quad \bar f_{(i)}\colon x_i \to f(\bar x_1, \dotsc, \bar x_{i-1}, x_i, \bar x_{i+1}, \dotsc, \bar x_n) \end{equation*}\] als Funktion mit einer Veränderlichen (und \(n-1\) Parametern) betrachten und wie gehabt ableiten. Die erhaltene, sogenannte partielle Ableitung hängt von den Parametern \(\bar x_j\) ab und wird mit \[\begin{equation*} \frac{\partial f}{\partial x_i} \end{equation*}\] bezeichnet. Alle \(n\) möglichen partiellen Ableitungen in einen Vektor geschrieben ergeben den sogenannten Gradienten \[\begin{equation*} \nabla f = \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{bmatrix} \colon \mathbb R^{n} \to \mathbb R^{n}, \end{equation*}\] der wiederum eine (vektorwertige) Funktion von \(n\) Variablen ist. Für unser obiges Beispiel bekommen wir \[\begin{equation*} \nabla g(x_1, x_2, x_3) = \begin{bmatrix} \cos(x_1)+2x_1x_2^2x_3^2\\ -x_3\sin(x_2) + x_1^2x_2x_3^2 - 2 \\ \cos(x_2) + 2x_1^2x_2^2x_3 \end{bmatrix} \end{equation*}\]
7.3 Richtungs-Ableitung
Die Betrachtung der Funktionen \(\bar f_{(i)}\) ermöglicht die Analysis des Verhaltens der Funktion entlang der \(i\)-ten Koordinaten Richtung. Um die Funktion in einer beliebigen Richtung um einen festen Punkt \[\begin{equation*} \bar x = (\bar x_1, \bar x_2, \dotsc, \bar x_n) \end{equation*}\] zu untersuchen, kann die Funktion entlang einer Richtung \(v \in \mathbb R^{n}\) parametrisiert werden: \[\begin{equation*} \bar f_{(v)} \colon \mathbb R^{} \to \mathbb R^{}, \quad t \mapsto \bar f_{(v)}(t) = f(\bar x + tv) \end{equation*}\]
Für \(v=e_i\) bekommen wir direkt, dass \(\bar f_{(v)}=\bar f_{(i)}\).
Wiederum handelt es sich um eine reelle Funktion in einer Variablen (hier der Parameter \(t\)), die wir schulbuchmäßig ableiten könnten. Für diese sogenannte Richtungsableitung gilt der folgende Zusammenhang8 \[\begin{equation*} \frac{\mathrm{d} \bar f_{(v)}}{\mathrm{d} t}(0) = \sum_i^n \frac{\partial f}{\partial x_i}(\bar x_i) v_i = \langle \nabla f(\bar x), v \rangle \end{equation*}\]
Die Veränderungsrate der Funktion \(f\) im Punkt \(\bar x\) in der Richtung von \(v\) ist gleich dem Skalarprodukt aus Gradient im Punkt \(\bar x\) und der gewählten Richtung.
Sei nun \(v\) normiert, also \(\|v\|=1\), dann gilt nach der Winkelformel, dass \[\begin{equation*} \langle \nabla f(\bar x), v \rangle = \|\nabla f(\bar x) \| \cos (\alpha) \end{equation*}\] wobei \(\alpha\) der von \(\nabla f(\bar x)\) und \(v\) eingeschlossene Winkel ist. Wir bemerken, dass die Veränderung maximal wird, wenn \(\alpha = 0\) oder \[\begin{equation*} v = \frac{1}{ \| \nabla f(\bar x) \| } \nabla f(\bar x) \end{equation*}\] als ein Vielfaches des Gradientenvektors gewählt wird. Andersherum können wir einige ganz wesentliche Aspekte folgern:
- der Gradient selbst in die Richtung des stärksten Anstiegs
- der negative Gradient \(-\nabla f(\bar x)\) zeigt in die Richtung des stärksten Abfalls
- ist der Gradient der Nullvektor, dann findet keine Veränderung mehr statt, d.h. dass aus \(\nabla f(\bar x) =0\) folgt, dass \(\bar x\) ein kritischer Punkt von \(f\) ist
- ist der Gradient nicht der Nullvektor, kann \(\bar x\) kein Minimum und kein Maximum sein (weil die Funktion in \(-\nabla f(\bar x)\) Richtung abfällt und in \(\nabla f(\bar x)\) Richtung ansteigt)
7.4 Optimierung
Ganz allgemein können wir unsere bisherigen Optimierungsprobleme schreiben als \[\begin{equation*} f(x) \to \min_{x\in \mathbb R^{n}}, \end{equation*}\] das heißt für eine Funktion \(f\colon \mathbb R^n \to \mathbb R^{}\) suchen wir das \(x \in D(f) \subset \mathbb R^{n}\), für das \(f(x)\) minimal wird.
Definition 7.1 Gegeben sei \(f\colon \mathbb R^{n} \to \mathbb R^{}\). Wir nennen \(x^* \in D(f)\subset \mathbb R^{n}\) die Stelle
eines lokales Minimum (von \(f\)) falls es ein \(\epsilon >0\) gibt, sodass \[\begin{equation*} f(x^*) \leq f(x) \end{equation*}\] für alle \(x \in D(f) \cap B_\epsilon (x^*)\).
eines globales Minimum, falls \(f(x^*) \leq f(x)\) für alle \(x\in D(f)\) ist.
In dieser Definition benutzen wir “\(\leq\)”, da das im Hinblick auf Minimierung (der Wert von \(f\) ist wichtig, die Stelle, an der das Minimum angenommen wird, ist weniger entscheidend) praktikabel ist. Wir könnten aber auch von strikten (oder “echten”) Minima sprechen und “\(<\)” verlangen.
Der Schnitt der Umgebung \[ B_\epsilon(x^*) := \{x\in \mathbb R^{n}| \|x-x^*\|< \epsilon\} \] mit dem Definitionsbereich \(D(f)\) ist relevant, wenn \(x^*\) genau auf dem Rand des Definitionsbereichs liegt.
Nun erstmal ein hinreichendes Kriterium für ein Extremum (vgl. Thm. 2.2, Nocedal and Wright 2006):
Theorem 7.1 Sei \(D(f) \subseteq \mathbb{R}^{n}\) offen, und sei \(f\colon D(f) \rightarrow \mathbb{R}\) stetig partiell differenzierbar. Besitzt \(f\) in \(\mathbf{x}^{*} \in D(f)\) ein lokales Extremum9, dann ist \(\nabla f(\mathbf{x}^{*})=0\).
Das können wir wie in der einfachen Kurvendiskussion verstehen: Liegt in \(x^*\) ein Extremum vor und \(x^*\) liegt nicht auf dem Rand, so verschwindet die erste Ableitung. Um festzustellen, ob ein Minimum, Maximum und vor allem nicht einfach ein Sattelpunkt vorliegt, wurde geschaut ob die zweite Ableitung positiv, negativ oder gleich 0 ist. Bei multivariablen Funktionen wird die zweite Ableitung durch eine Matrix repräsentiert. Und positiv, negativ oder indefinit wird wird über die Eigenwerte definiert.
Definition 7.2 (Hesse-Matrix) Sei \(D(f) \subseteq \mathbb{R}^{n}\) offen, und sei \(f\colon D(f) \rightarrow \mathbb{R}\) eine 2-mal stetig partiell differenzierbare Funktion. Für \(\mathbf{x}^{\star} \in D\) heißt die symmetrische \((n \times n)\)-Matrix \[ H_{f}\left(\mathbf{x}^{\star}\right)=\left(\begin{array}{cccc} \frac{\partial^{2} f}{\partial x_{1} \partial x_{1}}\left(\mathbf{x}^{\star}\right) & \frac{\partial^{2} f}{\partial x_{2} \partial x_{1}}\left(\mathbf{x}^{\star}\right) & \cdots & \frac{\partial^{2} f}{\partial x_{n} \partial x_{1}}\left(\mathbf{x}^{\star}\right) \\ \frac{\partial^{2} f}{\partial x_{1} \partial x_{2}}\left(\mathbf{x}^{\star}\right) & \frac{\partial^{2} f}{\partial x_{2} \partial x_{2}}\left(\mathbf{x}^{\star}\right) & \cdots & \frac{\partial^{2} f}{\partial x_{n} \partial x_{2}}\left(\mathbf{x}^{\star}\right) \\ \vdots & \vdots & \cdots & \vdots \\ \frac{\partial^{2} f}{\partial x_{1} \partial x_{n}}\left(\mathbf{x}^{\star}\right) & \frac{\partial^{2} f}{\partial x_{2} \partial x_{n}}\left(\mathbf{x}^{\star}\right) & \cdots & \frac{\partial^{2} f}{\partial x_{n} \partial x_{n}}\left(\mathbf{x}^{\star}\right) \end{array}\right) \] Hesse-Matrix von \(f\) in \(\mathbf{x}^{\star}\).
Hierbei ist \(\frac{\partial^{2} f}{\partial x_{i} \partial x_{j}}:=\frac{\partial }{\partial x_{i}}(\frac{\partial f}{\partial x_{j}})\) die wiederholte partielle Differentiation in möglicherweise verschiedene Koordinatenrichtungen. Die postulierte Symmetrie der Hesse-Matrix folgt aus der Gleichheit \[\begin{equation*} \frac{\partial }{\partial x_{i}}(\frac{\partial f}{\partial x_{j}}) = \frac{\partial }{\partial x_{j}}(\frac{\partial f}{\partial x_{i}}) \end{equation*}\] deren Gültigkeit wir noch in der Mathematik Vorlesung beweisen werden. Als nächstes ein Hinreichendes Kriterium für Minimalität (vgl. Theorem 2.4, Nocedal and Wright 2006):
Theorem 7.2 (Hinreichende Optimalitätsbedingung zweiter Ordnung) Sei \(D(f) \subset \mathbb{R}^{n}\) offen, und sei \(f\colon D(f) \rightarrow \mathbb{R}\) eine 2-mal stetig partiell differenzierbare Funktion. Sei \(x^{\star} \in D(f)\) mit \(\nabla f ({x}^{\star})={0}\) Ist \(H_{f}({x}^{\star})\) positiv definit, dann ist \(\mathbf{x}^{\star}\) ein lokales Minimum.
Ein paar Bemerkungen dazu
Eine symmetrische Matrix \(M\) heißt positiv definit, wenn \(x^TMx>0\) ist für alle \(x\in \mathbb R^{n}\setminus \{0\}\). Wir schreiben \(M \prec 0\).
Hinreichende Kriterien dafür sind
- alle Eigenwerte sind positiv oder
- alle Hauptminoren sind positiv (das sind die Determinante der Matrizen, die aus \(M\) durch Streichung der letzten \(r\) Zeilen und Spalten entstehen \(r=0,1,\dotsc, n-1\).)
Ist \(-M \prec 0\), dann liegt ein lokales Minimum von \(-f\) vor (oder eben ein Maximum von \(f\))
Gilt \(M \preccurlyeq 0\) (also \(M\) ist positiv semidefinit, das heißt die Eigenwerte sind nur “\(\geq 0\)” bzw. es gilt nur \(x^TMx\geq 0\)), dann ist keine Aussage möglich.
Ist die Matrix bestimmt indefinit, also alle Eigenwerte “\(\neq 0\)” aber manche positiv und manche negativ, dann liegt ein Sattelpunkt vor (und sicher kein Extremum).
7.5 Gradientenabstiegsverfahren
Aus dem Wissen, dass in einem Minimum \(x^*\), der Gradient \(\nabla f(x^*)\) verschwindet und dass in einem beliebigen Punkt \(x^0\) (der kein Extremum ist), der negative Gradient \(-\nabla f(x^0)\) in die Richtung des stärksten Abstiegs zeigt, ergibt sich der folgende Zusammenhang:
Für einen beliebigen Startpunkt \(x^0\) gibt es eine Schrittweite \(\alpha^0\), so dass \[f(x^1) := f(x^0 - \alpha^0 \nabla f(x^0)) < f(x_0) \]
Das heißt in einem Startpunkt können wir einen kleinen Schritt in die Richtung des stärksten Abstiegs gehen und so die Funktion etwas minimieren. Das wiederholte Anwenden dieses Prinzips ergibt das Gradientenabstiegsverfahren, \[f(x^{n+1}) := f(x^n - \alpha^n \nabla f(x^n)) < f(x_n) \], das die Funktion immer weiter minimiert bis entweder der Definitionsbereich verlassen ist oder ein kritischer Punkt mit \(\nabla f(x^k)=0\) erreicht wurde. An diesem könnte nun die Hessematrix ausgewertet werden um festzustellen ob tatsächlich ein Minimum vorliegt.
Neben der Berechnung des Gradienten, die für große Dimensionen sehr aufwändig werden kann, ist die Bestimmung der Schrittweite \(\alpha^k\) in jedem Schritt entscheidend.
- Dazu kann beispielsweise in jeder Iteration die skalare Funktion \(\alpha \mapsto f(x^{k} - \alpha \nabla f(x^k))\) minimiert werden (exact line search)
- Da das aber auch aufwändig sein kann, wurden zahlreiche Approximationen an diese Zwischenoptimierung entwickelt (inexact line search).
- Vgl. auch den Wikipedia Artikel zum Gradientenverfahren#Bestimmen_der_Schrittweite
Für passend gewählte Schrittweiten und wenn \(f\) hinreichend glatt ist (der Gradient soll Lipshitz-stetig sein), lässt sich Konvergenz und sogar Konvergenzrate der Iteration zu einem stationären Punkt \(x^*\) mit \(\nabla f(x^*)=0\) bestimmen (vgl. Section 3.2 in Nocedal and Wright 2006).
Um tatsächlich die Konvergenz zu einem Minimum zu beweisen, wird beispielsweise vorausgesetzt, dass ein striktes lokales Minimum existiert (lokale Konvexität) und dass die Hesse-Matrix stetig ist (also \(f\) zweimal stetig partiell differenzierbar ist) (vgl. Section 3.2 in Nocedal and Wright 2006).
Wir können uns leicht überlegen, dass dieser Algorithmus immer zu einem lokalen Minimum konvergieren wird und das entscheidend von der Wahl des Startpunktes abhängt.
7.6 Extra: Nichtglatte Optimierung
Ist die Zielfunktion nicht differenzierbar (oder ist die Berechnung des Gradienten zu aufwändig) kann auf Optimierungsverfahren zurückgegriffen werden, die keinen Gradienten benötigen. Die bekanntesten sind
- oder auch (nonlinear Simplex) Verfahren: Berechnet für \(n+1\) Stützpunkte (ein Simplex im \(\mathbb R^{n}\) die Werte von \(f\) und ersetzt den schlechtesten nach Kriterien die eine (vergleichsweise) schnelle Konvergenz zu einem lokalen Minimum garantieren können.
- Sogenannte generische oder genetische Algorithmen: nach dem Prinzip der Variation (oder Mutation) und Selektion wird der Suchraum \(D(f)\) in zufälliger Weise aber mit einer gewissen Systematik abgesucht – diese Algorithmen konvergieren (in Wahrscheinlichkeit) zu einem globalen Minimum sind aber vergleichsweise langsam bzw. rechenaufwändig.
7.7 Extra: Automatisches Differenzieren
Wir sehen, dass in der glatten Optimierung die Berechnung des Gradienten die wichtigste und gleichzeitig aufwändigste Komponente ist. Kann der Gradient analytisch berechnet und als Funktion zur Verfügung gestellt werden, ist dieses Problem elegant umgangen. In der Praxis sind die Probleme aber oft als eine mehrschichitige Verknüpfung von Funktionen in einem Programmcode gegeben. Andererseits sind die kleinste Elemente dieser Funktion typischerweise Elementarfunktionen, die einfach und analytisch differenziert werden können.
Die Darstellung einer Funktion, zum Beispiel, \[\begin{equation*} f(x_1, x_2) = \|(x_1, x_2)\| = \sqrt{x_1^2 + x_2^2} \end{equation*}\] die als Koordinatenfunktion für \(x_1\) dargestellt werden kann als \[ \tilde f_1(x_1, z) = g_3(g_2(g_1(x_1); z)), \quad g_3(y) = \sqrt y, \quad g_2(y;z) = y + z^2, \quad g_1(y) = y^2 \] und mittels Kettenregel die partielle Ableitung als Kombination elementarer Ableitungen berechnet als \[\begin{equation*} \frac{\partial f}{\partial x_1}(x_1,x_2) = g_3'(g_2(g_1(x_1); x_2))\cdot g_2'(g_1(x_1); x_2)\cdot g_1'(x_1) \end{equation*}\]
macht sich Automatisches Differenzieren zu Nutze und kann zu einem Programmcode
def ffun(x):
# ..... alles was f machen soll
return fxeinen Programmcode erzeugen, der grad_ffun(x) berechnet. Das ist der sogenannten Vorwärtsmodus des Automatischen Differenzierens.
Der sogenannte Rückwärtsmodus ist effizienter und kann leicht ein Programme eingebaut werden und damit zu jeder Funktionsevalution, direkt den Gradienten an dieser Stelle mitliefern.
Die systematische Verwendung des Automatischen Differenzierens ist einer der wesentlichsten Garanten für den Erfolg von machine learning, da AD das träinieren von grossen Netzwerken überhaupt erst möglich macht.
7.8 Aufgaben
7.8.1 Numerische Berechnung des Gradienten (P+T)
Berechnen sie näherungsweise den Gradienten der Beispielfunktion \[\begin{equation*} f(x_1, x_2, x_3) = \sin(x_1) + x_3\cos(x_2) + - 2x_2 + x_1^2 + x_2^2 + x_3^2 \end{equation*}\] (Achtung dieses \(f\) ist nur fast das \(g\) wie oben) im Punkt \((x_1, x_2, x_3) = (1, 1, 1)\), indem sie die partiellen Ableitungen durch den Differenzenquotienten, z.B., \[\begin{equation*} \frac{\partial g}{\partial x_2}(1, 1, 1) \approx \frac{g(1, 1+h, 1) - g(1, 1,1)}{h} \end{equation*}\] für \(h\in\{10^{-3}, 10^{-6}, 10^{-9}, 10^{-12}\}\) berechnen. Berechnen sie auch die Norm der Differenz zum exakten Wert von \(\nabla g(1, 1, 1)\) (s.o.) und interpretieren sie die Ergebnisse.
import numpy as np
def gfun(x):
return np.sin(x[0]) + x[2]*np.cos(x[1]) \
- 2*x[1] + x[0]**2 + x[1]**2 \
+ x[2]**2
def gradg(x):
return np.array([np.NaN,
-x[2]*np.sin(x[1]) - 2 + 2*x[1],
np.NaN]).reshape((3, 1))
# Inkrement
h = 1e-3
# der x-wert und das h-Inkrement in der zweiten Komponente
xzero = np.ones((3, 1))
xzeroh = xzero + np.array([0, h, 0]).reshape((3, 1))
# partieller Differenzenquotient
dgdxtwo = 1/h*(gfun(xzeroh) - gfun(xzero))
# Alle partiellen Ableitungen ergeben den Gradienten
hgrad = np.array([np.NaN, dgdxtwo, np.NaN]).reshape((3, 1))
# Analytisch bestimmter Gradient
gradx = gradg(xzero)
# Die Differenz in der Norm
hdiff = np.linalg.norm((hgrad-gradx)[1])
# bitte alle Kompenenten berechnen
# und dann die Norm ueber den ganzen Vektor nehmen
print(f'h={h:.2e}: diff in gradient {hdiff.flatten()[0]:.2e}')7.8.2 Optimierung ohne Gradienten (P+T)
Werten sie \(g\) an \(1000\) zufällig gewählten Punkten aus und lokalisieren sie das \(\bar x \in \mathbb R^{3}\) an welchem \(g\) in diesem Sample den kleinsten Wert annimmt.
Überlegen Sie sich eine mögliche Verbesserung dieses rein auf Zufall basierenden Verfahrens. Wer Inspiration braucht, kann mal nach Generischen Algorithmen suchen.
7.8.3 Gradientenabstiegsverfahren (P)
Implementieren Sie ein Gradientenabstiegsverfahren mit line search durch Bisektion und berechnen Sie ein Minimum von \(g\) damit.
import numpy as np
from loesung_5_1 import gfun, gradg
def min_by_btls(func, v=None, curx=None,
azero=10., tau=.8, c=.9, maxiter=200):
''' find a smaller value of f in the direction
f(x+s*v)
for s in [0, azero]
by backtracking linesearch
https://en.wikipedia.org/wiki/Backtracking_line_search
'''
m = -v.T.dot(v)
cstep = azero
t = -c*m
cval = func(curx)
for kkk in range(maxiter):
newx = curx+cstep*v
if cval - func(newx) >= cstep*t:
return newx
else:
cstep = tau*cstep
raise UserWarning('no smaller value could be found')
return
def gradienten_abstieg_linesearch(func=None, grad=None, inix=None,
maxiter=100, grad_tol=1e-6):
'''sucht ein Minimum einer Funktion `func` durch
* Evaluieren des Gradienten `grad`
* und anpassen von `inix` in Richtung von `-grad`
* mit einem `line search Verfahren`
'''
# initialisierung
curx = inix
for kkk in range(maxiter):
# compute the current gradient
# finde ein neues `newx` in -Gradienten Richtung
# check ob der Gradient unter der Toleranz ist
# anderenfalls:
curx = newx # naechster Iterationschritt
print(f'max iter {maxiter} reached -- size of grad {nrmcgrd:.2e}')
return newx
# Startwert
xzero = np.ones((3, 1))
minx = gradienten_abstieg_linesearch(func=gfun, grad=gradg, inix=xzero)
print(f'found minimum f(x) = {gfun(minx)}')
print('at x = ', minx)7.8.4 Built-in Optimierung in Scipy (P)
Benutzen sie die
scipy.optimize.minimizeRoutine um ein Minimum von \(g\) zu finden und messen Sie die Zeit die der Algorithmus braucht.Geben Sie dem Algorithmus eine Funktion mit, die den Gradienten berechnet. Berechnen sie ein Minimum und vergleichen Sie die benötigte Zeit. Hinweis: die Routine braucht den Gradienten als flachen Vektor. Das kann (wie unten im Beispiel) durch eine wrapper Funktion erreicht werden.
import numpy as np
from timeit import default_timer
from scipy.optimize import minimize
from loesung_5_1 import gfun, gradg
def gradforopt(x):
return gradg(x).flatten()
starttime = default_timer()
result = minimize(...., jac=gradforopt)
runtime = default_timer() - starttime
print(f'with gradient: found minimum f(x) = {result.fun}')
print('at x = ', result.x)
print(f'in {runtime:.4f}s time')Referenzen
Nocedal, J., Wright, S.J.: Numerical optimization. Springer (2006)