Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych x,
należącego do zbioru rozwiązań dopuszczalnych R
n
takiego, że dla
n
R
∈
∀x
Co jest równoznaczne zapisowi
:
∧
x
( )
x
x
f
f
≤
∧
( )
=
∧
∈
x
x
x
f
f
n
R
min
( )
1
:
R
R
f
n
→
x
Funkcja celu f(x) :
Sformu
Sformu
ł
ł
owanie zadania optymalizacji
owanie zadania optymalizacji
nieliniowej
nieliniowej
bez ogranicze
bez ogranicze
ń
ń
:
:
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Zadanie programowania nieliniowego bez ograniczeń
DEFINICJA.
Kierunkiem d w przestrzeni R
n
nazywamy dowolny n-wymiarowy wektor
kolumnowy. Niech będzie dany punkt
oraz skalar
Dowolny punkt
leżący na półprostej wychodzącej z
punktu x w kierunku
będzie wówczas określony zależnością
LEMAT.
Niech
będzie funkcją różniczkowalną w punkcie
Załóżmy, że istnieje d, dla którego:
Wówczas istnieje takie
,że dla wszystkich zachodzi
n
R
∈
x
).
;
0
[ +∞
∈
τ
n
R
∈
y
0
≠
d
d
x
y
τ
+
=
1
:
R
R
f
n
→
=
X
X
x
0
∈
,
0
),
(
0
<
∇
d
x
f
,
0
>
σ
]
,
0
(
σ
τ
∈
).
(
)
(
0
0
x
f
d
x
f
<
+
τ
Dowód: wynika z własności różniczki Gateaux.
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Zadanie programowania nieliniowego bez ograniczeń
∧
x
Twierdzenie. Niech
będzie funkcją różniczkowalną . Jeśli
minimalizuje funkcję f(x)
tzn.
1
:
R
R
f
n
→
=
X
0
)
ˆ
(
to
,
),
(
)
(
=
∇
∈
∀
≤
∧
x
X
x
x
x
f
f
f
Dowód: nie wprost.
Twierdzenie. Niech
będzie funkcją wypukłą i
różniczkowalną. Punkt
stanowi minimum funkcji f(x), tzn.
dla każdego wtedy i tylko wtedy, gdy spełnia warunek
1
:
R
R
X
f
n
→
=
ˆ X
∈
x
),
(
)
ˆ
(
x
f
x
f
≤
0
)
ˆ
(
=
∇ x
f
Punkt jest nazywany
punktem stacjonarnym.
∧
x
X
x ∈
Jest to warunek konieczny istnienia ekstremum lokalnego f(x) w punkcie .
∧
x
X
x ∈
∧
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Minimum lokalne i globalne funkcji
f(x)
Punkt stanowi
minimum lokalne
funkcji f(x) w przestrzeni R
n
, jeżeli istnieje takie
otwarte otoczenie punktu , że
∧
x
∧
x
)
(
)
(
x
f
x
f
E
x
≤
∈
∀
∧
Przy czym jeśli zachodzi
)
(
)
(
x
f
x
f
<
∧
dla to istnieje wtedy
ścisłe minimum lokalne.
∧
≠ x
x
n
R
E ⊂
Punkt stanowi
minimum globalne
funkcji f(x) w przestrzeni R
n
, jeżeli istnieje takie
otwarte otoczenie R
n
punktu , że
)
(
)
(
x
f
x
f
R
x
n
≤
∈
∀
∧
Przy czym jeśli zachodzi dla to ten punkt stanowi ścisłe minimum
globalne.
)
(
)
(
x
f
x
f
<
∧
∧
≠ x
x
∧
x
∧
x
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Minimum globalne funkcji f(x)
Jeśli
będzie funkcją ściśle wypukłą i
różniczkowalną, to wektor
spełniający warunek
konieczny
jest jedynym minimum globalnym
funkcji f(x).
1
:
R
R
X
f
n
→
=
0
)
ˆ
(
=
∇ x
f
Twierdzenie:
ˆ X
∈
x
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Warunki wystarczające optymalizacji dla zadania bez ograniczeń
i
A
)
(
2
1
2
1
x
x
f
A
∂
∂
=
)
(
.....
)
(
......
.....
)
(
.....
)
(
2
2
1
2
1
2
2
1
2
x
x
f
x
x
x
f
x
x
x
f
x
x
f
A
i
i
i
i
∂
∂
∂
∂
∂
∂
∂
∂
=
Funkcja f(x) jest funkcją ciągłą i dwukrotnie różniczkowalną. Posiada macierz
drugich pochodnych (hesjan) - A
Macierz A posiada ciąg podwyznaczników głównych
)
(
...
)
(
...
)
(
...
...
...
...
...
)
(
...
)
(
...
)
(
...
...
...
...
...
)
(
...
)
(
...
)
(
2
2
2
1
2
2
2
2
1
2
1
2
1
2
2
1
2
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
x
f
A
n
i
n
n
n
i
i
i
n
i
n
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
=
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Warunki stacjonarności dla zadania optymalizacji nieliniowej bez
ograniczeń cd.
Twierdzenie:
Założono, że jest punktem stacjonarnym funkcji f(x). Wówczas zachodzą poniższe
zależności:
1.
Jeśli hesjan A jest dodatnio określony tzn: to
funkcja f(x) ma minimum lokalne w tym punkcie
2. Jeśli hesjan A jest ujemnie określony tzn: to
funkcja f(x) ma maksimum lokalne w tym punkcie
3. Jeśli hesjan A jest pół-dodatnio określony tzn:
bądź hesjan pół-ujemnie określony
to nie można rozstrzygnąć o typie ekstremum funkcji f(x) w tym punkcie
4. Jeśli nie są spełnione warunki 1 i 2 z nieostrymi nierównościami (wówczas hesjan A
nie jest określony) to funkcja f(x) nie ma ekstremum w punkcie
0
)
(
1
,...,
1
0
)
(
=
−
=
≥
∧
∧
n
i
x
A
oraz
n
i
dla
x
A
n
i
dla
x
A
i
,...,
1
0
)
(
=
>
∧
( )
n
i
dla
x
A
i
i
,...,
1
0
)
(
1
=
>
−
∧
∧
x
( )
0
)
(
1
,...,
1
0
)
(
1
=
−
=
≥
−
∧
∧
n
i
i
x
A
oraz
n
i
dla
x
A
∧
x
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Warunek stacjonarności:
poprawić gradient i hesjan A
)
(
2
∧
∇
=
x
f
A
0
)
(
>
∧
d
x
A
d
T
TWIERDZENIE. Jeśli funkcja f(x) jest dwukrotnie różniczkowalna, to w każdym jej
minimum lokalnym bez ograniczeń spełnione są następujące warunki konieczne
optymalności zadania ZPN bez ograniczeń.
0
=
∇
∧
x
f
•Warunek I rzędu jest często nazywamy warunkiem stacjonarności, ponieważ
oznacza zerowanie się pierwszej pochodnej.
•Warunek II rzędu dla funkcji dwukrotnie różniczkowalnych implikuje lokalną
wypukłość minimalizowanej funkcji celu.
)
(x
f
∇
warunek II rzędu
warunek I rzędu
dla
0
≠
∀d
Macierz A jest macierzą ściśle dodatnio określoną
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Sformułowanie zadania optymalizacji nieliniowej
z ograniczeniami PN :
.
:
oraz
:
},
,...,
1
,
0
)
(
:
{
:
gdzie
),
(
min
)
ˆ
(
1
1
R
R
X
g
R
R
X
f
m
i
g
X
f
f
n
i
n
i
X
→
=
→
=
=
≤
=
=
∈
x
x
x
x
x
Znaleźć
takie, że:
∧
x
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Sformułowanie zadania optymalizacji nieliniowej
z ograniczeniami
DEFINICJA. Kierunek d poprowadzony z punktu x jest
DEFINICJA. Kierunek d poprowadzony z punktu x jest
dopuszczalny, je
dopuszczalny, je
ś
ś
li istnieje takie
li istnieje takie
ż
ż
e dla dowolnego
e dla dowolnego
gdzie X
gdzie X
0
0
oznacza zbi
oznacza zbi
ó
ó
r okre
r okre
ś
ś
lony jako PN.
lony jako PN.
Zbi
Zbi
ó
ó
r wszystkich kierunk
r wszystkich kierunk
ó
ó
w dopuszczalnych :
w dopuszczalnych :
,
],
;
0
[
X
∈
+
∈
d
x
τ
σ
τ
0
>
σ
}.
]
;
0
[
że
takie,
0
:
{
)
(
X
d
x
D
∈
+
⇒
∈
>
∃
=
d
x
τ
σ
τ
σ
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Funkcja Lagrange’a
DEFINICJA.
Funkcją Lagrange’a zadania PN nazywamy skalarną
funkcję
gdzie
jest wektorem mnożników Lagrange’a.
,
)
(
,
)
(
)
(
x
λ
x
λ
x,
g
f
L
+
=
n
R
∈
λ
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Ograniczenia aktywne:
]
,
0
[
czym
przy
)
ˆ
(
,
0
)
ˆ
(
.
1
τ
τ
τ
∈
∈
∀
≤
+
x
d
x
A
i
g
i
0
)
(
),
ˆ
(
)
ˆ
(
)
ˆ
(
g
.
2
i
≤
+
∇
+
=
+
τ
τ
τ
O
g
g
i
i
d
x
x
d
x
)
ˆ
(
,
0
),
ˆ
(
x
d
x
A
i
g
i
∈
∀
≤
∇
3. warunkiem koniecznym na to, aby kierunek d był
dopuszczalny jest:
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Lemat Farkasa
Niech będzie dany w R
n
zbiór n-wymiarowych wektorów
Nierówność
zachodzi dla każdego
spełniającego
Wtedy i tylko wtedy, gdy istnieje
takie, że
}.
,...,
1
,
,
{
m
i
a
b
i
=
0
,
≥
x
b
,
n
R
x∈
,
0
,
≥
−
x
a
i
0
]
,...,
[
1
≥
=
T
m
λ
λ
λ
∑
=
=
+
m
i
i
a
b
1
1
.
0
λ
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Wzajemnie rozłączne zbiory kierunków
≥
>
∇
<
∈
≤
>
∇
<
=
∧
∧
∧
∧
0
),
(
),
(
,
0
),
(
:
)
(
1
d
x
f
x
A
i
d
x
g
d
x
D
i
<
>
∇
<
∈
≤
>
∇
<
=
∧
∧
∧
∧
0
),
(
),
(
,
0
),
(
:
)
(
2
d
x
f
x
A
i
d
x
g
d
x
D
i
∈
>
>
∇
<
=
∧
∧
∧
)
(
0
),
(
:
)
(
3
x
A
i
pewnych
dla
d
x
g
d
x
D
i
)
(
)
(
)
(
)
(
3
2
1
∧
∧
∧
∧
∪
∪
=
x
D
x
D
x
D
x
D
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Warunki konieczne Kuhn’a-Tucker’a-Karusch’a
TWIERDZENIE. Jeśli
a)funkcje
są różniczkowalne;
b)
jest lokalnym minimum ZPN, to istnieje
Takie, że
i
g
f
i
xˆ
.
ˆ
dim
,
0
ˆ
m
=
≥
λ
λ
m,
1,...,
i
,
0
)
ˆ
(
ˆ
0
)
ˆ
(
ˆ
)
ˆ
(
1
=
=
=
∇
+
∇
∑
=
x
x
λ
x
i
i
m
i
i
i
g
g
f
λ
Wtedy i tylko wtedy, gdy
φ
=
)
ˆ
(
2
x
D
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Dowód warunków koniecznych Kuhn’a-Tucker’a-Karusch’a
DOWÓD. Niech
oraz
wówczas zgodnie z lematem Farkasa, istnieje
takie, że
wtedy i tylko wtedy, gdy
Spełniającego warunek dla ograniczeń:,
tzn. wtedy i tylko wtedy, gdy
)
ˆ
(x
f
b
∇
=
)
ˆ
(
),
ˆ
(
x
x
A
i
g
a
i
i
∈
∀
∇
=
)
ˆ
(
,
0
ˆ
x
A
i
i
∈
≥
λ
∑
∈
−∇
=
∇
)
ˆ
(
))
ˆ
(
(
ˆ
)
ˆ
(
x
x
x
A
i
i
i
g
f
λ
,
,
0
ˆ
(
n
R
f
∈
∀
≥
∇
d
d
),
x
φ
=
)
ˆ
(
2
x
D
)
ˆ
(
,
0
),
ˆ
(
x
d
x
A
i
g
i
∈
∀
≤
∇
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Dowód warunków koniecznych Kuhn’a-Tucker’a-Karusch’a
Dla należy przyjąć
)
ˆ
(x
A
i ∉
0
ˆ =
i
λ
Wi
Wi
ę
ę
c s
c s
ą
ą
spe
spe
ł
ł
nione dwa r
nione dwa r
ó
ó
wnania:
wnania:
m,
1,...,
i
,
0
)
ˆ
(
ˆ
0
)
ˆ
(
ˆ
)
ˆ
(
1
=
=
=
∇
+
∇
∑
=
x
x
λ
x
i
i
m
i
i
g
g
f
λ
Ckd
Ckd
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Warunki konieczne Kuhn’a-Tucker’a-Karusch’a z wykorzystaniem
funkcji Lagrange’a
.
)
(
)
(
)
(
1
∑
=
+
=
m
i
i
i
g
f
L
x
x
λ
x,
λ
warunki konieczne:
,
0
)
ˆ
ˆ
(
=
∇
λ
,
x
L
x
0
)
ˆ
ˆ
(
,
ˆ
=
∇
λ
,
x
λ
L
λ
0
)
ˆ
ˆ
(
≤
∇
λ
,
x
L
λ
0
ˆ ≥
λ
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Warunki wystarczające optymalizacji określane jako
warunki regularności ograniczeń:
1. Wszystkie funkcje ogranicze
1. Wszystkie funkcje ogranicze
ń
ń
g
g
i
i
(x
(x
) s
) s
ą
ą
liniowe
liniowe
–
–
warunek
warunek
regularno
regularno
ś
ś
ci Karlina.
ci Karlina.
2.
Wszystkie funkcje ogranicze
Wszystkie funkcje ogranicze
ń
ń
g
g
i
i
(x
(x
) s
) s
ą
ą
funkcjami wypuk
funkcjami wypuk
ł
ł
ymi
ymi
oraz zbi
oraz zbi
ó
ó
r rozwi
r rozwi
ą
ą
za
za
ń
ń
dopuszczalnych ma niepuste wn
dopuszczalnych ma niepuste wn
ę
ę
trze
trze
–
–
warunek regularno
warunek regularno
ś
ś
ci
ci
Slatera
Slatera
3. Gradienty wszystkich ograniczeń aktywnych, a więc
dla
są liniowo niezależne – warunek regularności
Fiacco i McCormicka.
),
(
∧
∇
x
g
i
),
(
∧
∈
x
A
i
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Twierdzenie Kuhn’a-Tucker’a-Karusch’a – warunki konieczne i
wystarczające dla zadania optymalizacji nieliniowej z ograniczeniami
TWIERDZENIE. Jeśli
a)funkcje
są różniczkowalne;
b)
jest lokalnym minimum ZPN,
c) Warunek regularności ograniczeń Kuhn’a-Tucker’a-
Karusch’a jest spełniony w
to istnieje
Takie, że w punkcie zachodzą warunki konieczne
Kuhn’a-Tucker’a.
i
g
f
i
.
ˆ
dim
,
0
ˆ
m
=
≥
λ
λ
m,
1,...,
i
,
0
)
ˆ
(
ˆ
0
)
ˆ
(
ˆ
)
ˆ
(
1
=
=
=
∇
+
∇
∑
=
x
x
λ
x
i
i
m
i
i
i
g
g
f
λ
∧
x
xˆ
xˆ
Wyszukiwarka
Podobne podstrony:
2w timo 2011
1w timo 2011
11w timo 2011
7w timo 2011
6w timo 2011
5w timo 2011 cz2
3w timo 2011
8w timo 2011
10w timo 2011
4w timo 2011 cz1
4w timo 2011 cz1
9w to optym lokalna bez ogran 2011
9w to optym lokalna bez ogran 2011
2011 2 KOSZE
higiena dla studentów 2011 dr I Kosinska
Plan pracy na 2011 pps
W 8 Hormony 2010 2011
więcej podobnych podstron