Dokumentacja klasy PowellVariant2

#include <PowellVariant2.h>

Diagram dziedziczenia dla PowellVariant2

MethodWithLineSearch Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Powella - wariant drugi.

Bezgradientowa metoda kierunków sprzężonych.

Od wariantu pierwszego odróżnia ją metoda modyfikacji bazy kierunków $D$ (krok 4 procedury). Metoda zaimplementowana w tym wariancie gwarantuje zachowanie liniowej niezależności kierunków.

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,
$ D = D^{(1)},\: D^{(2)}, \: \ldots, \: D^{(n)} $ - baza wzajemnie ortogonalnych kierunków (macierz utworzona z wektorów kolumnowych),
$x$ - aktualny punkt,
$x_s$ - punkt startowy etapu,
$\tau$ - długość optymalnego krok w danym kierunku $d$, wyznaczona przez metodę optymalizacji w kierunku,
$\tau_p$ - najdłuższy krok wzdłuż jednego z $n$ kierunków w fazie przeszukiwania,
$p$ - indeks kierunku, w którym wykonano najdłuższy krok,
$\Delta^k$ - wyznacznik macierzy kierunków $D$ w $k$-tej iteracji,
$\Delta_p$ - wyznacznik macierzy kierunków $D$ po ewentualnym umieszczeniu w~niej nowego kierunku sprzężonego.


Procedura.


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

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

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

Podstawiamy:

\[ x = x_s, \]

\[ \Delta^1 = 1, \]

\[ \tau_p = 0, \]

\[ 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)} . \]

Jeśli wykonany krok jest najdłuższy w etapie ($|\tau| > \tau_p$), to zapamiętujemy jego długość i indeks kierunku:

\[ \tau_p = |\tau|, \]

\[ p = 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:
Sprawdzamy warunek modyfikacji bazy:

\[ \Delta_p = \frac{\tau_p \Delta^k}{\|x - x_s\|} \ge 0,8 \; , \]

Jeśli warunek ten jest spełniony, kierunek, w którym wykonano najdłuższy krok $\tau_p$, zostaje zastąpiony nowym kierunkiem sprzężonym:

\[ D^{(p)} = D^{(n+1)} \]

i zostaje zapamiętany nowy wyznacznik bazy:

\[ \Delta^{k+1} = \Delta_p. \]

Jeśli warunek nie jest spełniony, baza kierunków nie jest zmieniana.
Podstawiamy aktualny punkt za punkt startowy dla kolejnego etapu:

\[ x_s = x. \]

Podstawiamy $k = k + 1$, $\tau_p = 0$ i wracamy do kroku 1.


Uwagi.
Wariant ten jest mniej wydajny od podstawowego, jednak gwarantuje zachowanie liniowej niezależności kierunków.

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

PowellVariant1


Metody publiczne

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

 PowellVariant2 (void)
 Konstruktor domyślny.
 PowellVariant2 (const PowellVariant2 &from)
 Konstruktor kopiujący.
void SearchAllDirections (const FunctionBase &function, ColumnVector &rxBest, const SquareMatrix &D, double &rTau_p, unsigned &rP, PowellVariant2Iteration &rIterationData) const
 Przeszukuje kierunki.
virtual wxString & rName ()

Przyjaciele

class MethodWithLineSearchPanel< PowellVariant2 >


Dokumentacja konstruktora i destruktora

PowellVariant2::PowellVariant2 const PowellVariant2 from  )  [protected]
 

Konstruktor kopiujący.

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


Dokumentacja funkcji składowych

void PowellVariant2::SearchAllDirections const FunctionBase function,
ColumnVector &  rxBest,
const SquareMatrix &  D,
double &  rTau_p,
unsigned &  rP,
PowellVariant2Iteration 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)} . \]

Ponadto, zapamiętywany jest indeks $p$ kierunku, w którym wykonano najdłuższy krok i długość tego kroku $\tau_p$:

\[ \tau_p = \max_{i \in \overline{1,n}} |\tau_i| . \]

Parametry:
function Funkcja celu ($f$).
rxBest Referencja na aktualny punkt ($x$).
D Baza kierunków $d^{(i)}, \: i=1,\ldots,n$.
rTau_p Referencja na długość najdłuższego kroku ($\tau_p$).
rP Referencja na indeks kierunku, w którym wykonano najdłuższy krok ($p$).
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