Dokumentacja klasy RosenbrockDiscrete

#include <RosenbrockDiscrete.h>

Diagram dziedziczenia dla RosenbrockDiscrete

Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Rosenbrocka z krokiem dyskretnym.

Metoda poszukiwań prostych.
Podobnie jak algorytm Hooke'a i Jeevesa, oparta jest na wykonywaniu w każdej iteracji kroków próbnych wzdłuż $n$ ortogonalnych kierunków. Kierunki te, inaczej niż w metodzie HJ, mogą się zmieniać - na końcu każdej iteracji baza kierunków $D^{(i)},\: i=1,\ldots,n$ jest obracana w taki sposób, aby zawierała kierunek największej poprawy i pozostałych $n - 1$ wzajemnie ortonormalnych kierunków.


Informacje wejściowe:
$f$ - minimalizowana funkcja $n$ zmiennych,
$x^0$ - dowolnie wybrany punkt startowy,
$\tau_0^{(i)},\: i=1,\ldots,n$ - n-wymiarowy wektor początkowych długości kroku,
$\alpha$ - współczynnik wydłużania kroku ($\alpha > 1$),
$\beta$ - współczynnik skracania kroku ($0 < \beta < 1$),
$\delta$ - wstępny warunek stopu - minimalna długość kroku próbnego,
$\varepsilon$ - dokładność właściwego warunku stopu,
warunek stopu - do wyboru:


Oznaczenia:
$i$ - indeks aktualnego kierunku,
$k$ - numer aktualnej iteracji,
$D = D^{(i)},\: i=1,\ldots,n$ - aktualna baza kierunków,
$\lambda^{(i)},\: i=1,\ldots,n$ - wektor sum długości udanych kroków próbnych w poszczególnych kierunkach,
$x^i$ - aktualny punkt próbny,
$x^k_{min}$ - najlepszy punkt w k-tym etapie,
$F^k_{min}$ - wartość funkcji w punkcie $x^k_{min}$,
$F^k_b$ - najlepsza wartość funkcji przed rozpoczęciem przeszukiwania kierunków z bazy,
$A_i, \: i=1,\ldots,n$ - wektory sum przesunięć wykorzystywane przy obrocie bazy,
$t_i, \: i=1,\ldots,n$ - kwadraty norm wektorów $A_i$ wykorzystywane przy normalizacji nowej bazy ($t_i = \|A_i\|^2$).


Procedura.

Krok wstępny:
Podstawiamy:

\[ D = I(n), \mbox{ gdzie } I(n) - \mbox{ macierz jednostkowa } n \times n , \]

\[ \lambda = 0(n), \]

\[ x^1_{min} = x^0, \]

\[ F^0_{min} = f(x^0) , \]

\[ F^1_{min} = f(x^0) , \]

\[ F^1_b = f(x^0) , \]

\[ \tau = \tau_0 , \]

\[ k = 1 , \]

\[ i = 1 . \]


Krok 1:
Badamy wartość funkcji w nowym punkcie próbnym (wykonując krok w i-tym kierunku):

\[ x^i = x^k_{min} + \tau^{(i)} D^{(i)} . \]

Jeśli krok był udany ($f(x^i) < F^k_{min}$), to dodajemy długość kroku do sumy $\lambda^{(i)}$, wydłużamy krok w bieżącym kierunku i zapamiętujemy aktualny punkt jako najlepszy:

\[ \lambda^{(i)} = \lambda^{(i)} + \tau^{(i)}, \]

\[ \tau^{(i)} = \alpha \tau^{(i)}, \]

\[ x^k_{min} = x^i, \]

\[ F^k_{min} = f(x^i). \]

Jeśli krok był nieudany ($f(x^i) \ge F^k_{min}$), to skracamy krok w bieżącym kierunku i odwracamy jego zwrot:

\[ \tau^{(i)} = -\beta \tau^{(i)}. \]

Podstawiamy $i = i + 1$ i sprawdzamy, czy $i \le n $. Jeśli tak, ponownie wykonujemy krok 1. Jeśli nie, podstawiamy $i = 1$ i przechodzimy do kroku 2.


Krok 2:
Sprawdzamy, czy przy ostatnim przeszukiwaniu $n$ kierunków nastąpiła poprawa.
Jeśli tak ($F^k_{min} < F^k_b$), to podstawiamy:

\[ F^k_b = F^k_{min} \]

i przechodzimy do kroku 1. W przeciwnym wypadku przechodzimy do kroku 3.


Krok 3:
Sprawdzamy wstępny warunek stopu:

\[ \min_{i \in \overline{1,\ldots,n}} |\tau^{(i)}| < \delta \]

i zapamiętujemy jego wartość logiczną.

Następnie sprawdzamy, czy w całej iteracji nastąpiła poprawa - jeśli tak ($F^k_{min} < F^{k-1}_{min}$), to przechodzimy do kroku 4.

W przeciwnym wypadku ($F^k_{min} = F^{k-1}_{min}$), jeśli wstępny warunek stopu jest spełniony, to STOP. Jeśli nie jest, podstawiamy $k = k + 1$ i przechodzimy do kroku 1.


Krok 4:

Sprawdzamy główny warunek stopu. Jeśli ten oraz wstępny warunek stopu z kroku 2 są spełnione, to STOP. W przeciwnym razie przechodzimy do kroku 5.


Krok 5:

Dokonujemy obrotu bazy, według algorytmu Palmera:

1) Dla $ i = 1,\ldots,n $:
Wyliczamy wektory sum przesunięć:

\[ A_i = \sum_{j=i}^n \lambda^{(j)} D^{(j)} \]

oraz wektor $t$:

\[ t_i = \|A_i\|^2 . \]

2) Tworzymy nowe kierunki ortonormalne $D^{(i)}$ :
a) Dla $i = n,\ldots,2$ :

\[ div = \sqrt{t_{i-1} t_i} . \]

\[ \mbox{Jesli } div \ne 0 : D^{(i)} = \frac{\lambda^{(i-1)} A_i - D^{(i-1)} t_i}{div} , \]

b) Na koniec tworzymy kierunek największej poprawy $D^{(1)}$.

\[ div = \sqrt{t_1} , \]

\[ D^{(1)} = \frac{A_1}{div}. \]

W ten sposób otrzymujemy nową bazę kierunków $D^{(i)},\: i=1,\ldots,n$.

Następnie podstawiamy:

\[ \tau = \tau_0 , \]

\[ \lambda = 0(n), \]

\[ x^{k+1}_{min} = x^k_{min}, \]

\[ F^{k+1}_{min} = F^k_{min}, \]

\[ F^{k+1}_b = F^k_{min}, \]

\[ k = k + 1 \]

i przechodzimy do kroku 1.


Uwagi.
Oryginalna metoda Rosenbrocka wykorzystywała przy ortonormalizacji nowej bazy metodę Grama-Schmidta. W tej implementacji użyto metody Palmera, bardziej wydajnej i tworzącej poprawną bazę również w przypadku, gdy w iteracji istnieją kierunki, w których nie wykonano żadnego udanego kroku.

Metoda zaimplementowana na podstawie programu Franka Vanden Berghena (http://iridia.ulb.ac.be/%7Efvandenb/download.php?id=33), który powstał na podstawie publikacji:
1) Rosenbrock, H. H., An Automatic Method for Finding the Greatest or Least Value of a Function (1960). (http://iridia.ulb.ac.be/~fvandenb/optimization/paper_rosenbrock.zip)
2) Palmer, J. R., An improved procedure for orthogonalising the search vectors in Rosenbrock's and Swann's direct search optimisation methods (1969). (http://iridia.ulb.ac.be/~fvandenb/optimization/paper_palmer.zip)

Zobacz również:
RosenbrockOptimal

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.