Dokumentacja klasy RosenbrockOptimal

#include <RosenbrockOptimal.h>

Diagram dziedziczenia dla RosenbrockOptimal

MethodWithLineSearch Method Observable Lista wszystkich składowych.

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:

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


Metody publiczne

 ~RosenbrockOptimal (void)
 Destruktor.
virtual std::auto_ptr< MethodClone () const
 Tworzy kopię metody.
virtual const wxString & Name () const
 Zwraca nazwę metody.
virtual MethodIdType Id () const
 Zwraca ID metody.
virtual bool CanHandle (const ProblemBase *pProblem) const
 Sprawdza, czy dany problem może być rozwiązany tą metodą.
virtual StopConditions AllowedStopConditions () const
 Zwraca listę warunków stopu odpowiednich dla danej metody.

Statyczne metody publiczne

static MethodIdType ClassId ()
 Zwraca ID metody.

Metody chronione

 RosenbrockOptimal (void)
 Konstruktor domyślny.
 RosenbrockOptimal (const RosenbrockOptimal &from)
 Konstruktor kopiujący.
void SearchAllDirections (const FunctionBase &function, ColumnVector &rxBest, const SquareMatrix &D, ColumnVector &rLambda, RosenbrockOptimalIteration &rIterationData) const
 Przeszukuje kierunki.
void RotateBase (SquareMatrix &rD, const ColumnVector &lambda, RosenbrockOptimalIteration &rIterationData) const
 Dokonuje obrotu bazy kierunków.
virtual wxString & rName ()

Przyjaciele

class MethodWithLineSearchPanel< RosenbrockOptimal >


Dokumentacja konstruktora i destruktora

RosenbrockOptimal::RosenbrockOptimal const RosenbrockOptimal from  )  [protected]
 

Konstruktor kopiujący.

Parametry:
from Obiekt, którego wartość jest kopiowana.


Dokumentacja funkcji składowych

void RosenbrockOptimal::RotateBase SquareMatrix &  rD,
const ColumnVector &  lambda,
RosenbrockOptimalIteration rIterationData
const [protected]
 

Dokonuje obrotu bazy kierunków.

Na podstawie sum długości udanych kroków $\lambda^{(i)}$, zmienia bazę wektorów kierunków $d^{(i)}, \: i=1,\ldots,n$. Pierwszy wektor w nowej bazie jest kierunkiem największej poprawy znalezionym w danym etapie, kolejny wektor - najlepszym kierunkiem normalnym dla pierwszego, itd.

Metoda wykorzystuje ortogonalizację Palmera:
na początku wyliczane są wektory sum przesunięć $A_i, i = 1,\ldots,n : $

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

gdzie:
$\lambda^{(j)}$ - suma długości udanych kroków w kierunku $d^{(j)}$,

oraz wektor $t$:

\[ t^{(i)} = |A_i|^2 , \: i = 1,\ldots,n. \]

Następnie wykonana zostaje procedura utworzenia nowych kierunków ortonormalnych $d^{(i)}$ :
1. 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} , \]

2.

\[ div = \sqrt{t^{(1)}} , \]

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

Parametry:
rD Referencja na zmienianą bazę kierunków $d^{(i)}, \: i=1,\ldots,n$.
lambda Wektor sum długości udanych kroków w poszczególnych kierunkach ($\lambda^{(i)}, \: i=1,\ldots,n$).
rIterationData Referencja na dane bieżącej iteracji dla wyniku.

void RosenbrockOptimal::SearchAllDirections const FunctionBase function,
ColumnVector &  rxBest,
const SquareMatrix &  D,
ColumnVector &  rLambda,
RosenbrockOptimalIteration rIterationData
const [protected]
 

Przeszukuje kierunki.

Dla każdego kierunku $d^{(i)}, \: i=1,\ldots,n$ metoda wykonuje jeden krok próbny o optymalnej długości $\tau^{(i)}$:

\[ \tau^{(i)} = \arg \min_{\tau^{(i)}} f(x^k_{min} + \tau^{(i)} d^{(i)}) , \]

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

Długość kroku jest zapamiętywana jako $\lambda^{(i)}$ :

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

Parametry:
function Funkcja celu ($f$).
rxBest Referencja na najlepszy dotąd punkt ($x^k_{min}$).
D Baza kierunków $d^{(i)}, \: i=1,\ldots,n$.
rLambda Referencja na wektor sum długości udanych kroków w poszczególnych kierunkach ($\lambda^{(i)}, \: i=1,\ldots,n$).
rIterationData Referencja na dane bieżącej iteracji dla wyniku.


Dokumentacja dla tej klasy została wygenerowana z plików:
Wygenerowano Fri Sep 29 21:04:54 2006 dla EduOptim2 programem  doxygen 1.4.6