Dokumentacja klasy AlphaDivision

#include <AlphaDivision.h>

Diagram dziedziczenia dla AlphaDivision

Opis szczegółowy

Metoda alfa-podziału.

Metoda optymalizacji w kierunku polegająca na stopniowym skracaniu zadanego odcinka (patrz SectionLineSearch).

Skracanie odcinka następuje w każdej iteracji, na podstawie badania wartości funkcji w dwóch punktach: $\lambda$ i $\mu$ . Punkty te rozmieszczane są w taki sposób, aby dzieliły odcinek symetrycznie:

$\lambda^k = a^k + (1 - \alpha) (b^k - a^k),$

$\mu^k = a^k + \alpha (b^k - a^k),$

gdzie:
$a^k, b^k$ - końce zadanego odcinka,
$\alpha$ - współczynnik podziału odcinka zadany przez użytkownika, $\alpha \in (0,5; 1).$
Dzięki takiemu podziałowi w każdej iteracji zachodzi:

$\lambda^k - a^k = b^k - \mu^k = (1 - \alpha) (b^k - a^k) .$

Redukcja odcinka polega na odrzuceniu jednego z jego skrajnych fragmentów: $[a^k, \lambda^k]$ lub $[\mu^k, b^k]$ , w zależności od wartości funkcji w punktach próbnych. W każdej iteracji odcinek jest więc skracany o długość:

$(1 - \alpha) (b^k - a^k) .$

W przypadku gdy metoda działa samodzielnie, wynikiem jest odcinek $[a^k, b^k]$ ; jeśli służy tylko do minimalizacji kierunkowej przy rozwiązywaniu problemu optymalizacji funkcji wielu zmiennych, wynikiem jest punkt - środek tego odcinka: $\frac{a^k + b^k}{2}$ .

Informacje wejściowe:
$f(x)$ - minimalizowana funkcja jednej zmiennej,
$a^0$ - lewy kraniec początkowego przedziału poszukiwań,
$b^0$ - prawy kraniec początkowego przedziału poszukiwań,
$\alpha$ - współczynnik podziału odcinka, $\alpha \in (0,5; 1),$
$\varepsilon$ - wymagana dokładność (graniczna długość odcinka).

Oznaczenia:
$k$ - numer aktualnej iteracji,
$a^k$ - lewy kraniec aktualnego przedziału poszukiwań,
$b^k$ - prawy kraniec aktualnego przedziału poszukiwań,
$\lambda^k$ - punkt próbny znajdujący się po lewej stronie,
$\mu^k$ - punkt próbny znajdujący się po prawej stronie,
$F_{\lambda^k}$ - wartość funkcji w punkcie $\lambda^k$ ,
$F_{\mu^k}$ - wartość funkcji w punkcie $\mu^k$ .

Procedura.

Krok wstępny:
Podstawiamy:

$a^1 = a^0,$

$b^1 = b^0,$

$\lambda^1 = a^1 + (1 - \alpha) (b^1 - a^1),$

$\mu^1 = a^1 + \alpha (b^1 - a^1),$

$F_{\lambda^1} = f(\lambda^1),$

$F_{\mu^1} = f(\mu^1),$

$k = 1 .$

Krok 1:
Jeśli $F_{\lambda^k} \le F_{\mu^k}$ , to przechodzimy do kroku 2. W przeciwnym razie przechodzimy do kroku 3.

Krok 2:
Redukujemy odcinek do $[a^k, \mu^k]$ :

$a^{k+1} = a^k,$

$b^{k+1} = \mu^k$

i dokonujemy podziału otrzymanego odcinka:

$\lambda^{k+1} = a^{k+1} + (1 - \alpha) (b^{k+1} - a^{k+1}),$

$\mu^{k+1} = a^{k+1} + \alpha (b^{k+1} - a^{k+1}) ,$

$F_{\lambda^{k+1}} = f(\lambda^{k+1}),$

$F_{\mu^{k+1}} = f(\mu^{k+1}).$

Przechodzimy do kroku 4.

Krok 3:
Redukujemy odcinek do $[\lambda^k, b^k]$ :

$a^{k+1} = \lambda^k,$

$b^{k+1} = b^k$

i dokonujemy podziału otrzymanego odcinka:

$\lambda^{k+1} = a^{k+1} + (1 - \alpha) (b^{k+1} - a^{k+1}),$

$\mu^{k+1} = a^{k+1} + \alpha (b^{k+1} - a^{k+1}) ,$

$F_{\lambda^{k+1}} = f(\lambda^{k+1}),$

$F_{\mu^{k+1}} = f(\mu^{k+1}).$

Przechodzimy do kroku 4.

Krok 4:
Sprawdzamy warunek stopu:
Jeśli $(b^{k+1} - a^{k+1}) < \varepsilon$ , to STOP. W przeciwnym razie podstawiamy $k = k + 1$ i przechodzimy do kroku 1.

Szczególnym, najczęściej stosowanym przypadkiem metody jest algorytm z parametrem $\alpha = \frac{\sqrt{5} - 1}{2} \approx 0,618$ . Dla tej wartości parametru odcinek $[a, b]$ jest w każdej iteracji dzielony przez punkty próbne na pododcinki spełniające warunek "złotego podziału":

$\frac{\mu^k - a^k}{b^k - a^k} = \frac{b^k - \mu^k}{\mu^k - a^k} = \alpha,$

$\frac{b^k - \lambda^k}{b^k - a^k} = \frac{\lambda^k - a^k} {b^k - \lambda^k} = \alpha,$

Stąd:

$\frac{\lambda^k - a^k}{\mu^k - a^k} = \alpha .$

Dzięki ostatniej własności procedura podziałów odcinka upraszcza się: w każdej iteracji wyznaczamy tylko jeden nowy punkt próbny i, co za tym idzie, tylko raz obliczamy wartość funkcji.

Procedura.

Krok wstępny:
Podstawiamy:

$a^1 = a^0,$

$b^1 = b^0,$

$\lambda^1 = a^1 + (1 - \alpha) (b^1 - a^1),$

$\mu^1 = a^1 + \alpha (b^1 - a^1),$

$F_{\lambda^1} = f(\lambda^1),$

$F_{\mu^1} = f(\mu^1),$

$k = 1 .$

Krok 1:
Jeśli $F_{\lambda^k} < F_{\mu^k}$ , to przechodzimy do kroku 2. W przeciwnym razie przechodzimy do kroku 3.

Krok 2:
Redukujemy odcinek do $[a^k, \mu^k]$ :

$a^{k+1} = a^k,$

$b^{k+1} = \mu^k$

i dokonujemy podziału otrzymanego odcinka:

$\lambda^{k+1} = a^{k+1} + (1 - \alpha) (b^{k+1} - a^{k+1}),$

$\mu^{k+1} = \lambda^k,$

$F_{\lambda^{k+1}} = f(\lambda^{k+1}),$

$F_{\mu^{k+1}} = F_{\lambda^k}.$

Przechodzimy do kroku 4.

Krok 3:
Redukujemy odcinek do $[\lambda^k, b^k]$ :

$a^{k+1} = \lambda^k,$

$b^{k+1} = b^k$

i dokonujemy podziału otrzymanego odcinka:

$\lambda^{k+1} = \mu^k,$

$\mu^{k+1} = a^{k+1} + \alpha (b^{k+1} - a^{k+1}) ,$

$F_{\lambda^{k+1}} = F_{\mu^k},$

$F_{\mu^{k+1}} = f(\mu^{k+1}).$

Przechodzimy do kroku 4.

Krok 4:
Sprawdzamy warunek stopu:
Jeśli $(b^{k+1} - a^{k+1}) < \varepsilon$ , to STOP. W przeciwnym razie podstawiamy $k = k + 1$ i przechodzimy do kroku 1.

Taki wariant metody nazywany jest popularnie metodą złotego podziału.

Zobacz również:: SectionLineSearch
MethodWithLineSearch

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.