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.
Beschrijving van de methode
[bewerken | brontekst bewerken]De methode start met een initiële simplex die is bepaald door (n 1) punten in de n-dimensionale ruimte. De bijhorende functiewaarden zijn . We duiden met het punt aan met de hoogste functiewaarde , en met het punt met de laagste functiewaarde . Het zwaartepunt van alle punten behalve wordt aangeduid met .
In een iteratiestap wordt vervangen door een nieuw punt. Daarvoor worden drie bewerkingen gebruikt: reflectie, contractie en expansie.
De reflectie van is een nieuw punt , waarvan de coördinaten gegeven zijn door de vergelijking:
De reflectiecoëfficiënt is een vooraf bepaalde, positieve constante. ligt op de lijn die en verbindt aan de overkant van ten opzichte van .
Indien nu de functiewaarde in gelegen is tussen en , dan vervangen we door en herbeginnen met de nieuwe simplex.
Wanneer echter , hebben we een nieuw minimum. Dan proberen we een expansie door te voeren van naar :
- .
De expansiecoëfficiënt is een constante en is groter dan 1. Wanneer is de expansie succesvol en vervangen we door en herbeginnen met de nieuwe simplex. In het andere geval leverde de expansie geen verbetering op; we vervangen dan door en herbeginnen.
Wanneer na de reflectie ten slotte blijkt dat voor alle , dan blijft de maximale functiewaarde indien we vervangen door . Indien vervangen we door ; anders behouden we . We vormen dan
en berekenen .
De contractiecoëfficiënt is een constante tussen 0 en 1. Als de contractie een succes is (), vervangen we door en herstarten. Wanneer de contractie faalde, d.w.z. het punt is niet beter dan , dan vervangen we alle 's door 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:
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 , de contractiecoëfficiënt en de expansiecoëfficiënt . De keuze van deze constanten heeft een invloed op de snelheid van convergentie; de beste strategie, volgens Nelder en Mead, bleek te zijn . 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 | brontekst bewerken]De figuur hiernaast illustreert het verloop van de methode bij het zoeken van het minimum van de functie:
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 . 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.
- ↑ 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