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
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.
Algorytm Idea algorytmu frame|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ł 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ć:
Jeśli:
Jeśli 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:
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ż 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
Kategoria:Metody numeryczne Kategoria:Metody optymalizacji Kategoria:Algorytmy wyszukiwania Kategoria:Złoty podział