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.

---