Méthode de Nelder-Mead

Illustration de la méthode de Nelder-Mead sur la fonction de Rosenbrock

La méthode de Nelder-Mead est un algorithme d'optimisation non linéaire qui a été publiée par John Nelder et Roger Mead (en) en 1965. C'est une méthode numérique heuristique qui cherche à minimiser une fonction continue dans un espace à plusieurs dimensions.

Appelée également downhill simplex method, l’algorithme exploite le concept de simplexe qui est un polytope de N+1 sommets dans un espace à N dimensions. Partant initialement d’un tel simplexe, celui-ci subit des transformations simples au cours des itérations : il se déforme, se déplace et se réduit progressivement jusqu’à ce que ses sommets se rapprochent d’un point où la fonction est localement minimale.

La méthode de Nelder-Mead avec recuit simulé est issue du couplage entre l’algorithme d’origine et le mécanisme empirique du recuit simulé.

Algorithme

Soit une fonction f définie sur un espace de dimension N. L'algorithme débute par la définition d'un simplexe non dégénéré choisi dans cet espace. Par itérations successives, le processus consiste à déterminer le point du simplexe où la fonction est maximale afin de le remplacer par la réflexion (c'est-à-dire le symétrique) de ce point par rapport au centre de gravité des N points restants. Si la valeur de la fonction en ce nouveau point est inférieure à toutes les autres valeurs prises sur les autres points, le simplexe est étiré dans cette direction. Sinon si la valeur de la fonction en ce nouveau point est meilleure que la deuxième moins bonne mais moins bonne que la meilleure, on garde cette valeur et on recommence. Sinon, il est supposé que l'allure locale de la fonction est une vallée, et le simplexe est contracté sur lui même. Si cela ne donne toujours pas un meilleur point, le simplexe est réduit par une homothétie centrée sur le point du simplexe où la fonction est minimale.

Plus précisément :

1. Choix de N+1 points de l'espace des inconnues de dimension N. Cela forme un simplexe : {$x_{1},x_{2},...,x_{N+1}$},
2. Calcul des valeurs de la fonction f en ces points, tri des points de façon à avoir $f(x_{1})\leq f(x_{2})\leq ...\leq f(x_{N+1})$. Il suffit en fait de connaître le premier et les deux derniers.
3. Calcul de x₀, centre de gravité de tous les points sauf x_N+1.
4. Calcul de $x_{r}=x_{0}+\alpha (x_{0}-x_{N+1})$ (réflexion de x_N+1 par rapport à x₀).
5. Soit $f(x_{1})\leq f(x_{r})<f(x_{N})$, remplacement de x_N+1 par $x_{r}$et retour à l'étape 2.
6. Soit $f(x_{r})<f(x_{1})$, calcul de $x_{e}=x_{0}+\gamma (x_{r}-x_{0})$ (expansion du simplexe). Si $f(x_{e})\leq f(x_{r})$, remplacement de x_N+1 par $x_{e}$ sinon, remplacement de x_N+1 par x_r et retour à l'étape 2.
7. Soit $f(x_{r})\geq f(x_{N})$, calcul de $x_{c}=x_{0}+\rho (x_{N+1}-x_{0})$ (contraction du simplexe). Si $f(x_{c})<f(x_{N+1})$, remplacement de x_N+1 par x_c et retour à l'étape 2, sinon aller à l'étape 8.
8. Homothétie de rapport $\sigma$ et de centre x₁ : remplacement de x_i par $x_{1}+\sigma (x_{i}-x_{1})$ et retour à l'étape 2.

Avec $\alpha ,\gamma ,\rho ,\sigma$ des coefficients tels que $\alpha >0$, $\gamma >1$ et $0<\rho \leq 0.5$. Des valeurs standards sont $\alpha =1$, $\gamma =2$, $\rho =1/2$ et $\sigma =1/2$.

Analyse

Avantages

• La généralité : la méthode s'applique à une fonction continue sans avoir à évaluer ses dérivées.
• La simplicité de la mise en œuvre.
• L’efficacité pour une fonction non dérivable.
• L’interprétation géométrique sous-jacente.
• Assurance d’obtenir une série décroissante de valeurs.

Inconvénients

1. S’applique mal (ou difficilement) lorsque le domaine de définition de la fonction est complexe ou que le minimum recherché se situe dans un voisinage de la frontière.
2. Elle nécessite la donnée « arbitraire » d’un simplexe de départ, qui peut ralentir l’algorithme si mal choisi.
3. Une dégradation des performances lorsque la dimension N augmente.
4. Le risque que les simplexes obtenus successivement aient tendance à dégénérer (bien que l’expérience montre que ce soit rarement le cas)^{[réf. nécessaire]}.
5. L'optimum obtenu par la méthode n'est pas forcément un optimum global.

Amélioration facile et très efficace : redémarrer l'algorithme

Pour pallier les inconvénients 1) et 4), ainsi que d'autres, le fait de redémarrer l'algorithme de Nelder-Mead à partir de la dernière solution obtenue (et continuer de le redémarrer jusqu'à ce qu'il n'y ait plus d'amélioration, jusqu'à une précision donnée) ne peut qu'améliorer (parfois très fortement) la solution finale. De même, il est souvent conseillé de faire plusieurs exécutions de l'algorithme, à partir de solutions initiales différentes (là encore, pour diminuer l'impact des inconvénients de la méthode et permettre de trouver une meilleure solution finale).

Lorsque le domaine de définition admet une frontière et que le minimum se situe sur ou à proximité de cette frontière, les déformations successives du simplex ont tendance à le dégénérer. Une manière efficace de l'éviter consiste à prolonger la fonction hors de sa frontière en lui ajoutant une pénalité.

Méthode de Nelder-Mead avec recuit simulé

Lorsque la fonction possède de nombreux minima locaux, il arrive fréquemment de converger vers l’un d’eux et de manquer la solution. Dans un tel cas, il est possible d’introduire dans la méthode de Nelder-Mead un couplage avec le mécanisme empirique du recuit simulé : à chaque itération, les valeurs effectives de la fonction aux divers sommets sont perturbées par un bruit de fond « thermique » aléatoire dont l’importance décroît au fur et à mesure que l’algorithme progresse.