Metoda Powella
Dana jest funkcja 4 zmiennych, dla której mamy przeprowadzić minimalizację z wykorzystaniem metody Powella.
Plik fn.m - implementacja funkcji w Matlabie:
function y = fn(x)
y=1542+20*x(1)*x(4)+8*x(3)^2+96*x(2)*x(3)+96*x(1)*x(3)+298*x(2)^2+616*x(1)*x(2)+333*x(1)^2+40*x(4)+16*x(3)+286*x(2)+5*x(4)^2+10*x(2)*x(4)+556*x(1);
%dana funkcja zmiennych x1,x2,x3,x4
Plik powell.m - algorytm metody Powella:
function wynik = powell(x,eps)
p = 1;
i=0;
baza=[1,0,0,0;
0,1,0,0;
0,0,1,0;
0,0,0,1];
%pętla działająca do momentu spełnienia kryterium stopu
while( p > eps)
%wywołanie metody złotego podziału dla każdej współrzędnej
x0=x;
x=x+baza(:,1)*zlotyp(x,baza(:,1),eps);
x=x+baza(:,2)*zlotyp(x,baza(:,2),eps);
x=x+baza(:,3)*zlotyp(x,baza(:,3),eps);
x=x+baza(:,4)*zlotyp(x,baza(:,4),eps);
%wyznaczenie nowego kierunku poszukiwań
baza(:,5) = x0 - x;
%wywołanie metody złotego podziału dla wyznaczonego kierunku
x = x + baza(:,5)*zlotyp(x,baza(:,5),eps);
%kryterium stopu
p = sqrt( (x0(1)-x(1))^2 + (x0(2)-x(2))^2 + (x0(3)-x(3))^2 +(x0(4)-x(4))^2 );
%aktualizacja bazy kierunków
baza(:,1) = baza(:,2);
baza(:,2) = baza(:,3);
baza(:,3) = baza(:,4);
baza(:,4) = baza(:,5);
%licznik iteracji
i=i+1;
end
%wyświetlenie wyniku
pkt=x'
wynik = fn( x );
i
Plik zlotyp.m - algorytm metody złotego podziału:
function min = zlotyp(x,baza,eps)
%ustalenie punktów granicznych
zakres = 200 ;
a = -zakres;
b = zakres;
k = (sqrt(5)-1)/2;
j=1;
while j==1
while( (b-a) > eps )
%wybór 2 punktów wewnątrz przedziału poszukiwań
xp = b-((b-a)*k);
xk = a+((b-a)*k);
if fn(x+xp*baza) > fn(x+xk*baza)
a=xp;
xp = b-((b-a)*k);
xk = a+((b-a)*k);
else
b=xk;
xk = a+((b-a)*k);
xp = b-((b-a)*k);
end
end
%zwracana współrzędna punktu optymalnego
min = (xp+xk)/2;
%sprawdzenie czy zwrócony punkt nie jest punktem granicznym przedziału
%i ewentualne przesunięcie przedziału
if((a+eps)>min && (a-eps)<min)
a = a-zakres+eps;
b = a+eps;
j = 0;
end
if((b-eps)<min && (b+eps)>min)
a = b-eps;
b = b+zakres-eps;
j = 0;
end
end
Sprawdziliśmy poprawność działania napisanych algorytmów poprzez znalezienie minimum funkcją fminsearch:
f=@(x)1542+20*x(1)*x(4)+8*x(3)^2+96*x(2)*x(3)+96*x(1)*x(3)+298*x(2)^2+616*x(1)*x(2)+333*x(1)^2+40*x(4)+16*x(3)+286*x(2)+5*x(4)^2+10*x(2)*x(4)+556*x(1);
[min, fval] = fminsearch (f, [-1, 1,1,1]);
min
fval
Otrzymany wynik jest zbliżony do wyników zwracanych przez metodę Powella:
min =
-8.0000 1.0000 41.0000 11.0000
fval =
9.0000
W dalszej części sprawozdania wykorzystamy te same dane startowe, których używaliśmy dla metody Gaussa - Seidla w celu porównania działania obydwu metod.
Przykładowy przebieg procesu znajdowania minimum funkcji metodą Powella dla punktu początkowego (-7.5 , 0.5 , 39.5 , 10.5) oraz epsilon równego 0.01:
nr iteracji |
punkt osiągnięty |
wartość funkcji |
kryterium stopu (T/N) |
1 |
-7.3332, 0.5294, 39.6210, 10.1357 |
15.2734 |
0.4196 - Nie |
2 |
-7.9436, 0.8511, 41.5488, 11.0978 |
9.0418 |
2.2624 - Nie |
3 |
-7.9445, 0.8517, 41.5577, 1.0372 |
9.0224 |
0.0612 - Nie |
4 |
-7.9444, 0.8518, 41.5579, 1.0373 |
9.0224 |
2.0844e-004 - Tak |
W poniższej tabeli zamieściliśmy rezultaty kilku wywołań metody Powella dla różnych punktów przy stałej wartości epsilon.
liczba iteracji |
punkt startowy |
punkt osiągnięty |
wartość minimum |
epsilon |
8 |
0; 0; 0; 0 |
-8.0001, 1.0000, 41.0002, 10.9997 |
9.0000 |
0.001 |
7 |
1; 1; 1; 1 |
-8.0000, 0.9999, 41.0005, 11.0000 |
9.0000 |
0.001 |
7 |
1; 2; 3; 4 |
-8.0000, 1.0001, 40.9997, 11.0000 |
9.0000 |
0.001 |
5 |
4; 8; 15; 16 |
-10.8253, 6.6524, 24.3410, 10.9982 |
49.6496 |
0.001 |
10 |
0; 8; 0; 19 |
-8.0000, 1.0001, 40.9997, 10.9998 |
9.0000 |
0.001 |
10 |
10; 20; 30; 40 |
-8.0000, 1.0000, 41.0000, 11.0000 |
9.0000 |
0.001 |
7 |
88; 27; -13; 105 |
-9.4885, 5.1450, 24.1135, 13.0921 |
87.2224 |
0.001 |
10 |
-100; -2000; 3; 4 |
-7.8319, 0.9439, 41.4517, 11.4375 |
22.2019 |
0.001 |
Dobór punktu startowego ma nieznaczny wpływ na ilość iteracji, gdyż metoda ogólnie jest szybka. W większości przypadków funkcja zwróciła oczekiwany wynik. Dla kilku punktów znalezione minimum znacząco odbiega od pozostałych. Sprawdziliśmy, że zmniejszenie wartości epsilon pozwoliło uzyskać prawidłowy wynik przy nieznacznym wzroście liczby iteracji.
W poniższej tabelce zamieściliśmy rezultaty kilku wywołań metody Powella dla stałego punktu startowego przy różnych wartościach epsilon.
liczba iteracji |
punkt startowy |
punkt osiągnięty |
wartość minimum |
epsilon |
4 |
0,0,0,0 |
-9.5725, 5.2395, 25.0033, 9.9010 |
27.3536 |
0.1 |
6 |
0,0,0,0 |
-9.4523, 4.8905, 26.4346, 9.9684 |
24.4486 |
0.01 |
8 |
0,0,0,0 |
-8.0001, 1.0000, 41.0002, 10.9997 |
9.0000 |
0.001 |
7 |
0,0,0,0 |
-8.0000, 1.0000, 40.9999, 11.0000 |
9.0000 |
0.002 |
15 |
0,0,0,0 |
-8.0007, 1.0048, 40.9763, 10.9999 |
9.0001 |
0.007 |
11 |
0,0,0,0 |
-8.0000, 1.0000, 41.0001, 11.0000 |
9.0000 |
0.0001 |
7 |
0,0,0,0 |
-8.0000, 1.0000, 40.9999, 11.0000 |
9.0000 |
0.0004 |
14 |
0,0,0,0 |
-8.0000, 1.0001, 40.9997, 11.0000 |
9.0000 |
0.0009 |
Z analizy wyników tego doświadczenia możemy wyciągnąć wniosek, że im mniejsza wartość epsilon, tym dokładniejszy wynik uzyskujemy, ale możliwy jest wzrost ilości iteracji. Przyjęcie zbyt dużej wartości epsilon powoduje, że znalezione minimum nie jest globalnym minimum funkcji, którego poszukiwaliśmy.
Wnioski ogólne
Metoda Powella jest skuteczna. Sprawność i szybkość jej działania zależą od wyboru punktu startowego oraz dokładności epsilon. Odpowiednie dobranie epsilon ma szczególne znaczenie, gdyż dla zbyt dużych wartości funkcja zatrzymywała się w punkcie, który nie był minimum globalnym.
Dla zadanej funkcji minimum znajduje się w punkcie (-8,1,41,11), a jego wartość wynosi 9.
Wcześniej implementowaliśmy metodę Gaussa - Seidla. Po porównaniu wyników uzyskanych dla tych samych punktów i dokładności, stwierdzamy, że metoda Powella jest o wiele szybsza. Często nawet stukrotnie. Uzyskane wyniki również w większości przypadków są bardziej dokładne.