1

MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH

METODY SPRZĘŻONYCH KIERUNKÓW POPRAWY

Wprowadzenie

Celem dwiczenia jest zapoznanie się z niektórymi metodami minimalizacji funkcji wielu

zmiennych bez ograniczeo. Metody te można podzielid na następujące klasy:

-

metody poszukiwao prostych;

-

metody kierunków poprawy, wśród których możemy wyróżnid następujące grupy:
1. metody bezgradientowe, w przypadku których do znalezienia minimum potrzebne

jest wyznaczenie jedynie wartości wskaźnika jakości

 

f x

;

2. metody gradientowe, dla w których procesie poszukiwao minimum korzystamy z

wyznaczanych wartości minimalizowanego wskaźnika jakości

 

f x

oraz jego

gradientu

 

x

f



x

;

3. metody newtonowskie, gdzie poszukiwanie minimum przeprowadzamy z

wyznaczeniem w kolejnych punktach wartości wskaźnika jakości, jego gradientu

oraz hesjanu

 

T

x

x

f

 









x

.

Dokładnie zostaną omówione dwie metody wykorzystujące w procesie minimalizacji kierunki
sprzężone.

Dla wszystkich typów metod należących do klasy metod kierunków poprawy

wykorzystujemy wspólny schemat prowadzenia obliczeo iteracyjnych. Polega on na tym, że do
punktu odpowiadającego minimum wskaźnika jakości,

 

f x

, dochodzimy w kolejnych krokach

poszukiwania minimum wzdłuż odpowiednio wyznaczonych kierunków

d

w przestrzeni

n

-wymiarowej, zwanych kierunkami poszukiwao.

Jeżeli po

1

k



krokach optymalizacji osiągnięto punkt poszukiwao

1

ˆ

k



x

to w kolejnym

k

-tym kroku

przeprowadza się minimalizację wzdłuż prostej wyznaczonej przez punkt

1

ˆ

k



x

i wektor kierunku

k

d

, tj. znajdujemy taką optymalna wartośd ˆ

k



, że





1

ˆ

ˆ

: min

k

k

k

k

k

f











x

d

,

a więc rozwiązujemy zagadnienie minimalizacji funkcji jednej zmiennej - tą zmienną jest

k



.

Kierunki te mogą byd stałe w trakcie całego iteracyjnego procesu poszukiwao minimum bądź też
mogą ulegad zmianie na kolejnych etapach w zależności od wartości minimalizowanej funkcji, jej
gradientu lub również hesjanu.

W algorytmie poszukiwao można wyróżnid następujące, wspólne dla wszystkich metod,

fazy:

-

wybór punktu początkowego poszukiwao

0

x

;

-

wyznaczenie kolejnego punktu ˆ

k

x

, stanowiącego przybliżenie punktu ˆx odpowiadającego

minimum wskaźnika jakości; punkt ten wyznaczamy przez poszukiwania wzdłuż kierunku

k

d

, którego określenie, jak i również odległośd przesunięcia w tym kierunku są zależne od

2

wybranej metody optymalizacji; kolejny punkt, będący nowym (lepszym) przybliżeniem
punktu minimalizującego funkcję

 

f x

, jest wyznaczany z zależności

1

ˆ

ˆ

ˆ

;

k

k

k

k









x

x

d

-

sprawdzenie warunków zbieżności (kryterium osiągnięcia punktu minimalnego wskaźnika
jakości) i – w zależności od wyniku – kontynuowanie poszukiwao iteracyjnych albo ich
zakooczenie.

Punkt początkowy poszukiwao wybieramy na podstawie posiadanych informacji dotyczących

położenia punktu minimalnego wskaźnika jakości. Należy podkreślid, że w przypadku zadania
minimalizacji nieliniowego wskaźnika jakości wielu zmiennych dobór punktu początkowego
poszukiwao może w znaczący sposób przyspieszyd lub opóźnid znalezienie minimum wskaźnika
jakości albo wręcz zdecydowad o możliwości znalezienia minimum globalnego wskaźnika jakości.


Metoda Powella (metoda bezgradientowa)

Metoda Powella należy do bezgradientowych metod poprawy, w których minimum, funkcji

celu,

 

f x

, znajdujemy poprzez przeszukiwanie przestrzeni

n



w odpowiednio dobranych

kierunkach stanowiących bazę tej przestrzeni. W metodzie Powella poszukiwao dokonujemy w
kolejnych iteracjach, z których każda polega na kolejno wykonanych minimalizacjach wzdłuż n
kierunków, gdzie n jest liczbą zmiennych decyzyjnych.
Na zakooczenie każdej iteracji dokonujemy minimalizacji wzdłuż nowo wyznaczonego (

1

n



)-go

kierunku poszukiwao

1

k



d

. Kierunki poszukiwao nie są w metodzie Powella stałe: w pierwszej

iteracji jako kierunki poszukiwao wykorzystujemy zwykle kierunki osi współrzędnych (wersory),
a w koocowej fazie każdej iteracji dodawany jest do zbioru kierunków poszukiwao nowo
wyznaczony kierunek

1

k



d

, a usuwany jest zeo

1

d

.

Na wstępie wyznaczamy kierunki w przestrzeni

n



n liniowo niezależnych wektorów

1

,...,

n

d

d

, będących początkowymi kierunkami poszukiwao i stanowiących tzw. bazę podstawową.

Kierunki początkowe mogą byd wybrane dowolnie (przy spełnieniu liniowej niezależności), zwykle
dla uproszczenia przyjmujemy jako początkowe kierunki poszukiwao kierunki osi układu
współrzędnych. W koocowej fazie etapu wstępnego dokonujemy minimalizacji wzdłuż ostatniego
z początkowych kierunków poszukiwao, startując z punktu początkowego,

0

x

, i osiągając punkt

startowy dla pierwszej iteracji metody Powella,

1,0

x

.

Minimalizacja funkcji celu za pomącą metody Powella przebiega w kolejnych iteracjach.

W każdej iteracji realizowane są 4 etapy (oznaczenia dotyczą i -tej iteracji):

1. Startując z początkowego punktu poszukiwao dla iteracji i -tej,

,0

i

x

, dokonujemy n

kolejnych minimalizacji wzdłuż kierunków poszukiwao dla i -tej iteracji:

,1

,

,...,

i

i n

d

d

. Jako

wynik tych minimalizacji otrzymujemy punkty

,1

,2

,

ˆ

ˆ

ˆ

,

,...,

i

i

i n

x

x

x

.

Kolejny punkt, będący nowym przybliżeniem punktu minimalizującego funkcję

 

f x

, jest

wyznaczany z zależności

,

,

1

,

,

ˆ

ˆ

ˆ

.

i k

i k

i k

i k









x

x

d

2. Wyznaczamy nowy kierunek poszukiwao zgodnie z zależnością

3

,

1

,

,0

ˆ

ˆ

i n

i n

i







d

x

x

a następnie dokonujemy wzdłuż nowo wyznaczonego kierunku,

,

1

i n



d

, minimalizacji funkcji

celu – osiągając punkt

,

1

ˆ

i n



x

.

3. Sprawdzamy warunek zakooczenia obliczeo (kryterium stopu):

,

1

,0

ˆ

ˆ

i n

i









x

x

(możliwe jest również wykorzystanie innych kryteriów stopu lub ich kombinacji:



  

,

1

,0

ˆ

ˆ

i n

i

f

f









x

x

lub



  

,

1

,0

,

1

,0

ˆ

ˆ

ˆ

ˆ

i n

i

i n

i

f

f













x

x

x

x

lub

max

i

It



)

gdzie



jest pewną, zadaną z góry dokładnością przeprowadzania minimalizacji. Jeśli

kryterium stopu jest spełnione, następuje zakooczenie procesu minimalizacji i przyjęcie
punktu

,

1

ˆ

i n



x

za punkt optymalny, ˆx .

4. Jeśli warunek zakooczenia obliczeo nie jest spełniony dokonujemy przedefiniowania

(zmiany) kierunków poszukiwao dla kolejnej (

1

i



)-szej iteracji według następującego

algorytmu:

1,1

,2

1,2

,3

1,

,

1

.

i

i

i

i

i

n

i n















d

d

d

d

d

d

Nowy kierunek wyznaczamy ostatnim kierunkiem poszukiwao w kolejnej iteracji, a ze
zbioru kierunków poszukiwao usuwamy kierunek będący na pierwszej pozycji w iteracji

i

-tej.

Teoria metody Powella dotyczy funkcji kwadratowych. Metodę tę można jednak stosowad

do innych funkcji celu. Oczywiście trudno się wtedy spodziewad osiągnięcia minimum w n
iteracjach dla funkcji celu n zmiennych. Proces obliczeniowy trwa w tym przypadku tym dłużej, im
mniej dokładnie można funkcje celu aproksymowad za pomocą funkcji kwadratowej.


Metoda gradientu sprzężonego (metoda gradientowa)

Metoda gradientu sprzężonego należy do mieszanych metod kierunków poprawy,

stanowiących połączenie metod poszukiwania minimum funkcji celu

 

f x

w kierunku przeciwnym

do kierunku gradientu funkcji (metody gradientowe) i bezgradientowych metod wykorzystujących
własności sprzężonych kierunków poszukiwania minimum. Metoda gradientu sprzężonego ma
charakter iteracyjny: każda iteracja polega w tym przypadku na przeprowadzeniu minimalizacji

4

kierunkowej wzdłuż obowiązującego kierunku poszukiwao,

d

, oraz wyznaczenia nowego kierunku

poszukiwao dla kolejnej iteracji.

Pierwszym kierunkiem poszukiwao jest kierunek przeciwny do kierunku gradientu

minimalizowanej funkcji w punkcie startowym

0

x

, co czyni wynik pierwszej iteracji tożsamy z

metodą najszybszego spadku:

 

0

1

x

f

 

x

d

x

W każdej iteracji metody gradientu sprzężonego nowy kierunek poszukiwao, dla i -tej iteracji, jest
wyznaczany wg następującej zależności:

 

1

ˆ

i

i

i

i

x

f





 



x

d

x

d

Współczynnik

i



występujący w powyższej zależności jest dobierany w taki sposób, aby nowo

wyznaczony kierunek

1

i



d

był A-sprzężony z poprzednim kierunkiem poszukiwao

i

d

względem

kwadratowego przybliżenia minimalizowanej funkcji celu

 

f x

. Spełnienie podanego wymagania

zapewni, że kierunki poszukiwao w metodzie gradientu sprzężonego będą z jednej strony w
korzystny sposób „zawierały” kierunek przeciwny do wektora gradientu minimalizowanej funkcji, a
z drugiej – będą kierunkami sprzężonymi względem macierzy A przybliżenia kwadratowego
minimalizowanej funkcji. Algorytm doboru współczynnika funkcji

i



, zapewniający A-sprzężonośd

generowanych kierunków poszukiwao, jest następujący:

algorytm Fletchera-Reevesa

 

 

 

 

 

 

1

1

1

2

ˆ

ˆ

ˆ

2

ˆ

ˆ

ˆ

i

i

i

i

i

i

T

x

x

x

i

FR

T

x

x

x

f

f

f

f

f

f

























x

x

x

x

x

x

x

x

x

x

x

x

,

algorytm Polaka-Ribiére’a

 

 

 





 

 

 

 

1

1

1

1

ˆ

ˆ

ˆ

ˆ

2

ˆ

ˆ

ˆ

i

i

i

i

i

i

i

T

T

i

x

x

x

x

i

PR

T

x

x

x

f

f

f

f

f

f

f















 















x

x

x

x

x

x

x

x

x

x

x

g

x

x

x

gdzie wektor

i



g

określony jest jako różnica wektorów gradientu w odpowiednich punktach:

 

 

1

ˆ

ˆ

i

i

i

x

x

f

f



  



x

x

g

x

x

.

Dla funkcji kwadratowej n zmiennych algorytm gradientu sprzężonego powinien

doprowadzid do punktu globalnie minimalnego po najwyżej n iteracjach, jako że w metodzie
gradientu sprzężonego po n kolejnych iteracjach dysponujemy n kierunkami sprzężonymi dla
kwadratowej funkcji celu. W związku z powyższym w metodzie gradientu sprzężonego po n
kolejnych iteracjach oraz zawsze wtedy, gdy nowo wyznaczony kierunek nie jest kierunkiem
poprawy, dokonuje się tzw. odnowy kierunków poszukiwao, poprzez przyjęcie jako kierunku
poszukiwao dla kolejnej iteracji kierunku przeciwnego do wektora gradientu minimalizowanej
funkcji w ostatnio osiągniętym punkcie poszukiwao.

5

Iteracyjne poszukiwanie minimum za pomocą metody gradientu sprzężonego kooczymy w

przypadku, gdy norma wektora gradientu minimalizowanej funkcji dla ostatniego przybliżenia
punktu minimalnego jest mniejsza od założonej dokładności obliczeo



:

 

ˆ

i

x

f







x

x

(możliwe jest również wykorzystanie innych kryteriów stopu lub ich kombinacji:

 

2

ˆ

i

x

f







x

x

lub

1

ˆ

ˆ

i

i









x

x

lub

   

1

ˆ

ˆ

i

i

f

f









x

x

lub

   

1

1

ˆ

ˆ

ˆ

ˆ

i

i

i

i

f

f













x

x

x

x

lub

max

i

It



).

Jako punkt minimalizujący, ˆx , daną funkcję przyjmuje się ostatnie przybliżenie tego punktu ˆ

i

x

.

DODATEK

Definicje:
Kierunki sprzężone: Kierunki

1

2

,

,...,

0

n



d d

d

nazywamy sprzężonymi względem dodatnio

określonej symetrycznej macierzy A o wymiarach n n



(A-sprzężonymi), jeżeli zachodzi:

,

1,..,

¹

0

T
i

j

i j

n

i j







d Ad

Uwaga:

1. Kierunki A-sprzężone są liniowo niezależne.
2. Relacja A-sprzężoności nie jest przechodnia tj. z faktu

0

T
i

j



d Ad

oraz

0

T

j

k



d Ad

nie wynika, że

0

T
i

k



d Ad

, czyli nie wynika, że kierunki

i

d

,

j

d

i

k

d

są A-sprzężone.

Rozmaitość liniowa:

r

-wymiarową rozmaitością liniowa w przestrzeni n -wymiarowej nazywamy

zbiór:

0

1

:

r

n

i

i

i













x

x

x

d

przy czym:





,

,

1,..., ,

i

i

r



  



n

i



d

- kierunek w n -wymiarowej przestrzeni poszukiwao,

1,...,

i

i

r



d

- kierunki liniowo niezależne,

6

0

n



x

- dowolny punkt w n -wymiarowej przestrzeni poszukiwao.

Twierdzenie:
Jeżeli

1

2

,

,...,

n

d d

d

są kierunkami A-sprzężonymi, to minimum funkcji kwadratowej n zmiennych

 

1

2

T

T

f

c

 



x

b x

x Ax

w rozmaitości liniowej określonej przez te kierunki i dowolny punkt

0

x

może byd wyznaczone w n

krokach poprzez minimalizację funkcji

 

f x

na każdym z tych kierunków tylko jeden raz.

Program dwiczenia

1. Dla podanych przez prowadzącego funkcji wielu zmiennych zaimplementowad algorytm

poszukiwania punktu minimalizującego z zastosowaniem metody Powella oraz metody
gradientu sprzężonego

1

.

2. Przedstawid w postaci schematu blokowego algorytm działania badanej metody

minimalizacji funkcji wielu zmiennych.

3. Dla jednego przykładowego zestawu parametrów

0



x

0

i

0, 0001





(punktu startowego

i zadanej dokładności obliczeo) przedstawid wyniki działania metody dla podanej funkcji
celu. Wyniki przedstawid w postaci tabelarycznej:

Nr iteracji

Punkt osiągnięty

w danej iteracji

Wartośd funkcji celu

w danej iteracji

Wartośd kryterium

stopu (przy danym



)

0

1

4. Zbadad eksperymentalnie czy zbieżnośd badanej metody, dla podanej przez prowadzącego

funkcji, jest zależna od wyboru punktu początkowego

0

x

. Odpowiedź uzasadnid oraz

poprzed wynikami eksperymentów.

5. Zbadad eksperymentalnie czy zbieżnośd badanej metody, dla podanej przez prowadzącego

funkcji, jest zależna od wyboru wartości parametru



. Odpowiedź uzasadnid oraz poprzed

wynikami eksperymentów.

6. W sprawozdaniu zamieścid wydruki procedur realizujących opisywane metody

minimalizacji funkcji wielu zmiennych.

7. Porównad wyniki działania analizowanej metody z wynikami działania metody analizowanej

na dwiczeniu: „MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH - METODA PROSTYCH
KIERUNKÓW POPRAWY” (odpowiednio met. Powella z met. Gaussa-Seidla oraz met.
gradientu sprzężonego z met. najszybszego spadku).

Literatura:

J. Figwer, J. Mościoski, Z. Ogonowski: Laboratorium metod optymalizacji statycznej, skrypt
uczelniany nr 2114, Wydawnictwo Politechniki Śląskiej, Gliwice 1998

1

O wyborze metody decyduje prowadzący zajęcia