Dokumentacja klasy PowellVariant1

#include <PowellVariant1.h>

Diagram dziedziczenia dla PowellVariant1

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:

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

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

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.