Metoda gradientu sprzężonego

(Fletchera - Reevsa)

Metody kierunków sprzężonych stanowią grupę metod znajdowania punktu minimum f-cji wielu zmiennych, w których bardzo często wykorzystuje się model kwadratowy funkcji tzn. f-cja celu f(x) od dołu jest aproksymowana przez f-cje kwadratową (ściśle wypukłą w dół):

F(x)=1/2x^TAx + b^Tx + c

gdzie :

A - macierz symetryczna dodatnio określona, której elementami są drugie pochodne cząstkowe f-cji f(x).

Jest to użyteczne zwłaszcza wtedy gdy ze wzgl. na wymiarowość zadania nie dysponujemy dostateczną ilością pamięci do przechowywania hesjanu, albo jego aproksymacji, bądź też z jakiś względów nie chcemy wykonywać w każdej iteracji szeregu operacji macierzowych. Metody kwadratowe mogą być użyte do minimalizacji dowolnych f-cji dwukrotnie różniczkowalnych.

Definicja kierunków sprzężonych.

Do punktu minimum zbliżamy się ciągiem kroków wykonywanych w kierunkach poszukiwań odpowiednio między sobą uzależnionymi, zwanych kierunkami sprzężonymi. Kierunki poszukiwań są tworzone tak, aby każdy następny był „sprzężony” ze wszystkimi poprzednimi stosowanymi kierunkami. Przez odpowiednie sprzężenie kierunków poszukiwań uwzględniamy jakby globalne zachowanie się f-cji.

Mówimy, że układ N liniowo niezależnych wektorów :

ξ(0), ξ(1), ... , ξ(N-1)

jest układem wektorów sprzężonych względem symetrycznej, dodatnio określonej macierzy A stopnia N , jeśli :

ξ^T(n)A ξ^T(n') = 0, n ≠n'

przy czym:

n, n' ∈ <0,1,...,N-1>

N - liczba zmiennych f-cji f(x).

Kierunki określone przez układ wektorów sprzężonych nazywamy więc kierunkami sprzężonymi.

Przez sprzężenie kierunków poszukiwań zmniejszamy liczbę wykonywanych kroków, lecz odbywa się to kosztem zwiększonego nakładu obliczeń przypadających na każdy wykonywany krok. Wspólną cechą algorytmów opartych o tą metodę (jednym z nich jest algorytm Fletchera - Reevsa) jest sposób realizacji kolejnej iteracji :

1. wyznaczenie kierunku poszukiwań

2. określenie minimum w tym kierunku

Różnią się natomiast głównie sposobem tworzenia kierunków sprzężonych.

Algorytm gradientu sprzężonego (Fletchera - Reevsa).

Metody gradientowe korzystają z informacji o pochodnych funkcji. W algorytmie gradientu sprzężonego kierunki poszukiwań są sprzężone, a do ich wyznaczenia korzystamy z wektorów gradientu.

Rys. Ilustracja działania metody gradientu sprzężonego dla problemu dwuwymiarowego.

Uwaga.

W poniższej notyfikacji stosuje się indeks górny (odnoszący daną zmienną do kolejnego kroku algorytmu), a nie wykładnik potęgi.

Najpierw wybieramy dowolny punkt początkowy x⁰ i znajdujemy punkt x¹ tj. punkt, w którym f-cja f(x) osiąga minimum w kierunku ξ⁰. Następnie wyznaczmy nowy kierunek sprzężony ξ₁ i znajdujemy punkt x² - minimum f-cji f(x) w kierunku ξ¹ itd.

Algorytm :

1. Oblicz w punkcie startowym x⁰ wartość f-cji celu Q(x⁰) i gradient :

grad Q(x⁰)= g⁰

2. Podstaw i=1 i wyznacz początkowy kierunek poszukiwań :

ξ^i-1 = -g⁰

3. Dla i=1,..N wzdłuż kierunku ξ_i-1 dokonaj minimalizacji f-cji Q(x^i-1 + λ_i^*ξ^i-1). Znajdź λ_i^*_. Oblicz współrzędne nowego punktu :

xⁱ=x^i-1 + λ_i^*ξ^i-1

λ - przesunięcie

4. Oblicz w x_i wartość f-cji Q (xⁱ) oraz grad Q (xⁱ)= gⁱ.

5. Zbadaj czy spełnione jest kryterium zbieżności (np. czy gⁱ_*gⁱ<ε). Jeśli tak, to koniec obliczeń. Jeśli nie, to wyznacz współczynnik :

βⁱ= gⁱ_*gⁱ / g^i-1_*g^i-1

oraz nowy kierunek sprzężony :

ξⁱ=-gⁱ + βⁱξ^i-1

6. Powtórz czynności od punktu 3. (Podstaw xⁱ w miejscu x^i-1 oraz ξⁱ w miejsce ξ^{i -1} )

Uwaga.

Jeśli po N iteracjach nie osiągnięto ekstremum (tzn. nie jest spełnione kryterium zbieżności), to wraca się do pkt. 1 algorytmu podstawiając x_N→x⁰ i ξ⁰ → - grad Q(x⁰).

Jeśli f(x) jest f-cją kwadratową N-zmiennych, to punkt jej minimum wyznaczamy wykonując nie więcej niż N kroków. Jeżeli f-cja f(x) nie jest kwadratowa i po wykonaniu N kroków nie znaleźlibyśmy jeszcze punktu jej minimum, to ostatni wyznaczony punkt przyjmujemy za nowy punkt startowy i powtarzamy postępowanie od początku. Za warunek zakończenia szukania (kryterium zbieżności) przyjmuje się, aby norma gradientu była mniejsza niż ustalona z góry dostatecznie mała liczba ε, lub warunek ||ξⁱ|| ≤ ε.

Rodzaje algorytmów gradientu sprzężonego :

• Fletchera-Reevesa

• Polaka- Ribiery

• Wzór sprzężonego kierunku spadku zapewniający, że następny kierunek jest kierunkiem spadku

Utworzony przez : Damian Janyga, Adrian Cichoń, Daria Stęchły

---