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

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?

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:

où 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ù α $\tilde{H}$$d_{k}$$x_{k}$$f$$\nabla{f}$$x_{k+1} = x_{k} + \alpha_{k}d_{k}$$\alpha_{k}$est 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ération$N$$N$
• 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ération$N^{2}$

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.

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.

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é).

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 .

Voici une solution à votre problème.

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