2008-03-05
Szczecin
1
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
2
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
3
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
4
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
5
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
6
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
7
Metody optymalizacji, Informatyka
Ekstremum funkcji wielu zmiennych
Warunki konieczne 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
2008-03-05
Szczecin
8
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
9
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
10
Metody optymalizacji, Informatyka
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
}
2008-03-05
Szczecin
11
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
12
Metody optymalizacji, Informatyka
[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)
2008-03-05
Szczecin
13
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
14
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
15
Metody optymalizacji, Informatyka
Minimalizacja funkcji w zadanym kierunku poszukiwań
Metody bezgradientowe – metoda Gaussa-Seidla
2008-03-05
Szczecin
16
Metody optymalizacji, Informatyka
[x
m
,y
m
]
[x
0
,y
0
]
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)
2008-03-05
Szczecin
17
Metody optymalizacji, Informatyka
Metody bezgradientowe – metoda Gaussa-Seidla – przykład
x
1
y
1
=
x
0
y
0
⋅d
1
=
−3
3
⋅
1
0
=
−3
3
x
0
y
0
=
−3
3
f
x , y=2 x
2
y
2
d
1
=e
1
=
1
0
d
2
=e
2
=
0
1
Krok 1 – Minimalizacja w kierunku d
1
f
−3 ,3=2−3
2
3
2
=2
2
−1227= f
min f
∂ f
∂
=4 −12=0 =3
x
1
y
1
=
−3
3
=
0
3
f
0,3=9
2008-03-05
Szczecin
18
Metody optymalizacji, Informatyka
Metody bezgradientowe – metoda Gaussa-Seidla – przykład
x
2
y
2
=
x
1
y
1
⋅d
2
=
0
3
⋅
0
1
=
0
3
x
0
y
0
=
−3
3
f
x , y=2 x
2
y
2
d
1
=e
1
=
1
0
d
2
=e
2
=
0
1
Krok 2 – Minimalizacja w kierunku d
2
f
0,3=
2
6 9= f
min f
∂ f
∂
=2 6=0 =−3
x
2
y
2
=
0
3
=
0
0
f
0,0=0
2008-03-05
Szczecin
19
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
20
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
21
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
22
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
23
Metody optymalizacji, Informatyka
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
2008-03-05
Szczecin
24
Metody optymalizacji, Informatyka
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