Finden eines globalen Minimums einer glatten, begrenzten, nicht konvexen 2D-Funktion, deren Auswertung kostspielig ist

Ich habe eine beschränkte nicht-konvexe 2-D-Funktion, für die ich das Minimum finden möchte. Die Funktion ist ziemlich flüssig. Die Bewertung ist kostspielig. Ein akzeptabler Fehler beträgt ungefähr 3% der Funktionsdomäne in jeder Achse.

Ich habe versucht, die Implementierung des DIRECT-Algorithmus in der NLOPT-Bibliothek auszuführen, aber es ergab sich keine wesentliche Verbesserung gegenüber der Brute-Force-Suche in Bezug auf die Anzahl der Funktionsbewertungen, die für die erforderliche Genauigkeit erforderlich sind, und es gab einige Ausreißer.

Welche anderen globalen Optimierungslöser sollte ich berücksichtigen?

Ich möchte einen etwas anderen Ansatz vorschlagen als die anderen Antworten, obwohl @barron indirekt dasselbe diskutiert hat.

Statt Ihre Funktion direkt zu optimieren, das heißt , indem sie bei einer Reihe von Punkten Auswertung Punkte , die (hoffentlich) Converge zu einem (lokalen) optimal, Sie das Konzept der Verwendung könnten Surrogat - Modellierung , das ist Sehr gut geeignet für Probleme der von Ihnen beschriebenen Art (hohe Kosten, glatt, begrenzt, niedrig dimensioniert, dh weniger als 20 Unbekannte).$\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_k$$\textit{surrogate modelling}$

Insbesondere Surrogat Modellierung funktioniert durch eine Modellfunktion der Einrichtung Ihrer wahren Funktion f ∈ R d → R . Der Schlüssel ist, dass c zwar nicht perfekt für f steht, die Bewertung jedoch weitaus billiger ist.$c \in \mathbb{R}^d \rightarrow \mathbb{R}$$f \in \mathbb{R}^d \rightarrow \mathbb{R}$$c$$f$

Ein typischer Optimierungsprozess wäre also:

1. Bewerten Sie an einer Menge von j Anfangspunkten x 1 , x 2 , … , x j . Beachten Sie, dass keine Derivate benötigt werden. Beachten Sie auch, dass diese Punkte gleichmäßig über den Suchraum verteilt sein sollten, z. B. durch Latin Hypercube Sampling oder ein ähnliches raumfüllendes Design.$f$$j$$\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_j$
2. Basierend auf diesem ursprünglichen Daten - Set, erstellen Sie eine Modellfunktion . Sie könnten eine Kreuzvalidierung verwenden, um Ihr Modell zu validieren (dh Sie können nur eine Teilmenge der ursprünglichen j- Punkte verwenden, um c zu erstellen , und dann anhand des restlichen Datensatzes überprüfen, wie gut c diese Werte vorhersagt).$c$$j$$c$$c$
3. Verwenden Sie ein Kriterium wie das Kriterium der erwarteten Verbesserung (Expected Improvement, EI), um herauszufinden, wo mehr Stichproben „eingetragen“ werden müssen, um durch Stichprobenerfassung genauer zu machen . F. Dies ist theoretisch weitaus besser untersucht, als es scheint, und das EI-Kriterium ist sehr gut erforscht. Das EI-Kriterium ist auch kein gieriges Kriterium, sodass Sie beide eine gute Gesamtverbesserung der Modellgenauigkeit erzielen und gleichzeitig die Genauigkeit in der Nähe potenzieller Optima priorisieren.$c$$f$
4. Wenn Ihr Modell nicht genau genug ist, wiederholen Sie Schritt 3, oder verwenden Sie Ihre bevorzugte Optimierungsroutine, um das Optimum von zu finden , das sich sehr kostengünstig auswerten lässt (Sie können also jede beliebige Routine verwenden, auch solche, die Ableitungen erfordern, oder einfach Funktion feinmaschig auswerten).$c$

Im Allgemeinen ist dies mit EGO, Efficient Global Optimization, gemeint, wie von @barron vorgeschlagen. Ich möchte betonen, dass dies für Ihre Anwendung perfekt geeignet erscheint: Sie erhalten ein überraschend genaues Modell, das auf relativ wenigen Auswertungen von basiert , und können dann jeden gewünschten Optimierungsalgorithmus verwenden. Was häufig auch interessant ist, ist, dass Sie jetzt c auf einem Netz auswerten und zeichnen können, um so einen Einblick in das allgemeine Erscheinungsbild von f zu erhalten . Ein weiterer interessanter Punkt ist, dass die meisten Ersatzmodellierungstechniken auch statistische Fehlerschätzungen liefern, wodurch eine Unsicherheitsschätzung möglich wird.$f$$c$$f$

Wie man konstruiert, ist natürlich eine offene Frage, aber oft werden Kriging- oder sogenannte Space-Mapping-Modelle verwendet.$c$

Natürlich ist das alles ziemlich viel Programmierarbeit, aber viele andere Leute haben sehr gute Implementierungen gemacht. In Matlab kenne ich nur die DACE-Software-Toolbox, die DACE kostenlos ist. TOMLAB bietet möglicherweise auch ein Matlab-Paket an, kostet aber Geld - ich glaube jedoch, dass es auch in C ++ funktioniert und weitaus mehr Funktionen bietet, als DACE jemals haben wird. (Hinweis: Ich bin einer der Entwickler der neuen Version von DACE, die in Kürze veröffentlicht wird und zusätzliche Unterstützung für EGO bieten wird.)

Ich hoffe, dieser grobe Überblick hat Ihnen geholfen. Bitte stellen Sie Fragen, ob es Punkte gibt, die klarer formuliert werden können oder Dinge, die ich verpasst habe, oder ob Sie weiteres Material zu diesem Thema wünschen.

Sehen

LM Rios und NV Sahinidis, Derivatfreie Optimierung: Eine Überprüfung der Algorithmen und ein Vergleich der Softwareimplementierungen

für einen sehr nützlichen aktuellen Vergleich von Lösern.

DOI: 10.1007 / s10898-012-9951-y

Für eine reibungslose Funktion sollte die Methode Efficient Global Optimization eine recht gute Leistung erbringen und wesentlich effizienter als DIRECT sein. Implementierungen sind in TOMLAB (habe es selbst nicht verwendet) und DAKOTA (mit denen ich einige Erfolge hatte ) verfügbar .

Da die Funktion glatt ist, ist Newtons Methode die effizienteste Methode, um ein Minimum zu finden. Da die Funktion nicht konvex ist, müssen Sie die üblichen Tricks anwenden, um Newtons Methode konvergieren zu lassen (Levenberg-Marquardt-Modifikation, Liniensuche oder Vertrauensbereich zur Globalisierung). Wenn Sie keine Ableitungen Ihrer Funktion erhalten können, versuchen Sie, diese entweder über endliche Differenzen oder mit einem BFGS-Update zu berechnen. Wenn Sie vermuten, dass das Problem mehr als ein lokales Minimum hat, starten Sie die Newton-Methode einfach aus einer Reihe zufällig oder nicht ganz zufällig ausgewählter Punkte und sehen, wo sie konvergieren.

Da Ihre Auswertungen teuer sind, müssen Sie mehrere Funktionsauswertungen parallel ausführen.

Ich würde Ihnen empfehlen, sich diesen Code anzuschauen . Die Mathematik dahinter wird hier beschrieben .