Dokumentacja klasy PowellVariant1

#include <PowellVariant1.h>

Diagram dziedziczenia dla PowellVariant1

MethodWithLineSearch Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Powella - wariant pierwszy.

Bezgradientowa metoda kierunków sprzężonych.

Metoda oparta na dwóch twierdzeniach:
1. Dla wzajemnie sprzężonych względem dodatnio określonej macierzy $A$ kierunków

\[ d^{(1)}, \: d^{(2)}, \: \ldots, \: d^{(n)} \]

minimum formy kwadratowej

\[ f(x) = q + b^T x + \frac{1}{2} x^T A x \]

może być znalezione w wyniku minimalizacji funkcji $f(x)$ wzdłuż każdego z kierunków $d^{(i)}$ tylko raz.

Kierunki $ d^{(1)}, \: d^{(2)}, \: \ldots, \: d^{(n)} $ są wzajemnie sprzężone względem dodatnio określonej macierzy $A$, gdy spełniony jest warunek:

\[ (d^{(i)})^T A d^{(j)} = 0 \mbox{ dla wszystkich } i \neq j. \]

2. Jeśli $x^0$ jest minimum w kierunku $d$ należącym do pewnej rozmaitości liniowej oraz jeśli $x^1$ jest minimum w tym samym kierunku $d$, ale w innej rozmaitości zawierającej ten kierunek (np. $x^0$ i $x^1$ znaleziono w wyniku minimalizacji w kierunku $d$ zaczynając z różnych punktów startowych), to kierunek

\[ (x^1 - x^0) \]

łączący te dwa punkty jest sprzężony z kierunkiem $d$.

Twierdzenie 1 zapewnia, że metoda, przy wykorzystaniu dokładnych poszukiwań w kierunku, będzie znajdować minimum wielomianu drugiego stopnia w $n$ krokach, gdzie $n$ jest liczbą zmiennych.
Twierdzenie 2 dostarcza łatwej metody generowania kierunków sprzężonych.

Informacje wejściowe:
$f$ - minimalizowana funkcja $n$ zmiennych,
$x^0$ - dowolnie wybrany punkt startowy,
$\varepsilon$ - wymagana dokładność obliczeń,
warunek stopu - do wyboru:

wybrana metoda minimalizacji w kierunku wraz z parametrami.


Oznaczenia:
$i$ - indeks aktualnego kierunku,
$k$ - numer aktualnej iteracji,
$x$ - aktualny punkt,
$ D = D^{(1)}, \: D^{(2)}, \: \ldots, \: D^{(n)} $ - baza wzajemnie ortogonalnych kierunków (macierz utworzona z wektorów kolumnowych),
$x_s$ - punkt startowy etapu,
$\tau$ - długość optymalnego kroku w danym kierunku $d$, wyznaczona przez metodę optymalizacji w kierunku.


Procedura.

Krok wstępny:
Podstawiamy $ D = I(n) $, gdzie $I(n)$ - macierz identycznościowa o wymiarach $ n \times n $.
Wyliczamy pierwszy punkt początkowy:

\[ \tau = \arg \min_{\tau} f(x + \tau D^{(n)}), \]

\[ x_s = x^0 + \tau D^{(n)}. \]

Podstawiamy:

\[ x = x_s, \]

\[ k = 1 , \]

\[ i = 1 . \]


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

\[ \tau = \arg \min_{\tau} f(x + \tau D^{(i)}) . \]

\[ x = x + \tau D^{(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$.
W przeciwnym razie przechodzimy do kroku 3.


Krok 3:
Wyznaczamy nowy kierunek sprzężony:

\[ D^{(n+1)} = \frac{x - x_s}{\| x - x_s \|} . \]

Następnie wykonujemy krok o optymalnej długości w tym kierunku:

\[ \tau = \arg \min_{\tau} f(x + \tau D^{(n+1)}) , \]

\[ x = x + \tau D^{(n+1)}. \]


Krok 4:
Dodajemy nowo uworzony kierunek do bazy $D$, usuwając dotychczasowy kierunek $D^{(1)}$:

\[ D^{(i)} = D^{(i+1)}, \mbox{ dla i = 1, \ldots, n.} \]

Podstawiamy aktualny punkt za punkt startowy dla kolejnego etapu:

\[ x_s = x. \]

Podstawiamy $k = k + 1$ i wracamy do kroku 1.


Uwagi.
Taka metoda modyfikacji bazy może doprowadzić do występowania w niej kierunków zależnych liniowo. W celu wyeliminowania takiej możliwości wprowadzono wariant drugi metody Powella.

Metoda zaimplementowana na podstawie opisu zamieszczonego w:
Findeisen W., Szymanowski J., Wierzbicki A.: Teoria i metody obliczeniowe optymalizacji. Warszawa, PWN 1977.
W odróżnieniu od tego opisu, w implementacji warunek stopu sprawdzany jest przed obliczeniem nowego kierunku sprzężonego, w celu uniknięcia ryzyka dzielenia przez 0 przy wyznaczaniu kierunku.

Zobacz również:
MethodWithLineSearch

PowellVariant2


Metody publiczne

 ~PowellVariant1 (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

 PowellVariant1 (void)
 Konstruktor domyślny.
 PowellVariant1 (const PowellVariant1 &from)
 Konstruktor kopiujący.
void SearchAllDirections (const FunctionBase &function, ColumnVector &rxBest, const SquareMatrix &D, PowellVariant1Iteration &rIterationData) const
 Przeszukuje kierunki.
virtual wxString & rName ()

Przyjaciele

class MethodWithLineSearchPanel< PowellVariant1 >


Dokumentacja konstruktora i destruktora

PowellVariant1::PowellVariant1 const PowellVariant1 from  )  [protected]
 

Konstruktor kopiujący.

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


Dokumentacja funkcji składowych

void PowellVariant1::SearchAllDirections const FunctionBase function,
ColumnVector &  rxBest,
const SquareMatrix &  D,
PowellVariant1Iteration 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$:

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

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

Parametry:
function Funkcja celu ($f$).
rxBest Referencja na aktualny punkt ($x$).
D Baza kierunków $d^{(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