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