Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Kategorie klasyfikacji zadań optymalizacji
Model procesu:
Statyczny
Dynamiczny
Model procesu bez ograniczeń
Model procesu z ograniczeniami
Przestrzeń rozwiązań zmiennych decyzyjnych
Zmienne rzeczywiste
Zmienne całkowitoliczbowe
Zmienne binarne
Postać funkcji celu:
Funkcja skalarna
Funkcja wektorowa
Dane o procesie niezbędne w algorytmie optymalizacji
Wartości funkcji celu
Gradient funkcji – algorytm pierwszego rzędu
Hesjan funkcji - algorytm drugiego rzędu
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Właściwe minimum lokalne:
Funkcja f(x) ma w punkcie
Funkcja f(x) ma w punkcie
w
w
ł
ł
a
a
ś
ś
ciwe minimum lokalne, je
ciwe minimum lokalne, je
Ŝ
Ŝ
eli istnieje
eli istnieje
takie,
takie,
Ŝ
Ŝ
e:
e:
0
>
δ
E
x ∈
∀
( ) ( )
x
f
x
f
<
)
przy czym
przy czym
:
:
∆
∩
= X
E
{
}
δ
<
−
<
=
∆
x
x
x
)
0
:
Słabe minimum lokalne
Funkcja f(x) ma w punkcie
Funkcja f(x) ma w punkcie
s
s
ł
ł
abe
abe
minimum lokalne, je
minimum lokalne, je
Ŝ
Ŝ
eli istnieje
eli istnieje
takie,
takie,
Ŝ
Ŝ
e
e
0
>
l
δ
l
E
x ∈
∀
( ) ( )
l
x
f
x
f
)
) ≤
przy czym
przy czym
:
:
l
l
X
E
∆
∩
=
{
}
l
l
x
x
x
δ
<
−
<
=
∆
)
0
:
∧
x
∧
x
∧
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
KaŜde minimum globalne jest minimum lokalnym, lecz nie na odwrót.
•
Zadanie optymalizacji bez ograniczeń dla
• Zadanie optymalizacji z ograniczeniami:
Zadanie programowania liniowego ZPL
Zadanie programowania nieliniowego ZPN
( )
=
∧
∈
x
x
x
f
f
X
min
n
R
X =
( )
=
∧
∈
x
x
x
f
f
X
min
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Twierdzenie Weierstrass’a
Funkcja f(x) ciągła na zwartym zbiorze rozwiązań dopuszczalnych [zbiorze
ograniczonym i domkniętym]
jest na tym zbiorze ograniczona i osiąga swe kresy tzn.: istnieją punkty
takie, Ŝe dla kaŜdego
zachodzi
:
:
X
x
x
∈
2
1
,
X
x ∈
)
(
)
(
)
(
2
1
x
f
x
f
x
f
≤
≤
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Własności funkcji wypukłych
Definicja zbioru wypuk
Definicja zbioru wypuk
ł
ł
ego:
ego:
Zbi
Zbi
ó
ó
r
r
nazywamy wypuk
nazywamy wypuk
ł
ł
ym, je
ym, je
Ŝ
Ŝ
eli dla ka
eli dla ka
Ŝ
Ŝ
dych dw
dych dw
ó
ó
ch punkt
ch punkt
ó
ó
w
w
odcinek
odcinek
łą
łą
cz
cz
ą
ą
cy te dwa punkty tak
cy te dwa punkty tak
Ŝ
Ŝ
e nale
e nale
Ŝ
Ŝ
y do X tzn.:
y do X tzn.:
n
R
X ⊂
X
x
x
∈
2
1
,
(
)
{
}
1
0
,
1
:
2
1
≤
≤
−
+
=
=
λ
λ
λ
x
x
x
x
X
Definicja funkcji wypukłej:
Niech
Niech
b
b
ę
ę
dzie zbiorem wypuk
dzie zbiorem wypuk
ł
ł
ym. Funkcj
ym. Funkcj
ę
ę
b
b
ę
ę
dziemy
dziemy
nazywali wypuk
nazywali wypuk
łą
łą
, je
, je
Ŝ
Ŝ
eli dla dowolnych dw
eli dla dowolnych dw
ó
ó
ch punkt
ch punkt
ó
ó
w
w
i dla
i dla
ka
ka
Ŝ
Ŝ
dego
dego
:
:
n
R
X ⊂
1
:
R
X
f
→
X
x
x
∈
2
1
,
[ ]
1
,
0
∈
λ
(
)
(
)
( )
(
)
( )
2
1
2
1
1
1
x
f
x
f
x
x
f
λ
λ
λ
λ
−
+
≤
−
+
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Kiedy funkcja f(x) jest wypukła
Macierz A o wymiarze nxn nazywamy hesjanem, gdy jej elementami są drugie
pochodne cząstkowe funkcji f(x):
∂
∂
∂
=
j
i
x
x
x
f
x
A
)
(
)
(
2
Lemat 1
Niech
ma ciągłe drugie pochodne cząstkowe oraz niech
będzie zbiorem wypukłym . Funkcja f(x) jest wypukła wtedy i tylko wtedy, gdy jej hesjan
A(x) jest dodatnio pół-określony dla kaŜdego
.
1
:
R
X
f
→
n
R
X ⊂
X
x ∈
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Definicja macierzy A dodatnio półokreślonej
Macierz A o wymiarze
Macierz A o wymiarze
nxn
nxn
jest dodatnio p
jest dodatnio p
ó
ó
ł
ł
-
-
okre
okre
ś
ś
lona, je
lona, je
ś
ś
li
li
0
,
≥
Ax
x
dla ka
dla ka
Ŝ
Ŝ
dego
dego
n
R
x ∈
Definicja macierzy A dodatnio określonej
Macierz A o wymiarze
Macierz A o wymiarze
nxn
nxn
jest dodatnio okre
jest dodatnio okre
ś
ś
lona, je
lona, je
ś
ś
li
li
0
,
>
Ax
x
dla ka
dla ka
Ŝ
Ŝ
dego niezerowego
dego niezerowego
n
R
x ∈
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Kryterium Sylwestra –
praktyczne sprawdzenie wypukłości funkcji f(x)
Kwadratowa macierz symetryczna A jest dodatnio p
Kwadratowa macierz symetryczna A jest dodatnio p
ó
ó
ł
ł
-
-
okre
okre
ś
ś
lona wtedy i
lona wtedy i
tylko wtedy, gdy:
tylko wtedy, gdy:
0
.
...
.
,...,
,...,
,...,
0
,
0
,
...
1
2
22
21
1
12
11
22
21
12
11
11
≥
≥
≥
nn
a
n
n
n
a
a
a
a
a
a
a
a
a
a
a
a
Kwadratowa macierz symetryczna A jest dodatnio okre
Kwadratowa macierz symetryczna A jest dodatnio okre
ś
ś
lona wtedy i tylko
lona wtedy i tylko
wtedy, gdy:
wtedy, gdy:
0
.
...
.
,...,
,...,
,...,
0
,
0
,
...
1
2
22
21
1
12
11
22
21
12
11
11
>
>
>
nn
a
n
n
n
a
a
a
a
a
a
a
a
a
a
a
a
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Rys.1 Zbiór X - wypukły
Funkcja f(x) teŜ jest wypukła
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Rys.2 Zbiór X – nie jest wypukły
Funkcja f(x) – funkcja wypukła.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Rys.3 Zbiór X – jest wypukły
Funkcja f(x) nie jest wypukła,
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Rys.4 Zbiór X – nie jest wypukły
Funkcja f(x) teŜ nie jest wypukła.
Lemat 2
Niech funkcja będzie funkcją róŜniczkowalną oraz zbiór
będzie zbiorem wypukłym.
Funkcja f(x) jest wypukła wtedy i tylko wtedy, gdy
>
−
∇
<
+
≥
0
0
0
),
(
)
(
)
(
x
x
x
f
x
f
x
f
X
x
x
∈
∀
0
,
Lemat 3
Niech funkcja , dla
będzie funkcja wypukłą, wówczas dla
dowolnego rzeczywistego α zbiór
1
:
R
X
f
→
n
R
X ⊂
{
}
α
α
≤
=
)
(
:
x
f
x
X
jest wypukły.
n
R
X ⊂
Funkcje wypukłe
)
(x
f
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Lemat 4
Niech
będzie zbiorem wypukłym. Jeśli funkcje dla
i=1,...,k są funkcjami wypukłymi oraz jeśli wielkości
skalarne s
skalarne s
ą
ą
wi
wi
ę
ę
ksze od zera
ksze od zera
dla i=1,...,k to funkcja
dla i=1,...,k to funkcja
f(x)
f(x)
jest funkcją wypukłą.
1
:
R
X
f
i
→
0
≥
i
α
( )
x
f
x
f
i
k
i
i
∑
=
=
1
)
(
α
n
R
X ⊂
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Twierdzenie 2
Dowolne minimum lokalne funkcji wypukłej f(x) na wypukłym zbiorze rozwiązań
dopuszczalnych
jest na tym zbiorze jej minimum globalnym.
Dowód:
Niech w punkcie
funkcja f(x) ma swoje minimum lokalne. Oznacza to, Ŝe
istnieje takie
, Ŝe:
gdzie:
Przyjmijmy
,
. Wybierzmy
oraz
Ze względu na wypukłość f(x) :
X
x ∈
1
n
R
X ⊂
0
>
ε
( )
( )
x
f
x
f
V
x∈
= min
1
{
}
ε
≤
−
∈
=
1
,
x
x
X
x
V
X
x ∈
2
2
1
x
x ≠
1
0
<
<
λ
(
)
V
x
x
∈
−
+
2
1
1
λ
λ
( )
(
)
( )
(
)
(
)
2
1
2
1
1
1
x
x
f
x
f
x
f
λ
λ
λ
λ
−
+
≥
−
+
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
( )
(
)
(
) ( ) ( ) ( ) ( )
1
1
1
1
2
1
2
1
1
1
x
f
x
f
x
f
x
f
x
x
f
x
f
≥
−
−
≥
−
−
−
+
≥
λ
λ
λ
λ
λ
λ
ckd
ckd
Twierdzenie 3
Ściśle wypukła funkcja f(x) określona na wypukłym zbiorze rozwiązań
dopuszczalnych X ma na tym zbiorze co najwyŜej jedno minimum.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wykład 3
Wydział Elektroniki
EiT III r. subkier. EKA
Przykład
Niech , . Wykazać, Ŝe funkcja określona
formułą liniową:
jest jednocześnie wypukła i wklęsła na R
n.
n
R
c∈
1
R
d ∈
1
:
R
R
f
n
→
( )
d
x
c
x
f
T
+
=