Vor den Hinweis auf eine mögliche, einfache Implementierung eines zur Verfügung gestellt werden Quasi-Newton-Optimierungsroutine in CUDA, einige Worte darüber, wie ein Quasi-Newton-Optimierer arbeitet.
Betrachten sie eine Funktion f von N realen Variablen x und eine zweite Ordnung Expansions um einen bestimmten Punkt xi:
wo A die Hesse-Matrix ist .
Um ein Minimum ausgehend von einem Punkt xi impliziert zu finden, Newton-Verfahren besteht aus Zwingen
was zur Folge hat
und was wiederum wissen die Umkehrung des Hessischen.Darüber hinaus die Funktion ab, die Update-Richtung
sein sollte, so dass
, die die
Gemäß der obigen Ungleichheit impliziert, um sicherzustellen, , sollte die hessische Matrix sein definitiv positiv. Leider ist die Hesse-Matrix nicht notwendigerweise eindeutig positiv, insbesondere weit entfernt von einem Minimum von f, so dass die Verwendung der Umkehrung des Hessischen, zusätzlich rechnerisch belastet, auch schädlich sein kann und den Vorgang noch weiter vom Minimum zu Regionen von steigende Werte von f. Allgemein gesprochen ist es praktischer, ein Quasi-Newton-Verfahren zu verwenden, d. H. Eine Näherung der Umkehrung des Hessischen, die definitiv positiv bleibt und die Iteration nach Iterationen aktualisiert, die zur Inversion des Hessschen selbst konvergieren. Eine grobe Begründung für eine Quasi-Newton-Methode lautet wie folgt. Betrachten
und
Subtraktion der beiden Gleichungen, haben wir die Update-Regel für das Newton Verfahren
Die Aktualisierungsregel für die quasi- Newton-Verfahren ist das folgende
wo Hallo + 1 ist die genannte Matrix, die die Inverse der Hessian annähert und der Schritt nach dem Schritt der Aktualisierung.
Es gibt mehrere Regeln für die Aktualisierung Hallo + 1, und ich gehe nicht in die Details dieses Punktes. Eine sehr häufige wird von der Broyden-Fletcher-Goldfarb-Shanno zur Verfügung gestellt, aber in vielen Fällen ist das Polak-Ribiére Schema wirksam genug.
Die Umsetzung CUDA die gleichen Schritte des klassischen Numerical Recipes Ansatz folgen kann, aber unter Berücksichtigung, dass:
1) Vektor- und Matrixoperationen wirksam durch CUDA Thrust oder cuBLAS erreicht werden; 2) Die Steuerlogik kann von der CPU ausgeführt werden; 3) Die Zeilenminimierung mit Roots-Bracketing und Root-Ergebnissen kann auf der CPU durchgeführt werden und beschleunigt nur die Kostenfunktions- und Gradientenauswertungen der GPU.
Durch das obige Schema können Unbekannte, Gradienten und Hessian auf dem Gerät gespeichert werden, ohne dass sie von Host zu Gerät verschoben werden müssen.
Bitte beachten Sie auch, dass einige Ansätze in der Literatur verfügbar sind, in dem Versuch, die Linie Minimierung parallelisieren werden ebenfalls vorgeschlagen, siehe
Y. Fei, G. Rong, B. Wang, W. Wang, " Parallel L-BFGS-B Algorithmus auf GPU ", Computer & Grafiken, vol. 40, 2014, S. 1-9.
An diesen github page, eine voll ist CUDA Implementierung zur Verfügung, die Numerical Recipes Ansatz linmin, mkbrak und dbrent auf den GPU parallel Fall beschäftigt verallgemeinern. Dieser Ansatz implementiert das Schema von Polak-Ribière, kann jedoch leicht auf andere Quasi-Newton-Optimierungsprobleme verallgemeinert werden.
https://developer.nvidia.com/cublas kann mit linear-algebra helfen – adray
@adray: Danke! Sind auch einige der Optimierungsverfahren verfügbar, vielleicht in einer anderen Bibliothek? –