Ich möchte eine Gradienten-Abstiegsoptimierung durchführen, um die Kosten für eine Instanziierung von Variablen zu minimieren. Mein Programm ist sehr rechenintensiv, deshalb suche ich nach einer beliebten Bibliothek mit einer schnellen Implementierung von GD. Was ist die empfohlene Bibliothek / Referenz?
GSL ist eine großartige (und kostenlose) Bibliothek, die bereits gemeinsame Funktionen von mathematischem und wissenschaftlichem Interesse implementiert. p>
Sie können das gesamte Referenzhandbuch online durchlesen. Herum stochern, das fängt an, interessant auszusehen, aber ich denke wir müssten mehr über das Problem wissen.
Eine der angesehensten Bibliotheken für diese Art von Optimierungsarbeit sind die NAG-Bibliotheken . Diese werden weltweit in Universitäten und in der Industrie eingesetzt. Sie sind für C / FORTRAN verfügbar. Sie sind sehr unfrei und enthalten viel mehr als nur Minimierungsfunktionen - Eine Menge allgemeiner numerischer Mathematik wird behandelt.
Jedenfalls vermute ich, dass diese Bibliothek für das, was Sie brauchen, übertrieben ist. Aber hier sind die Teile zur Minimierung: Lokale Minimierung und Globale Minimierung .
Es klingt, als ob Sie mit Minimierungsmethoden ziemlich neu sind. Wann immer ich eine neue Reihe von numerischen Methoden lernen muss, schaue ich normalerweise in Numerical Recipes nach. Es ist ein Buch, das einen guten Überblick über die gängigsten Methoden auf diesem Gebiet, ihre Kompromisse und (wichtig) gibt, wo man in der Literatur nach mehr Informationen sucht. Es ist normalerweise nicht, wo ich stoppe, aber es ist oft ein hilfreicher Ausgangspunkt.
Wenn Ihre Funktion beispielsweise kostspielig ist, ist es Ihr Ziel, die Anzahl der Evaluierungen zu minimieren, die konvergieren müssen. Wenn Sie analytische Ausdrücke für den Gradienten haben, dann wird eine gradientenbasierte Methode wahrscheinlich zu Ihrem Vorteil funktionieren, wenn Sie davon ausgehen, dass die Funktion und ihr Gradient sich in der interessierenden Domäne gut verhalten (Singularitäten fehlen).
Wenn Sie keine analytischen Gradienten haben, ist es fast immer besser, einen Ansatz wie zu verwenden downhill simplex , das nur die Funktion bewertet (nicht ihre Gradienten). Numerische Gradienten sind teuer .
Beachten Sie auch, dass alle diese Ansätze zu lokalen Minima konvergieren, sodass sie ziemlich empfindlich auf den Punkt reagieren, an dem Sie das Optimierungsprogramm anfänglich starten. Globale Optimierung ist ein ganz anderes Biest.
Als abschließender Gedanke wird fast der gesamte Code, den Sie zur Minimierung finden können, einigermaßen effizient sein. Der tatsächliche Aufwand für die Minimierung liegt in der Kostenfunktion. Sie sollten Zeit damit verbringen, Ihre Kostenfunktion zu profilieren und zu optimieren, und einen Algorithmus auswählen, der die Häufigkeit minimiert, mit der Sie ihn aufrufen müssen (Methoden wie Downhill-Simplex, konjugierter Gradient und BFGS alle scheinen auf verschiedene Arten von Problemen).
In Bezug auf den tatsächlichen Code finden Sie neben NETLIB viele nette Routinen zusätzlich zu den anderen erwähnten Bibliotheken. Die meisten Routinen sind in FORTRAN 77, aber nicht alle; Um sie in C zu konvertieren, ist f2c ziemlich nützlich.
Tags und Links optimization c++ visual-studio-2010 numerical-methods gradient-descent