Méthode de Nelder-Mead

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne pas confondre avec l'algorithme du simplexe qui s'applique aux problèmes d'optimisation linéaires.
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[1] par Nelder (en) et Mead 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[modifier | modifier le code]

Soit N la dimension de l'espace où f prend ses valeurs. 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 substituer par la réflexion 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 aux valeurs prises sur les autres points, le simplexe est étiré dans cette direction. Sinon, il est supposé que l'allure locale de la fonction est une vallée, et le simplexe est réduit par une similitude 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 à N dimensions des inconnues, formant un simplexe : {x_1,x_2,...,x_{N+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}). Il suffit en fait de connaître le premier et les deux derniers.
  3. Calcul de x_0, centre de gravité de tous les points sauf x_{N+1}.
  4. Calcul de x_r=x_0+(x_0-x_{N+1}) (réflexion de x_{N+1} par rapport à x_0).
  5. Si f(x_r)<f(x_N), calcul de x_e=x_0+2(x_0-x_{N+1}) (étirement du simplexe). Si f(x_e)<f(x_r), remplacement de x_{N+1} par x_e, sinon, remplacement de x_{N+1} par x_r. Retour à l'étape 2.
  6. Si f(x_N)<f(x_r), calcul de x_c=x_{N+1}+1/2(x_0-x_{N+1}) (contraction du simplexe). Si f(x_c)\leq f(x_N), remplacement de x_{N+1} par x_c et retour à l'étape 2, sinon aller à l'étape 7.
  7. Homothétie de rapport 1/2 et de centre x_1 : remplacement de x_i par x_1+1/2(x_i-x_1) pour i>=2. Retour à l'étape 2.

Intérêt[modifier | modifier le code]

Avantages[modifier | modifier le code]

  • La généralité : une fonction continue (sans é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.
  • L’assurance d’obtenir une série décroissante de valeurs.

Inconvénients[modifier | modifier le code]

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) La donnée « arbitraire » d’un simplexe de départ.

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).

Amélioration facile et très efficace: Redémarrer l'algorithme[modifier | modifier le code]

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 (voir par exemple http://www.mathworks.com/matlabcentral/fileexchange/33328 et http://arxiv.org/abs/1104.5369 ). 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).

Méthode de Nelder-Mead avec recuit simulé[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. (en) John Nelder et Roger Mead, « A simplex method for function minimization », Computer Journal, vol. 7, no 4,‎ 1965, p. 308-313
  2. W. H Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, « Numerical Recipes : The Art of Scientific Computing », Cambridge University Press, Third Edition (2007)