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