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


Metody publiczne

 ~RosenbrockDiscrete (void)
 Destruktor.
virtual std::auto_ptr< MethodClone () const
 Tworzy kopię metody.
virtual void UpdateStartingConditions (const Result *result) const
virtual void ResetStartingConditions () const
virtual const wxString & Name () const
 Zwraca nazwę metody.
virtual MethodIdType Id () const
 Zwraca ID metody.
virtual wxString ToString (bool standalone=true) const
 Zwraca opis tekstowy metody (nazwa + parametry).
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

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

Atrybuty chronione

ColumnVector mTau
 Początkowe (zadane przez użytkownika) długości kroku próbnego, mogą się różnić dla poszczególnych kierunków.
DoubleParameter mAlpha
 Współczynnik wydłużania kroku ($\alpha > 1$).
DoubleParameter mBeta
 Współczynnik skracania kroku ($0 < \beta < 1$).
DoubleParameter mDelta
 Minimalna długość kroku próbnego ($\delta$).
ColumnVector mStartingPoint
 Punkt startowy ($x^0$).
ColumnVector mInitialStartingPoint
CountedPtr< const StandardStopConditionmcpStopCondition
 Warunek stopu.

Przyjaciele

class RosenbrockDiscretePanel


Dokumentacja konstruktora i destruktora

RosenbrockDiscrete::RosenbrockDiscrete const RosenbrockDiscrete from  )  [protected]
 

Konstruktor kopiujący.

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


Dokumentacja funkcji składowych

void RosenbrockDiscrete::RotateBase SquareMatrix &  rD,
const ColumnVector &  lambda,
RosenbrockDiscreteIteration 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 RosenbrockDiscrete::SearchAllDirections const FunctionBase function,
ColumnVector &  rxBest,
double &  rMin,
const SquareMatrix &  D,
ColumnVector &  rTau,
ColumnVector &  rLambda,
RosenbrockDiscreteIteration rIterationData
const [protected]
 

Przeszukuje kierunki.

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

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

gdzie:
$x^i$ - aktualny punkt próbny,
$x^k_{min}$ - najlepszy punkt w bieżącym etapie.
Jeśli krok był udany ($f(x^i) < f(x^k_{min})$), długość $\tau^{(i)}$ jest dodawana do $\lambda^{(i)}$, a następnie zwiększana:

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

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

gdzie:
$\alpha > 1$ - współczynnik wydłużenia kroku.

Punkt próbny zostaje również zapamiętany jako najlepszy:

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

Jeśli krok nie powiódł się ($f(x^i) \ge f(x^k_{min})$), $\tau^{(i)}$ jest zmniejszana, a zwrot kroku odwracany:

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

gdzie:
$\beta \in (0,1) $ - współczynnik skrócenia kroku.

Przebieg jest powtarzany do momentu, kiedy w żadnym z kierunków nie wykonano udanego kroku.

Parametry:
function Funkcja celu ($f$).
rxBest Referencja na najlepszy dotąd punkt ($x^k_{min}$).
rMin Referencja na najmniejszą dotąd znalezioną wartość funkcji ($f(x^k_{min}) = F^k_{min}$).
D Baza kierunków $d^{(i)}, \: i=1,\ldots,n$.
rTau Referencja na wektor długości kroków w poszczególnych kierunkach ($\tau^{(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:53 2006 dla EduOptim2 programem  doxygen 1.4.6