Optimiser une fonction inconnue qui ne peut être évaluée que?

Étant donné une fonction inconnue , nous pouvons évaluer sa valeur en tout point de son domaine, mais nous n'avons pas son expression. En d'autres termes, est comme une boîte noire pour nous. $f:\mathbb R^d \to \mathbb R$ $f$

Quel est le nom du problème de trouver le minimiseur de ? Quelles sont les méthodes disponibles? $f$

Quel est le nom du problème de trouver la solution de l'équation ? Quelles sont les méthodes disponibles? $f(x)=0$

Dans les deux problèmes ci-dessus, est-ce une bonne idée d'interpoler ou d'adapter à certaines évaluations de f: utilisant une fonction de forme et de paramètre connus à déterminer, puis minimiser ou trouver sa racine? $(x_i, f(x_i)), i=1, \dots, n$ $g_\theta$ $\theta$ $g_\theta$

Merci et salutations!

optimization Tim
la source

Pouvez-vous évaluer son gradient à un point donné?

chaohuang

@chaohuang: Il y a deux cas: vous pouvez ou non évaluer son gradient, en fonction d'hypothèses.

Tim

Si gradient est disponible, les tâches que vous demandez peuvent être accomplies par des algorithmes basés sur un gradient. Par exemple, le minimum, ou au moins un minimum local, peut être calculé par la méthode de descente la plus abrupte, et les racines peuvent être trouvées par la méthode de Newton.

chaohuang

Et si le gradient est inconnu, il existe des méthodes métaheuristiques , également appelées méthodes sans dérivé ou boîte noire et généralement sous forme d'optimisation stochastique.

chaohuang

Savez-vous si la fonction est lisse (même si vous ne pouvez pas évaluer le gradient)? Savez-vous si la fonction est convexe? Si ce n'est pas convexe, savez-vous si c'est au moins Lipschitz continu? Si la fonction est complètement générale, c'est un problème désespéré.

Brian Borchers

Réponses:

Les méthodes que vous recherchez - c'est-à-dire qui n'utilisent que des évaluations de fonctions mais pas de dérivées - sont appelées méthodes d'optimisation sans dérivé . Il y a une grande littérature sur eux, et vous pouvez trouver un chapitre sur ces méthodes dans la plupart des livres sur l'optimisation. Les approches typiques incluent

Approximation du gradient par des différences finies si l'on peut raisonnablement s'attendre à ce que la fonction soit lisse et, éventuellement, convexe;
Les méthodes de Monte Carlo telles que le recuit simulé;
Algorithmes génétiques.

Wolfgang Bangerth
la source

Puis-je simplement ajouter "Modélisation de substitution" à cette liste? Ils sont très applicables à l'optimisation de boîte noire, en particulier si la fonction est coûteuse à évaluer.

OscarB

Oui, vous pouvez :-) Certainement un excellent ajout.

Wolfgang Bangerth

On pourrait également utiliser la méthode Nelder-Mead si de bonnes estimations des optima sont connues.

Oui, vous pouvez utiliser Nelder-Mead, mais c'est un algorithme terrible par rapport à la plupart des autres.

Wolfgang Bangerth

@WolfgangBangerth: Votre commentaire sur Nelder-Mead n'est valide que dans la dimension d> 2. En deux dimensions, c'est sur de nombreux problèmes une méthode excellente et très difficile à battre.

Arnold Neumaier

Je pense que vous devriez commencer par: Atelier GECCO sur l'analyse comparative d'optimisation de la boîte noire à paramètres réels (BBOB 2016) http://numbbo.github.io/workshops/index.html

Vous trouverez de nombreux algorithmes différents qui ont été utilisés lors de compétitions précédentes, et qui ont été comparés sur une base commune. Si vous commencez ailleurs, vous allez bientôt vous noyer dans les centaines d'articles qui affirment que leurs méthodes et algorithmes fonctionnent mieux que d'autres avec peu de preuves réelles de ces affirmations.

Jusqu'à récemment, c'était, pour être honnête, une situation honteuse et tout pouvoir pour l'INRIA, GECCO et bien d'autres pour les efforts qu'ils ont déployés pour établir un cadre de comparaison rationnelle.

Lysistrata
la source

-1

J'ajouterais simplement que l'une des clés ici est de pouvoir mettre à l'échelle la méthode d'optimisation sur les processeurs multicœurs . Si vous pouvez effectuer plusieurs évaluations de fonctions simultanément, cela vous donne une accélération égale à un certain nombre de cœurs impliqués. Comparez cela à l'utilisation d'un modèle de réponse légèrement plus précis, ce qui vous rend environ 10% plus efficace.

Je recommanderais de regarder ce code , il peut être utile pour les personnes ayant accès à de nombreux cœurs. Une mathématique derrière elle est décrite dans cet article .

Paul
la source

Cette réponse est trop courte pour être utile (et reste utile, car les liens peuvent disparaître à tout moment). Veuillez également mentionner que vous êtes l'auteur de ce logiciel .

Christian Clason