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

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.

Optimalisatiealgoritme