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\colon \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 Neldera i Rogera Meada (1965).

Opis metody

Wybieramy trzy parametry (liczby rzeczywiste): $\alpha >0,\;\beta \in (0,1)$ oraz $\gamma \geq 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}\colon \{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)})\geq f(x^{(1)})\geq \ldots \geq f(x^{(n)}).$

Teraz definiujemy trzy punkty: $u:={\frac {1}{n}}\sum _{i=1}^{n}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)\;\geq \;f(x^{(n)})\;i\;f(v)\;\leq \;f(x^{(1)}).$

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

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

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

Teraz – w razie potrzeby – dokonujemy przenumerowania nowych punktów $x^{(0)},\ldots ,x^{(n)}$ tak, aby zachodziło uporządkowanie $f(x^{(0)})\geq f(x^{(1)})\geq \ldots \geq 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. paula.univ.gda.pl. [zarchiwizowane z tego adresu (2011-09-04)].