Metoda złotego podziału

Metoda złotego podziału – to pojęcie z zakresu optymalizacji matematycznej. Jest to numeryczna 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 jednowymiarowej

Niech dana będzie funkcja celu $f$:

$\mathbb{R} \supset D \ni x \mapsto f(x) \in \mathbb{R}$

oraz przedział $[a, b] \subset D$ w którym $f$ jest unimodalna (jest ciągła i posiada co najwyżej jedno ekstremum lokalne). Zadaniem optymalizacji jednowymiarowej funkcji $f$ jest znalezienie jej minimum w przedziale $[a, b]$.

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.

Algorytm

Idea algorytmu

Metoda złotego podziału. Badane są wartości funkcji w punktach $x_L$ i $x_R$. Zgodnie z rysunkiem $f(x_L)>f(x_R)$ z czego wynika, iż minimum musi znajdować się w przedziale $[x_L, b]$

Funkcja ciągła $f$ w przedziale $[a, b]$ 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 $x_L$ i $x_R$ takich, że $a < x_L < x_R < b$, a następnie zbadać ich wielkości:

• Jeżeli $f(x_L) > f(x_R)$, to szukane minimum znajduje się w przedziale $[x_L, b]$.
• Jeżeli $f(x_L) < f(x_R)$, to szukane minimum znajduje się w przedziale $[a, x_R]$.

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

$(b - a) \leqslant \epsilon$

dla ustalonej dokładności obliczeń $\epsilon$.

Wielkość otrzymanego w wyniku powyższego postępowania przedziału po $n$ krokach wynosi: $(b^{(n)} - a^{(n)}) k^{n}$ gdzie $k$ jest stałym współczynnikiem o który zmniejszana jest wielkość przedziałów w kolejnych krokach algorytmu.

Złoty podział

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

$k = \frac{\sqrt{5} - 1}{2} \approx 0,61803398$

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

Strategię obliczania minimum funkcji można zapisać:

1. $\left\{\begin{array}{l} x_L^{(0)} := b^{(0)} - (b^{(0)}-a^{(0)})k \\ x_R^{(0)} := a^{(0)} + (b^{(0)}-a^{(0)})k \end{array}\right.$
2. Jeśli:
   • $f(x_L^{(i)}) > f(x_R^{(i)}) \Rightarrow \left\{\begin{array}{l} a^{(i+1)} := x_L^{(i)} \\ b^{(i+1)} := b^{(i)} \\ x_L^{(i+1)} := x_R^{(i)} \\ x_R^{(i+1)} := a^{(i+1)} + (b^{(i+1)}-a^{(i+1)})k \end{array}\right.$
   • $f(x_L^{(i)}) < f(x_R^{(i)}) \Rightarrow \left\{\begin{array}{l} a^{(i+1)} := a^{(i)} \\ b^{(i+1)} := x_R^{(i)} \\ x_L^{(i+1)} := b^{(i+1)} - (b^{(i+1)}-a^{(i+1)})k \\ x_R^{(i+1)} := x_L^{(i)} \end{array}\right.$
3. Jeśli $(b^{(i+1)}-a^{(i+1)}) \leqslant \epsilon$ to STOP, w przeciwnym wypadku powtórz punkt 2.

Pseudokod

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ść metody

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

$(b^{(i+1)} - a^{(i+1)})= k(b^{(i)} - a^{(i)})$

z czego wynika iż zbieżność metody jest liniowa (rząd zbieżności wynosi $1$, zaś współczynnik zbieżności $k \approx 0,61803398 < 1$). Ilość iteracji $N$ potrzebna do zawężenia przedziału początkowego $[a, b]$ do zadanej dokładności $\epsilon$ wynosi:

$N = \left \lceil \log_k{\frac{\epsilon}{b-a}} \right \rceil$

Zobacz też

• Programowanie matematyczne
• Funkcja unimodalna
• Metoda dychotomii
• Metoda punktu środkowego
• Metoda Newtona (optymalizacja)

Bibliografia

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

Linki zewnętrzne

• http://kmg.ps.pl/opt/wyklad/bezgrad/podzial.html
• http://optymalizacja.w8.pl/Jednowymiarowa.html