Metoda Neldera-Meada

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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)[1].

Opis metody[edytuj | edytuj kod]

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 – w razie 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.

Przypisy

  1. John A. Nalder, Roger Mead. A Simplex Method for Function Minimization. „The Computer Journal”. 7 (4), s. 308-313, 1965. doi:10.1093/comjnl/7.4.308 (ang.). 

Linki zewnętrzne[edytuj | edytuj kod]