Dokumentacja klasy RosenbrockDiscrete

#include <RosenbrockDiscrete.h>

Diagram dziedziczenia dla RosenbrockDiscrete

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:

$\|x^{k+1} - x^k\| < \varepsilon$ ,
$|f(x^{k+1}) - f(x^k)| < \varepsilon$ ,
$\frac{|f(x^{k+1}) - f(x^k)|}{\|x^{k+1} - x^k\|} < \varepsilon$ ,

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.