Algorithmes d'optimisation parallèle pour un problème avec une fonction objectif très coûteuse

15

J'optimise une fonction de 10-20 variables. La mauvaise nouvelle est que chaque évaluation de fonction est coûteuse, environ 30 min de calcul en série. La bonne nouvelle est que j'ai un cluster avec quelques dizaines de nœuds de calcul à ma disposition.

D'où la question: existe-t-il des algorithmes d'optimisation qui me permettraient d'utiliser efficacement toute cette puissance de calcul?

D'un côté du spectre, il y aurait une recherche exhaustive: subdiviser tout l'espace de recherche en une grille fine et calculer la fonction à chaque point de grille indépendamment. Il s'agit certainement d'un calcul très parallèle, mais l'algorithme est horriblement inefficace.

De l'autre côté du spectre, il y aurait des algorithmes quasi-Newton: mettre à jour intelligemment la prochaine estimation des paramètres en fonction de l'histoire antérieure. Il s'agit d'un algorithme efficace, mais je ne sais pas comment le rendre parallèle: le concept de "l'estimation des paramètres sur la base de l'histoire antérieure" ressemble à un calcul en série.

Les algorithmes quadratiques semblent être quelque part au milieu: on peut construire le "modèle de substitution" initial en calculant un tas de valeurs en parallèle, mais je ne sais pas si les itérations restantes sont parallélisables.

Des suggestions sur le type de méthodes d'optimisation sans gradient qui fonctionneraient bien sur un cluster? Existe-t-il également des implémentations parallèles d'algorithmes d'optimisation actuellement disponibles?

Michael
la source
1
Vous pouvez toujours calculer le gradient en parallèle (pour les méthodes quasi-Newton utilisant des différences finies) et obtenir une accélération proportionnelle au nombre de paramètres, c'est-à-dire 10x-20x.
stali
@stali: Vous avez besoin de la Hesse pour les méthodes quasi-Newton en optimisation. Calculer la Hesse via des différences finies d'évaluations de fonctions n'est vraiment pas une bonne idée. Le calcul d'approximations aux différences finies du gradient pour l'optimisation n'est généralement pas non plus une bonne idée.
Geoff Oxberry
De nombreuses méthodes quasi-Newton telles que BFGS ne nécessitent pas explicitement la Hesse. Je pense qu'en utilisant des gradients, en combinaison avec le L-BFGS, l'OP peut rapidement atteindre ce qu'il veut.
stali
@stali: J'ai souligné pourquoi l'utilisation d'une approximation par différence finie du gradient serait une mauvaise idée dans ma réponse. Il dégradera la convergence en introduisant l'erreur dans le côté droit de l'itération quasi-Newton. En outre, cela gaspille les évaluations de fonctions car il n'y a aucune possibilité de réutiliser les anciennes évaluations (contrairement aux méthodes de substitution). L'utilisation de BFGS ne résout que la moitié des problèmes liés à votre approche proposée.
Geoff Oxberry
Il s'agit plutôt d'un commentaire et non d'une réponse. Mais je n'ai pas le choix, car je n'ai pas assez de représentants pour poster un commentaire. Michael, j'ai un type de problème très similaire: les évaluations de fonctions coûteuses qui impliquent des simulations complexes exécutées sur un cluster. Avez-vous déjà trouvé un code approprié pour exécuter l'optimisation lorsque l'évaluation de la fonction implique une simulation sur un cluster?
MoonMan

Réponses:

16

Comme le déclare Paul, sans plus d'informations, il est difficile de donner des conseils sans hypothèses.

Avec 10 à 20 variables et des évaluations de fonctions coûteuses, la tendance est de recommander des algorithmes d'optimisation sans dérivé. Je vais être en profond désaccord avec les conseils de Paul: vous avez généralement besoin d'un gradient de précision machine à moins que vous n'utilisiez une sorte de méthode spéciale (par exemple, la descente de gradient stochastique dans l'apprentissage automatique exploitera la forme de l'objectif pour arriver à un résultat raisonnable). estimations de gradient).

Chaque étape quasi-Newton va prendre la forme:

H~(Xk)k=-F(Xk),

est une approximation de la matrice de Hesse, d k est la direction de recherche, x k est la valeur des variables de décision à l'itération actuelle, f est votre fonction objectif, et f est le gradient de votre objectif, et le les variables de décision sont mises à jour comme x k + 1 = x k + α k d k , où α kH~kXkFFXk+1=Xk+αkkαkest une taille de pas déterminée d'une certaine manière (comme une recherche de ligne). Vous pouvez vous éloigner de l'approximation de la Hesse de certaines manières et vos itérations convergeront, bien que si vous utilisez quelque chose comme des approximations de différences finies de la Hesse via des gradients exacts, vous pourriez souffrir de problèmes dus à un mauvais conditionnement. En règle générale, le Hessian est approximé en utilisant le gradient (par exemple, les méthodes de type BFGS avec des mises à jour de rang 1 pour le Hessian).

Rapprocher la Hesse et le gradient via des différences finies est une mauvaise idée pour plusieurs raisons:

  • vous allez avoir une erreur dans le gradient, donc la méthode quasi-Newton que vous appliquez s'apparente à trouver la racine d'une fonction bruyante
  • si les évaluations de fonctions sont coûteuses et que vous essayez d'évaluer un gradient par rapport à variables, cela vous coûtera N évaluations de fonctions par itérationNN
  • si vous avez une erreur dans le gradient, vous allez avoir plus d'erreur dans votre Hesse, ce qui est un gros problème en termes de conditionnement du système linéaire
  • ... et ça va vous coûter évaluations de fonction par itérationN2

Donc, pour obtenir une mauvaise itération de quasi-Newton, vous faites quelque chose comme jusqu'à 420 évaluations de fonctions à 30 minutes par évaluation, ce qui signifie que vous allez attendre un certain temps pour chaque itération, ou vous allez besoin d'un grand cluster juste pour les évaluations de fonctions. Les résolutions linéaires réelles seront de 20 x 20 matrices (au plus!), Il n'y a donc aucune raison de les paralléliser. Si vous pouvez obtenir des informations sur le gradient, par exemple, en résolvant un problème adjoint, alors cela pourrait être plus intéressant, auquel cas, cela pourrait valoir la peine de consulter un livre comme Nocedal & Wright.

Si vous allez faire beaucoup d'évaluations de fonctions en parallèle, vous devriez plutôt chercher des approches de modélisation de substitution ou générer des méthodes de recherche d'ensemble avant d'envisager des approches quasi-Newton. Les articles de la revue classique sont celui de Rios et Sahinidis sur les méthodes sans dérivés , qui a été publié en 2012 et fournit une comparaison très bonne et large; l'article d'analyse comparative de More et Wild de 2009; le manuel 2009 "Introduction to Derivative-Free Optimization" par Conn, Scheinberg et Vicente; et l' article de synthèse sur la génération de méthodes de recherche par Kolda, Lewis et Torczon de 2003.

Comme indiqué ci-dessus, le progiciel DAKOTA implémentera certaines de ces méthodes, tout comme NLOPT , qui implémente DIRECT, et quelques-unes des méthodes de modélisation de substitution de Powell. Vous pouvez également jeter un œil à MCS ; il est écrit en MATLAB, mais vous pouvez peut-être porter l'implémentation MATLAB dans la langue de votre choix. DAKOTA est essentiellement une collection de scripts que vous pouvez utiliser pour exécuter votre simulation coûteuse et collecter des données pour les algorithmes d'optimisation, et NLOPT a des interfaces dans un grand nombre de langages, donc le choix du langage de programmation ne devrait pas être un problème majeur dans l'utilisation de l'un ou l'autre des logiciels; Cependant, DAKOTA prend un certain temps à apprendre et a une énorme quantité de documentation à parcourir.

Geoff Oxberry
la source
2
C'est un plaisir pour moi de me tromper complètement et d'apprendre quelque chose de nouveau et d'utile dans le processus :).
Paul
Merci! Encore une précision: lesquels de ces algorithmes sont capables d'effectuer des évaluations de fonctions en parallèle? Par exemple, sur une grille k-way effectuant des itérations n + 1, ..., n + k basées uniquement sur les informations obtenues à partir des itérations 1, ..., n?
Michael
k
3

Peut-être que vous recherchez des algorithmes d'optimisation de substitution. Ces algorithmes utilisent des modèles de substitution pour remplacer les vrais modèles de calcul coûteux au cours du processus d'optimisation et tentent d'obtenir une solution appropriée en utilisant le moins possible d'évaluations des modèles de calcul coûteux.

Je pense que la méthode d'échantillonnage en mode poursuite peut être utilisée pour résoudre votre problème. Cet algorithme utilise le modèle de substitution RBF pour approximer la fonction objectif coûteuse et peut gérer des contraintes non linéaires. Plus important encore, il sélectionne plusieurs candidats pour effectuer les évaluations de fonctions coûteuses afin que vous puissiez distribuer ces candidats pour le calcul parallèle afin d'accélérer davantage le processus de recherche. Le code est open-source et écrit en MATLAB.

Référence

Wang, L., Shan, S., et Wang, GG (2004). Méthode d'échantillonnage à poursuite de mode pour l'optimisation globale des fonctions de boîte noire coûteuses. Engineering Optimization, 36 (4), 419-438.

Zhan Dawei
la source
2

Je ne suis pas sûr qu'un algorithme parallèle soit vraiment ce que vous recherchez. Ce sont vos évaluations de fonctions qui sont très coûteuses. Ce que vous voulez faire, c'est paralléliser la fonction elle-même, pas nécessairement l'algorithme d'optimisation.

Si vous ne pouvez pas faire cela, alors il y a un juste milieu entre la recherche exhaustive et l'algorithme de Newton, ce sont les méthodes de Monte Carlo. Vous pouvez, sur un tas de cœurs / nœuds différents, démarrer le même algorithme qui est susceptible de tomber dans des optima locaux (par exemple des algorithmes quasi-Newton), mais tous avec des conditions initiales aléatoires. Votre meilleure estimation alors pour les vrais optima est le minimum des minimums. Ceci est trivial pour paralléliser et peut être utilisé pour étendre n'importe quelle méthode. Bien qu'il ne soit pas parfaitement efficace, si vous avez suffisamment de puissance de calcul à votre disposition, il peut définitivement gagner la bataille de la productivité de programmation contre les performances de l'algorithme (si vous avez beaucoup de puissance de calcul, cela peut se terminer avant que vous ayez fini de créer un algorithme plus sophistiqué).

Chris Rackauckas
la source
0

Le choix de l'algorithme d'optimisation (et donc de sa parallélisation) dépend fortement des propriétés de la fonction objectif et des contraintes. Sans en savoir plus sur le problème, il est difficile de donner des conseils utiles.

Mais d'après vos considérations sur les méthodes newtoniennes, j'en déduis que votre fonction objective est différentiable. Si possible, votre problème bénéficierait grandement de la parallélisation de l'évaluation des fonctions. Si cela n'est pas possible, vous pouvez également envisager une méthode de newton inexacte qui remplace les gradients / hessians exacts par des approximations de différences finies. Ensuite, vous pouvez utiliser tous ces processeurs à votre disposition pour calculer chaque élément non nul du jacobien, comme le suggère @stali.

Pour plus d'informations, lisez Optimisation numérique de Nocedal & Wright, chapitre 7 . Il existe de nombreux progiciels d'optimisation qui implémentent cela en parallèle. Le logiciel DAKOTA (Sandia National Labs) est l' un des logiciels gratuits les plus utilisés .

Paul
la source
5
N
-2

Voici une solution à votre problème.

La description d'une méthode mathématique est fournie dans cet article .

Paul
la source
3
Bienvenue sur SciComp.SE. Pouvez-vous fournir des détails sur l'approche décrite dans le document et mise en œuvre dans le logiciel? Quelle est la méthode utilisée? Pourquoi est-il bon? Que propose cette approche que les autres réponses ne couvrent pas?
nicoguaro
2
De plus, il semble que ce soit votre propre travail. Si tel est le cas, veuillez l'indiquer explicitement dans votre réponse.
nicoguaro
@nicoguaro: merci, mais je sais comment cliquer sur les liens.
Michael
2
@Michael, ce n'est pas pour vous. La philosophie de ce site est d'être une collection de réponses. Vous obtenez votre réponse aujourd'hui, mais à l'avenir, quelqu'un d'autre pourra avoir besoin de la même aide. C'est pourquoi il existe des normes de facto sur ce qu'est une bonne réponse.
nicoguaro