1
MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH
METODY PROSTYCH 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 których w 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
poszukiwao.
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
2
k
d
, którego określenie, jak i również odległośd przesunięcia w tym kierunku są zależne od
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 Gaussa-Seidla (metoda bezgradientowa)
Metoda Gaussa-Seildla jest jedną z najprostszych metod poszukiwao, której zastosowanie
jest w zasadzie ograniczone do wąskiej klasy funkcji
f x
- takich, które w otoczeniu punktu
minimalizowanego można aproksymowad pewną ściśle wypukłą funkcją kwadratową. W metodzie
tej dokonujemy kolejnych poszukiwao minimum wskaźnika jakości wzdłuż tylko jednej zmiennej
decyzyjnej
1
,
,
n
x
x
. Oznacza to, że kierunki poszukiwao są w tej metodzie stał i ortogonalne,
odpowiadające osiom układu współrzędnych dziedziny minimalizowanej funkcji. Wielkośd
przesunięcia ˆ
k
w kierunku poszukiwao
k
d
w każdym kroku jest wyznaczana w taki sposób, aby
osiągnąd minimum wskaźnika jakości na bieżącym kierunku poszukiwao. Ponieważ kierunki
poszukiwao są zgodne z osiami układu współrzędnych odpowiadających zmiennym decyzyjnym
wskaźnika jakości, oznacza to, że w każdym etapie minimalizujemy wskaźnik jakości tylko według
jednej zmiennej decyzyjnej lub inaczej na kierunku określanym przez wersor
k
e
danej k -tej osi
układu współrzędnych.
Jednorazowe przeprowadzenie optymalizacji wzdłuż kierunków poszukiwao
1
,
,
n
e
e
,
odpowiadających wszystkim zmiennym decyzyjnym
1
,
,
n
x
x
, określamy jako jedną iterację.
Kierunki poszukiwao
k
k
d
e
są ortogonalnymi wektorami jednostkowymi, tj.:
-ty elemet
0,
, 0,
1
, 0,
, 0
T
k
k
e
,
0 dla
;
1 dla
.
T
j
k
k
j
k
j
e e
Jeżeli po
1
k
krokach optymalizacji w danej iteracji osiągnięto punkt poszukiwao
1
ˆ
k
x
, to
kolejnym krokiem w opisywanym algorytmie jest przeprowadzenie minimalizacji wzdłuż prostej
wyznaczonej przez punkt
1
ˆ
k
x
i wektor
k
e
, tj. znalezienie takiego optymalnego ˆ
k
, że
3
1
ˆ
ˆ
: min
k
k
k
k
k
f
x
e
,
a więc rozwiązanie zagadnienia minimalizacji funkcji jednej zmiennej.
Koocowym etapem każdej iteracji jest sprawdzenie prawdziwości kryterium stopu
pozwalające na zakooczenie obliczeo poszukiwania minimum analizowanej funkcji
f x
.
Sprawdzany warunek zakooczenia obliczeo (kryterium stopu) następującej postaci:
,
,0
ˆ
ˆ
i n
i
x
x
(możliwe jest również wykorzystanie innych kryteriów stopu lub ich kombinacji:
,
,0
ˆ
ˆ
i n
i
f
f
x
x
lub
,
,0
,
,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 oraz
,0
,
ˆ
ˆ
,
i
i n
x
x
są
odpowiednio punktem startowym i -tej iteracji oraz punktem będącym przybliżeniem
poszukiwanego punktu optymalnego uzyskanym po minimalizacji na n kierunkach w tej iteracji.
Jeśli kryterium stopu jest spełnione, następuje zakooczenie procesu minimalizacji i przyjęcie
punktu
,
ˆ
i n
x
za punkt optymalny, ˆx .
Jak wspomniano powyżej, w metodzie Gaussa-Seidla kierunki poszukiwao są stałe w trakcie
poszukiwania minimum, co powoduje, że w szczególnie niekorzystnych przypadkach metoda ta
może byd niezbieżna w ogóle, a średnio charakteryzuje się zbieżnością wolną. Zaletą tej metody
optymalizacji jest jej prostota i szybkośd przeprowadzania obliczeo w każdym kroku iteracji
optymalizacji (która może byd jednak niwelowana poprzez konieczną do przeprowadzenia dużą
liczbę iteracji).
Metoda najszybszego spadku (metoda gradientowa)
Jedną z najprostszych gradientowych metod poszukiwao jest metoda najszybszego spadku.
Z godnie z nazwą metody, kierunek poszukiwao jest każdorazowo wyznaczany jako przeciwny do
kierunku gradientu minimalizowanej funkcji
1
ˆ
i
i
x
f
x
d
x
,
tj. kierunek poszukiwao odpowiada kierunkowi najszybszego malenia wartości minimalizowanej
funkcji – najszybszego „spadku”. Zakładając, że funkcję minimalizowana można w dostatecznie
małym otoczeniu analizowanego punktu opisad za pomocą jej rozwinięcia w szereg Taylora, i
ograniczając się do wyrazu liniowego w tym rozwinięciu, minimalizowany wskaźnik jakości w
otoczeniu punktu
1
ˆ
i
x
możemy opisad następująco:
4
1
1
1
ˆ
ˆ
ˆ
ˆ
ˆ
i
T
i
i
i
i
x
f
f
f
x
x
x
x
x
x
.
W metodzie najszybszego spadku punkt w kolejnej iteracji ˆ
i
x
jest wyznaczany przez minimalizację
wartości wskaźnika jakości wzdłuż określonego powyżej kierunku
i
d
, tj:
1
1
1
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
i
i
i
i
i
i
i
x
f
x
x
x
d
x
x
,
gdzie
1
1
ˆ
ˆ
ˆ
: min
i
i
i
i
i
x
f
f
x
x
x
.
Iteracyjne poszukiwanie minimum za pomocą metody najszybszego spadku 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
.
Metoda najszybszego spadku jest szczególnie efektywna dla punktów odległych od punktu
minimalnego wskaźnika jakości i pozwala szybko osiągnąd jego pobliże. W pobliżu punktu
minimalnego, gdzie gradient minimalizowanej funkcji przyjmuje wartości bliskie zeru, efektywnośd
metody najszybszego spadku może byd niższa.
Program ćwiczenia
1. Dla podanych przez prowadzącego funkcji wielu zmiennych zaimplementowad algorytm
poszukiwania punktu minimalizującego z zastosowaniem metody Gaussa-Seidla oraz
metody najszybszego spadku
1
.
1
O wyborze metody decyduje prowadzący zajęcia
5
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.
Literatura:
J. Figwer, J. Mościoski, Z. Ogonowski: Laboratorium metod optymalizacji statycznej, skrypt
uczelniany nr 2114, Wydawnictwo Politechniki Śląskiej, Gliwice 1998