Internetowa Encyklopedia „Wiki”

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→ℝ 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): α>0,β∈(0,1) oraz γ⩾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),…,x(n)},

taki, że wektory x(1)−x(0),…,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))⩾…⩾f(x(n)).

Teraz definiujemy trzy punkty: u:=1n∑i=1nx(i)v:=(1+α)u−αx(0),w:=(1+γ)v−γ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óżnia się 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:=βx(0)+(1−β)u. Jeżeli f(w)⩽f(x(0)), to x(0):=w, a w przeciwnym razie dla i=0,…,n−1 definiujemy x(i):=12(x(i)+x(n)).

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