Bestimmen der Abstiegsrichtung

Eine Abstiegsrichtung im Punkt ${\displaystyle x^{k}}$ ist ein Vektor ${\displaystyle d^{k}}$, der

${\displaystyle \left(\nabla f(x^{k})\right)^{T}d^{k}<0}$

erfüllt. Intuitiv bedeutet das, dass der Winkel zwischen ${\displaystyle \nabla f(x^{k})}$ und ${\displaystyle d^{k}}$ größer als 90° ist. Da der Gradient ${\displaystyle \nabla f(x^{k})}$ in Richtung des steilsten Anstiegs zeigt, ist ${\displaystyle d^{k}}$ eine Richtung entlang derer sich der Funktionswert verringert.

Viele Gradientenmethoden berechnen die Abstiegsrichtung anhand

${\displaystyle d^{k}=-D^{k}\nabla f(x^{k}),}$

wobei ${\displaystyle D^{k}}$ eine positiv definite Matrix ist. In diesem Fall lautet die Bedingung für die Abstiegsrichtung

${\displaystyle \left(\nabla f(x^{k})\right)^{T}\left(-D^{k}\right)\nabla f(x^{k})<0,}$

und ist dank der positiven Definitheit von ${\displaystyle D^{k}}$ immer erfüllt.

Mit der Wahl der Matrix ${\displaystyle D^{k}}$ erhält man folgende Algorithmen:

• ${\displaystyle D^{k}=I}$, wobei ${\displaystyle I}$ die Einheitsmatrix ist, ergibt das Verfahren des steilsten Abstiegs. Die Abstiegsrichtung ist in diesem Fall einfach der negative Gradient, ${\displaystyle d^{k}=-\nabla f(x^{k})}$.
• ${\displaystyle D^{k}={\begin{bmatrix}a_{1}&0&\cdots &0\\0&a_{2}&\ddots &\vdots \\\vdots &\ddots &\ddots &0\\0&\cdots &0&a_{n}\end{bmatrix}}}$, wobei ${\displaystyle a_{i}>0,\ i=1,\ldots ,n}$ sodass ${\displaystyle D^{k}}$ positiv definit ist, ist ein diagonal skalierter steilster Abstieg. Oft werden die ${\displaystyle a_{i}}$ als Approximation der Inversen der 2. Ableitung gewählt, also ${\displaystyle a_{i}\approx \left({\frac {\partial ^{2}f(x^{k})}{\left(\partial x_{i}\right)^{2}}}\right)^{-1}}$.
• ${\displaystyle D^{k}=\left(\nabla ^{2}f(x^{k})\right)^{-1}}$, die Inverse Hesse-Matrix, ergibt das Newton-Verfahren für die Lösung nichtlinearer Minimierungsprobleme.
• Da die Berechnung der Hesse-Matrix oft aufwändig ist, gibt es eine Klasse von Algorithmen, welche eine Approximation ${\displaystyle D^{k}\approx \left(\nabla ^{2}f(x)\right)^{-1}}$ verwenden. Solche Methoden werden als Quasi-Newton-Verfahren bezeichnet, es gibt verschiedene Arten wie die Approximation berechnet wird. Ein wichtiger Vertreter aus der Klasse der Quasi-Newton Methoden ist der BFGS Algorithmus.
• Falls das Optimierungsproblem in der speziellen Form

${\displaystyle \min _{x\in \mathbb {R} ^{n}}\left\{\|f(x)\|^{2}=\sum _{i=1}^{m}\left(f_{i}(x)\right)^{2}\right\}}$,

also als Summe von Quadraten von Funktionen, gegeben ist, erhält man mit ${\displaystyle D^{k}=\left(J^{T}J\right)^{-1}}$, wobei ${\displaystyle J}$ die Jacobi-Matrix von ${\displaystyle f}$ im Punkt ${\displaystyle x^{k}}$ ist, das Gauß-Newton-Verfahren.

Bestimmen der Schrittweite

Die Bestimmung der Schrittweite ${\displaystyle \alpha ^{k}}$ ist ein wichtiger Teil des Gradientenverfahren, der großen Einfluss auf die Konvergenz haben kann. Ausgehend vom Iterationsschritt ${\displaystyle x^{k+1}=x^{k}+\alpha ^{k}d^{k}}$ betrachtet man den Wert von ${\displaystyle f}$ entlang der Linie ${\displaystyle x^{k}+\alpha d^{k}}$, also ${\displaystyle f(\alpha )=f(x^{k}+\alpha d^{k})}$. Man spricht in diesem Zusammenhang oft auch von Liniensuche. Die ideale Wahl wäre es, die Schrittweite als jenen Wert zu berechnen, der die Funktion ${\displaystyle f(\alpha )}$ minimiert, also das eindimensionale Problem

${\displaystyle \min _{\alpha >0}\left\{f(\alpha )=f(x^{k}+\alpha d^{k})\right\}}$

zu lösen. Dies wird als exakte Liniensuche bezeichnet und wird in dieser Form in der Praxis selten angewandt, da selbst für einfache Optimierungsprobleme die exakte Bestimmung der Schrittweite sehr rechenaufwändig ist.

Als Alternative zur exakten Liniensuche lockert man die Erfordernisse und beschränkt sich darauf, dass der Funktionswert sich mit jedem Iterationsschritt „genügend“ verringert. Dies wird auch als inexakte Liniensuche bezeichnet. Die einfachste Möglichkeit besteht darin, die Schrittweite ${\displaystyle \alpha }$ ausgehend von einem Startwert (z. B. ${\displaystyle \alpha =1}$) so lange zu verringern, bis ${\displaystyle f(x^{k+1})=f(x^{k}+\alpha d^{k})<f(x^{k})}$ erreicht ist. Diese Methode funktioniert in der Praxis oft zufriedenstellend, man kann jedoch zeigen, dass für manche pathologischen Funktionen diese Liniensuche zwar in jedem Schritt den Funktionswert verringert, die Folge ${\displaystyle x^{k}}$ jedoch nicht zu einem stationären Punkt konvergiert.

Wähle Startwert für ${\displaystyle \alpha }$, z. B. ${\displaystyle \alpha =1}$, wähle Konstanten ${\displaystyle \sigma \in (0,1),\ \rho \in (0,1)}$

while ${\displaystyle f(x^{k}+\alpha d^{k})>f(x^{k})+\sigma \alpha \left(\nabla f(x^{k})\right)^{T}d^{k}}$
  ${\displaystyle \alpha =\rho \alpha }$
end

Setze ${\displaystyle \alpha ^{k}=\alpha }$