TECHNIKA OPTYMALIZACJI - LABOLATORIUM

Ćwiczenie III: Zadanie programowania nieliniowego bez ograniczeń

algorytmy optymalizacji lokalnej.

Skład grupy:

Prowadzący:

Data wykonania

ćwiczenia:

- Dawid Cekus

- Mateusz Grzelak

Dr inż. Ewa

Szlachcic

3.12.2014

1. Cel ćwiczenia

Celem ćwiczenia było poznanie metody rozwiązywania nieliniowego zadania
optymalizacji. Na funkcję celu nie zostały nałożone żadne ograniczenia.
Wykorzystany został algorytm optymalizacji lokalnej. Algorytm ten umożliwia
wyznaczenie takiego wektora zmiennych decyzyjnych x, dla którego funkcja celu
f(x) osiąga minimum:

min f (x )=f ( ^x)

x ∈R

n

2. Przebieg ćwiczenia

2.1. Zadanie testowe nr 6

Funkcja dla której będzie poszukiwana wartość minimalna ma postać:

f (x

1

, x

2

)=

x

1

4

+

x

2

4

−

2x

1

2

x

2

−

4 x

1

+

3

W celu obliczenia minimum lokalnego posłużono się narzędziem fminunc.
Wyniki działania procedury dla wartości TolFun=0.01 oraz punktu startowego
x0=[1.5;1]:
x=[1.3129;0.9542]
fval=-1.7410
exitflag=1

output:

iterations:3
algorithm: 'medium-scale: Quasi-Newton line search'

hessian=

(

16.8724 −5.2519

−

5.2519 10.9298

)

grad=

(

0.0408
0.0283

)

Wykres funkcji celu:

Wykres warstwicy funkcji wraz z punktami uzyskanymi w kolejnych iteracjach dla
TolFun=0.01:

Wykres przedstawiający wartości funkcji celu w kolejnych iteracjach dla
TolFun=0.01

Wyniki działania procedury dla wartości TolFun=0.00001 oraz punktu startowego
x

0

=[1.5;1]:

x=[1.3091;0.9498]
fval=-1.7411
exitflag=1

output:

iterations:7
algorithm: 'medium-scale: Quasi-Newton line search'

hessian=

(

16.7702 −5.2367

−

5.2367 10.8284

)

grad=

1.0e-5∗

(

−

0.1184

−

0.1431

)

Wykres warstwicy funkcji wraz z punktami uzyskanymi w kolejnych iteracjach dla
TolFun=0.00001:

Wykres przedstawiający wartości funkcji celu w kolejnych iteracjach dla
TolFun=0.00001

Rozwiązanie analityczne:

f (x

1

, x

2

)=

x

1

4

+

x

2

4

−

2x

1

2

x

2

−

4 x

1

+

3

∇

f (x

1,

x

2

)=[

4x

1

3

−

4x

1

x

2

−

4,4 x

2

3

−

2x

1

2

]

Warunek konieczny istnienia ekstremum w punkcie mówi, że gradient w tym punkcie
jest równy zero:

∇

f (x

1,

x

2

)=

0

W przypadku funkcji numer 6 warunek ten jest spełniony dla:

x

1

=

1.309083347

x

2

=

0.9498059087

Wyznaczony punkt jest określany jako punkt stacjonarny. Może się tam znajdować
ekstremum. W celu zbadania czy w powyższym punkcie znajduje się ekstremum
należy zbudować macierz drugich pochodnych tzw. macierz Hessego(hesjan).

W tym przypadku hesjan ma nastepującą postać ogolną:

(

12x

1

2

−

4 x

2

−

4 x

1

−

4 x

1

12 x

2

2

)

W punkcie stacjonarnym ma następującą postać:

(

16.765166877912669 −5.236333388000000

−

5.236333388000000 10.825575170417192

)

Macierz jest dodatnio określona. Świadczy to o tym, że w punkcie stacjonarnym
znajduje się minimum lokalne.

2.2. Zadanie testowe nr 17

Funkcja dla której będą poszukiwane minima lokalne oraz globalne ma postać:

f (x

1,

x

2

)=

4 x

1

2

−

2.1 x

1

4

+

1

3

x

1

6

+

x

1

x

2

−

4 x

2

2

+

4 x

2

4

Wykres funkcji celu:

Wykres warstwicowy funkcji celu:

Na podstawie tego wykresu widać, że funkcja posiada 6 minimów(4 lokalne i 2
globalne) i pomaga dobrać punkty startowe dla poszukiwań. Dodatkowo minima są
pogrupowane w 3 pary. Minima z każdej z par są symetryczne względem punktu
(0,0).

W celu odnalezienia wszystkich minimów posłużono się narzędziem fminsearch.
Pierwsze minimum obliczone dla punktu startowego x

0

=[0,1] dla TolFun=0.1

x

0

=[0;1]:

x=[-0.0898;0.7127]
fval=-1.0316
exitflag=1

output:

iterations:48
algorithm: 'Nelder-Mead simplex direct search'

Procedura fminsearch nie posiada możliwości policzenia gradientu ani hesjanu w
punkcie dlatego obliczenia te zostały przeprowadzone przy użyciu narzędzi
dostępnych w programie Maple.

∇

f (−0.0898,0 .7127)=

(

0.0003711875

0.00075611813

)

H (−0.0898,0 .7127)=

(

7.797436479

1

1

16.38118192

)

Wykres warstwicy funkcji wraz z punktami uzyskanymi w kolejnych iteracjach dla
TolFun=0.1 (pierwsze minimum):

Wykres przedstawiający wartości funkcji celu w kolejnych iteracjach dla
TolFun=0.1(pierwsze minimum):

Drugie minimum zostało odnalezione dla punktu startowego x

0

=[-1.75,0.8] oraz dla

TolFun=0.1
x

0

=[-1.75;0.8]:

x=[-1.7036;0.7961]
fval=-0.2155
exitflag=1

output:

iterations:23
algorithm: 'Nelder-Mead simplex direct search'

∇

f (−1.7036, 0.7961)=

(

0.00014466

0.000375115

)

H (−0.0898,0 .7127)=

(

19.09394785

1

1

22.42121008

)

Wykres warstwicy funkcji wraz z punktami uzyskanymi w kolejnych iteracjach dla
TolFun=0.1 (drugie minimum):

Wykres przedstawiający wartości funkcji celu w kolejnych iteracjach dla
TolFun=0.1(drugie minimum):

Trzecie minimum zostało odnalezione dla punktu startowego x

0

=[-.175,-0.6] oraz dla

TolFun=0.1

x

0

=[-1.75;0.8]:

x=[-1.6071;-0.5686]
fval=2.1043
exitflag=1

output:

iterations: 25
algorithm: 'Nelder-Mead simplex direct search'

∇

f (−1.6071,−05686)=

(

0.00009718

0.000391698

)

H(−1.6071,−0.5686)=

(

9.62121558

1

1

7.51868608

)

Wykres przedstawiający wartości funkcji celu w kolejnych iteracjach dla
TolFun=0.1(trzecie minimum):

Czwarte minimum zostało odnalezione dla punktu startowego x

0

=[0,-1] oraz dla

TolFun=0.0001

x

0

=[0;-1]:

x=[0.0898;-0.7127]
fval= -1.0316
exitflag=1

output:

iterations: 49
algorithm: 'Nelder-Mead simplex direct search'

∇

f (0.0898,−0.7127)=

(

−

0.0003711875

−

0.00075611813

)

H(0.0898,−0.7127)=

(

7.797436479

1

1

16.38118192

)

Wykres przedstawiający wartości funkcji celu w kolejnych iteracjach dla
TolFun=0.0001(czwarte minimum):

Piąte minimum zostało odnalezione dla punktu startowego x

0

=[1.75,-0.8] oraz dla

TolFun=0.0001
x

0

=[1.75;-0.8]:

x=[1.7036;-0.7961]
fval=
exitflag=1

output:

iterations: 23
algorithm: 'Nelder-Mead simplex direct search'

∇

f (1.7036,−0.7961)=

(

−

0.00014466

−

0.000375115

)

H(1.7036,−0.8)=

(

19.09394785

1

1

22.42121008

)

Szóste minimum zostało odnalezione dla punktu startowego x

0

=[1.75,-0.6] oraz dla

TolFun=0.0001
x

0

=[1.75;0.6]:

x=[1.6071,0.5686]
fval= 2.1043
exitflag=1

output:

iterations: 25
algorithm: 'Nelder-Mead simplex direct search'

∇

f (1.6071,0 .5686)=

(

−

0.000009718

−

0.0000391698

)

H(1.6071,0.5686)=

(

9.62121558

1

1

7.51868608

)

Zarówno dla piątego minimum jak i szóstego wykres wartości funkcji celu w
zależności od iteracji był identyczny jak dla minimów symetrycznych względem
punktu (0,0)

3. Opis wykorzystanych metod optymalizacji.

Podczas zajęć były wykorzystywane dwa narzędzia pakietu Matlab:
fminsearch oraz fmiunc. Pierwsze z nich wykorzystuje metodę pełzającego simplexu
Neldera-Meada natomiast drugie korzysta z metod Quasi-newtonowskie.

3.1 Metoda pełzającego simplexu Neldera-Meada.

Metoda pełzającego simplexu jest metodą bezgradientową. W tej metodzie
przeszukuje się kolejno pewne dane kierunki przy wykorzystaniu wersorów osi
współrzędnych.
W tej metodzie działanie jest rozpoczynane od uporządkowania (n+1) punktów
x

1

,x

2

,...,x

n+1

w następujący sposób:

f

n+1

⩾

f

n

⩾

...⩾f

2

⩾

f

1

Wierzchołki te tworzą sympleks o (n+1) wierzchołkach.

W każdej iteracji punkt x

n+1

jest zastępowany punktem „lepszym”

Punkt ciężkości c jest zdefiniowano następująco:

c=

1
n

∑

i=1

n

x

i

Przebieg jednej iteracji metody ma następującą postać:
Konstruowany jest punkt próbny, który jest odpowiedzialny za odbicie punktu
x

n+1

względem hiperpowierzchni rozpiętej na punktach x

1

, .., x

2

, który ma postać:

x

r

=

c+α(c−x

n+1

)

,α>0

α jest współczynnikiem odbicia. Wartość funkcji w punkcie x

r

jest oznaczana: f

r

.

Operacja konstrukcji punktu próbnego jest tożsama z przesunięciem z punktu c w
kierunku (c - x

n+1

) ze współczynnikiem α.

Należy dokonać analizy położenia wartości f

r

.

a) f

1

<= f

r

<= f

n

Punkt x

n+1

jest zastępowany przez x

r

i następuje przejście do następnej iteracji.

Odrzucany jest najgorszy z poprzednich punktów. Może istnieć konieczność
ponownego uporządkowania ze względu na wartość funkcji.

b) fr < f1
Uzyskany punkt jest lepszy od najlepszego dotychczasowych.
Dokonywana jest próba ekspansji(rozciągnięcia) w tym kierunku. Konstruowany jest
następujący punkt:

x

e

=

x+β(x

r

−

c),β>1

β- współczynnik ekspansji
Jeżeli f

e

< f

r

to x

n+1

=x

e

w przeciwnym wypadku x

n+1

=x

r

. Punkty należy znów

uporządkować tak aby wartości funkcji były uporządkowane od najmniejszej do
największej.

c)f

r

> f

n

W tym przypadku wartość próbna może być porównywalna tylko z najgorszą.
W zaistniałej sytuacji istnieje wymóg aby zmniejszyć simpleks. Spowoduje to fakt,
iż będzie można liczyć na ewentualną poprawę wartości funkcji. Należy wówczas
wykonać operację kontrakcji. Należy dokonać wyboru dwóch sympleksów leżących
albo po jednej albo po drugiej stronie hiperpowierzchni, która jest rozpięta na
punktach x

1

, …, x

n

.

Kryterium wyboru odnosi się w tym przypadku do wzajemnej relacji wartości funkcji

w wierzchołku (n+1) -f

r

i f

n+1

gdy f

r

>= f

n+1

x

e

=

c+γ(x

n+1

−

c)

gdy f

r

< f

n+1

x

e

=

c+γ(x

r

−

c)

γ- współczynnik kontrakcji
0 < γ < 1

Jeżeli f

e

< min{f

r

, f

n+1

}, wtedy x

n+1

= x

e

następuje wówczas przejście do kolejnego

kroku. W przypadku gdy ten warunek jest niespełniony operacja ściśnięcia.
Operacje ściśnięcia można zastąpić ściśnięciem całego sympleksu wokół punktu
dotychczas najlepszego

x

i

=

x

1

+γ(

x

i

−

x

1

)

,i=2,...,n+1

Należy również pamiętać o przywróceniu uporządkowania punktów ze względu na
wartość funkcji
Metoda sympleksu Neldera-Meada jest stosowana w odniesieniu do funkcji, które
mogą być nieciągłe albo nieróżniczkowalne. Skuteczność metody ogranicza się do
zadań o małym wymiarze.
Liczba iteracji konieczna do odnalezienia minimum jest większa niż w przypadku
zastosowania metod wykorzystujących pochodne.

3.2 Metody Quasi-newtonowskie

Metody quasi-newtonowskie stanowią alternatywę wobec dyskretnej metody
Newtona. Metoda wykorzystuje informacje o pochodnych drugiego rzędu bez
konieczności jawnego wyliczania macierzy hesjanu. Wykorzystywana jest informacja
o pochodnych pierwszego rzędu w aktualnym punkcie x

k

oraz punkcie następnym

x

k+1

. Wyrażenia opisujące pochodne pierwszego i drugiego rzędu na kierunku s

k

są

uzyskiwane na podstawie rozwinięcia gradientu w szereg Taylora względem
przyrostu zmiennych niezależnych. Wspomniane wyżej wyrażenia mają następującą
postać:

~f'(0)=∇ f (x

k

)

T

s

k

=

g(x

k

)

T

s

k

~f' '(0)=s

kT

∇

2

f (x

k

)

s

k

=

s

kT

G

k

s

k

Wyrażenie, które pozwala określić krzywiznę minimalizowanej funkcji f wzdłuż
kierunku s

k

:

s

kT

G

k

s

k

≈(

g(x

k

+

s

k

)−

g(x

k

))

T

s

k

Metody quasi-newtonowskie wykorzystują fakt, że skoro można oszacować
krzywiznę wzdłuż kierunku na podstawie różnic pochodnych pierwszego rzędu to
można dokonywać próby aproksymacji hesjanu na podstawie informacji
analogicznej. W metodach tego typu aproksymujemy macierz G

k

bądź też jej

odwrotność (G

k

)

-1

. Na początku k-tej iteracji do dyspozycji B

k

, H

k

. W pierwszym

przypadku kolejny kierunek poszukiwań jest wyznaczony z następującej zależności:

B

k

d

k

=−

g

k

w drugim przypadku :

d

k

=−

H

k

g

k

W przypadku braku informacji przyjmuje się H

0

=I(B

0

=I).

I-macierz identycznościowa
Po znalezieniu kolejnego przybliżenia rozwiązania- punktu x

k+1

macierz H

k

lub B

k

jest

modyfikowana w następujący sposób:

H

k+1

=

H

k

+

U

k

gdzie U

k

jest poprawką wyznaczoną na podstawie przyrostów zmiennych

niezależnych i przyrostów gradientu. Poprawka jest konstruowana jest w taki sposób,
aby kolejna macierz spełniała warunek quasi-newtonowski:

H

k+1

r

k

=

s

k

W metodach quasi-newtonowskich rozważa się w głównie poprawki pierwszego i
drugiego rzędu.

Opis metod został stworzony na podstawie książki:
„Podstawy optymalizacji” A.Stachurski, A.P Wierzbicki.

4. Wnioski

Dla pierwszego zadania testowego zostało znalezione jedno minimum lokalne. W
celu jego znalezienia skorzystano z narzędzia fminunc,które korzysta z metod
quasi-newtonowskich. Obliczenia dokonano dla dwóch wartości parametru
TolFun=0.01 oraz TolFun=0.00001. Dla mniejszej wartości parametru można
dostrzec, że wartość rozwiązania jest bardziej dokładna, dodatkowo można
zaobserwować większą liczbę iteracji.
Dla drugiego zadania testowego znaleziono 6 minimów- 2 globalne, 4 lokalne.
Wykreślenie warstwic funkcji było pomocne dla określenia poszczególnych punktów
startowych od których rozpoczną się poszukiwania. W tym przypadku skorzystano z
narzędzia fminsearch, które korzysta z metody pełzającego sympleksu Neldera-
Meada. Pierwsze 3 minima zostały znalezione dla wartości parametru TolFun=0.1 a
następne 3 dla TolFun=0.0001. Zmiana wartości TolFun nie wpłynęła na poprawę
dokładności wyniku oraz na liczbę iteracji.
Znalezione minima są pogrupowane w trzy pary. Minima z każdej pary są
symetryczne względem punktu (0,0).
Na podstawie wyników obliczeń można dostrzec, że sympleks Neldera-Meada jest
mniej efektywny niż metody quasi-newtonowskie. Świadczy o tym liczba iteracji
potrzebna do znalezienia szukanego punktu.