Nieliniowe zadanie optymalizacji
statycznej bez ograniczeń - PN bez
ograniczeń
Wykład 8
dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek: Elektronika i Telekomunikacja III r.
Subkierunek: Elektronika
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
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
ń
ń
:
:
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
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
)
(
)
(
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
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
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.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
Zadanie programowania nieliniowego bez ograniczeń
X
x ∈
∧
∧
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 globalne funkcji
dla każdego wtedy i tylko wtedy, gdy
spełnia warunek
1
:
R
R
X
f
n
→
=
ˆ X
∈
x
),
(
)
ˆ
(
tzn
),
(
x
f
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
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
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
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
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
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
=
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
Warunki stacjonarności dla nieliniowej zadania optymalizacji 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
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
EiT
EiT
III r.
III r.
Sub
Sub
-
-
kier
kier
. Elektronika
. Elektronika
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ą
Wyszukiwarka
Podobne podstrony:
więcej podobnych podstron