Dokumentacja klasy RosenbrockOptimal

#include <RosenbrockOptimal.h>

Diagram dziedziczenia dla RosenbrockOptimal

Opis szczegółowy

Metoda Rosenbrocka z krokiem optymalnym.

Metoda poszukiwań prostych.
Podobnie jak metoda Rosenbrocka z krokiem dyskretnym, polega na przeszukiwaniu w każdej iteracji $n$ ortogonalnych kierunków i obracaniu bazy w taki sposób, aby nowe kierunki były kierunkami największej dotychczasowej poprawy. W odróżnieniu od pierwotnego wariantu metody Rosenbrocka, w metodzie z krokiem optymalnym wzdłuż każdego z kierunków wykonywany jest tylko jeden krok - krok o optymalnej długości wyznaczonej przez metodę optymalizacji w kierunku. Dzięki temu każdy krok próbny jest krokiem udanym (kończącym się w punkcie o mniejszej niż poprzednio wartości funkcji celu). Upraszcza to znacznie procedurę.

Informacje wejściowe:
$f$ - minimalizowana funkcja $n$ zmiennych,
$x^0$ - dowolnie wybrany punkt startowy,
$\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$ ,

$\varepsilon$ - minimalna długość kroku w całym etapie,
wybrana metoda minimalizacji w kierunku wraz z parametrami.

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,
$\tau^{(i)}$ - optymalna długość kroku w i-tym kierunku,
$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,$

$k = 1 ,$

$i = 1 .$

Krok 1:
Przy pomocy metody optymalizacji w kierunku wyznaczamy optymalną długość kroku $\tau^{(i)}$ i wykonujemy krok:

$\tau^{(i)} = \arg \min_{\tau^{(i)}} f(x^k_{min} + \tau^{(i)} D^{(i)}) .$

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

Zapamiętujemy długość kroku i aktualny punkt:

$\lambda^{(i)} = \tau^{(i)} ,$

$x^k_{min} = x^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 warunek stopu. Jeśli jest on spełniony, to STOP. Wynikiem jest $x^k_{min}$ .
W przeciwnym wypadku przechodzimy do kroku 3.

Krok 3:
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:

$\lambda = 0(n),$

$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.

Zobacz również:: MethodWithLineSearch
RosenbrockDiscrete

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.