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
Document Outline
- Slajd 1
- Slajd 2
- Slajd 3
- Slajd 4
- Slajd 5
- Slajd 6
- Slajd 7
- Slajd 8
- Slajd 9
- Slajd 10
- Slajd 11
- Slajd 12
- Slajd 13
- Slajd 14
- Slajd 15
- Slajd 16
- Slajd 17
- Slajd 18
- Slajd 19
- Slajd 20
- Slajd 21
- Slajd 22
- Slajd 23
- Slajd 24
- Slajd 25
- Slajd 26
- Slajd 27
- Slajd 28
- Slajd 29
- Slajd 30
- Slajd 31
- Slajd 32
- Slajd 33
- Slajd 34
- Slajd 35
- Slajd 36
- Slajd 37
- Slajd 38
- Slajd 39
- Slajd 40
- Slajd 41
- Slajd 42
- Slajd 43
- Slajd 44
- Slajd 45
- Slajd 46
- Slajd 47
- Slajd 48
- Slajd 49
- Slajd 50
- Slajd 51
- Slajd 52
- Slajd 53
- Slajd 54
- Slajd 55
- Slajd 56
- Slajd 57
- Slajd 58
- Slajd 59
- Slajd 60
- Slajd 61
Wyszukiwarka
Podobne podstrony:
Logika W2 2013 14 ppt
Optymalizacja w4 2013
Optymalizacja w2 pdf id 338946 Nieznany
ZJ w2 2013
Optymalizacja w1 2013
Optymalizacja w5 2013
Optymalizacja w3 2013
Logika W2 2013 14 ppt
Optymalizacja w4 2013
Optymalizacja w2 pdf id 338946 Nieznany
ITIL Podstawy W2 Budowa i optymalizacja procesów i serwisów ITIL
W2 10 2013
PPS 2013 W2
więcej podobnych podstron