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
Sformułowanie zadania optymalizacji nieliniowej
Sformułowanie zadania optymalizacji nieliniowej
bez ograniczeń:
bez ograniczeń:
Funkcja celu f(x) :
f (x):Rn çÅ‚
çÅ‚ R1
Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych x,
nale\
ącego do zbioru rozwiązań dopuszczalnych Rn
'"
x
"x"Rn
takiego, \
e dla
'"
ëÅ‚ öÅ‚
f x d" f (x )
ìÅ‚ ÷Å‚
íÅ‚ Å‚Å‚
Co jest równoznaczne zapisowi:
'"
ëÅ‚xöÅ‚
f (x)= f
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x"Rn
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika
Minimum lokalne i globalne funkcji f(x)
'"
x
Punkt stanowi minimum lokalne funkcji f(x) w przestrzeni Rn, je\
eli istnieje takie
'"
x
E ‚" Rn
otwarte otoczenie punktu , \
e
'"
"x " E f (x) d" f (x)
'" '"
f (x) < f (x)
dla to istnieje wtedy ścisłe minimum lokalne.
x `" x
Przy czym jeśli zachodzi
'"
x
Punkt stanowi minimum globalne funkcji f(x) w przestrzeni Rn, je\
eli
'"
"x " Rn f (x) d" f (x)
'"
'"
x `" x
Przy czym jeśli zachodzi dla to ten punkt stanowi ścisłe minimum
f (x) < f (x)
globalne.
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika
Zadanie programowania nieliniowego bez ograniczeń
DEFINICJA.
Kierunkiem d w przestrzeni Rn nazywamy dowolny n-wymiarowy wektor
x"Rn
kolumnowy. Niech będzie dany punkt oraz skalar
Ä "[0;+").
y " Rn
Dowolny punkt le\
ący na półprostej wychodzącej z
d `" 0
punktu x w kierunku będzie wówczas określony zale\
nością
y = x + Ä d
LEMAT.
0
f : X = Rn R1 będzie funkcją ró\
niczkowalnÄ… w punkcie x " X
Niech
Załó\
my, \
e istnieje d, dla którego:
0
" f ( x ), d < 0 ,
Ä " (0,Ã ]
Wówczas istnieje takie à > 0, ,\
e dla wszystkich zachodzi
0 0
f ( x + Äd ) < f ( x ).
Dowód: wynika z własności ró\
niczki Gateaux.
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika
Zadanie programowania nieliniowego bez ograniczeń
f : X = Rn R1
Twierdzenie. Niech będzie funkcją ró\
niczkowalną . Jeśli
'"
x " X
minimalizuje funkcjÄ™ f(x) tzn.
'"
f (x) d" f (x), "x"X,
to
Ć
"f (x) =0
Dowód: nie wprost.
'"
x
Punkt jest nazywany punktem stacjonarnym.
f : X = Rn R1
Twierdzenie. Niech będzie funkcją wypukłą i
Ć
x"X
ró\
niczkowalnÄ…. Punkt stanowi minimum globalne funkcji
Ć
f (x), tzn f (x) d" f (x),
'"
x " X
dla ka\
dego wtedy i tylko wtedy, gdy spełnia warunek
x
Ć
"f (x) = 0
'"
Jest to warunek konieczny istnienia ekstremum lokalnego f(x) w punkcie x
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika
Minimum globalne funkcji f(x)
Twierdzenie:
f : X = Rn R1
Jeśli będzie funkcją ściśle wypukłą i
Ć
x"X
ró\
niczkowalną, to wektor spełniający warunek
konieczny jest jedynym minimum globalnym
Ć
"f (x) = 0
funkcji f(x).
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika
Warunki wystarczające optymalizacji dla zadania bez ograniczeń
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
A
i
"2 f
A1 = (x)
2
"x1
"2 f "2 f "2 f
(x) (x) (x)
2
"x1 "x1xi "x1xn
"2 f "2 f
(x) ..... (x)
2
"x1 "x1xi "2 f "2 f "2 f
A = (x) (x) (x)
A = ..... ......
n
i
"xix1 "xi2 "xixn
"2 f "2 f
(x) ..... (x)
"xix1 "xi2
"2 f "2 f "2 f
(x) (x) (x)
2
"xnx1 "xnxi "xn
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika
Warunki stacjonarności dla nieliniowej zadania optymalizacji bez
ograniczeń cd.
Twierdzenie:
'"
x
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
A(x) > 0 dla i =1,..., n
i
funkcja f(x) ma minimum lokalne w tym punkcie
'"
i
2. Jeśli hesjan A jest ujemnie określony tzn: to
(-1) A(x) > 0 dla i = 1,..., n
i
funkcja f(x) ma maksimum lokalne w tym punkcie
'" '"
A(x) e" 0 dla i = 1,..., n -1 oraz A(x) = 0
3. Jeśli hesjan A jest pół-dodatnio określony tzn:
i n
bÄ…dz
hesjan pół-ujemnie określony
'" '"
i
(-1) A(x) e" 0 dla i = 1,..., n -1 oraz A(x) = 0
i n
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
x
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika
Warunek stacjonarności:
poprawić gradient i hesjan A
"f (x)
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ń.
'"
ëÅ‚
"f xöÅ‚ = 0
ìÅ‚ ÷Å‚ warunek I rzÄ™du
íÅ‚ Å‚Å‚
'"
T
dla warunek II rzędu
d A(x) d > 0 "d `" 0
'"
A = "2 f (x)
Macierz A jest macierzą ściśle dodatnio określoną
" 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.
Technika optymalizacji Wydział Elektroniki
Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. Sub-kier. Elektronika
EiT III r. Sub-kier. Elektronika