9.05.2013
Szczecin
1
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Zadanie poszukiwania bezwarunkowego minimum funkcji f(x)
argumentu wektorowego zadanego na
całej przestrzeni E
n
.
x=
[
x
1,
x
2,
, x
n
]
T
9.05.2013
Szczecin
2
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
9.05.2013
Szczecin
3
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
9.05.2013
Szczecin
4
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
9.05.2013
Szczecin
5
Metody optymalizacji
Jeśli funkcja jest ciągła i różniczkowalna względem wszystkich
zmiennych, to istnieje gradient tej funkcji
Ekstremum funkcji wielu zmiennych
∇
f x=
[
∂
f
∂
x
1
∂
f
∂
x
2
⋯
∂
f
∂
x
n
]
T
zwrócony w kierunku najszybszego wzrostu wartości funkcji,
ortogonalny do linii poziomu przebiegającej przez dany zadany punkt
9.05.2013
Szczecin
6
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Y
X
f(x,y)=const
x
k
∇
f x
k
∇
f x=
[
∂
f
∂
x
1
∂
f
∂
x
2
⋯
∂
f
∂
x
n
]
T
x
min
−∇
f x
k
∇
f x=∇
∇
f x
k
=∇
k
9.05.2013
Szczecin
7
Metody optymalizacji
f x= f x
k
∇
k
T
x−x
k
1
2
x−x
k
T
H
k
x−x
k
Rozkład w szereg Taylora funkcji wielu zmiennych
Ekstremum funkcji wielu zmiennych
H =
[
∂
2
f x
∂
x
1
2
∂
2
f x
∂
x
1
∂
x
2
⋯
∂
2
f x
∂
x
1
∂
x
n
∂
2
f x
∂
x
2
∂
x
1
∂
2
f x
∂
x
2
2
⋯
∂
2
f x
∂
x
2
∂
x
n
⋮
⋮
⋮
⋮
∂
2
f x
∂
x
n
∂
x
1
∂
2
f x
∂
x
n
∂
x
2
⋯
∂
2
f x
∂
x
n
2
]
H x=H
H x
k
=
H
k
x=
x
1
x
2
⋮
x
n
H – macierz Hesse'go,
macierz symetryczna
9.05.2013
Szczecin
8
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Rozłożyć w szereg Taylora funkcję
f x= f x
1,
x
2
=
x
1
3
2x
2
2
3x
1
x
2
x
k
=
[
1
1
]
w otoczeniu punktu
∇ =
[
3x
1
2
3x
2
4x
2
3x
1
]
H =
[
6x
1
3
3
4
]
f x=6
[
6 7
]
[
x
1
−
1
x
2
−
1
]
1
2
[
x
1
−
1 x
2
−
1
]
[
6 3
3 4
]
[
x
1
−
1
x
2
−
1
]
f x=3x
1
2
2x
2
2
3 x
1
x
2
−
3 x
1
1
f x= f x
k
∇
k
T
x−x
k
1
2
x−x
k
T
H
k
x−x
k
9.05.2013
Szczecin
9
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
f x= f x
1,
x
2
=
x
1
3
2x
2
2
3x
1
x
2
f x=3x
1
2
2x
2
2
3 x
1
x
2
−
3 x
1
1
9.05.2013
Szczecin
10
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
f x= f x
1,
x
2
=
x
1
3
2x
2
2
3x
1
x
2
f x=3x
1
2
2x
2
2
3 x
1
x
2
−
3 x
1
1
9.05.2013
Szczecin
11
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Aby w punkcie x* funkcja f(x
1
,x
2
,...,x
n
) miała bezwarunkowe
ekstremum lokalne konieczne jest zerowanie się jej
pierwszych pochodnych cząstkowych, względem każdej ze
zmiennych:
∂
f x
∂
x
j
∣
x= x
∗
=
0,
j=1,2 , , n
albo ∇ f x
∗
=
0
9.05.2013
Szczecin
12
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Aby mająca ciągłe pochodne cząstkowe do drugiego rzędu
włącznie funkcja n zmiennych f(x) miała w stacjonarnym
punkcie x* bezwarunkowe minimum lokalne konieczne jest
aby macierz jej drugich pochodnych była w tym punkcie
dodatnio półokreślona:
H x
j
0, j=1,2 , , n
9.05.2013
Szczecin
13
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Warunki konieczne istnienia ekstremum funkcji wielu
zmiennych
{
∇
f x
∗
=
0
H x
j
0, j=1,2 ,, n
H =
[
∂
2
f x
∂
x
1
2
∂
2
f x
∂
x
1
∂
x
2
⋯
∂
2
f x
∂
x
1
∂
x
n
∂
2
f x
∂
x
2
∂
x
1
∂
2
f x
∂
x
2
2
⋯
∂
2
f x
∂
x
2
∂
x
n
⋮
⋮
⋮
⋮
∂
2
f x
∂
x
n
∂
x
1
∂
2
f x
∂
x
n
∂
x
2
⋯
∂
2
f x
∂
x
n
2
]
∇
f x=
[
∂
f
∂
x
1
∂
f
∂
x
2
⋯
∂
f
∂
x
n
]
T
9.05.2013
Szczecin
14
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Aby mająca ciągłe pochodne cząstkowe do drugiego rzędu
włącznie funkcja n zmiennych F(x) miała w stacjonarnym
punkcie x* bezwarunkowe minimum lokalne wystarczające
jest aby macierz jej drugich pochodnych była w tym punkcie
dodatnio określona:
H x
j
0, j=1,2 , , n
9.05.2013
Szczecin
15
Metody optymalizacji
Definicja formy kwadratowej
Rzeczywistą formą kwadratową n zmiennych y o
macierzy symetrycznej A nazywamy wyrażenie
Różniczka zupełna rzędu drugiego jest formą
kwadratową.
y=x
T
A x=
∑
i=1
n
∑
j=1
n
a
ij
x
i
x
j
d
2
f
x
0
=
d x
0
T
H
0
d x
0
=
∑
i=1
n
∑
j=1
n
h
ij
d x
i
d x
j
9.05.2013
Szczecin
16
Metody optymalizacji
Definicja formy kwadratowej
Kryterium Sylvestera o dodatniej określoności formy
kwadratowej.
Forma kwadratowa y jest dodatnio określona jeśli
wszystkie minory główne macierzy A formy są dodatnio
określone:
a
11
0,
∣
a
11
a
12
a
21
a
22
∣
0,
9.05.2013
Szczecin
17
Metody optymalizacji
Definicja formy kwadratowej
Jeśli co najmniej jeden z minorów jest ujemny, to macierz
A nie jest dodatnio półokreślona. Jeśli każdy A
i
≥ 0, dla
każdego punktu , to macierz A jest dodatnio
półokreślona.
x∈ D
9.05.2013
Szczecin
18
Metody optymalizacji
Definicja formy kwadratowej
Forma kwadratowa jest ujemnie określona jeśli wszystkie
minory główne macierzy A formy stopnia parzystego są
dodatnio określone, natomiast wszystkie minory stopnia
nieparzystego są ujemnie określone, tj.
A
1
0, A
2
0, ,−1
n
A
n
0, dla n=2 k
oraz −1
n
A
n
0, dla n=2 k1
Forma kwadratowa jest ujemnie określona, gdy macierz
–A jest dodatnio określona.
9.05.2013
Szczecin
19
Metody optymalizacji
Ekstremum – funkcja dwóch zmiennych
Jeśli funkcja f jest klasy C
2
(tzn. jest dwukrotnie różniczkowalna i obie
pochodne są ciągłe) w otoczeniu punktu P0 = (x0, y0) i jeśli ma obie
pochodne cząstkowe 1 rzędu w tym punkcie równe zeru
f
x
P
0
=
f
y
P
0
=
0
a wyznacznik pochodnych cząstkowych 2 rzędu funkcji f jest w tym
punkcie dodatni
W P
0
=
∣
f
xx
P
0
f
xy
P
0
f
yx
P
0
f
yy
P
0
∣
0
to funkcja ta ma w punkcie P
0
ekstremum właściwe.
9.05.2013
Szczecin
20
Metody optymalizacji
Ekstremum – funkcja dwóch zmiennych
w punkcie P
0
(x
0
,y
0
) jest:
f
xx
P
0
0, f
yy
P
0
0, W P
0
0
➔
maksimum lokalne, gdy
f
xx
P
0
0, f
yy
P
0
0, W P
0
0
➔
minimum lokalne, gdy
9.05.2013
Szczecin
21
Metody optymalizacji
Metody poszukiwania ekstremum funkcji
wielu zmiennych
Metody bezgradientowe
metoda spadku względem współrzędnych,
metoda Gaussa-Seidla,
metoda Powella
,
metoda Daviesa-Swanna i Campeya,
metoda Zangwilla,
metoda Rosenbrocka
Ekstremum funkcji wielu zmiennych – metody bezgradientowe
9.05.2013
Szczecin
22
Metody optymalizacji
Wersor
Wersor (wektor jednostkowy) – wektor którego długość wynosi 1.
1
1
-1
-1
x
y
e
1
e
2
e
3
e
4
e=
{
e
1,
e
2,
e
3,
e
4
}
=
{
1
0
,
0
1
,
−
1
0
,
0
−
1
}
9.05.2013
Szczecin
23
Metody optymalizacji
Wersor
Jak z dowolnego wektora zrobić wersor kierunkowy?
-1
x
y
-3
2
1
d
P
0
=
−
3,0
P
1
=
1,2
V =
1−−3
2−0
=
4
2
∣
V∣=
4
2
2
2
=
20=2
5
d =
V
∣
V
∣
=
4
2
2
5
=
2
5
1
5
9.05.2013
Szczecin
24
Metody optymalizacji
[x
10
,x
20
]
Metody bezgradientowe – spadek względem współrzędnych
[x
1m
,x
2m
]
k – numer iteracji k=0,1,2...
e – wersor kierunkowy
α
– długość kroku
j – numer wersora kierunkowego
x
(j)k+1
=x
k
+
α
e
(j)
9.05.2013
Szczecin
25
Metody optymalizacji
Metody bezgradientowe – spadek względem współrzędnych
2 6
.5 7
2 6 . 5 7
2 6 .5 7
2 6 .5 7
2 6 .5 7
2 6 .5
7
1 7 .3 7
1 7 .3 7
1 7 .
3 7
17
.3
7
1 7 .3 7
1 7 .3 7
1 7 .
3 7
1 1
.7 7
1 1 .7 7
1 1 .7
7
11
.7
7
1 1 .7 7
1 1 . 7 7
1 1
.7
7
X
Y
6 .5
7
6 . 5 7
6 .
5 7
6 . 5 7
6 . 5 7
2 .9
7
2 . 9 7
2 . 9 7
2.
97
1 . 3 7
1 .3
7
0 . 1 7
0
0 . 1 7
- 4
- 3
- 2
- 1
0
1
2
3
4
- 4
- 3
- 2
- 1
0
1
2
3
4
9.05.2013
Szczecin
26
Metody optymalizacji
Metody bezgradientowe – spadek względem współrzędnych
2 6 .
5 7
2 6 .5 7
2 6 .5 7
2 6 .5
7
2 6 .5 7
2 6 .5 7
2 1
.4 7
2 1 .4 7
2 1 .4 7
2 1
.4 7
2 1 .4 7
2 1 .4 7
1 7 .3
7
1 7 .3 7
1 7 .3
7
17
.3
7
1 7 .3
7
1 7 .3 7
1 7 .3 7
X
Y
1 4
.2 7
1 4 .2 7
1 4 .2 7
1 4
.2
7
1 4 .2
7
1 4 .2 7
1 4 .2
7
1 1
.2 2
1 1 .2 2
1 1 .2
2
11
.2
2
1 1 .2 2
1 1 .2 2
11
.2
2
8 . 6
7
8 . 6 7
8 .
6 7
8 . 6 7
8 . 6 7
8 .
6 7
6 . 5 7
6 . 5 7
6.5
7
6 . 5 7
6 . 5
7
4 . 5 2
4 . 5
2
4 . 5 2
4 . 5
2
2 .9
7
2 . 9 7
2 . 9 7
2 .
9 7
1 . 8 7
1 . 8
7
1 .
8 7
0 . 8 2
0 . 8 2
0
0 . 1 2
- 4
- 3
- 2
- 1
0
1
2
3
4
- 4
- 3
- 2
- 1
0
1
2
3
4
9.05.2013
Szczecin
27
Metody optymalizacji
Metody bezgradientowe – spadek względem współrzędnych
2 6 . 5 7
2 6 .5 7
2 6 .5 7
2 6 .5 7
2 6 .5 7
2 6 . 5 7
2 4
.4 1
2 4 .4 1
2 4 .4 1
2 4 .4
1
2 4 .4 1
2 4 .4 1
2 2
.4 1
2 2 .4 1
2 2 .4 1
2 2
.4 1
2 2 .4 1
2 2 .4 1
X
Y
2 0
.5 7
2 0 . 5 7
2 0 .5 7
2 0 .5
7
2 0
.5 7
2 0 .5 7
2 0 .5 7
2 0
.5 7
1 8
.8
9
1 8 . 8 9
1 8 .8 9
1 8 .8
9
1 8
.8 9
1 8 .8 9
1 8 .8 9
1 8
.8 9
1 7 .3 7
1 7 .3 7
1 7
.3 7
1 7
.3
7
1 7 .3 7
1 7 .3 7
1 7
.3 7
1 6 .0
1
1 6 .0 1
1 6 .0
1
16
.0
1
1 6 .0 1
1 6 .0 1
1 6 .0
1
1 4
.7 3
1 4 .7 3
1 4 .7 3
1 4
.7
3
1 4 .7
3
1 4 .7 3
1 4 .7
3
1 3 .5 3
1 3 . 5 3
1 3 .
5 3
1 3
.5
3
1 3 .5 3
1 3 .5 3
1 3
.5
3
1 2
.3 3
1 2 .3 3
1 2 .3 3
12
.3
3
1 2 .3 3
1 2 .3 3
1 2
.3 3
1 1
.2 1
1 1 .2 1
1 1 .2
1
11
.2
1
1 1 .2 1
1 1 .2 1
11
.2
1
1 0 .1 7
1 0 .1 7
10
.1
7
1 0 .1 7
1 0 .1 7
10
.1
7
9 . 1 3
9 . 1 3
9 .
1 3
9 . 1 3
9 . 1 3
9 .
1 3
0
0 . 0 1
- 4
- 3
- 2
- 1
0
1
2
3
4
- 4
- 3
- 2
- 1
0
1
2
3
4
9.05.2013
Szczecin
28
Metody optymalizacji
Metody bezgradientowe – spadek względem współrzędnych
Zad.1 Znajdź minimum podanej funkcji metodą spadku względem
współrzędnych.
min f x , y =2 x
2
y
2
x
0
y
0
=
−
3
3
=
1
e=
{
1
0
,
0
1
,
−
1
0
,
0
−
1
}
f x
0,
y
0
=
27
9.05.2013
Szczecin
29
Metody optymalizacji
Metody bezgradientowe – spadek względem współrzędnych
e=
{
1
0
,
0
1
,
−
1
0
,
0
−
1
}
x
1
y
1
=
x
0
y
0
1
0
=
−
3
3
1⋅
1
0
=
−
2
3
f −2,3=17
K1.1
x
1
y
1
=
x
0
y
0
0
1
=
−
3
3
1⋅
0
1
=
−
3
4
f −3,4=34
K1.2
x
1
y
1
=
x
0
y
0
−
1
0
=
−
3
3
1⋅
−
1
0
=
−
4
3
f −4,3=41
K1.3
x
1
y
1
=
x
0
y
0
0
−
1
=
−
3
3
1⋅
0
−
1
=
−
3
2
f −3,2=22
K1.4
[x
0
,y
0
]
[x
1
,y
1
]
9.05.2013
Szczecin
30
Metody optymalizacji
Metody bezgradientowe – spadek względem współrzędnych
e=
{
1
0
,
0
1
,
−
1
0
,
0
−
1
}
x
2
y
2
=
x
1
y
1
1
0
=
−
2
3
1⋅
1
0
=
−
1
3
f −1,3=11
K2.1
K2.2
K2.3
[x
0
,y
0
]
[x
1
,y
1
]
[x
2
,y
2
]
x
2
y
2
=
x
1
y
1
0
1
=
−
2
3
1⋅
0
1
=
−
2
4
f −2,4=24
x
2
y
2
=
x
1
y
1
0
−
1
=
−
2
3
1⋅
0
−
1
=
−
2
2
f −2,2=12
9.05.2013
Szczecin
31
Metody optymalizacji
Minimalizacja funkcji w zadanym kierunku poszukiwań
X
Y
(x
0
,y
0
)
(x
1
,y
1
)
d
X
Y
Z
(x
0
,y
0
)
(x
1
,y
1
)
d =
d
x
d
y
9.05.2013
Szczecin
32
Metody optymalizacji
Minimalizacja funkcji w zadanym kierunku poszukiwań
x
1
y
1
=
x
0
y
0
⋅
d
d =
d
x
d
y
−
krok
F x
0
d
x
, y
0
d
y
F
9.05.2013
Szczecin
33
Metody optymalizacji
Minimalizacja funkcji w zadanym kierunku poszukiwań
Metody bezgradientowe – metoda Gaussa-Seidla
9.05.2013
Szczecin
34
Metody optymalizacji
[x
m
,y
m
]
Metody bezgradientowe – metoda Gaussa-Seidla
k – numer iteracji k=0,1,2...
e – wersor kierunkowy
α
– długość kroku
j – numer wersora kierunkowego
x
(j)k+1
=x
k
+
α
e
(j)
[x
0
,y
0
]
9.05.2013
Szczecin
35
Metody optymalizacji
Metody bezgradientowe – metoda Gaussa-Seidla
Zad.2 Znajdź minimum podanej funkcji metodą Gaussa-Seidla.
min f x , y =2 x
2
y
2
x
0
y
0
=
−
3
3
e=
1
0
d
1
,
0
1
d
2
f x
0,
y
0
=
27
Dwa kierunki poszukiwań
9.05.2013
Szczecin
36
Metody optymalizacji
Minimalizacja w kierunku d
1
Metody bezgradientowe – metoda Gaussa-Seidla
K1.1
x
1
y
1
=
x
0
y
0
⋅
d
1
=
−
3
3
⋅
1
0
=
−
3
3
f =2−3
2
3
2
=
2
2
−
12 27
min f x , y =2 x
2
y
2
min f
d f
d
=
4 −12=0
=
3
x
1
y
1
=
−
3
3
=
−
33
3
=
0
3
f 0,3=9
9.05.2013
Szczecin
37
Metody optymalizacji
Minimalizacja w kierunku d
2
Metody bezgradientowe – metoda Gaussa-Seidla
K1.2
x
1
y
1
=
x
0
y
0
⋅
d
2
=
−
3
3
⋅
0
1
=
−
3
3
f =2−3
2
3
2
=
2
6 27
min f x , y =2 x
2
y
2
min f
d f
d
=
2 6=0 =−3
x
1
y
1
=
−
3
3
=
−
3
3−3
=
−
3
0
f −3,0=18
9.05.2013
Szczecin
38
Metody optymalizacji
Minimalizacja w kierunku d
2
Metody bezgradientowe – metoda Gaussa-Seidla
K 2
x
2
y
2
=
x
1
y
1
⋅
d
2
=
0
3
⋅
0
1
=
0
3
f =3
2
=
2
6 9
min f x , y =2 x
2
y
2
min f
d f
d
=
2 6=0 =−3
x
2
y
2
=
0
3
=
0
3−3
=
0
0
f 0,0=0
9.05.2013
Szczecin
39
Metody optymalizacji
d
i
T
⋅
H⋅d
j
=
0 dla i≠ j
Kierunki (wektory) d
i
i d
j
nazywamy sprzężonymi względem
kwadratowej dodatnio określonej macierzy H jeżeli:
Metody bezgradientowe – metoda Powella
9.05.2013
Szczecin
40
Metody optymalizacji
Jeżeli startując z punktu początkowego x
0
w kierunku d
minimum funkcji kwadratowej F(x) osiągamy w punkcie x
a
, a
startując z innego punktu
w tym samym kierunku d minimum
otrzymamy w x
b
, to przy F(x
b
) < F(x
a
) kierunek (x
b
– x
a
) jest
sprzężony z kierunkiem d względem hesjanu H.
x
1
≠
x
0
x
y
d
d
x
a
x
1
x
0
x
b
x
b
-x
a
0
Metody bezgradientowe – metoda Powella
9.05.2013
Szczecin
41
Metody optymalizacji
[x
m
,y
m
]
Y
X
x
k+1
=x
k
+
α
d
(j)k
d
10
=[1 0]
T
d
20
=[0 1]
T
F(x
0
,y
0
)=const
x
0
x
1
x
2
d
30
=
x
2
−
x
0
∣
x
2
−
x
0
∣
Metody bezgradientowe – metoda Powella
9.05.2013
Szczecin
42
Metody optymalizacji
Metody bezgradientowe – metoda Powella
Zad.3 Punkty p
0
= (-3,0) i p
2
= (1,2) wyznaczają kierunek poszukiwań
d
3
minimum funkcji f(x,y) = x
2
+2y
2
. Sprawdź, czy kierunek d
3
jest
sprzężony z kierunkiem d
2
= (0 1)
T
. Dokonaj minimalizacji funkcji w
kierunku d
3
.
min f x , y =x
2
2y
2
Wyznaczamy wersor kierunkowy d
3
d
3
=
13 2−0
T
13
2
2−0
2
=
4 2
T
2
5
=
2
5
1
5
∣
d
3
∣
=
2
5
2
1
5
2
=
4
5
1
5
=
1
9.05.2013
Szczecin
43
Metody optymalizacji
Metody bezgradientowe – metoda Powella
Sprawdzamy czy kierunek d
3
jest sprzężony z kierunkiem d
2
.
det
0
2
5
1
1
5
=−
2
5
=−
0.894
∣
−
0.894
∣
=
0.8940.7
9.05.2013
Szczecin
44
Metody optymalizacji
Metody bezgradientowe – metoda Powella
Minimalizacja w kierunku d
3
x
3
y
3
=
x
2
y
2
⋅
d
3
=
1
2
⋅
2
5
1
5
=
1
2
5
2
1
5
f =
1
2
5
2
2
2
1
5
2
=
6
5
2
12
5
9
min f
d f
d
=
12
5
12
5
=
0
=−
5
x
2
y
2
=
1
2
x
3
y
3
=
−
1
1
f −1,1=3
min f x , y =x
2
2y
2
9.05.2013
Szczecin
45
Metody optymalizacji
Metody poszukiwania ekstremum funkcji
wielu zmiennych
Ekstremum funkcji wielu zmiennych – metody gradientowe
Metody gradientowe
metoda gradientu prostego,
metoda najszybszego spadku,
metoda gradientu sprzężonego,
metoda Newtona
9.05.2013
Szczecin
46
Metody optymalizacji
W metodach gradientowych poszukujemy ekstremum
funkcji wielu zmiennych w sposób iteracyjny, który
polega na określeniu w każdym kroku iteracji kierunku
poszukiwań (kierunku użytecznego), z wykorzystaniem
gradientu funkcji celu.
Ekstremum funkcji wielu zmiennych – metody gradientowe
9.05.2013
Szczecin
47
Metody optymalizacji
Metody gradientowe – gradient prosty
Y
X
F(x,y)=const
x
0
x
min
x
k 1
= x
k
−
k
∇
k
k – numer iteracji k=0,1,2...
α
κ
– długość w danym kroku
k
=
∥∇
k
∥
λ
κ
– stała długość w danym kroku
x
1
x
2
x
3
x
4
9.05.2013
Szczecin
48
Metody optymalizacji
Metody gradientowe – gradient prosty
x
k 1
= x
k
−
k
∇
k
k – numer iteracji k=0,1,2...
α
κ
– długość w danym kroku
k
=
∥∇
k
∥
λ
κ
– stała długość w danym kroku
∣∣∇∣∣−
norma euklidesowa wektora
∣∣∇∣∣=
∇
T
⋅∇ =
∑
j=1
n
∇
j
2
9.05.2013
Szczecin
49
Metody optymalizacji
Metody gradientowe – gradient prosty
∇=
[
4 x1
2 y−1
]
Zad.4 Metodą gradientu prostego znajdź minimum funkcji
min f x , y=2 x
2
y
2
x− y
p
0
=
[
3
3
]
=
0.5
f 3,3=27
9.05.2013
Szczecin
50
Metody optymalizacji
Metody gradientowe – gradient prosty
∇
0
=
[
4⋅31
2⋅3−1
]
=
[
13
5
]
Krok 1
p
0
=
[
3
3
]
0
=
∇
0
T
⋅∇
0
=
0.5
[
13 5
]
[
13
5
]
=
0.036
p
1
=
p
0
−
0
⋅∇
0
=
[
3
3
]
−
0.036⋅
[
13
5
]
=
[
2.53
2.82
]
f 2.53,2 .82=20.46
9.05.2013
Szczecin
51
Metody optymalizacji
Metody gradientowe – gradient prosty
∇
1
=
[
11.12
4.46
]
Krok 2
p
1
=
[
2.53
2.82
]
1
=
∇
1
T
⋅∇
1
=
0.5
12.05
=
0.042
p
2
=
p
1
−
1
⋅∇
1
=
[
2.53
2.82
]
−
0.042⋅
[
11.12
4.46
]
=
[
2.06
2.63
]
f 2.06,2 .63=14.83
9.05.2013
Szczecin
52
Metody optymalizacji
Metody gradientowe – metoda najszybszego spadku
Y
X
F(x,y)=const
x
0
x
k 1
= x
k
−
k
∇
k
k
=
∇
k
T
∇
k
∇
k
T
H
k
∇
k
x
1
x
2
x
3
x
4
x
min
9.05.2013
Szczecin
53
Metody optymalizacji
Metody gradientowe – metoda najszybszego spadku
Wersja 1
x
k 1
= x
k
−
k
∇
k
k
=
∇
k
T
∇
k
∇
k
T
H
k
∇
k
Wersja 2
F x
k
d
k
Minimalizujemy funkcję
w zadanym kierunku
d
k
d
k
=
∇
k
∣∇
k
∣
przyjmując
9.05.2013
Szczecin
54
Metody optymalizacji
Metody gradientowe – metoda najszybszego spadku
∇=
[
3 x
2
2 y
2
4 y x
−
6 z
]
Zad.5 Metodą najszybszego spadku znajdź minimum funkcji
min f x , y , z=x
3
2 x y
2
−
3 z
2
p
0
=
[
5
3
3
]
f 5,3,3=188
H =
[
6 x 4 y
0
4y
4x
0
0
0
−
6
]
9.05.2013
Szczecin
55
Metody optymalizacji
Metody gradientowe – metoda najszybszego spadku
∇
0
=
[
3⋅5
2
2⋅3
2
4⋅3⋅5
−
6⋅3
]
=
[
93
60
−
18
]
Krok 1
p
0
=
[
5
3
3
]
H
0
=
[
30 12
0
12 20
0
0
0
−
6
]
0
=
∇
0
T
⋅∇
0
∇
0
T
⋅
H
0
⋅∇
0
=
12573
463446
=
0.027
p
1
=
p
0
−
1
⋅∇
0
=
[
5
3
3
]
−
0.027⋅
[
93
60
−
18
]
=
[
2.48
1.37
3.49
]
f 2.48,1 .37,3 .49=−11.98
9.05.2013
Szczecin
56
Metody optymalizacji
Metody gradientowe – metoda najszybszego spadku
∇
1
=
[
22.21
13.59
−
20.94
]
Krok 2
p
1
=
[
2.48
1.37
3.49
]
H
1
=
[
14.88 5.48
0
5.48
9.92
0
0
0
−
6
]
1
=
∇
1
T
⋅∇
1
∇
1
T
⋅
H
1
⋅∇
1
=
0.113
p
2
=
p
1
−
1
⋅∇
1
=
[
−
0.04
−
0.17
5.86
]
f −0.04 ,−0.17,5 .86=−103.02
9.05.2013
Szczecin
57
Metody optymalizacji
Metody gradientowe – metoda Newtona
x
k 1
= x
k
−
k
∇
k
k
=
H
k
−
1
Wersja 1
Wersja 2
F x
k
d
k
Minimalizujemy funkcję
w zadanym kierunku
d
k
d
k
=
H
k
−
1
∇
k
∣
H
k
−
1
∇
k
∣
przyjmując
9.05.2013
Szczecin
58
Metody optymalizacji
Metody gradientowe – metoda Newtona
Zad.6 Metodą Newtona znajdź minimum funkcji
min f x , y , z=x
3
2 y
2
2 z
3
x
0
=
[
2
1
1
]
x
k 1
= x
k
−
k
∇
k
k
=
H
k
−
1
Wersja 1
∇=
[
3 x
2
4 y
6 z
2
]
H =
[
6 x 0
0
0
4
0
0
0 12 z
]
9.05.2013
Szczecin
59
Metody optymalizacji
Metody gradientowe – metoda Newtona
min f x , y , z=x
3
2 y
2
2 z
3
x
0
=
[
2
1
1
]
f 2,1 ,1=2
3
2⋅1
2
2⋅1
3
=
12
∇
0
=
[
3⋅2
2
4⋅1
6⋅1
2
]
=
[
12
4
6
]
H
0
=
[
12 0
0
0
4
0
0
0 12
]
inv H
0
=
[
1
12
0
0
0
1
4
0
0
0
1
12
]
9.05.2013
Szczecin
60
Metody optymalizacji
Metody gradientowe – metoda Newtona
∇
0
=
[
3⋅2
2
4⋅1
6⋅1
2
]
=
[
12
4
6
]
H
0
=
[
12 0
0
0
4
0
0
0 12
]
inv H
0
=
[
1
12
0
0
0
1
4
0
0
0
1
12
]
p
1
=
p
0
−
inv H
0
⋅∇
0
=
[
2
1
1
]
−
[
1
12
0
0
0
1
4
0
0
0
1
12
]
⋅
[
12
4
6
]
=
[
1
0
1
2
]
f 1,0 ,
1
2
=
1.25
Krok 1
9.05.2013
Szczecin
61
Metody optymalizacji
Metody gradientowe – metoda Newtona
∇
1
=
[
3
0
1
2
]
H
1
=
[
6 0 0
0 4 0
0 0 6
]
inv H
0
=
[
1
6
0
0
0
1
4
0
0
0
1
6
]
p
2
=
p
1
−
inv H
1
⋅∇
1
=
[
1
0
1
2
]
−
[
1
6
0
0
0
1
4
0
0
0
1
6
]
⋅
[
3
0
1
2
]
=
[
1
2
0
1
4
]
f
1
2
,0 ,
1
2
=
0.15625
Krok 2