Dokumentacja klasy FletcherReeves

#include <FletcherReeves.h>

Diagram dziedziczenia dla FletcherReeves

MethodWithLineSearch Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Fletchera-Reevesa.

Matoda Fletchera-Reevesa należy do klasy metod gradientów sprzężonych, co oznacza, że do otrzymywania kierunków sprzężonych wykorzystano w niej wartości składników gradientów.

Metoda powinna znaleźć minimum dowolnej funkcji kwadratowej w liczbie kroków co najwyżej równej wymiarowi problemu.

Algorytm metody:

Oznaczenia:
$ k $ - numer aktualnej iteracji
$x^k$ - punkt w $k$-tej iteracji,
$d^k$ - kierunek poszukiwań w $k$-tej iteracji,
$\gamma^k$ -współczynnik zapewniający sprzężenie nowego kierunku $d^k$ z poprzednim,
$ \tau $ - długość kroku

Dane potrzebne do obliczeń:
$ f(x) $ - minimalizowana funkcja celu
$ x^0 $ - punkt startowy
$ \varepsilon $ - wymagana dokładność
warunek stopu - do wyboru:


Krok 0 (wstępny):
Oblicz $ \nabla f(x^0) $.
Podstaw $ k=0 $.
Przejdź do kroku 1.

Krok 1:
Jeśli spełniony jest warunek stopu, to przerwij działanie algorytmu i jako wynik przedstaw $ x^k $. W przeciwnym wypadku przejdź do kroku 2.

Krok 2:
Przejdź do kroku 3, jeśli $ k=0 $ gdy używana jest tradycyjna wersja algorytmu lub jeśli $ k \mbox{ mod } n = 0 $ w przypadku gdy wprowadzono modyfikację (patrz: Uwagi). W przeciwnym wypadku przejdź do kroku 4.

Krok 3:
Podstaw:

\[ d^k = -\nabla(f(x^k)) \]

Przejdź do kroku 5.

Krok 4:
Podstaw:

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

gdzie:

\[ \gamma^k = \frac{\|\nabla f(x^k)\|^2}{\|\nabla f(x^{k-1}))\|^2} \]

Przejdź do kroku 5.
Krok 5:

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

gdzie $ \tau $ dobierane jest tak, by funkcja $ f(x) $ osiągała minimum w kierunku $ d^k $.
Podstaw: $ k = k+1 $.
Przejdź do kroku 1.


Uwagi:

  1. Modyfikacja wprowadzona do oryginalnego algorytmu Fletchera-Reevesa polega na powracaniu do poszukiwań w kierunku przeciwnym do gradientu po wykonaniu liczby kroków równej wymiarowi problemu. Pozwala on na zapobieżenie wygenerowaniu kierunków liniowo zależnych, co powoduje spowolnienie zbieżności.

Algorytm zaimplementowano na podstawie:
Ostanin. A: Metody i algorytmy optymalizacji, Wydawnictwo Politechniki Białostockiej, Białystok, 2003

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.