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:{ℝ}^n\to ℝ$ 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 ⩾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 ${ℝ}^n:\{x^{(0)},\dots ,x^{(n)}\},$

taki, że wektory $x^{(1)}-x^{(0)},\dots ,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)})⩾f(x^{(1)})⩾\dots ⩾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)⩾f(x^{(n)})if(v)⩽f(x^{(1)}).$

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

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

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

Teraz – w razie potrzeby – dokonujemy przenumerowania nowych punktów $x^{(0)},\dots ,x^{(n)}$ tak, aby zachodziło uporządkowanie $f(x^{(0)})⩾f(x^{(1)})⩾\dots ⩾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

• Szablon:Cytuj stronę