Gradient Descent und die konjugierte Gradientenmethode sind beide Algorithmen zur Minimierung nichtlinearer Funktionen, dh Funktionen wie die Rosenbrock-Funktion
f(x1,x2)=(1−x1)2+100(x2−x21)2
oder eine multivariate quadratische Funktion (in diesem Fall mit einem symmetrischen quadratischen Term)
f(x)=12xTATAx−bTAx.
Beide Algorithmen sind auch iterativ und suchrichtungsbasiert. Für den Rest dieses Beitrags sind und Vektoren der Länge ; und sind Skalare, und hochgestellte Zeichen bezeichnen den Iterationsindex. Der Gradientenabstieg und die konjugierte Gradientenmethode können verwendet werden, um den Wert zu finden, der gelöst wirdd n f ( x ) α x ∗xdnf(x)αx∗
minf(x)
Beide Methoden beginnen mit einer anfänglichen Vermutung, , und berechnen dann die nächste Iteration unter Verwendung einer Funktion des Formularsx0
xi+1=xi+αidi.
Mit anderen Worten, der nächste Wert von wird gefunden, indem an der aktuellen Position und in der Suchrichtung für eine gewisse Entfernung bewegt wird . Bei beiden Methoden kann die zu bewegende Entfernung durch eine Liniensuche ermittelt werden (minimiere über ). Es können auch andere Kriterien angewendet werden. Wo sich die beiden Methoden unterscheiden, liegt in ihrer Wahl von . Für die Gradientenmethode ist . Für die konjugierte Gradientenmethode wird das Grahm-Schmidt-Verfahren verwendet, um die Gradientenvektoren zu orthogonalisieren. Insbesondere ist , aber dann ist gleichxxidiαif(xi+αidi)αididi=−∇f(xi)d0=−∇f(x0)d1−∇f(x1) minus der Projektion dieses Vektors auf so dass . Jeder nachfolgende Gradientenvektor ist gegen alle vorherigen orthogonalisiert, was zu sehr schönen Eigenschaften für die obige quadratische Funktion führt.d0(d1)Td0=0
Die obige quadratische Funktion (und verwandte Formulierungen) ist auch , wo sich die Diskussion des Lösens die konjugierte Gradientenverfahren unter Verwendung kommt, da das Minimum des an dem Punkt erreicht wird , wo .f ( x ) x A x = bAx=bf(x)xAx=b