Metoda złotego podziału

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Idea algorytmu[edytuj | edytuj kod]

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ł[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  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[edytuj | edytuj kod]