Nelder-Mead-methode

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.

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

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 $\overline{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 )\overline{P}-\alpha P_h$

De reflectiecoëfficiënt $\alpha$ is een vooraf bepaalde, positieve constante. $P^{*}$ ligt op de lijn die $P_h$ en $\overline{P}$ verbindt aan de overkant van $\overline{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 )\overline{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 ten slotte blijkt dat $y^{*}>y_i$ voor alle $i\ne 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 )\overline{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-\overline{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 =\frac{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

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.