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ˆ