Test des méthodes d'optimisation numérique: Rosenbrock vs fonctions de test réelles

15

Il semble y avoir deux principaux types de fonction de test pour les optimiseurs sans dérivation:

  • des lignes simples comme la fonction Rosenbrock ff., avec des points de départ
  • ensembles de points de données réels, avec un interpolateur

Est-il possible de comparer, disons, 10d Rosenbrock avec de vrais problèmes 10d?
On pourrait comparer de différentes manières: décrire la structure des minima locaux,
ou exécuter des optimiseurs ABC sur Rosenbrock et sur certains problèmes réels;
mais les deux semblent difficiles.

(Peut-être que les théoriciens et les expérimentateurs ne sont que deux cultures très différentes, alors je demande une chimère?)

Voir également:


(Ajouté en septembre 2014):
Le graphique ci-dessous compare 3 algorithmes du MPO sur 14 fonctions de test en 8d à partir de 10 points de départ aléatoires: BOBYQA PRAXIS SBPLX de NLOpt
14 fonctions de test N-dimensionnelles, Python sous gist.github de ce Matlab par A. Hedar × 10 points de départ aléatoires uniformes dans le cadre de sélection de chaque fonction.×
×

Sur Ackley, par exemple, la rangée du haut montre que SBPLX est meilleur et PRAXIS terrible; sur Schwefel, le panneau en bas à droite montre SBPLX trouver un minimum sur le 5ème point de départ aléatoire.

Dans l'ensemble, BOBYQA est le meilleur sur 1, PRAXIS sur 5 et SBPLX (~ Nelder-Mead avec redémarrages) sur 7 des 13 fonctions de test, avec Powersum un tossup. YMMV! En particulier, Johnson déclare: «Je vous conseillerais de ne pas utiliser la fonction-valeur (ftol) ou les tolérances de paramètre (xtol) dans l'optimisation globale».

Conclusion: ne mettez pas tout votre argent sur un cheval ou sur une fonction de test.

entrez la description de l'image ici

denis
la source

Réponses:

13

Des fonctions simples comme celle de Rosenbrock sont utilisées pour déboguer et pré-tester les algorithmes nouvellement écrits: ils sont rapides à implémenter et à exécuter, et une méthode qui ne peut pas bien résoudre les problèmes standard ne fonctionnera probablement pas bien sur des problèmes réels.

Pour une comparaison approfondie récente des méthodes sans dérivé pour les fonctions coûteuses, voir Optimisation sans dérivé: examen des algorithmes et comparaison des implémentations logicielles . LM Rios, NV Sahinidis - doi 10.1007 / s10898-012-9951-y Journal of Global Optimization, 2012. (Voir également la page Web qui l'accompagne: http://archimedes.cheme.cmu.edu/?q=dfocomp )

Arnold Neumaier
la source
Professeur Neumaier, pourriez-vous indiquer de vrais problèmes, des preuves, pour "une méthode qui ne peut pas bien résoudre les problèmes standard est peu susceptible de bien fonctionner sur des problèmes réels"? Je me rends compte que ce n'est pas facile. (Je serais intéressé par vos commentaires sur Hooker.) De plus, un rapide coup d'œil aux modèles c de votre lien montre que princetonlibgloballib nécessite AMPL et que source_convexmodels * .c ont tous un ";" après fscanf () - trivial but
denis
@Denis: Des problèmes comme Rosenbrock proviennent des premiers jours de l'optimisation automatisée, où les gens ont isolé les difficultés typiques dans des exemples représentatifs simples qui peuvent être étudiés sans la complexité numérique des problèmes de la vie réelle. Ils ne sont donc pas vraiment des modèles artificiels mais simplifiés de difficultés réelles. Par exemple, Rosenbrock illustre l'effet combiné d'une forte non-linéarité et d'une mauvaise condition légère.
Arnold Neumaier
Le site AMPL ampl.com propose une version étudiante gratuite pour AMPL.
Arnold Neumaier
7

L'avantage des cas de test synthétiques comme la fonction de Rosenbrock est qu'il existe une littérature existante avec laquelle comparer, et il y a un sens dans la communauté comment les bonnes méthodes se comportent sur de tels cas de test. Si chacun utilisait son propre test, il serait beaucoup plus difficile de parvenir à un consensus sur les méthodes qui fonctionnent et celles qui ne fonctionnent pas.

Wolfgang Bangerth
la source
1

(J'espère qu'il n'y a pas d'objection à ce que je vire à la fin de cette discussion. Je suis nouveau ici, alors faites-moi savoir si j'ai transgressé!)

Les fonctions de test pour les algorithmes évolutionnaires sont maintenant beaucoup plus compliquées qu'elles ne l'étaient il y a même 2 ou 3 ans, comme le montrent les suites utilisées dans les compétitions lors de conférences comme le (très récent) Congrès de 2015 sur le calcul évolutionnaire. Voir:

http://www.cec2015.org/

Ces suites de tests incluent désormais des fonctions avec plusieurs interactions non linéaires entre les variables. Le nombre de variables peut atteindre 1000, et je suppose que cela pourrait augmenter dans un avenir proche.

Une autre innovation très récente est le "Black Box Optimization Competition". Voir: http://bbcomp.ini.rub.de/

Un algorithme peut interroger la valeur f (x) pour un point x, mais il n'obtient pas d'informations sur le gradient, et en particulier il ne peut faire aucune hypothèse sur la forme analytique de la fonction objectif.

Dans un sens, cela pourrait être plus proche de ce que vous avez appelé un "vrai problème" mais dans un cadre organisé et objectif.

Lysistrata
la source
1) "pas d'objection": au contraire, vos bons liens sont les bienvenus! 2) de bonnes parcelles là-bas? Les méthodes et les problèmes sont tous deux fractalisants, il devient donc de plus en plus difficile pour quiconque de trouver un problème comme le leur. Connaissez-vous en particulier les méthodes de prévision des séries chronologiques ?
denis
Les fonctions objectives du Concours CEC 2015 sur l'optimisation dynamique multi-objectifs peuvent être consultées sur: sites.google.com/site/cec2015dmoocomp/competition-process/… Pour les autres concours, rendez-vous sur cec2015.org et cliquez sur concours, puis cliquez sur sur les concours acceptés. Chacun a ses propres fonctions. Les articles sur certains d'entre eux ont de jolis tracés (pour les cas 2D). Les compétitions de la conférence GECCO peuvent être consultées sur: sigevo.org/gecco-2015/competitions.html#bbc Les résultats seront disponibles après le 15 juillet.
Lysistrata
0

Tu peux avoir le meilleur des deux mondes. Le NIST a un ensemble de problèmes pour les minimiseurs, comme l'ajustement de ce polinôme du 10e degré , avec les résultats attendus et les incertitudes. Bien sûr, prouver que ces valeurs sont la meilleure solution réelle, ou l'existence et les propriétés d'autres minima locaux est plus difficile que sur une expression mathématique contrôlée.

Davidmh
la source
Eh bien, les problèmes NIST sont petits (2 3 1 1 11 7 6 6 6 6 6 params). Existe-t-il des ensembles de tests qui sont à la fois "réels" et reproductibles , pour n'importe quel coin du "réel"? Cf. une demande de problèmes d'optimisation basée sur la simulation
denis