Metody gradientowe optymalizacji statycznej

 

Metody gradientowe polegają na wyznaczaniu kolejnego kierunku poszukiwań na podstawie znajomości

gradientu funkcji celu, w punkcie osiągniętym w poprzednim kroku. Funkcja celu musi być więc znaną

w postaci analitycznej i ograniczoną od dołu funkcją wypukłą klasy C2 taką, by można ją było przybliżyć

formą kwadratową postaci

f(x) = a+cTx + ½( xTAx)                                             (1)

 

w której macierz A jest symetryczna dodatnio określona,

o elementach równych drugim pochodnym cząstkowym funkcji f(x).

 

Metoda gradientu prostego jest podstawową, choć nie najbardziej efektywną metodą

poszukiwania ekstremum. Jej algorytm przy poszukiwaniu minimum funkcji f(x) jest następujący:  

 

1. Przyjąć punkt startowy x0, długość kroku e, współczynnik redukcji kroku a< 1,

            dokładność wyznaczenia ekstremum (zerowania się gradientu) ε. Przyjąć i=0.

2.      Obliczyć w punkcie xi wartość funkcji celu f(xi) i jej gradientu g(xi).

3.      Wyznaczyć kierunek poszukiwań przeciwny do kierunku gradientu d=-g(xi). 

4.      Wykonać z punktu xi krok w wyznaczonym kierunku d o długości e przechodząc

            do punktu    xi+1= xi + ed     czyli do punktu   [xi - eg (xi)].

5.      Obliczyć wartość funkcji celu i jej gradientu w nowym punkcie.  

6.      Jeśli gTg< ε, zakończyć postępowanie. W przeciwnym razie przejść do punktu 6.

7.      Jeśli  f(xi+1)< f(xi), powtórzyć postępowanie dla wyznaczonego punktu xi+1,

            czyli przyjąć i=i+1, przejść do punktu 2.

8.      W przypadku przeciwnym cofnąć się do poprzedniego punktu i zmniejszyć krok,

            czyli przyjąć e=ae  i przejść do punktu 4. 

 

 

Metoda najszybszego spadku (NS) jest modyfikacją metody gradientu prostego.

Modyfikacja polega na tym, że w metodzie NS po wyznaczeniu kierunku poszukiwań wyznaczane jest

minimum funkcji w tym kierunku, a nie przesunięcie ze stałym krokiem.

Algorytm metody NS przy poszukiwaniu minimum funkcji f(x) jest następujący:

 

2.      Przyjąć punkt startowy x0, dokładność wyznaczenia ekstremum

            (zerowania się gradientu) ε.      Przyjąć i=0.

3.      Obliczyć w punkcie xi wartość funkcji celu f(xi) i jej gradientu g(xi).

4.      Wyznaczyć kierunek poszukiwań przeciwny do kierunku gradientu d=-g(xi).

5.      Wykonać z punktu xi w wyznaczonym kierunku d krok e o takiej wartości, by osiągnąć

            minimum w tym kierunku, przechodząc do punktu xi+1= xi + ed.

6.      Obliczyć wartość funkcji celu i jej gradientu w nowym punkcie. Przyjąć i=i+1.

7.      Jeśli gTg> ε, przejść do punktu 2. W przeciwnym razie zakończyć postępowanie.

 

 

 

 

Metoda gradientu sprzężonego (GS) jest modyfikacją metody najszybszego spadku.

Modyfikacja polega na tym, że w metodzie GS kolejne kierunki poszukiwań są sprzężone

do poprzednich względem macierzy A. Z każdego punktu jest wyznaczane minimum funkcji w kierunku.

 

Algorytm metody GS przy poszukiwaniu minimum funkcji f(x) jest następujący:  

1. Przyjąć punkt startowy x0, dokładność wyznaczenia ekstremum

            (zerowania się gradientu)  ε.     Przyjąć i=0.

2.  Obliczyć w punkcie xi wartość funkcji celu f(xi) i jej gradientu g(xi).

3.      Wyznaczyć kierunek poszukiwań z1 przeciwny do kierunku gradientu

                        z1=-g(xi),         czyli z1=-Ax0 - c.

4.      W wyniku minimalizacji f(x) w tym kierunku z równania:  z1T [A(x0 +ez1)+c]=0

            otrzymuje się wartość kroku e, a następnie punkt  x1= x0 + ez1. 

5.      Obliczyć wartość funkcji celu i jej gradientu w nowym punkcie. Przyjąć i=i+1.     

6.      Wyznaczyć nowy kierunek poszukiwań sprzężony do poprzednich, czyli

            zi+1=-g(xi) + β zi,  

      gdzie 

                       

     

7.      Wykonać z punktu xi w wyznaczonym kierunku zi+1  krok e o takiej wartości, by osiągnąć

            minimum w tym kierunku,  przechodząc do punktu xi+1= xi + e zi+1.    

8.      Jeśli gTg> ε, przejść do punktu 4. W przeciwnym razie zakończyć postępowanie.

 

Inne metody gradientowe - Davidona, Pearsona i Newtona-Raphsona  wraz z ich modyfikacjami działają również

na zasadzie tworzenia kierunków sprzężonych. Jedynie sposób tworzenia tych kierunków jest nieco odmienny.

Kierunki poszukiwań są określane z zależności 

zi+1=-Hig(xi)

przy czym w każdej z wymienionych metod macierz Hi jest określana inaczej.