Nelder-Mead módszer


Szekvenciális egyszerűsítések a Nelder-Mead módszerben a Rosenbrock-függvényhez (fent) és a Himmelblau-függvényhez (lent)

Nem tévesztendő össze a lineáris programozásból származó " szimplex metódussal ", egy olyan módszerrel, amellyel egy lineáris rendszert korlátokkal lehet optimalizálni.

A Nelder-Mead módszer , más néven deformálható poliéder módszer és szimplex módszer , több változóból álló függvény feltétel nélküli optimalizálásának módszere, amely nem használja a függvény deriváltját (pontosabban gradienseit ), ezért könnyen használható. nem sima és/vagy zajos funkciókra alkalmazható .

A módszer lényege a szimplex szekvenciális mozgatása és deformálása a szélsőpont körül.

A módszer lokális szélsőséget talál, és az egyikben elakadhat. Ha továbbra is globális szélsőséget kell találnia, megpróbálhat másik kezdeti szimplexet választani. A lokális szélsőségek kiküszöbölésére fejlettebb megközelítést kínálnak a Monte Carlo módszeren alapuló algoritmusok , valamint az evolúciós algoritmusok .

Algoritmus

Legyen szükséges egy n változóból álló függvény feltétlen minimumának megtalálása . Feltételezzük, hogy a függvény definíciós tartományában nincsenek komoly megkötések, vagyis a függvény minden találkozási ponton definiálva van. $f\left(x^{{(1)}},x^{{(2)}},\ldots ,x^{{(n)}}\jobbra)$

A módszer paraméterei a következők:

a tükrözési együtthatót általában egyenlőnek választják . $\alpha >0$ $egy$
a tömörítési arányt általában egyenlőnek választják . $\beta>0$ $0{,}5$
a nyújtási tényezőt általában egyenlőnek választják . $\gamma >0$ $2$

"Kiképzés". Először kiválasztunk egy pontot , amely egy n-dimenziós tér szimplexét alkotja. Ezeken a pontokon számítjuk ki a függvény értékeit: . $n+1$ $x_{i}=\left(x_{i}^{{(1)}},x_{i}^{{(2)}},\ldots ,x_{i}^{{(n)}}\ jobbra),i=1..n+1$ $f_{1}=f(x_{1}),f_{2}=f(x_{2}),\ldots ,f_{{n+1}}=f(x_{{n+1}})$
"Válogató". A szimplex csúcsai közül három pontot választunk ki: a függvény legnagyobb (a kiválasztott) értékével, a következő legnagyobb értékkel és a függvény legkisebb értékével . A további manipulációk célja az lesz, hogy legalább . $x_{h}$ $f_{h}$ $x_{g}$ $f_{g}$ $x_{l}$ $f_{l}$ $f_{h}$
Keressük meg az összes pont súlypontját , kivéve : . Nem szükséges számolni . $x_{h}$ $x_{c}={\frac {1}{n}}\sum \limits _{{i\neq h}}x_{i}$ $f_{c}=f(x_{c})$
"Visszaverődés". A pontot az együtthatóhoz viszonyítva tükrözzük ( ennél központi szimmetria lesz , általános esetben - homothety ), megkapjuk a pontot és kiszámítjuk benne a függvényt: . Az új pont koordinátáit a következő képlet számítja ki: $x_{h}$ $x_{c}$ $\alpha$ $\alpha=1$ $x_{r}$ $f_{r}=f(x_{r})$ $x_{r}=(1+\alpha )x_{c}-\alpha x_{h}$ .
Ezután megnézzük, mennyit sikerült csökkenteni a funkciót, keressük a helyét a sorozatban . $f_{r}$ $f_{h},f_{g},f_{l}$ Ha , akkor az irány sikeres, és megpróbálhatja növelni a lépést. "nyújtást" gyártunk. Új pont és függvényérték . $f_{r}<f_{l}$ $x_{e}=(1-\gamma )x_{c}+\gamma x_{r}$ $f_{e}=f(x_{e})$ Ha , akkor a szimplexet kiterjeszthetjük idáig: értéket rendelünk a ponthoz , és befejezzük az iterációt (a 9. lépésben). $f_{e}<f_{r}$ $x_{h}$ $x_{e}$ Ha , akkor túl messzire került: rendeljen értéket a ponthoz , és fejezze be az iterációt (9. lépésre). $f_{r}<f_{e}$ $x_{h}$ $x_{r}$ Ha , akkor nem rossz a pont megválasztása (az új jobb, mint az előző kettő). Rendeljen értéket a ponthoz , és folytassa a 9. lépéssel. $f_{l}<f_{r}<f_{g}$ $x_{h}$ $x_{r}$ Ha , akkor cserélje fel és értékét . Ezenkívül fel kell cserélnie a és az értékeket . Ezt követően továbblépünk a 6. lépésre. $f_{g}<f_{r}<f_{h}$ $x_{r}$ $x_{h}$ $f_{r}$ $f_{h}$ Ha , akkor folytassa a következő 6. lépéssel. $f_{h}<f_{r}$ Ennek eredményeként (talán átnevezés után) . $f_{l}<f_{g}<f_{h}<f_{r}$
"Tömörítés". Építünk egy pontot , és kiszámítjuk az értéket benne . $x_{s}=\beta x_{h}+(1-\beta )x_{c}$ $f_{s}=f(x_{s})$
Ha , akkor rendeljen értéket a ponthoz , és folytassa a 9. lépéssel. $f_{s}<f_{h}$ $x_{h}$ $x_{s}$
Ha , akkor a kezdeti pontok bizonyultak a legsikeresebbnek. A szimplex - homotitás "globális összehúzódását" a legkisebb értékű pontig végezzük : $f_{s}>f_{h}$ $x_{l}$ $x_{i}\x_{l}+(x_{i}-x_{l})/2$ , . $i\neq l$
Az utolsó lépés a konvergencia ellenőrzése. Különböző módon megtehető, például egy ponthalmaz szórásának becslésével. Az ellenőrzés lényege, hogy ellenőrizzük a szimplex kapott csúcsai egymáshoz való közelségét, ami egyben a kívánt minimumhoz való közelségüket is jelenti. Ha még nem érte el a kívánt pontosságot, folytathatja az iterációt a 2. lépéstől.

Források

TANFOLYAM "Többdimenziós optimalizálás". 10. előadás _ _ Részletes leírás illusztrációkkal.
A Nelder-Mead módszer . Rövid algoritmus.
A numerikus módszerekre mutató hivatkozások listája
J. A. Nelder és R. Mead, Computer Journal, 1965, vol. 7. o. 308-313 . _

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás