Metoda Neldera-Meada

Metoda Neldera–Meada lub sympleksowa metoda spadku (ang. downhill simplex method) – metoda numeryczna wyznaczania ekstremum (typowo minimum) nieliniowej funkcji wielu zmiennych $f:\mathbb{R}^n\to \mathbb{R}$ bez korzystania z pochodnych. Tak więc może być stosowana do funkcji nieróżniczkowalnych. Została opisana po raz pierwszy przez Johna A. Naldera i Rogera Meada (1965).

Opis metody

Wybieramy trzy parametry (liczby rzeczywiste): $\alpha >0,\; \beta\in(0, 1)$ oraz $\gamma\ge 0$. Na przykład mogą to być wartości 1, 1/2 i 1. W każdym kroku metody dany jest układ $n\,+\,1$ punktów z $\mathbb{R}^n$: $\{x^{(0)},\ldots,x^{(n)}\},$

taki, że wektory $x^{(1)}-x^{(0)},\ldots,x^{(n)}-x^{(0)},$

są liniowo niezależne. Powłoka wypukła tych wektorów jest sympleksem n-wymiarowym. Numerację punktów tak wybieramy, aby zachodziły nierówności $f(x^{(0)})\ge f(x^{(1)})\ge\ldots\ge f(x^{(n)}).$

Teraz definiujemy trzy punkty: $u:={1\over n}\sum^n_{i=1}x^{(i)}\;\; v:=(1+\alpha)u-\alpha x^{(0)},\;\; w:=(1+\gamma)v-\gamma u.$

Zauważmy, że $u\,$ jest środkiem ściany sympleksu, która jest naprzeciw punktu $x^{(0)}\,$, czyli punktu "najgorszego" (szukamy minimum). Konstrukcja nowego sympleksu zależy od wartości funkcji w zdefiniowanych punktach $u,\;v,\;w$. Wyróżniamy trzy przypadki $u,\;v,\;w$.

• $f(v)\;<\;f(x^{(n)}).$

Jeżeli $f(w)\;<\;f(x^{(n)}),$ to $x^{(0)}\,:=\,w,$ a w przeciwnym razie $x^{(0)}\,:=\,v.$

• $f(v)\;\ge\;f(x^{(n)})\; i\;f(v)\;\le\;f(x^{(1)}).$

Teraz nowy punkt to $x^{(0)}\,:=\,v.$

• $f(v)\;>\;f(x^{(1)}).$

Jeżeli $f(v)\;\le\;f(x^{(0)}),$ to $x^{(0)}\,:=\,v.$ Ponadto definiujemy $w\,:=\,\beta x^{(0)}+(1-\beta)u.$ Jeżeli $f(w)\le f(x^{(0)}),$ to $x^{(0)}\,:=\,w,$ a w przeciwnym razie dla $i=0,\ldots,n-1$ definiujemy $x^{(i)}\,:={1\over 2}(x^{(i)}+x^{(n)}).$

Teraz – wrazie potrzeby – dokonujemy przenumerowania nowych punktów $x^{(0)},\ldots,x^{(n)}$ tak, aby zachodziło uporządkowanie $f(x^{(0)})\ge f(x^{(1)})\ge\ldots\ge f(x^{(n)})$ co kończy kolejny krok metody.

Podany opis bazuje na oryginalnej pracy Neldera i Meada. Istnieją też modyfikacje tej podstawowej metody — na przykład metoda wzmocnionego spadku Tsenga.

Linki zewnętrzne

• Nelder–Mead (Simplex) Method, Uniwersytet Gdański