Metoda złotego podziału

Metoda złotego podziału – 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 ${\displaystyle f{:}}$

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

oraz przedział ${\displaystyle [a,b]\subset D}$ w którym ${\displaystyle f}$ jest unimodalna (jest ciągła i posiada co najwyżej jedno ekstremum lokalne). Zadaniem optymalizacji jednowymiarowej funkcji ${\displaystyle f}$ jest znalezienie jej minimum w przedziale ${\displaystyle [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

Funkcja ciągła ${\displaystyle f}$ w przedziale ${\displaystyle [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 ${\displaystyle x_{L}}$ i ${\displaystyle x_{R}}$ takich, że ${\displaystyle a<x_{L}<x_{R}<b,}$ a następnie zbadać ich wielkości:

• Jeżeli ${\displaystyle f(x_{L})>f(x_{R}),}$ to szukane minimum znajduje się w przedziale ${\displaystyle [x_{L},b].}$
• Jeżeli ${\displaystyle f(x_{L})<f(x_{R}),}$ to szukane minimum znajduje się w przedziale ${\displaystyle [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:

${\displaystyle (b-a)\leqslant \epsilon }$

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

Wielkość otrzymanego w wyniku powyższego postępowania przedziału po ${\displaystyle n}$ krokach wynosi: ${\displaystyle (b^{(n)}-a^{(n)})k^{n}}$ gdzie ${\displaystyle 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 ${\displaystyle k}$ jest dobrana w taki sposób, aby przy kolejnych iteracjach wykorzystywać obliczoną w poprzednim kroku wartość funkcji jednej z dwóch próbek (${\displaystyle f(x_{L})}$ lub ${\displaystyle f(x_{R})}$). Aby osiągnąć powyższą własność, wartość współczynnika ${\displaystyle k}$ musi być równa wartości złotego podziału:

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

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

Strategię obliczania minimum funkcji można zapisać:

1. ${\displaystyle \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:
   • ${\displaystyle 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.}$
   • ${\displaystyle 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 ${\displaystyle (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:

${\displaystyle (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 ${\displaystyle 1,}$ zaś współczynnik zbieżności ${\displaystyle k\approx 0,61803398<1}$). Ilość iteracji ${\displaystyle N}$ potrzebna do zawężenia przedziału początkowego ${\displaystyle [a,b]}$ do zadanej dokładności ${\displaystyle \epsilon }$ wynosi:

${\displaystyle N=\left\lceil \log _{k}{\frac {\epsilon }{b-a}}\right\rceil }$

Zobacz też

• programowanie matematyczne
• funkcja unimodalna
• metoda Newtona (optymalizacja)
• metoda Brenta (optymalizacja)

Bibliografia

• 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ętrzne

• https://web.archive.org/web/20080530094827/http://www.kmg.ps.pl/opt/wyklad/bezgrad/podzial.html
• http://optymalizacja.w8.pl/Jednowymiarowa.html