Ich habe eine Zielfunktion von einem Wert abhängt , wobei die Lösung für eine PDE ist. Ich optimiere durch Gradientenabstieg auf den Anfangszustand der PDE: . Das heißt, ich aktualisiere und dann muss die PDE integriert werden, um meinen Rest zu berechnen. Das heißt, wenn ich eine Liniensuche nach der Schrittgröße des Gradientenabfalls durchführen würde (nenne es ), müsste ich für jeden möglichen Wert von die PDE erneut integrieren.
In meinem Fall wäre das unerschwinglich teuer. Gibt es eine andere Option für die Schrittgröße des adaptiven Gradientenabstiegs?
Ich suche hier nicht nur nach mathematisch prinzipiellen Schemata (obwohl das natürlich besser ist, wenn etwas existiert), sondern würde mich über alles freuen, was im Allgemeinen besser ist als eine statische Schrittgröße.
Vielen Dank!
quelle
Antworten:
Ich beginne mit einer allgemeinen Bemerkung: Informationen erster Ordnung (dh die Verwendung von nur Verläufen, die die Steigung codieren) können nur Richtungsinformationen liefern: Sie können Ihnen sagen, dass der Funktionswert in Suchrichtung abnimmt, jedoch nicht für wie lange . Um zu entscheiden, wie weit die Suchrichtung gehen soll, benötigen Sie zusätzliche Informationen (Gradientenabstieg mit konstanten Schrittlängen kann selbst bei konvexen quadratischen Problemen fehlschlagen). Dafür haben Sie grundsätzlich zwei Möglichkeiten:
Wenn Sie beim Schreiben keinen Zugriff auf zweite Ableitungen haben und die Bewertung der Zielfunktion sehr teuer ist, besteht Ihre einzige Hoffnung darin, Kompromisse einzugehen: Verwenden Sie genügend ungefähre Informationen zweiter Ordnung, um eine gute Kandidatenschrittlänge zu erhalten, sodass eine Linie entsteht Die Suche erfordert nur Auswertungen (dh höchstens ein (kleines) konstantes Vielfaches des Aufwands, den Sie zur Bewertung Ihres Gradienten benötigen).O(1)
Eine Möglichkeit ist die Verwendung von Barzilai-Borwein-Schrittlängen (siehe z. B. Fletcher: Zur Barzilai-Borwein-Methode . Optimierung und Steuerung mit Anwendungen, 235–256, Appl. Optim., 96, Springer, New York, 2005 ). Die Idee ist, eine endliche Differenznäherung der Krümmung entlang der Suchrichtung zu verwenden, um eine Schätzung der Schrittgröße zu erhalten. Wählen Sie insbesondere beliebig, setzen Sie g 0 : = ∇ f ( x 0 ) und dann für k = 0 , . . . ::α0>0 g0:=∇f(x0) k=0,...
Ein alternativer (und meiner Meinung nach viel besserer) Ansatz wäre die Verwendung dieser Finite-Differenzen-Näherung bereits bei der Berechnung der Suchrichtung. Dies wird als Quasi-Newton-Methode bezeichnet . Die Idee ist, schrittweise eine Approximation des Hessischen unter Verwendung von Gradientendifferenzen zu erstellen . Zum Beispiel könnten Sie (die Identitätsmatrix) nehmen und für lösen und setze mit wie oben und . (Dies wird als Broyden-Update bezeichnetH 0 = I d k = 0 , … H k s k = - g k , H k + 1 = H k + ( y k - H k s k ) T ( s k ) T.∇2f(xk) H0=Id k=0,…
Glücklicherweise gibt es in diesem Zusammenhang einen alternativen Ansatz, der jede Funktionsbewertung nutzt. Die Idee ist, dass für symmetrisch und positiv definit (was für das BFGS-Update garantiert ist) das Lösen von der Minimierung des quadratischen Modells In einer Vertrauensbereichsmethode würden Sie dies mit der zusätzlichen Einschränkung tun , wobei ein entsprechend gewählter Vertrauensbereichsradius ist (der die Rolle der Schrittlänge ). Die Schlüsselidee besteht nun darin, diesen Radius basierend auf dem berechneten Schritt adaptiv auszuwählen. Insbesondere betrachten Sie das VerhältnisHk (1)
quelle