Metoda złotego podziału

Metoda złotego podziałunumeryczna metoda optymalizacji jednowymiarowej funkcji celu.

Algorytm ten może być używany przy minimalizacji kierunkowej razem z innymi metodami optymalizacji funkcji wielowymiarowych, takich jak metody gradientowe (np. metoda gradientu prostego, metoda Newtona) lub bezgradientowe (np. metoda Gaussa-Seidela, metoda Powella).

Innymi metodami optymalizacji jednowymiarowej są metoda dychotomii, metoda punktu środkowego, metoda Newtona.

Zadanie optymalizacji jednowymiarowejEdytuj

Niech dana będzie funkcja celu  

 

oraz przedział   w którym   jest unimodalna (jest ciągła i posiada co najwyżej jedno ekstremum lokalne). Zadaniem optymalizacji jednowymiarowej funkcji   jest znalezienie jej minimum w przedziale  

Warto podkreślić fakt, iż algorytmy minimalizacji jednowymiarowej działają poprawnie jedynie dla przedziałów w których funkcja jest unimodalna. Jeżeli zadana funkcja nie posiada tej własności, należy znaleźć jej przedziały unimodalności i zastosować opisywaną metodę do każdego z nich.

AlgorytmEdytuj

Idea algorytmuEdytuj

 
Metoda złotego podziału. Badane są wartości funkcji w punktach   i   Zgodnie z rysunkiem   z czego wynika, iż minimum musi znajdować się w przedziale  

Funkcja ciągła   w przedziale   posiada dokładnie jedno minimum x*. Minimum to można znaleźć poprzez kolejne podziały zadanego przedziału. W tym celu należy obliczyć wartości funkcji w dwóch punktach   i   takich, że   a następnie zbadać ich wielkości:

  • Jeżeli   to szukane minimum znajduje się w przedziale  
  • Jeżeli   to szukane minimum znajduje się w przedziale  

W ten sposób można dowolnie zawężać przedział w którym znajduje się minimum, aż do momentu gdy spełniony zostanie warunek:

 

dla ustalonej dokładności obliczeń  

Wielkość otrzymanego w wyniku powyższego postępowania przedziału po   krokach wynosi:   gdzie   jest stałym współczynnikiem o który zmniejszana jest wielkość przedziałów w kolejnych krokach algorytmu.

Złoty podziałEdytuj

W metodzie złotego podziału wartość współczynnika   jest dobrana w taki sposób, aby przy kolejnych iteracjach wykorzystywać obliczoną w poprzednim kroku wartość funkcji jednej z dwóch próbek (  lub  ). Aby osiągnąć powyższą własność, wartość współczynnika   musi być równa wartości złotego podziału:

 

skąd wzięła się nazwa metody.

Strategię obliczania minimum funkcji można zapisać:

  1.  
  2. Jeśli:
    •  
    •  
  3. Jeśli   to STOP, w przeciwnym wypadku powtórz punkt 2.

PseudokodEdytuj

Algorytm można również zapisać przy pomocy poniższego kodu w języku C:

float GoldenRatioMethod( float a, float b )
{
        // współczynnik złotego podziału
        float k = ( sqrt( 5 ) - 1 ) / 2;

        // lewa i prawa próbka
        float xL = b - k * ( b - a );
        float xR = a + k * ( b - a );

        // pętla póki nie zostanie spełniony warunek stopu
        while ( ( b - a ) > EPSILON )
        {
                // porównaj wartości funkcji celu lewej i prawej próbki
                if ( f( xL ) < f( xR ) )
                {
                        // wybierz przedział [a, xR]
                        b = xR;
                        xR = xL;
                        xL = b - k * ( b - a );
                }
                else
                {
                        // wybierz przedział [xL, b]
                        a = xL;
                        xL = xR;
                        xR = a + k * ( b - a );
                }
        }

        // zwróć wartość środkową przedziału
        return ( a + b ) / 2;
}

Zbieżność metodyEdytuj

Kolejne obliczane przedziały w metodzie złotego podziału są wielkości:

 

z czego wynika iż zbieżność metody jest liniowa (rząd zbieżności wynosi   zaś współczynnik zbieżności  ). Ilość iteracji   potrzebna do zawężenia przedziału początkowego   do zadanej dokładności   wynosi:

 

Zobacz teżEdytuj

BibliografiaEdytuj

  • Fortuna Z., Macukow B., Wąsowski J.: Metody Numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.
  • Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999.

Linki zewnętrzneEdytuj