Parallele Optimierungsalgorithmen für ein Problem mit sehr teurer Objektivfunktion

Ich optimiere eine Funktion von 10-20 Variablen. Die schlechte Nachricht ist, dass jede Funktionsbewertung teuer ist, etwa 30 Minuten serielle Berechnung. Die gute Nachricht ist, dass mir ein Cluster mit ein paar Dutzend Rechenknoten zur Verfügung steht.

Daher die Frage: Gibt es Optimierungsalgorithmen, mit denen ich die gesamte Rechenleistung effizient nutzen kann?

Auf einer Seite des Spektrums wäre eine erschöpfende Suche: Unterteilen Sie den gesamten Suchraum in ein feines Gitter und berechnen Sie die Funktion an jedem Gitterpunkt unabhängig. Dies ist sicherlich eine sehr parallele Berechnung, aber der Algorithmus ist schrecklich ineffizient.

Auf der anderen Seite des Spektrums befinden sich Quasi-Newton-Algorithmen: Aktualisieren Sie intelligent die nächste Schätzung der Parameter basierend auf der Vorgeschichte. Dies ist ein effizienter Algorithmus, aber ich weiß nicht, wie ich ihn parallelisieren soll: Das Konzept der "Schätzung der Parameter basierend auf der Vorgeschichte" klingt wie eine serielle Berechnung.

Quadratische Algorithmen scheinen irgendwo in der Mitte zu liegen: Man kann das anfängliche "Ersatzmodell" aufbauen, indem man eine Reihe von Werten parallel berechnet, aber ich weiß nicht, ob die verbleibenden Iterationen parallelisierbar sind.

Irgendwelche Vorschläge, welche gradientenfreien Optimierungsmethoden in einem Cluster gut funktionieren würden? Gibt es auch parallele Implementierungen von Optimierungsalgorithmen, die derzeit verfügbar sind?

Wie Paulus feststellt, ist es ohne weitere Informationen schwierig, ohne Annahmen Ratschläge zu erteilen.

Bei 10-20 Variablen und teuren Funktionsauswertungen werden tendenziell ableitungsfreie Optimierungsalgorithmen empfohlen. Ich werde dem Rat von Paul stark widersprechen: Sie benötigen im Allgemeinen einen maschinengenauen Gradienten, es sei denn, Sie wenden eine spezielle Methode an (zum Beispiel wird die stochastische Gradientenabnahme beim maschinellen Lernen die Form des Ziels ausnutzen, vernünftig zu sein Gradientenschätzungen).

Jeder Quasi-Newton-Schritt hat die Form:

wo eine Annäherung an die Hessische Matrix ist,dkdie Suchrichtung ist,xkder Wert der Entscheidungsvariablen bei der aktuellen Iteration ist,fIhre Zielfunktion ist und∇fder Gradient Ihres Ziels ist und Entscheidungsvariablen werden wiefolgtaktualisiert:xk+1=xk+αkdk, wobeiα$\tilde{H}$$d_{k}$$x_{k}$$f$$\nabla{f}$$x_{k+1} = x_{k} + \alpha_{k}d_{k}$$\alpha_{k}$ist eine in gewisser Weise festgelegte Schrittweite (wie eine Liniensuche). Sie kommen auf bestimmte Weise mit der Approximation des Hessischen durch und Ihre Iterationen werden konvergieren. Wenn Sie jedoch so etwas wie endliche Differenzenapproximationen des Hessischen durch exakte Gradienten verwenden, können Sie unter Problemen leiden, die auf mangelnde Konditionierung zurückzuführen sind. Typischerweise wird das Hessische mithilfe des Gradienten approximiert (z. B. BFGS-Typ-Methoden mit Rang-1-Aktualisierungen des Hessischen).

Die Annäherung des Hessischen und des Gradienten über endliche Differenzen ist aus mehreren Gründen eine schlechte Idee:

• Da der Gradient fehlerhaft sein wird, entspricht die angewendete Quasi-Newton-Methode dem Auffinden der Wurzel einer verrauschten Funktion
• Wenn Funktionsauswertungen teuer sind und Sie versuchen, einen Gradienten in Bezug auf Variablen auszuwerten , werden Sie N Funktionsauswertungen pro Iteration kosten$N$$N$
• Wenn Sie Fehler in der Steigung haben, werden Sie mehr Fehler in Ihrem Hessischen haben, was ein großes Problem in Bezug auf die Konditionierung des linearen Systems darstellt
• ... und es kostet Sie Funktionsbewertungen pro Iteration$N^{2}$

Um also eine schlechte Iteration von Quasi-Newton zu erhalten, führen Sie bis zu 420 Funktionsbewertungen mit 30 Minuten pro Bewertung durch, was bedeutet, dass Sie entweder eine Weile auf jede Iteration warten müssen oder brauchen einen großen Cluster nur für die Funktionsauswertung. Die tatsächlichen linearen Lösungen werden (höchstens!) 20 mal 20 Matrizen haben, daher gibt es keinen Grund, diese zu parallelisieren. Wenn Sie Verlaufsinformationen erhalten können, indem Sie beispielsweise ein benachbartes Problem lösen, ist dies möglicherweise sinnvoller. In diesem Fall lohnt es sich möglicherweise, ein Buch wie Nocedal & Wright zu lesen.

Wenn Sie eine Vielzahl von Funktionsbewertungen parallel durchführen möchten, sollten Sie sich stattdessen mit Ersatzmodellierungsansätzen oder Methoden zur Generierung von Mengenrecherchen befassen, bevor Sie Quasi-Newton-Ansätze in Betracht ziehen. Die klassischen Übersichtsartikel sind die von Rios und Sahinidis zu derivatfreien Methoden , die 2012 veröffentlicht wurden und einen wirklich guten und umfassenden Vergleich liefern. der Benchmarking-Artikel von More and Wild aus dem Jahr 2009; das Lehrbuch 2009 "Introduction to Derivative-Free Optimization" von Conn, Scheinberg und Vicente; und der Übersichtsartikel über Suchmethoden für Generierungsmengen von Kolda, Lewis und Torczon aus dem Jahr 2003.

Wie bereits erwähnt, implementiert das DAKOTA-Softwarepaket einige dieser Methoden, ebenso wie NLOPT , das DIRECT implementiert, und einige der Ersatzmodellierungsmethoden von Powell. Vielleicht haben Sie auch einen Blick auf nehmen MCS ; Es ist in MATLAB geschrieben, aber vielleicht können Sie die MATLAB-Implementierung auf die Sprache Ihrer Wahl portieren. DAKOTA besteht im Wesentlichen aus einer Sammlung von Skripten, mit denen Sie Ihre teure Simulation ausführen und Daten für Optimierungsalgorithmen sammeln können. NLOPT verfügt über Schnittstellen in einer großen Anzahl von Sprachen. Das Erlernen von DAKOTA nimmt jedoch einige Zeit in Anspruch und es ist eine Menge Dokumentation zu lesen.

Vielleicht suchen Sie nach Algorithmen, die auf Ersatzzeichen basieren. Diese Algorithmen verwenden Ersatzmodelle, um die reellen rechenintensiven Modelle während des Optimierungsprozesses zu ersetzen, und versuchen, eine geeignete Lösung zu erhalten, indem so wenig Auswertungen der rechenintensiven Modelle wie möglich verwendet werden.

Ich denke, dass die Methode "Mode Pursuing Sampling" verwendet werden kann, um Ihr Problem zu lösen. Dieser Algorithmus verwendet das RBF-Ersatzmodell, um die teure Zielfunktion zu approximieren, und kann nichtlineare Einschränkungen verarbeiten. Noch wichtiger ist, dass mehrere Kandidaten für die teuren Funktionsbewertungen ausgewählt werden, sodass Sie diese Kandidaten für die parallele Berechnung verteilen können, um den Suchprozess weiter zu beschleunigen. Der Code ist Open Source und in MATLAB geschrieben.

Referenz

Wang, L., Shan, S. & Wang, GG (2004). Modusverfolgende Abtastmethode zur globalen Optimierung teurer Black-Box-Funktionen. Engineering Optimization, 36 (4), 419 & ndash; 438.

Ich bin nicht sicher, ob ein paralleler Algorithmus wirklich das ist, wonach Sie suchen. Es sind Ihre Funktionsbewertungen, die sehr kostspielig sind. Sie möchten die Funktion selbst parallelisieren, nicht unbedingt den Optimierungsalgorithmus.

Wenn Sie das nicht können, dann gibt es einen Mittelweg zwischen erschöpfender Suche und Newton-Algorithmus, es sind Monte-Carlo-Methoden. Sie können auf einer Reihe von verschiedenen Kernen / Knoten denselben Algorithmus starten, der für lokale Optima anfällig ist (Quasi-Newton-Algorithmen), aber alle mit zufälligen Anfangsbedingungen. Ihre beste Vermutung für das wahre Optimum ist das Minimum der Minima. Dies ist trivial zu parallelisieren und kann verwendet werden, um jede Methode zu erweitern. Obwohl es nicht perfekt effizient ist, kann es bei ausreichender Rechenleistung die Programmierproduktivität gegenüber der Algorithmusleistung entscheidend verbessern (wenn Sie über viel Rechenleistung verfügen, kann dies beendet werden, bevor Sie jemals einen schickeren Algorithmus fertiggestellt haben).

Die Wahl des Optimierungsalgorithmus (und damit seiner Parallelisierung) hängt stark von den Eigenschaften der Zielfunktion und den Randbedingungen ab. Ohne mehr über das Problem zu wissen, ist es schwierig, sinnvolle Ratschläge zu geben.

Aber aus Ihren Überlegungen zu Newton-Methoden schließe ich, dass Ihre objektive Funktion differenzierbar ist. Wenn möglich, würde Ihr Problem von einer Parallelisierung der Funktionsbewertung stark profitieren. Wenn dies nicht möglich ist, können Sie auch eine ungenaue Newton-Methode in Betracht ziehen, bei der die exakten Gradienten / Hessischen durch Näherungen mit endlichen Differenzen ersetzt werden. Anschließend können Sie alle Ihnen zur Verfügung stehenden Prozessoren verwenden, um jedes Nicht-Null-Element des jacobian zu berechnen, wie @stali vorschlägt.

Weitere Informationen finden Sie in Kapitel 7, Numerische Optimierung von Nocedal & Wright . Es gibt viele Optimierungssoftwarepakete, die dies parallel implementieren. Zu den am weitesten verbreiteten Freeware- Programmen gehört das DAKOTA-Softwarepaket (Sandia National Labs) .

Hier ist eine Lösung für Ihr Problem.

Beschreibung eines mathematischen Verfahren wird in diesem vorgesehenen Papier .