Méthode de Nelder-Mead

Un article de Wikipédia, l'encyclopédie libre.

La méthode de Nelder-Mead est un algorithme d'optimisation non-linéaire. Elle est due à Nelder et Mead en 1965. C'est une méthode numérique qui minimise une fonction dans un espace à plusieurs dimensions.

Cette méthode utilise le concept de simplexe qui est un polytope de N+1 sommets dans un espace à N dimensions.

Soit N la dimension de l'espace où f prend ses valeurs. On démarre avec un simplexe de cet espace. La première étape consiste à enlever le point du simplexe où la fonction est maximale et à le remplacer par la réflection de ce point par rapport au centre de gravité des N points restants. Si ce point est meilleur, on étire le simplexe dans cette direction. Sinon, on est dans une vallée, et on réduit le simplex par une similitude centrée sur le point du simplexe où la fonction est minimale.

[modifier] L'algorithme

1- Choix de N+1 points de l'espace à N dimensions des inconnues, formant un simplexe : {x1,x2,...,xN + 1},

2- Calcul des valeurs de la fonction f en ces points, réindexation des points de façon à avoir f(x_1)\leq f(x_2)\leq ...\leq f(x_{N+1}),

3- Calcul de x0, centre de gravité de tous les points sauf xN + 1,

4- Calcul de xr = x0 + (x0 − xN + 1) (réflexion de xN + 1 par rapport à x0),

5- Si f(xr) < f(x1), calcul de xe = x0 + 2(x0 − xN + 1) (étirement du simplexe). Si f(xe) < f(xr), remplacement de xN + 1 par xe, sinon, remplacement de xN + 1 par xr. Retour à l'étape 3.

6- Si f(xn) < f(xr), calcul de xc = xN + 1 + 1 / 2(x0 − xN + 1) (contraction du simplexe). Si f(x_c)\leq f(x_r), remplacement de xN + 1 par xc et retour à l'étape 3,

7- Similitude de rapport 1/2 et de centre x1 : remplacement de xi par x0 + 1 / 2(xi − x1). Retour à l'étape 3.