Trouver un minimum global d'une fonction 2D lisse, bornée et non convexe dont l'évaluation est coûteuse

J'ai une fonction 2D non convexe bornée dont j'aimerais trouver le minimum. La fonction est assez fluide. L'évaluer coûte cher. Une erreur acceptable est d'environ 3% du domaine de la fonction dans chaque axe.

J'ai essayé d'exécuter l'implémentation de l'algorithme DIRECT dans la bibliothèque NLOPT, mais cela n'a pas donné une amélioration considérable par rapport à la recherche par force brute en termes de quantité d'évaluations de fonctions nécessaires pour la précision requise et il y avait des valeurs aberrantes.

Quels autres solveurs d'optimisation globale dois-je considérer?

Je voudrais suggérer une approche quelque peu différente par rapport aux autres réponses, bien que @barron ait indirectement discuté de la même chose.

Au lieu d'optimiser directement votre fonction, c'est-à-dire en l'évaluant en une série de points points qui (espérons-le) convergent vers un optimum (local), vous pouvez utiliser le concept de modélisation de substitution , qui est très bien adapté aux problèmes du type que vous décrivez (coût élevé, lisse, borné, de faible dimension, c'est-à-dire moins de 20 inconnues).$\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_k$$\textit{surrogate modelling}$

Plus précisément, la modélisation de substitution fonctionne par la mise en place d' une fonction de modèle de votre véritable fonction f ∈ R d → R . La clé est que bien que c ne représente pas parfaitement f , il est beaucoup moins cher à évaluer.$c \in \mathbb{R}^d \rightarrow \mathbb{R}$$f \in \mathbb{R}^d \rightarrow \mathbb{R}$$c$$f$

Ainsi, un processus d'optimisation typique serait le suivant:

1. Évaluez à un ensemble de j points initiaux x 1 , x 2 , … , x j . Notez que les dérivés ne sont pas nécessaires. Notez également que ces points doivent être répartis uniformément dans tout l'espace de recherche, par exemple par Latin Hypercube Sampling ou une conception similaire remplissant l'espace.$f$$j$$\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_j$
2. Sur la base de cet ensemble de données d'origine, créez une fonction de modèle . Vous pouvez utiliser la validation croisée pour valider votre modèle (c'est-à-dire utiliser uniquement un sous-ensemble des j points d' origine pour créer c , puis utiliser le reste de l'ensemble de données pour vérifier dans quelle mesure c prédit ces valeurs)$c$$j$$c$$c$
3. Utilisez un critère tel que le critère d'amélioration attendue (IE) pour savoir où «remplir» plus d'échantillons pour rendre plus précis en échantillonnant f . Ceci est en réalité bien mieux étudié théoriquement qu'il n'y paraît, et le critère EI est très bien étudié. Le critère EI n'est pas non plus un critère gourmand, donc vous obtenez tous les deux une bonne amélioration globale de la précision du modèle, tout en priorisant la précision près des optima potentiels.$c$$f$
4. Si votre modèle n'est pas assez précis, répétez l'étape 3, sinon utilisez votre routine d'optimisation préférée pour trouver l'optimum de , qui sera très bon marché à évaluer (vous pouvez donc utiliser n'importe quelle routine que vous voulez, même celles qui nécessitent des dérivés, ou tout simplement évaluer la fonction dans un maillage fin).$c$

En général, c'est ce que l'on entend par EGO, Efficient Global Optimization, comme l'a suggéré @barron. Je voudrais souligner que pour votre application, cela semble parfaitement adapté - vous obtenez un modèle étonnamment précis basé sur relativement peu d'évaluations de , et pouvez ensuite utiliser n'importe quel algorithme d'optimisation que vous souhaitez. Ce qui est souvent aussi intéressant, c'est que vous pouvez maintenant évaluer c sur un maillage et le tracer, ce qui permet de mieux comprendre l'apparence générale de f . Un autre point intéressant est que la plupart des techniques de modélisation de substitution fournissent également des estimations d'erreur statistique, permettant ainsi une estimation de l'incertitude.$f$$c$$f$

Comment construire est bien sûr une question ouverte, mais souvent des modèles de krigeage ou dits de cartographie spatiale sont utilisés.$c$

Bien sûr, c'est tout un travail de codage, mais beaucoup d'autres personnes ont fait de très bonnes implémentations. Dans Matlab, je ne connais que la boîte à outils du logiciel DACE DACE est gratuit. TOMLAB pourrait également offrir un package Matlab, mais coûte de l'argent - cependant, je pense qu'il fonctionne également en C ++ et a beaucoup plus de capacités que DACE n'en aura jamais. (Remarque: je suis l'un des développeurs de la nouvelle version de DACE, qui sortira bientôt et qui offrira un support supplémentaire pour EGO.)

J'espère que cette vue d'ensemble vous a aidé, veuillez poser des questions s'il y a des points qui peuvent être clarifiés ou des choses que j'ai manquées, ou si vous souhaitez plus d'informations sur le sujet.

Voir

LM Rios et NV Sahinidis, Optimisation sans dérivé: revue des algorithmes et comparaison des implémentations logicielles

pour une comparaison récente très utile des solveurs.

DOI: 10.1007 / s10898-012-9951-y

Pour une fonction fluide, la méthode d'optimisation globale efficace devrait fonctionner assez bien et être considérablement plus efficace que DIRECT. Les implémentations sont disponibles dans TOMLAB (je ne l'ai pas utilisé moi-même) et DAKOTA (avec lesquelles j'ai eu un certain succès).

Puisque la fonction est fluide, la méthode de Newton sera la méthode la plus efficace pour trouver un minimum. Puisque la fonction n'est pas convexe, vous devrez appliquer les astuces habituelles pour faire converger la méthode de Newton (modification de Levenberg-Marquardt, recherche de ligne ou région de confiance à globaliser). Si vous ne pouvez pas obtenir de dérivés de votre fonction, essayez de la calculer via des différences finies ou en utilisant une mise à jour BFGS. Si vous soupçonnez que le problème a plus d'un minimum local, on pourrait simplement démarrer la méthode de Newton à partir d'un tas de points choisis au hasard ou pas si au hasard et voir où ils convergent.

Étant donné que vos évaluations sont coûteuses, vous devez tirer parti de plusieurs évaluations de fonctions en parallèle.

Je vous recommande de jeter un œil à ce code . Les mathématiques derrière sont décrites ici .