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.^[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.

De methode start met een initiële simplex die is bepaald door (n+1) punten ${\displaystyle P_{0},P_{1},\dots P_{n}}$ in de n-dimensionale ruimte. De bijhorende functiewaarden zijn ${\displaystyle y_{0},y_{1},\dots y_{n}}$. We duiden met ${\displaystyle P_{h}}$ het punt aan met de hoogste functiewaarde ${\displaystyle y_{h}}$, en met ${\displaystyle P_{l}}$ het punt met de laagste functiewaarde ${\displaystyle y_{l}}$. Het zwaartepunt van alle punten behalve ${\displaystyle P_{h}}$ wordt aangeduid met ${\displaystyle {\bar {P}}}$.

In een iteratiestap wordt ${\displaystyle P_{h}}$ vervangen door een nieuw punt. Daarvoor worden drie bewerkingen gebruikt: reflectie, contractie en expansie.

De reflectie van ${\displaystyle P_{h}}$ is een nieuw punt ${\displaystyle P^{*}}$, waarvan de coördinaten gegeven zijn door de vergelijking:

${\displaystyle P^{*}=(1+\alpha ){\bar {P}}-\alpha P_{h}}$

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

Indien nu de functiewaarde ${\displaystyle y^{*}}$ in ${\displaystyle P^{*}}$ gelegen is tussen ${\displaystyle y_{h}}$ en ${\displaystyle y_{l}}$, dan vervangen we ${\displaystyle P_{h}}$ door ${\displaystyle P^{*}}$ en herbeginnen met de nieuwe simplex.

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

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

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

Wanneer na de reflectie ten slotte blijkt dat ${\displaystyle y^{*}>y_{i}}$ voor alle ${\displaystyle i\neq h}$, dan blijft ${\displaystyle y^{*}}$ de maximale functiewaarde indien we ${\displaystyle P_{h}}$ vervangen door ${\displaystyle P^{*}}$. Indien ${\displaystyle y^{*}<y_{h}}$ vervangen we ${\displaystyle P_{h}}$ door ${\displaystyle P^{*}}$; anders behouden we ${\displaystyle P_{h}}$. We vormen dan

${\displaystyle P^{**}=\beta P_{h}+(1-\beta ){\bar {P}}}$

en berekenen ${\displaystyle y^{**}}$.

De contractiecoëfficiënt ${\displaystyle \beta }$ is een constante tussen 0 en 1. Als de contractie een succes is (${\displaystyle y^{**}<y_{h}}$), vervangen we ${\displaystyle P_{h}}$ door ${\displaystyle P^{**}}$ en herstarten. Wanneer de contractie faalde, d.w.z. het punt ${\displaystyle P^{**}}$ is niet beter dan ${\displaystyle P_{h}}$, dan vervangen we alle ${\displaystyle P_{i}}$'s door ${\displaystyle (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:

${\displaystyle {\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 ${\displaystyle \alpha }$, de contractiecoëfficiënt ${\displaystyle \beta }$ en de expansiecoëfficiënt ${\displaystyle \gamma }$. De keuze van deze constanten heeft een invloed op de snelheid van convergentie; de beste strategie, volgens Nelder en Mead, bleek te zijn ${\displaystyle \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.

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

${\displaystyle 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 ${\displaystyle 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.