Dokumentacja klasy AlphaDivision

#include <AlphaDivision.h>

Diagram dziedziczenia dla AlphaDivision

SectionLineSearch LineSearch Method Observable Lista wszystkich składowych.

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.