Dokumentacja klasy DFP

#include <DFP.h>

Diagram dziedziczenia dla DFP

MethodWithLineSearch Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Davidona-Fletchera-Powella.

Metoda zmiennej metryki.
Metoda z rodziny algorytmów quasi-Newtonowskich, opartych na tej samej własności i sposobie postępowania, co zmodyfikowana metoda Newtona: dla funkcji celu o postaci

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

wystarczy znajomość macierzy odwrotnej do hesjanu $A^{-1}$, aby w jednym kroku wyznaczyć minimum. Poszukiwanie przebiega wtedy zgodnie z prostą procedurą:

\[ x^{k+1} = x^k - \tau A^{-1} \nabla f(x^k). \]

Metody quasi-Newtonowskie zastępują macierz $A^{-1}$, której otrzymanie jest kosztowne ze względu na konieczność wyliczania drugich pochodnych, macierzą estymującą $D$. Staje się ona w kolejnych iteracjach coraz lepszym przybliżeniem macierzy odwrotnej do hesjanu. Pierwszym, ale efektywnym pomysłem na generowanie takiej macierzy był wzór Davidona-Fletchera-Powella:

\[ D^{k+1} = D^k + \frac{p^k (p^k)^T}{(p^k)^T q^k} - \frac{D^k q^k (q^k)^T D^k}{(q^k)^T D^k q^k}, \]

gdzie:

\[ p^k = x^{k+1} - x^k, \]

\[ q^k = \nabla f(x^{k+1}) - \nabla f(x^k). \]

Gdy przybliżenie uznaje się za zadowalające, procedura kończy się.

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,
informacja, czy realizowana będzie metoda z modyfikacją.


Oznaczenia:
$k$ - numer aktualnej iteracji,
$d^k$ - aktualny kierunek poszukiwań,
$x^k$ - aktualny punkt,
$g^k$ - gradient funkcji w punkcie $x^k$,
$\tau$ - długość wykonywanego aktualnie kroku,
$D^k$ - aktualna macierz estymująca m. odwrotną do hesjanu.


Procedura.

Krok wstępny:
Podstawiamy:

\[ D^1 = I(n), \mbox{ gdzie } I(n) - \mbox{ macierz jednostkowa } n \times n , \]

\[ g^0 = \nabla f(x^0), \]

\[ g^1 = g^0, \]

\[ d^1 = -g^0, \]

\[ x^1 = x^0, \]

\[ k = 1. \]


Krok 1:
Sprawdzamy warunek stopu.
Jeśli jest on spełniony, to STOP. Wynikiem jest $x^k$.
W przeciwnym wypadku przechodzimy do kroku 2.


Krok 2:
Wykonujemy krok o optymalnej długości $\tau$ w aktualnym kierunku:

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

\[ x^{k+1} = x^k + \tau d^k . \]

Obliczamy gradient w otrzymanym punkcie:

\[ g^{k+1} = \nabla f(x^{k+1}) . \]

Przechodzimy do kroku 3.


Krok 3:
Jeśli realizowana jest wersja z modyfikacją, sprawdzamy, czy $k = n, \: 2n, \: 3n, \: \ldots$. Jeśli tak, podstawiamy:

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

i przechodzimy do kroku 5.

W przeciwnym razie przechodzimy do kroku 4.


Krok 4:
Wyliczamy $D^{k+1}$ jako kolejne przybliżenie macierzy odwrotnej do hesjanu, zgodnie ze wzorem Davidona-Fletchera-Powella:

\[ D^{k+1} = D^k + \frac{p^k (p^k)^T}{(p^k)^T q^k} - \frac{D^k q^k (q^k)^T D^k}{(q^k)^T D^k q^k}, \]

gdzie:

\[ p^k = x^{k+1} - x^k, \]

\[ q^k = g^{k+1} - g^k. \]


Krok 5:
Wyznaczamy kolejny kierunek:

\[ d^{k+1} = -D^{k+1} g^{k+1} . \]

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


Uwagi.
Metody zmiennej metryki należą do najwydajniejszych algorytmów optymalizacji bez ograniczeń. Ze względu jednak na konieczność stopniowego estymowania macierzy odwrotnej do hesjanu, w niektórych wypadkach mogą być one wolniej zbieżne od zmodyfikowanej metody Newtona (w zamian za większą liczbę kroków potrzebnych do znalezienia minimum otrzymamy jednak znacznie mniejszą liczbę wyliczeń funkcji celu).

Regularne ponowne inicjowanie macierzy $D$ macierzą jednostkową (krok 3) wprowadzono w celu zwiększenia stabilności metody. Gdyby aktualizować macierz zgodnie ze wzorem Davidona-Fletchera-Powella w każdej iteracji, mogłaby ona stracić, na skutek niedokładnych obliczeń i niedokładności metody minimalizacji w kierunku, dodatnią określoność, a to mogłoby doprowadzić do dążenia algorytmu w kierunku maksimum. Ceną za poprawę stabilności w taki sposób jest oczywiście mniejsza szybkość zbieżności metody.

Metoda zaimplementowana na podstawie opisu zamieszczonego w:
Findeisen W., Szymanowski J., Wierzbicki A.: Teoria i metody obliczeniowe optymalizacji. Warszawa, PWN 1977.

Zobacz również:
MethodWithLineSearch

NewtonModified


Metody publiczne

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

virtual wxString & rName ()
 DFP (void)
 Konstruktor domyślny.
 DFP (const DFP &from)
 Konstruktor kopiujący.
SquareMatrix CalculateNewD (const SquareMatrix &D, const ColumnVector &x_diff, const ColumnVector &grad_diff) const
 Wyznacza zaktualizowaną macierz D.

Atrybuty chronione

bool mModification
 Czy do algorytmu ma zostać wprowadzone usprawninie (szczegóły w opisie metody).

Przyjaciele

class MethodWithLineSearchPanel< DFP >
 Panel ustawień metody.
class VariantedMethodWithLineSearchPanel< DFP >


Dokumentacja konstruktora i destruktora

DFP::DFP const DFP from  )  [protected]
 

Konstruktor kopiujący.

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


Dokumentacja funkcji składowych

SquareMatrix DFP::CalculateNewD const SquareMatrix &  D,
const ColumnVector &  x_diff,
const ColumnVector &  grad_diff
const [protected]
 

Wyznacza zaktualizowaną macierz D.

Wyznacza nową, bliższą macierzy odwrotnej do hesjanu, macierz $D$, według wzoru Davidona-Fletchera-Powella:

\[ D_{k+1} = D_k + \frac{p_k p_k^T}{p_k^T q_k} - \frac{D_k q_k q_k^T D_k}{q_k^T D_k q_k}, \]

gdzie:

\[ p_k = x_{k+1} - x_k, \]

\[ q_k = \nabla f(x_{k+1}) - \nabla f(x_k). \]

Parametry:
D Obecna macierz przybliżająca ($D_k$).
x_diff Wektor różnicy punktów ($p_k$).
grad_diff Wektor różnicy gradientów ($q_k$).
Zwraca:
Zaktualizowana macierz prybliżająca ($D_{k+1}$).


Dokumentacja dla tej klasy została wygenerowana z plików:
Wygenerowano Fri Sep 29 21:04:50 2006 dla EduOptim2 programem  doxygen 1.4.6