Metoda Neldera-Meada

Metoda Neldera–Meada lub sympleksowa metoda spadku (ang. downhill simplex method) – metoda numeryczna wyznaczania ekstremum (typowo minimum) nieliniowej funkcji wielu zmiennych ${\displaystyle 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)^[1].

Opis metody

Wybieramy trzy parametry (liczby rzeczywiste): ${\displaystyle \alpha >0,\;\beta \in (0,1)}$ oraz ${\displaystyle \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 ${\displaystyle n\,+\,1}$ punktów z ${\displaystyle \mathbb {R} ^{n}\colon \{x^{(0)},\ldots ,x^{(n)}\},}$

taki, że wektory ${\displaystyle 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 ${\displaystyle f(x^{(0)})\geq f(x^{(1)})\geq \ldots \geq f(x^{(n)}).}$

Teraz definiujemy trzy punkty: ${\displaystyle 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 ${\displaystyle u}$ jest środkiem ściany sympleksu, która jest naprzeciw punktu ${\displaystyle x^{(0)},}$ czyli punktu „najgorszego” (szukamy minimum). Konstrukcja nowego sympleksu zależy od wartości funkcji w zdefiniowanych punktach ${\displaystyle u,\;v,\;w.}$ Wyróżniamy trzy przypadki ${\displaystyle u,\;v,\;w.}$

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

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

• ${\displaystyle f(v)\;\geq \;f(x^{(n)})\;i\;f(v)\;\leq \;f(x^{(1)}).}$

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

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

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

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

Przypisy

Linki zewnętrzne

• Nelder–Mead (Simplex) Method, Uniwersytet Gdański. paula.univ.gda.pl. [zarchiwizowane z tego adresu (2011-09-04)].