Dokumentacja klasy NelderMead

#include <NelderMead.h>

Diagram dziedziczenia dla NelderMead

Opis szczegółowy

Algorytm optymalizacji metodą Neldera-Meada.

W metodzie Neldera-Meada po wykresie funkcji pełza sympleks złożony z N+1 punktów, gdzie N oznacza liczbę wymiarów problemu.

Algorytm metody:

Oznaczenia:
$ S^k $ - zbiór punktów sympleksu w k-tej iteracji
$ S_i $ - zbiór indeksów punktów należących do $ S^k $ .
$\check{S}^k = S^k \setminus \{x^k_w\}$
$\check{S}_i$ - zbiór indeksów punktów należących do $\check{S}^k$
$ x^k_b $ - najlepszy punkt sympleksu w k-tej iteracji
$ x^k_w $ - najgorszy punkt sympleksu w k-tej iteracji
$ x^k_v $ - prawie najgorszy punkt sympleksu w k-tej iteracji
$\bar{x}$ - środek ciężkości zbioru $\check{S}^k$
$ x_r $ - punkt powstały poprzez odbicie najgorszego punktu sympleksu względem punktu $\bar{x}$
$ x_e $ - punkt przesunięty jeszcze dalej w tym samym kierunku, w którym nastąpiło odbicie najgorszego punktu sympleksu przy tworzeniu punktu $ x_r $
$ x_c $ - punkt znajdujący się pomiędzy najgorszym punktem sympleksu, a środkiem ciężkości pozostałych jego punktów lub tymże środkiem ciężkości, a punktem $ x_r $

Dane potrzebne do obliczeń:
$ f(x) $ - funkcja celu
$ r $ - współczynnik odbicia ( $ r > 0 $ , domyślnie 1)
$ e $ - współczynnik rozciągnięcia ( $ e > r $ , domyślnie 2)
$ c $ - współczynnik ściśnięcia ( $ 0 < c < 1 $ , domyślnie $\frac{1}{2}$ )
$ s $ - współczynnik skurczenia ( $ 0 < s < 1 $ , domyślnie $\frac{1}{2}$ )
$ x^0 $ - środek początkowego sympleksu
$ d $ - długość krawędzi początkowego sympleksu

Krok 0 (wstępny):
W tym kroku wyliczamy współrzędne wierzchołków początkowego sympleksu w ten sposób, by punkt $ x^0 $ znalazł się w jego środku.
Poniższe wzory potrzebne do utworzenia regularnego sympleksu zaczerpnięto z [1].
Wzór na wyliczenie j-tej współrzędnej i-tego wierzchołka sympleksu ma postać:

$x^{(j)}_i = \left\{ \begin{array}{ll} x^{(j)}_0 + \delta_1 \mbox{ gdy } i \not= j;\\ x^{(j)}_0 + \delta_2 \mbox{ gdy } i = j. \end{array} \right.$

Wartości współczynnika $\sigma_1$ i $\sigma_2$ wyliczamy ze wzorów:

$\delta_1 = \left(\frac{\sqrt{N+1}+N-1}{N\sqrt{2}}\right)\frac{d}{2}$

$\delta_2 = \left(\frac{\sqrt{N+1}-1}{N\sqrt{2}}\right)\frac{d}{2}$

W powyższy sposób otwrzymujemy zbiór $ S^1 $ .
W wierzchołkach aktualnego sympleksu wyliczamy wartości funkcji.
Wybieramy szczególne punkty sympleksu: $ x^1_b $ , $ x^1_w $ i $ x^1_v $ . Zapamiętujemy rownież wartości funkcji $ F_b = f(x^1_b) $ , $ F_w = f(x^1_w) $ oraz $ F_v = f(x^1_v) $
Podstawiamy $ k = 1 $ i przechodzimy do kroku 1.

Krok 1:
Wyliczamy środek ciężkości punktów sympleksu z pominięciem punktu najgorszego wg wzoru:

$\bar{x} = \frac{ \sum_{i \in \check{S}_i} x_i }{N}$

Przechodzimy do kroku 2.
Krok 2:
Wyznaczamy punkt $ x_r $ poprzez odbicie najgorszego punktu sympleksu względem środka ciężkości:

$x_r = \bar{x} + r(\bar{x}-x^k_w)$

Wyliczamy wartość funkcji celu w tym punkcie.
Jeśli $ F_r < F_b $ , to przechodzimy do kroku 3. W przeciwnym przypadku przechodzimy do kroku 5.

Krok 3:
Wyznaczamy punkt $ x_e $ zgodnie ze wzorem:

$x_e = \bar{x} + e(\bar{x}-x^k_w)$

Wyliczamy wartość funkcji w tym punkcie.
Jeśli $ F_e < F_r $ to przechodzimy do kroku 4a. W przeciwnym wypadku przechodzimy do kroku 4b.

Krok 4a:
W sympleksie zastępujemy punkt $ x^k_w $ punktem $ x_e $ i przechodzimy do kroku 12.

Krok 4b:
W sympleksie zastępujemy punkt punktem $ x_r $ i przechodzimy do kroku 12.

Krok 5:
Jeśli $F_b \leq F_r < F_v$ , to przechodzimy do kroku 6. W przeciwnym wypadku przechodzimy do kroku 7.

Krok 6:
W sympleksie zastępujemy punkt $ x^k_w $ punktem $ x_r $ i przechodzimy do kroku 12.

Krok 7:
Jeśli $F_v \leq F_r < F_w$ , to przechodzimy do kroku 8. W przeciwnym Wypadku przechodzimy do kroku 9.

Krok 8:
Wyznaczamy punkt $ x_c $ ze wzoru:

$x_c = x_r - c(x_r - \bar{x})$

Wyliczamy w tym punkcie wartość funkcji.
Jeśli $F_c \leq F_r$ , przechodzimy do kroku 10. W przeciwnym wypadku przechodzimy do kroku 11.

Krok 9:
Wyznaczamy punkt $ x_c $ ze wzoru:

$x_c = x^k_w + c(\bar{x} - x^k_w)$

Wyliczamy w tym punkcie wartość funkcji.
Jeśli $F_c \leq F^k_w$ , przechodzimy do kroku 10. W przeciwnym wypadku przechodzimy do kroku 11.

Krok 10:
W sympleksie zastępujemy punkt $ x^k_w $ punktem $ x_c $ i przechodzimy do kroku 12.

Krok 11:
Dokonujemy skurczenia sympleksu w kierunku punktu najlepszego zgodnie z procedurą:

$x^{k+1}_i = x^k_i - s(x^k_i - x_b) \mbox{ dla } i \in S_i$

Oczywiście w wyniku działania tej procedury punkt najlepszy nie zmieni swojego położenia.
W nowych punktach obliczamy wartości funkcji.

Krok 12:
Podstawiamy $ k = k+1 $ .
Wybieramy szczególne punkty sympleksu: $x^{k+1}_b$ , $x^{k+1}_w$ i $x^{k+1}_v$ . Zapamiętujemy rownież wartości funkcji $ F_b = f(x_b) $ , $ F_w = f(x_w) $ oraz $ F_v = f(x_v) $
Przechodzimy do kroku 13.

Krok 13:
Jeśli spełniony jest warunek stopu, zakończ działanie algorytmu. Punktem wynikowym jest najlepszy punkt ostatniego sympleksu.
Jeśli warunek niejest spełniony przechodzimy do kroku 1.

Uwagi:
W metodzie można zastosować kilka rożnych warunków stopu

Warunek $\| x^k_w - x'^k_w \| \leq \varepsilon$ , gdzie poprzez oznaczamy punkt, który zastąpił w sympleksie punkt . Ten warunek jest odpowiednikiem tradycyjnego warunku sprawdzającego długość wykonanego kroku, wykorzystywanego często w metodach gradientowych.
Warunek $f(x^k_w) - f(x'^k_w) \leq \varepsilon$ , gdzie poprzez oznaczamy punkt, który zastąpił w sympleksie punkt .
Warunek $\| x^k_w - x^{k-1}_w \| \leq \varepsilon$ .
Warunek $F_w - F_b \leq \varepsilon$ .
Warunek $\| x^k_w - x^k_b \| \leq \varepsilon$ .
Warunek $D \leq \varepsilon$ , gdzie oznacza sumę długości wszystkich krawędzi sympleksu.

Postępując zgodnie z [2] do implementacji algorytmu wprowadzono usprawnienie dotyczące jest uznany za gorszy od wszystkich punktów o takiej samej wartości funkcji celu.

[1] Aleksander Ostanin - Metody i algorytmy optymalizacji, Wydawnictwo Politechniki Białostockiej, Białystok 2003 oraz: [2] J. C. Lagarias, J. A. Reeds, M. H. Wright, P. E. Wright - Convergence Properties of the Nelder-Mead Simplex Function in low dimensions. (SIAM Journal on Optimization, Vol. 1, No. 1, pp 112-147).

W drugim źródle zaproponowano sposoby postępowania w przypadku gdy co najmniej w dwóch wierzchołkach sympleksu wartość funkcji jest taka sama.

Niniejszy dokument został półautomatycznie wycięty z dokumentacji kodu źródłowego programu Eduoptim 2. Pełna dokumentacja dostępna jest wraz ze źródłami bądź osobno w dziale pliki.
Hierarchia klas w programie nie odpowiada klasyfikacji metod optymalizacji.