Méthode de Nelder-Mead

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 : {${\displaystyle 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 ${\displaystyle 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 ${\displaystyle x_{r}=x_{0}+\alpha (x_{0}-x_{N+1})}$ (réflexion de x_N+1 par rapport à x₀).
5. Soit ${\displaystyle f(x_{1})\leq f(x_{r})<f(x_{N})}$, remplacement de x_N+1 par ${\displaystyle x_{r}}$et retour à l'étape 2.
6. Soit ${\displaystyle f(x_{r})<f(x_{1})}$, calcul de ${\displaystyle x_{e}=x_{0}+\gamma (x_{r}-x_{0})}$ (expansion du simplexe). Si ${\displaystyle f(x_{e})\leq f(x_{r})}$, remplacement de x_N+1 par ${\displaystyle x_{e}}$ sinon, remplacement de x_N+1 par x_r et retour à l'étape 2.
7. Soit ${\displaystyle f(x_{r})\geq f(x_{N})}$, calcul de ${\displaystyle x_{c}=x_{0}+\rho (x_{N+1}-x_{0})}$ (contraction du simplexe). Si ${\displaystyle 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 ${\displaystyle \sigma }$ et de centre x₁ : remplacement de x_i par ${\displaystyle x_{1}+\sigma (x_{i}-x_{1})}$ et retour à l'étape 2.

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

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[4] 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.