Test numerischer Optimierungsmethoden: Rosenbrock vs. reale Testfunktionen

15

Es scheint zwei Hauptarten von Testfunktionen für nicht abgeleitete Optimierer zu geben:

  • Einzeiler wie die Rosenbrock-Funktion ff. mit Startpunkten
  • Sätze von realen Datenpunkten mit einem Interpolator

Kann man etwa 10d Rosenbrock mit echten 10d Problemen vergleichen?
Man kann auf verschiedene Arten vergleichen: die Struktur lokaler Minima beschreiben
oder Optimierer ABC auf Rosenbrock und auf einige reale Probleme ausführen;
aber beide scheinen schwierig zu sein.

(Vielleicht sind Theoretiker und Experimentatoren nur zwei ganz unterschiedliche Kulturen, also bitte ich um eine Chimäre?)

Siehe auch:


(Hinzugefügt im September 2014):
Die folgende Grafik vergleicht 3 DFO-Algorithmen mit 14 Testfunktionen in 8d von 10 zufälligen Startpunkten: BOBYQA PRAXIS SBPLX von NLOpt
14 N-dimensionale Testfunktionen, Python unter gist.github von diesem Matlab von A. Hedar × 10 gleichmäßig zufällige Startpunkte im Begrenzungsrahmen jeder Funktion.×
×

Auf Ackley zum Beispiel zeigt die obere Reihe, dass SBPLX am besten und PRAXIS schrecklich ist; Auf Schwefel zeigt das untere rechte Feld, dass SBPLX am 5. zufälligen Startpunkt ein Minimum findet.

Insgesamt ist BOBYQA bei 1, PRAXIS bei 5 und SBPLX (~ Nelder-Mead mit Neustart) bei 7 von 13 Testfunktionen am besten, mit Powersum als Ergebnis. YMMV! Insbesondere sagt Johnson: "Ich rate Ihnen, bei der globalen Optimierung keine Funktionswerte (ftol) oder Parametertoleranzen (xtol) zu verwenden."

Fazit: Setzen Sie nicht Ihr gesamtes Geld auf ein Pferd oder eine Testfunktion.

Bildbeschreibung hier eingeben

denis
quelle

Antworten:

13

Einfache Funktionen wie die von Rosenbrock werden verwendet, um neu geschriebene Algorithmen zu debuggen und vorab zu testen: Sie sind schnell zu implementieren und auszuführen, und es ist unwahrscheinlich, dass eine Methode, die die Standardprobleme nicht gut lösen kann, bei Problemen im wirklichen Leben gut funktioniert.

Einen aktuellen ausführlichen Vergleich der derivatfreien Methoden für teure Funktionen finden Sie unter Derivatfreie Optimierung: Eine Überprüfung der Algorithmen und ein Vergleich der Softwareimplementierungen . LM Rios, NV Sahinidis - doi 10.1007 / s10898-012-9951-y Journal of Global Optimization, 2012. (Siehe auch die zugehörige Webseite: http://archimedes.cheme.cmu.edu/?q=dfocomp )

Arnold Neumaier
quelle
Herr Prof. Neumaier, könnten Sie auf einige echte Probleme hinweisen, Beweise dafür, dass "eine Methode, die die Standardprobleme nicht gut lösen kann, wahrscheinlich nicht gut bei echten Problemen funktioniert"? Mir ist klar, dass das nicht einfach ist. (Ich wäre an Ihren Kommentaren zu Hooker interessiert.) Auch ein kurzer Blick auf c-Modelle aus Ihrem Link zeigt, dass princetonlibgloballib AMPL erfordert und source_convexmodels * .c alle ein ";" nach fscanf () - trivial aber
denis
@Denis: Probleme wie Rosenbrock stammen aus den Anfängen der automatisierten Optimierung, in denen Menschen die typischen Schwierigkeiten in einfachen repräsentativen Beispielen isoliert haben, die ohne die numerischen Komplexitäten realer Probleme untersucht werden können. Sie sind also nicht wirklich künstlich, sondern vereinfachte Modelle wirklicher Schwierigkeiten. Zum Beispiel zeigt Rosenbrock die kombinierte Wirkung von starker Nichtlinearität und leichter Krankheit.
Arnold Neumaier
Die AMPL-Site ampl.com bietet eine kostenlose Studentenversion für AMPL.
Arnold Neumaier
7

Synthetische Testfälle wie die Rosenbrock-Funktion haben den Vorteil, dass es bereits vergleichbare Literatur gibt und die Community ein Gespür dafür hat, wie sich gute Methoden bei solchen Testfällen verhalten. Wenn jeder seinen eigenen Testfall verwenden würde, wäre es viel schwieriger, einen Konsens darüber zu erzielen, welche Methoden funktionieren und welche nicht.

Wolfgang Bangerth
quelle
1

(Ich hoffe, es gibt keine Einwände gegen meine Annäherung an das Ende dieser Diskussion. Ich bin neu hier, also lass es mich wissen, wenn ich übertreten habe!)

Testfunktionen für evolutionäre Algorithmen sind jetzt viel komplizierter als noch vor zwei oder drei Jahren, wie die Suiten zeigen, die bei Konferenzen wie dem (jüngsten) Kongress für evolutionäre Berechnungen 2015 zum Einsatz kamen. Sehen:

http://www.cec2015.org/

Diese Testsuiten enthalten jetzt Funktionen mit mehreren nichtlinearen Wechselwirkungen zwischen Variablen. Die Anzahl der Variablen kann bis zu 1000 betragen, was in naher Zukunft wahrscheinlich zunehmen wird.

Eine weitere Innovation aus jüngster Zeit ist der "Black Box Optimization Competition". Sehen: http://bbcomp.ini.rub.de/

Ein Algorithmus kann den Wert f (x) für einen Punkt x abfragen, erhält jedoch keine Gradienteninformation und kann insbesondere keine Annahmen über die analytische Form der Zielfunktion treffen.

In gewissem Sinne ist dies möglicherweise näher an dem, was Sie als "echtes Problem" bezeichnet haben, aber in einer organisierten, objektiven Umgebung.

Lysistrata
quelle
1) "keine Einwände": Im Gegenteil, Ihre guten Links sind willkommen! 2) Gibt es gute Grundstücke? Methoden und Probleme sind beide fraktalisierend, so dass es für jeden immer schwieriger wird, ein Problem wie das ihre zu finden. Kennen Sie insbesondere Methoden für die Vorhersage von Zeitreihen ?
denis
Die Zielfunktionen für den CEC 2015-Wettbewerb zur dynamischen Optimierung mehrerer Objektive finden Sie unter: sites.google.com/site/cec2015dmoocomp/competition-process/… Für andere Wettbewerbe gehen Sie zu cec2015.org und klicken Sie auf Wettbewerbe und dann auf auf angenommenen Wettbewerben. Jeder hat seine eigenen Funktionen. Papiere auf einigen von ihnen haben reizende Pläne (für die 2D Fälle). Die GECCO-Konferenzwettbewerbe finden Sie unter: sigevo.org/gecco-2015/competitions.html#bbc Die Ergebnisse werden nach dem 15. Juli veröffentlicht.
Lysistrata
0

Sie können das Beste aus beiden Welten haben. NIST hat eine Reihe von Problemen mit Minimierern, wie das Anpassen dieses Polinoms 10. Grades , mit erwarteten Ergebnissen und Unsicherheiten. Es ist natürlich schwieriger zu beweisen, dass diese Werte die tatsächlich beste Lösung sind oder dass es andere lokale Minima gibt und welche Eigenschaften sie haben, als mit einem kontrollierten mathematischen Ausdruck.

Davidmh
quelle
Nun, die NIST-Probleme sind gering (2 3 1 1 11 7 6 6 6 6 params). Gibt es Testsätze, die sowohl "echt" als auch reproduzierbar sind , für jede Ecke von "echt"? Vgl. eine Anfrage für simulationsbasierte Optimierungsprobleme
denis