Nelder-Mead metod


Sekventiella förenklingar i Nelder-Mead-metoden för Rosenbrock-funktionen (överst) och Himmelblau-funktionen (nederst)

Ej att förväxla med " simplexmetoden " från linjär programmering, en metod för att optimera ett linjärt system med begränsningar.

Nelder-Mead-metoden , även känd som den deformerbara polyedermetoden och simplexmetoden , är en metod för ovillkorlig optimering av en funktion av flera variabler som inte använder derivatan (mer exakt, gradienter ) av funktionen, och därför är lätt tillämpas på icke- jämna och/eller bullriga funktioner.

Kärnan i metoden är att sekventiellt flytta och deformera simplexen runt extremumpunkten.

Metoden hittar ett lokalt extremum och kan fastna i ett av dem. Om du fortfarande behöver hitta ett globalt extremum kan du försöka välja en annan initial simplex. En mer avancerad metod för att eliminera lokala extrema finns i algoritmer baserade på Monte Carlo-metoden , såväl som i evolutionära algoritmer .

Algoritm

Låt det krävas att hitta det ovillkorliga minimumet av en funktion av n variabler . Det antas att det inte finns några allvarliga begränsningar för funktionens definitionsdomän, det vill säga funktionen definieras vid alla påträffade punkter. $f\left(x^{{(1)}},x^{{(2)}},\ldots,x^{{(n)}}\höger)$

Metodparametrarna är:

reflektionskoefficienten , väljs vanligtvis lika med . $\alfa >0$ $ett$
kompressionsförhållandet väljs vanligtvis lika med . $\beta>0$ $0{,}5$
sträckfaktorn väljs vanligtvis lika med . $\gamma >0$ $2$

"Träning". Först väljs en punkt som bildar en simplex av ett n-dimensionellt utrymme. Vid dessa punkter beräknas funktionens värden: . $n+1$ $x_{i}=\left(x_{i}^{{(1)}},x_{i}^{{(2)}},\ldots,x_{i}^{{(n)}}\ höger), i=1..n+1$ $f_{1}=f(x_{1}),f_{2}=f(x_{2}),\ldots ,f_{{n+1}}=f(x_{{n+1}})$
"Sortering". Vi väljer tre punkter från hörnen i simplexen: med det största (från det valda) värdet på funktionen , med det näst största värdet och med det minsta värdet på funktionen . Målet med ytterligare manipulationer kommer att vara att åtminstone minska . $x_{h}$ $f_{h}$ $x_{g}$ $f_{g}$ $x_{l}$ $f_{l}$ $f_{h}$
Låt oss hitta tyngdpunkten för alla punkter, förutom : . Det är inte nödvändigt att beräkna . $x_{h}$ $x_{c}={\frac {1}{n}}\summa \limits _{{i\neq h}}x_{i}$ $f_{c}=f(x_{c})$
"Reflexion". Vi reflekterar punkten med avseende på koefficienten (vid detta kommer att vara central symmetri , i det allmänna fallet - homoteti ), vi får punkten och beräknar funktionen i den: . Koordinaterna för den nya punkten beräknas med formeln: $x_{h}$ $x_{c}$ $\alfa$ $\alpha=1$ $x_{r}$ $f_{r}=f(x_{r})$ $x_{r}=(1+\alpha )x_{c}-\alpha x_{h}$ .
Därefter tittar vi på hur mycket vi lyckades minska funktionen, vi letar efter en plats i serien . $f_{r}$ $f_{h},f_{g},f_{l}$ Om , då är riktningen framgångsrik och du kan försöka öka steget. Vi producerar "stretching". Nytt punkt och funktionsvärde . $f_{r}<f_{l}$ $x_{e}=(1-\gamma )x_{c}+\gamma x_{r}$ $f_{e}=f(x_{e})$ Om , då kan vi utöka simplexen till denna punkt: vi tilldelar punkten ett värde och avslutar iterationen (i steg 9). $f_{e}<f_{r}$ $x_{h}$ $x_{e}$ Om , sedan flyttat för långt: tilldela ett värde till punkten och avsluta iterationen (till steg 9). $f_{r}<f_{e}$ $x_{h}$ $x_{r}$ Om , då är valet av punkt inte dåligt (den nya är bättre än de två tidigare). Tilldela ett värde till punkten och gå till steg 9. $f_{l}<f_{r}<f_{g}$ $x_{h}$ $x_{r}$ Om , byt sedan ut värdena för och . Du måste också byta ut värdena för och . Efter det går vi till steg 6. $f_{g}<f_{r}<f_{h}$ $x_{r}$ $x_{h}$ $f_{r}$ $f_{h}$ Om , gå bara till nästa steg 6. $f_{h}<f_{r}$ Som ett resultat (kanske efter byte av namn) . $f_{l}<f_{g}<f_{h}<f_{r}$
"Kompression". Vi bygger en punkt och beräknar värdet i den . $x_{s}=\beta x_{h}+(1-\beta )x_{c}$ $f_{s}=f(x_{s})$
Om , tilldela sedan ett värde till punkten och gå till steg 9. $f_{s}<f_{h}$ $x_{h}$ $x_{s}$
Om , då visade sig de första punkterna vara de mest framgångsrika. Vi gör en "global sammandragning" av simplex -homoteten till den punkt med det minsta värdet : $f_{s}>f_{h}$ $x_{l}$ $x_{i}\får x_{l}+(x_{i}-x_{l})/2$ , . $i\neq l$
Det sista steget är att kontrollera konvergensen. Det kan göras på olika sätt, till exempel genom att uppskatta variansen för en uppsättning punkter. Kärnan i kontrollen är att kontrollera den ömsesidiga närheten av de erhållna hörnen i simplexen, vilket också innebär att de är nära det erforderliga minimumet. Om den erforderliga noggrannheten ännu inte uppnåtts kan du fortsätta att iterera från steg 2.

Källor

KURS "Multidimensionell optimering". Föreläsning 10 _ _ Detaljerad beskrivning med illustrationer.
Nelder-Mead-metoden . Kort algoritm.
Lista över länkar till numeriska metoder
J.A. Nelder och R. Mead, Computer Journal, 1965, vol. 7, sid. 308-313 . _

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering