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