#include <PowellVariant1.h>
Diagram dziedziczenia dla PowellVariant1
Bezgradientowa metoda kierunków sprzężonych.
Metoda oparta na dwóch twierdzeniach:
1. Dla wzajemnie sprzężonych względem dodatnio określonej macierzy kierunków
minimum formy kwadratowej
może być znalezione w wyniku minimalizacji funkcji wzdłuż każdego z kierunków
tylko raz.
Kierunki są wzajemnie sprzężone względem dodatnio określonej macierzy
, gdy spełniony jest warunek:
2. Jeśli jest minimum w kierunku
należącym do pewnej rozmaitości liniowej oraz jeśli
jest minimum w tym samym kierunku
, ale w innej rozmaitości zawierającej ten kierunek (np.
i
znaleziono w wyniku minimalizacji w kierunku
zaczynając z różnych punktów startowych), to kierunek
łączący te dwa punkty jest sprzężony z kierunkiem .
Twierdzenie 1 zapewnia, że metoda, przy wykorzystaniu dokładnych poszukiwań w kierunku, będzie znajdować minimum wielomianu drugiego stopnia w krokach, gdzie
jest liczbą zmiennych.
Twierdzenie 2 dostarcza łatwej metody generowania kierunków sprzężonych.
Informacje wejściowe:
- minimalizowana funkcja
zmiennych,
- dowolnie wybrany punkt startowy,
- wymagana dokładność obliczeń,
warunek stopu - do wyboru:
Oznaczenia:
- indeks aktualnego kierunku,
- numer aktualnej iteracji,
- aktualny punkt,
- baza wzajemnie ortogonalnych kierunków (macierz utworzona z wektorów kolumnowych),
- punkt startowy etapu,
- długość optymalnego kroku w danym kierunku
, wyznaczona przez metodę optymalizacji w kierunku.
Procedura.
Krok wstępny:
Podstawiamy , gdzie
- macierz identycznościowa o wymiarach
.
Wyliczamy pierwszy punkt początkowy:
Podstawiamy:
Krok 1:
Przy pomocy metody optymalizacji w kierunku wyznaczamy optymalną długość kroku i wykonujemy krok:
Podstawiamy i sprawdzamy, czy
. Jeśli tak, ponownie wykonujemy krok 1. Jeśli nie, podstawiamy
i przechodzimy do kroku 2.
Krok 2:
Sprawdzamy warunek stopu. Jeśli jest on spełniony, to STOP. Wynikiem jest .
W przeciwnym razie przechodzimy do kroku 3.
Krok 3:
Wyznaczamy nowy kierunek sprzężony:
Następnie wykonujemy krok o optymalnej długości w tym kierunku:
Krok 4:
Dodajemy nowo uworzony kierunek do bazy , usuwając dotychczasowy kierunek
:
Podstawiamy aktualny punkt za punkt startowy dla kolejnego etapu:
Podstawiamy 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.
Metody publiczne | |
~PowellVariant1 (void) | |
Destruktor. | |
virtual std::auto_ptr< Method > | Clone () 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 > |
|
Konstruktor kopiujący.
|
|
Przeszukuje kierunki.
Dla każdego kierunku
|