Technika optymalizacji
Nieliniowe zadanie optymalizacji bez ograniczeń
 metody iteracyjne optymalizacji
'"
ëÅ‚
Nieliniowe zadanie optymalizacji f (x) = f xöÅ‚
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x"Rn
statycznej bez ograniczeń -
nieliniowe algorytmy optymalizacji Algorytmy poszukiwania minimum lokalnego zadania programowania
nieliniowego:
lokalnej
" Bez ograniczeń
" Z ograniczeniami
Wykład 9
dr in\
. Ewa Szlachcic
Algorytmy zbie\
ne do minimum lokalnego x*, je\
eli taki punkt istnieje.
Wydział Elektroniki
Kierunek: Elektronika i Telekomunikacja III r.
Potok: Elektronika
Technika optymalizacji
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Warunek stacjonarności: I. Techniki optymalizacji lokalnej
poprawić gradient i hesjan A
"f (x)
Ad.I Iteracyjne algorytmy optymalizacji
Algorytmy optymalizacji w kierunku
TWIERDZENIE. Jeśli funkcja f(x) jest dwukrotnie ró\
niczkowalna, to w
Algorytmy optymalizacji bez ograniczeń
ka\
dym jej minimum lokalnym bez ograniczeń spełnione są
następujące warunki konieczne optymalności zadania ZPN bez
Algorytmy optymalizacji z ograniczeniami
ograniczeń.
'"
ëÅ‚
warunek I rzędu
"f xöÅ‚ = 0
ìÅ‚ ÷Å‚
Algorytmy poszukiwania minimum lokalnego zadania programowania
íÅ‚ Å‚Å‚
warunek II rzędu nieliniowego:
" Bez ograniczeń
dT Ad e" 0, "d " Rn
" Z ograniczeniami
" Warunek I rzędu jest często nazywamy warunkiem stacjonarności,
poniewa\
oznacza zerowanie siÄ™ pierwszej pochodnej.
Algorytmy zbie\
ne do minimum lokalnego x*, je\
eli taki punkt istnieje.
" Warunek II rzędu dla funkcji dwukrotnie ró\
niczkowalnych
implikuje lokalną wypukłość minimalizowanej funkcji celu.
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
II. Techniki optymalizacji globalnej Kryteria zbie\
ności:
1. Test teoretyczny
'"
Ad.II Algorytmy optymalizacji globalnej
Ć
f (xk ) - fĆ(x) d" µ1, xk - x d" µ2
Algorytmy optymalizacji ewolucyjne
2. Przybli\
ona stacjonarność rozwiązania
Algorytmy optymalizacji genetyczne
Algorytmy optymalizacji  symulowanego wy\
arzania "f (xk ) = gk Ò! gk d" µ
Algorytmy optymalizacji TABU Search
3. Testy praktyczne:
Algorytmy optymalizacji- Harmony Search
xik - xik+1 d" µi , "i = 1,..., n
Algorytmy optymalizacji rojem czÄ…stek
lub
f (xk ) - f (xk +1) d" µ1
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
1
Technika optymalizacji
Iteracja metody poszukiwania minimum w kierunku
Do minimalizacji w kierunku mo\
na u\
yć kilku algorytmów takich
jak np.:
Algorytmy bez-gradientowe:
złotego podziału,
Przebieg typowej k-tej iteracji dowolnej metody realizujÄ…cej
aproksymacji kwadratowej,
ideę poszukiwania wzdłu\
kierunku jest następujący:
k
d .
1. Określ kierunek poszukiwań
Algorytmy gradientowe:
~
k k
2. Znajdz
ą minimalizujące f (ą ) = f (x +ąd ) ze względu na ą.
ekspansji i kontrakcji geometrycznej z testem
jednoskośnym,
k
3. Podstaw xk+1 = xk +Ä… d .
logarytmiczny złoty podział odcinka ze wstępną ekspansją
i kontrakcjÄ… geometrycznÄ…,
aproksymacji parabolicznej z testem jednoskośnym,
bisekcji z testem dwuskośnym Goldstein a,
Technika optymalizacji
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Metoda najszybszego spadku NS
Algorytm obliczeń  metoda NS
jest to metoda gradientowa, która pozwala szukać minimum ró\
niczkowalnej funkcji
nieliniowej f(x).
(1) Wybierz punkt startowy xo=xk. Oblicz wartość
Koncepcja metody wynika z lematu, w którym wykazano, \
e jeśli istnieje kierunek d w
funkcji f(xk) oraz jej gradient " f(xk)
"
"
"
przestrzeni taki, \
e
Rn
"f (x),d < 0
(2) Zbadaj kryterium zbie\
ności:
to
"f (xk ),"f (xk ) = 0 czyli "f (xk ),"f (xk ) d" µ
f (x +Äd) < f (x)
gdzie µ "[0, ´ ] np.:µ =10-6
Jeśli tak, to koniec, jeśli nie, to przejdz
do (3)
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
(3) Wyznacz kierunek poszukiwań :
k
d = -"f (xk ) Do minimalizacji w kierunku zastosowano
gradientowy algorytm bisekcji z testem dwuskośnym
(4) Wykonaj minimalizacjÄ™ kierunkowÄ…
Goldstein a :
wybranÄ… metodÄ…:
k
xk +1 "T (xk ,d )
Iteracyjny algorytm gradientowy
(5) Podstaw xk Ð! xk +1 oraz k Ð! k + 1 i powtórz (1)
Technika optymalizacji
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
2
Technika optymalizacji
Działanie algorytmu bisekcji z testem dwuskośnym Goldstein'a
Algorytm bisekcji z testem dwuskośnym Golstein a  algorytm
dla funkcji:
gradientowy
Praktycznie do wyszukania punktów spełniających test dwuskośny
f(x1, x2) = (x1)2 + 2(x2)2  6x1 + x1x2
Goldsteina stosuje się następujący algorytm bisekcji:
p = "f (xo)T d
(1) Oblicz pochodną w kierunku oraz współczynnik
punkt poczÄ…tkowy x0 = [0, 0]T
0 0
kierunek d = [1, 0]T
Ä > 0 taki , \
e f ( x + Ä d ) < f ( x )
kroku R R
2
współczynnik testu ² =
5
1
(2) Wyznacz Ä = (ÄL +Ä ). Oblicz f (x0 +Äd).
poczÄ…tkowa wartość współczynnika kroku ÄR = 9
R
2
dokładność dla testu
2
µ =10-5
f (x0 +Äd) < f (x0) + (1- ² ) pÄ
(3) Jeśli to podstaw
Ä Ò! Ä
L
i przejdz
do kroku (2), w przeciwnym razie przejdz
do kroku (4)
(4) Jeśli to podstaw
Ä Ò!Ä
f (x0 +Äd) > f (x0 ) + ²pÄ
R
i przejdz
do kroku (2), w przeciwnym przypadku koniec.
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
1
Pochodna w kierunku p = "f (xo )T d
(2) Obliczamy Ä = (Ä +Ä ) oraz f (x0 +Äd).
L R
2
zatem mamy:
1 1
îÅ‚ Å‚Å‚ Ä = (Ä ) = (9) = 4,5
R
ïÅ‚
2 2
śł
"f (x)=ïÅ‚"f (x),"f (x)śł= îÅ‚ x2,4x2+x1Å‚Å‚
ïÅ‚2x1-6+ śł
ïÅ‚ śł
śł
"x1 "x2 ïÅ‚ ûÅ‚
ðÅ‚
ïÅ‚ śł
ðÅ‚ ûÅ‚
îÅ‚ Å‚Å‚
dla x = x0 = [0, 0]T
f (x0 +Äd) = f + (4,5 ,0)śł = 20,25 - 27 = - 6,75
ïÅ‚(0,0)
ðÅ‚ ûÅ‚
"f (x0 ) = [- 6,0]
Otrzymujemy wartość pochodnej p:
Przechodzimy do kroku (3)
1
îÅ‚ Å‚Å‚
p = "f (xo )T d = [- 6 0]Å" = -6
ïÅ‚0śł
ðÅ‚ ûÅ‚
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
0 0
f (x +Äd) > f (x ) + ²pÄ
(4) Je\
eli
to podstaw Ä Ò!Ä
R
(3) Je\
eli
f (x0 +Äd) < f (x0) + (1- ² ) pÄ i przejdz
do kroku (2). W przeciwnym wypadku KONIEC
to podstaw Ä Ò! Ä
L
i przejdz
do kroku (2). W przeciwnym wypadku przejdz
do 0 + (-6)Å"(0,4)Å"(4,5) = -10,8
sprawdzamy: -6,75 >?
kroku (4)
TAK
i przechodzimy do kroku (2)
sprawdzamy: -6,75 0 + (-6) Å"(0,6)Å"(4,5) = -16,2
DRUGA ITERACJA
(...)
NIE
Po trzeciej iteracji otrzymujemy wynik
Ä =3,375
Przechodzimy do kroku (4)
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
3
Technika optymalizacji
Obliczamy
d0 =-"f (x0)=[-2,-2]T
Poniewa\
pierwsza stosowana wartość współczynnika kroku
Działanie algorytmu najszybszego spadku dla funkcji:
ÄR = 1 speÅ‚nia test dwuskoÅ›ny Goldsteina, wiÄ™c:
f(x1, x2) = 2(x1)2 + (x2)2  2 x1x2
x1 = x0 + Ä0 d0 = [0 1]T d1 = -"f (x1) = [2 - 2]T
W drugiej iteracji mamy:
punkt poczÄ…tkowy x0 = [2, 3]T
2
f (x1 +Äd1) = 20Ä - 8Ä +1
1
Otrzymujemy:
współczynnik testu ² =
4 îÅ‚- 2
Å‚Å‚
p = "f (x1)T d1 = Å"[2 - 2] = -8
ïÅ‚ śł
2
ðÅ‚ ûÅ‚
poczÄ…tkowa wartość współczynnika kroku ÄR = 1
Technika optymalizacji
Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kolejno podane sÄ… punkty wyznaczone za pomocÄ…
Zatem test dwuskośny ma postać
algorytmu najszybszego spadku dla funkcji:
f(x1, x2) = 2(x1)2 + (x2)2  2 x1x2
0
-6 d" 20Ä2 - 8Ä d" -2
x = [2 3]
1
x = [0 1]
Za pomocą algorytmu bisekcji (test dwuskośny Goldsteina) w
2
1 1
trzeciej próbie znajdujemy wartość współczynnika Ä1 = 0,25
x = [ ]
2 2
StÄ…d
3
1 1
x = [4 2 ]
x2 = x1 + Ä1 d1 = [1 1 ]T
2 2
4
1 1
x = [4 4 ] itd....
Postępując zgodnie z algorytmem otrzymujemy kolejne
I tak kolejno, a\
do momentu gdy zostanie spełniony
wartości punktów optymalizowanej funkcji.
warunek
^ ^
-3
"f (x), "f ( x) d" µ = 10
TAK OTRZYMUJEMY PUNKT MIN (0,0)
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
Kolejne iteracje metody najszybszego spadku NS
Funkcja celu f(x)
x0
x1
x3 x2
x5 x4
x^
M
Technika optymalizacji Technika optymalizacji
Wydział Elektroniki Wydział Elektroniki
M
Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika. Dr in\
. Ewa Szlachcic Kierunek EiT III r Potok: Elektronika.
4