1
MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH
METODY NEWTONOWSKIE I QUASI-NEWTONOWSKIE
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
lub jego przybliżenia.
Dokładnie zostaną omówione metody wykorzystujące w procesie minimalizacji informację o
wartości funkcji, wartości jej gradientu oraz hesjanu.
Omawiane metody należące do klasy metod newtonowskich i quasi-newtonowskich
(zmiennej metryki) opierają się o na kwadratowym modelu minimalizowanej funkcji celu:
1
2
T
T
f
c
x
b x
x Ax
.
Gdzie gradient wyrażony jest zależnością:
x
f
x
b
Ax
natomiast macierz hesjanu:
2
T
x
x
x
f
f
x
x
A
.
Metoda Newtona
Metoda ta, podobnie jak metoda najszybszego spadku, wykorzystuje możliwośd
przybliżonej reprezentacji minimalizowanej funkcji w otoczeniu punktu odpowiadającemu
ostatniemu przybliżeniu punktu minimalizowanego za pomocą rozwinięcia w szereg Taylora.
W metodzie Newtona bierzemy pod uwagę wyrazy szeregu rozwinięcia do kwadratowych, a więc
więcej niż w metodzie najszybszego spadku, co pozwala na dokładniejszą aproksymację
2
minimalizowanej funkcji i w efekcie wyznaczenie lepszego kierunku poszukiwao (skierowanego
bardziej do globalnego punktu minimalizującego wskaźnik jakości). Wykorzystywane rozwinięcie
wskaźnika jakości ma następującą postad:
1
1
1
1
1
2
1
ˆ
ˆ
1
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
2
i
i
T
T
i
i
i
i
i
i
i
i
x
x
f
f
f
f
x
x
x
x
x
x
x
x
x
x
x
x
Warunkiem koniecznym, aby kolejne przybliżenie ˆ
i
x
odpowiadało punktowi minimalnemu funkcji
jest spełnienie warunku:
ˆ
ˆ
i
i
f
x
0
x
czyli
1
1
1
ˆ
ˆ
ˆ
i
i
i
i
x
f
x
x
H
x
x
0
gdzie
1
1
2
ˆ
i
i
x
f
x
H
x
jest macierzą drugich pochodnych cząstkowych (hesjanem) funkcji celu wyliczanych w punkcie
1
ˆ
i
x
(aktualnym).
Powyższy warunek możemy przekształcid do postaci, z której wyznaczamy kolejne
przybliżenia punktu minimalizującego funkcję celu:
1
1
1
1
ˆ
ˆ
ˆ
i
i
i
i
x
f
x
x
x
H
x
Zależnośd ta określa nowe przybliżenie punktu minimalizującego funkcję, a nie kierunek
poszukiwao. Oznacza to, że w metodzie Newtona nie dokonujemy minimalizacji funkcji jednej
zmiennej po wyznaczeniu kierunku poszukiwao, a jedynie wyznaczamy wartości minimalizowanej
funkcji, jej gradientu i hesjanu oraz kolejne przybliżenie punktu optymalnego.
Dla funkcji kwadratowej
f x
metoda Newtona zapewnia osiągnięcie punktu globalnego
minimum funkcji w jednym kroku iteracji algorytmu nie zależnie od wybranego warunku
początkowego.
Zmodyfikowana metoda Newtona (modyfikacja Newtona-Raphsona)
Podstawowa wersja algorytmu Newtona nie jest niezawodna przy minimalizacji funkcji
wyższego rzędu niż kwadratowe. Gdy punkt startowy znajduje się daleko od minimum, krok
metody może okazad się zbyt duży, co z kolei może doprowadzid do niezbieżności oraz
niestabilności numerycznej metody. Z tego powodu wprowadzono modyfikacje: poszukiwanie
optymalnej długości kroku w aktualnym kierunku
i
d
polegającej na uwzględnieniu w kolejnych
iteracjach minimalizacji na kierunku. Zapewnia to zmniejszanie się wartości funkcji w punkcie
roboczym z kroku na krok oraz zwiększanie obszaru zbieżności metody.
3
W zmodyfikowanej metodzie Newtona kolejne przybliżenie punktu minimalizującego
funkcje celu wyznaczamy z zależności:
1
ˆ
ˆ
ˆ
i
i
i
i
x
x
d
gdzie kierunek w i -tej iteracji obliczamy ze wzoru:
1
1
1
ˆ
i
i
i
x
f
x
d
H
x
oraz dokonywana jest na jego podstawie minimalizacja na kierunku, tzn. określana jest optymalna
długość kroku ˆ
i
:
1
ˆ
ˆ
: min
i
i
i
i
i
f
x
d
.
W celu określenia, czy osiągnięty w danym kroku punkt dostatecznie dobrze przybliża
minimum funkcji celu w metodzie Newtona oraz jej zmodyfikowanej wersji, można użyd
następujących kryteriów stopu dla założonej dokładności obliczeo
:
ˆ
i
x
f
x
x
lub
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
.
Metoda quasi-newtonowska (zmiennej metryki)
Metoda quasi-newtonowska (Q-N) jest stosowana, gdy obliczenie hesjanu (macierzy
drugich pochodnych cząstkowych) wymaganego przez zmodyfikowaną metodę Newtona jest
trudne lub czasochłonne. W metodzie tej estymuje się hesjan minimalizowanej funkcji (lub jego
odwrotnośd) na podstawie zmian gradientu funkcji celu w kolejnych przybliżeniach punktów
optymalnych osiąganych w kolejnych iteracjach metody quasi-newtonowskiej. Im lepsza jest
aproksymacja hesjanu minimalizowanej funkcji (lub jego odwrotnośd), tym omawiana metoda
optymalizacji jest bliższa zmodyfikowanej metodzie Newtona i tym lepsze powinny byd wyniki jej
zastosowania w sensie szybkości zbieżności do punktu optymalnego.
4
W kolejnych iteracjach metody Q-N wyznacza się kierunek poszukiwao
i
d
wg
następującego wzoru:
1
1
ˆ
i
i
i
x
f
x
d
B
x
,
a następnie dokonuje się w tym kierunku minimalizacji osiągając punkt ˆ
i
x
stanowiący kolejne
przybliżenie punktu optymalnego zadanej funkcji celu:
1
1
1
1
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
i
i
i
i
i
i
i
i
x
f
x
x
x
d
x
B
x
.
Istota metod quasi-newtonowskich jest zastępowanie macierzy
1
H
macierzą estymującą
B
. Staje się ona w kolejnych iteracjach coraz lepszym przybliżeniem macierzy odwrotnej do
hesjanu.
Pierwszym, ale efektywnym pomysłem na generowanie takiej macierzy, był algorytm
Davidona-Fletchera-Powella:
1
1
1
1
T
T
i
i
i
i
i
i
DFP
DFP
i
i
DFP
DFP
T
T
i
i
i
i
i
DFP
x
x
B
g
g
B
B
B
x
g
g
B
g
,
często do estymacji macierzy
B
wykorzystywany jest również algorytm Broydena-Fletchera-
Goldfarba-Shanno:
1
1
1
1
1
T
T
T
T
i
i
i
i
i
i
i
i
i
i
i
BFGS
BFGS
BFGS
i
i
BFGS
BFGS
T
T
T
i
i
i
i
i
i
g
B
g
x
x
x
g
B
B
g
x
B
B
x
g
g
x
g
x
gdzie
1
ˆ
ˆ
i
i
i
x
x
x
i
1
ˆ
ˆ
i
i
i
x
x
f
f
x
x
g
x
x
.
Macierz
0
B
w pierwszej iteracji jest przyjmowana jako macierz jednostkowa,
0
B
I
, co
oznacza, że w pierwszej iteracji kierunek poszukiwania minimum jest przeciwny do kierunku
gradientu minimalizowanej funkcji,
0
1
x
f
x
d
x
, podobnie jak w metodach gradientowych.
Także podobnie jak w metodzie gradientu sprzężonego, w warunkach słabej zbieżności algorytmu,
przeprowadza się tzw. odnowy kierunków poszukiwao – w przypadku metody Q-N oznacza to
przyjęcie do obliczeo w kolejnej iteracji macierzy
i
B
równej macierzy jednostkowej. Odnowę
dokonuje się zawsze po
2
1
n
iteracjach metody Q-N oraz zawsze, gdy kierunek poszukiwao nie
jest kierunkiem poprawy.
Poszukiwanie minimum za pomocą metody Q-N uważa się za zakooczone, 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 także wykorzystanie innych kryteriów stopu metody:
5
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
.
Program ćwiczenia
1. Dla podanych przez prowadzącego funkcji wielu zmiennych zaimplementowad algorytm
poszukiwania punktu minimalizującego z zastosowaniem metody newtonowskiej oraz
metody quasi-newtonowskiej
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 metod
analizowanych na dwiczeniach: „MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH - METODA
PROSTYCH KIERUNKÓW POPRAWY” oraz „MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH -
METODA SPŻĘRZONYCH KIERUNKÓW POPRAWY”.
Literatura:
1
O wyborze metody decyduje prowadzący zajęcia
6
J. Figwer, J. Mościoski, Z. Ogonowski: Laboratorium metod optymalizacji statycznej, skrypt
uczelniany nr 2114, Wydawnictwo Politechniki Śląskiej, Gliwice 1998