Nelder-Mead-methode

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De Nelder-Mead-methode is een algoritme voor het bepalen van het minimum van een functie in meerdere variabelen. Ze werd in 1965 ingevoerd door de Britten John Nelder en Roger Mead.[1]

De methode zoekt het minimum van een functie van n variabelen door het vergelijken van de functiewaarden in de (n+1) hoekpunten van een algemene simplex. Een simplex is het convex omhulsel van n+1 onafhankelijke punten in de n-dimensionale ruimte; bijvoorbeeld een driehoek in het tweedimensionale vlak of een viervlak in de driedimensionale ruimte. In elke iteratiestap wordt het hoekpunt met de hoogste functiewaarde vervangen door een nieuw punt. De simplex past zich zo aan de vorm van de functie aan, en trekt zich uiteindelijk samen rond het minimum.

De methode maakt enkel gebruik van functiewaarden, niet van eerste of hogere afgeleiden. Ze is daarmee geschikt voor het minimiseren van functies waarvan men de analytische vorm niet kent, maar waarvan de functiewaarden het resultaat zijn van een meting of een (mogelijk kostelijk) experiment. De enige aannames die gemaakt worden zijn, dat de functie continu is en een uniek minimum heeft in het gebied dat doorzocht wordt.

Beschrijving van de methode[bewerken]

De methode start met een initiële simplex die is bepaald door (n+1) punten P_0, P_1, \dots P_n in de n-dimensionale ruimte. De bijhorende functiewaarden zijn y_0, y_1, \dots y_n. We duiden met P_h het punt aan met de hoogste functiewaarde y_h, en met P_l het punt met de laagste functiewaarde y_l. Het zwaartepunt van alle punten behalve P_h wordt aangeduid met \bar P.

In een iteratiestap wordt P_h vervangen door een nieuw punt. Daarvoor worden drie bewerkingen gebruikt: reflectie, contractie en expansie.

De reflectie van P_h is een nieuw punt P^*, waarvan de coördinaten gegeven zijn door de vergelijking:

P^* = (1 + \alpha)\bar P - \alpha P_h

De reflectiecoëfficiënt \alpha is een vooraf bepaalde, positieve constante. P^* ligt op de lijn die P_h en \bar P verbindt aan de overkant van \bar P ten opzichte van P_h.

Indien nu de functiewaarde y^* in P^* gelegen is tussen y_h en y_l, dan vervangen we P_h door P^* en herbeginnen met de nieuwe simplex.

Wanneer echter y^* < y_l, hebben we een nieuw minimum. Dan proberen we een expansie door te voeren van P^* naar P^{**}:

 P^{**} = \gamma P^* + (1 - \gamma) \bar P.

De expansiecoëfficiënt \gamma is een constante en is groter dan 1. Wanneer y^{**} < y_l is de expansie succesvol en vervangen we P_h door P^{**} en herbeginnen met de nieuwe simplex. In het andere geval leverde de expansie geen verbetering op; we vervangen dan P_h door P^* en herbeginnen.

Wanneer na de reflectie tenslotte blijkt dat y^* > y_i voor alle i \neq h, dan blijft y^* de maximale functiewaarde indien we P_h vervangen door P^*. Indien y^* < y_h vervangen we P_h door P^*; anders behouden we P_h. We vormen dan

P^{**} = \beta P_h + (1 - \beta) \bar P

en berekenen y^{**}.

De contractiecoëfficiënt \beta is een constante tussen 0 en 1. Als de contractie een succes is (y^{**} < y_h), vervangen we P_h door P^{**} en herstarten. Wanneer de contractie faalde, d.w.z. het punt P^{**} is niet beter dan P_h, dan vervangen we alle P_i's door (P_i + P_l)/2 en herstarten.

Het algoritme stopt wanneer het minimum, binnen een voorafbepaalde nauwkeurigheid, bereikt is. Nelder en Mead namen als criterium hiervoor de "standaardfout" van de functiewaarden:

 \sqrt{ \frac { \sum_i {(y_i - \bar y)^2}}{n} }

Het algoritme stopt wanneer deze waarde kleiner wordt dan een voorafbepaalde waarde. Zij gebruikten dit criterium omdat het nuttig is bij statistische problemen.

Naast het stopcriterium moet men dus vooraf drie constanten vastleggen: de reflectiecoëfficiënt \alpha, de contractiecoëfficiënt \beta en de expansiecoëfficiënt \gamma. De keuze van deze constanten heeft een invloed op de snelheid van convergentie; de beste strategie, volgens Nelder en Mead, bleek te zijn  \alpha = 1, \beta = \tfrac{1}{2}, \gamma = 2. Ook de keuze van de initiële simplex is belangrijk. In sommige gevallen kan de methode convergeren naar een punt dat niet het minimum is.

Voorbeeld[bewerken]

Verloop van de simplexmethode bij de "banaanfunctie" van Rosenbrock

De figuur hiernaast illustreert het verloop van de methode bij het zoeken van het minimum van de functie:

y = 100(x_2 - x_1^2)^2 + (1-x_1)^2

Deze niet-convexe functie werd in 1960 door Howard Rosenbrock voorgesteld als testfunctie voor optimalisatiealgoritmen. Ze staat bekend als de vallei van Rosenbrock of de banaanfunctie van Rosenbrock. Het globale minimum ligt in een lange, smalle, vlakke, parabolische vallei in het punt x_1, x_2 = 1. Men ziet hoe de simplex (hier een driehoek) zich verplaatst naar de bodem van de vallei en dan langzaam langs de bodem naar het minimum evolueert.

Bronnen, noten en/of referenties
  1. J.A. Nelder, R. Mead. "A simplex method for function minimization." The Computer Journal (1965), vol. 7 nr. 4, blz. 308-313. DOI:10.1093/comjnl/7.4.308