1 Analiza numeryczna i symulacja systemówJanusz Miller Przegląd metod optymalizacji numerycznej

2 Numeryczne metody optymalizacjiDeterministyczne (klasyczne) * bez ograniczeń: - bezgradientowe: + simpleks Neldera-Meada, + spadku względem współrzędnych (Gaussa-Seidela), + Powella, Rosenbrocka, Hooke’a-Jeevesa,... - gradientowe pierwszego rzędu: + największego spadku, + gradientów sprzężonych. - gradientowe drugiego rzędu i „superliniowe”: + Newtona, BFGS, + „Trust region”. * z ograniczeniami: + eliminacji zmiennych, + Lagrange’a, + z funkcją kary, + SQP. Niedeterministyczne - Monte Carlo, symulowane wyżarzanie, algorytmy genetyczne i ewolucyjne, algorytmy rojowe itp. ANiSS 2014/15 - Metody optymalizacji

3 ANiSS 2014/15 - Metody optymalizacjiCel Znaleźć gdy zadanie bez ograniczeń, gdy zadanie z ograniczeniami. Szukanie postępuje krok po kroku: - wektor wyznaczający kierunek kroku, - liczba określająca długość kroku. ANiSS 2014/15 - Metody optymalizacji

4 ANiSS 2014/15 - Metody optymalizacjiOznaczenia Funkcja celu Gradient Hesjan ANiSS 2014/15 - Metody optymalizacji

5 Metoda simpleksów Neldera-Meada1. W przestrzeni n wymiarowej tworzymy wokół punktu x0 simpleks n+1 wymiarowy. 2. Porządkujemy punkty simpleksu tak, aby f(xi) 3. Generujemy punkt r=2m-xn+1, gdzie m=(x1+...+xn)/n. 4. Jeżeli f(x1)<=f(r) 5. Jeżeli f(r)<=f(x1), to obliczamy s=m+2 i a. jeżeli f(s) b. jeżeli nie, to akceptujemy r, reflect. 6. Jeżeli f(r)>=f(xn), to kontrakcja między m a lepszym(r,xn+1 ) a. jeżeli f(r) jeżeli f(c) jeżeli nie, to do punktu 7, b. jeżeli f(r)>=f(xn+1), to obliczamy cc=m+(xn+1-m)/2, jeżeli f(cc) jeżeli nie, to do punktu 7. 7. Obliczamy n punktów vi=x1+(xi-x1)/2, i=2,...,n+1, shrink. Ew. unikanie degradacji. ANiSS 2014/15 - Metody optymalizacji

6 ANiSS 2014/15 - Metody optymalizacjiMetody rozwiązywania układów równań nieliniowych Metoda simpleks (Nelder-Mead) xn+1 cc x1 m c r s ANiSS 2014/15 - Metody optymalizacji

7 Podstawowe schematy jednego kroku metod optymalizacji1. Wyznaczenie kierunku poszukiwania minimum pk. 2. Wykonanie kroków (w tym kierunku) do minimum. B: (Trust Region) 1. Określenie maksymalnej długości kroku. 2. Wyznaczenie kierunku, w którym należy wykonać krok. ANiSS 2014/15 - Metody optymalizacji

8 Poszukiwanie na kierunku (line search methods)Szukanie minimum na kierunku: Obliczanie wartości funkcji w kolejnych punktach, aż do napotkania wzrostu wartości funkcji. Interpolacja wielomianem Lagrange’a 3 ostatnich punktów. Przybliżone minimum w minimum paraboli. Kryterium wyboru długości “kroku” a Warunek Wolfe’a: Redukcja wartości funkcji powinna być proporcjonalna do długości kroku oraz do pochodnej kierunkowej: (nierówność Armijo) Wybór metody zależy od kosztu zmiany kierunku (zerowy albo obliczanie gradientu lub hesjanu). ANiSS 2014/15 - Metody optymalizacji

9 ANiSS 2014/15 - Metody optymalizacjiMetoda spadku względem współrzędnych (Gauss-Seidel, coordinate descent method) Grupa A, Bez ograniczeń, bezgradientowa: Idea: Szukanie minimum na kierunkach kolejnych współrzędnych. ANiSS 2014/15 - Metody optymalizacji

10 ANiSS 2014/15 - Metody optymalizacjiPrzykład: ANiSS 2014/15 - Metody optymalizacji

11 ANiSS 2014/15 - Metody optymalizacjiMetoda spadku względem współrzędnych ANiSS 2014/15 - Metody optymalizacji

12 ANiSS 2014/15 - Metody optymalizacjiMetoda spadku względem współrzędnych ANiSS 2014/15 - Metody optymalizacji

13 Metoda najszybszego spadku (steepest descent)Grupa A Bez ograniczeń gradientowa (pierwszego rzędu) Idea: ANiSS 2014/15 - Metody optymalizacji

14 ANiSS 2014/15 - Metody optymalizacjiMetoda najszybszego spadku ANiSS 2014/15 - Metody optymalizacji

15 Metoda gradientów sprzężonych Conjugate gradient (CG) methodGrupa A Bez ograniczeń Gradientowa (pierwszego rzędu) Idea: ANiSS 2014/15 - Metody optymalizacji

16 Numeryczne metody optymalizacjiMetoda Newtona Szybka -metoda gradientowa drugiego rzędu. Skuteczna - w pobliżu minimum (ogólnie - gdy model rzędu dobrze przybliża funkcję), - gdy hesjan jest macierzą dodatnio określoną. Kosztowna - wymaga częstego obliczania hesjanu. ANiSS 2014/15 - Metody optymalizacji

17 ANiSS 2014/15 - Metody optymalizacjiMetoda Newtona (Grupa A) Przykład: ANiSS 2014/15 - Metody optymalizacji

18 Numeryczne metody optymalizacji (Grupa A)Quasi-Newton Zbieżność superliniowa (rząd > 1). Mniejszy koszt - nie wymagają obliczania hesjanu. Hesjan zastąpiony macierzą Bk - uaktualnianą informacją o funkcji uzyskaną w kolejnych krokach - zmiana gradientu wzdłuż kierunku poszukiwań dostarcza przybliżoną informację o drugiej pochodnej. Najbardziej popularna BFGS (Broyden, Fletcher, Goldfarb,Shanno): ANiSS 2014/15 - Metody optymalizacji

19 Trust-Region Methods (Grupa B)Idea: - Budujemy model otoczenia punktu xk Bk- wg Newtona, CG, BFGS itp.. - Szukamy minimum w tym otoczeniu - Promień D ustalany na podstawie zgodności modelu i funkcji celu w poprzednim kroku. ANiSS 2014/15 - Metody optymalizacji

20 ANiSS 2014/15 - Metody optymalizacjiIdea metody Trust-Region funkcja f model m “trust region” D ANiSS 2014/15 - Metody optymalizacji

21 Trust-Region Methods Metoda DoglegSchemat algorytmu: - Wyznaczamy punkt Cauchy’ego (punkt na kierunku antygradientu, w którym model ma minimum). - Drogę do punktu xk+1 skłądamy z odcinka do punktu Cauchy’ego i odcinka od punktu Cauchy’ego do minimum modelu. - Jeżeli wiarygodność modelu jest mała, to dominuje najszybszy spadek. - Jeżeli wiarygodność jest duża, to dominuje model 2. rzędu. - Są metody bardziej zaawansowane np. Levenberga - Marquardta ANiSS 2014/15 - Metody optymalizacji

22 Ilustracja kroku metody metody DoglegANiSS 2014/15 - Metody optymalizacji

23 Numeryczne metody optymalizacji z ograniczeniami- ograniczenia równościowe i nierównościowe, - Metody: * eliminacja zmiennych, * metody z funkcją kary, * metoda Lagrange’a - Warunek konieczny 1. rzędu - Warunek 2. rzędu - Quadratic Programming - SQP - Sequential Quadratic Programming ANiSS 2014/15 - Metody optymalizacji

24 ANiSS 2014/15 - Metody optymalizacjiKryterium stopu Minimum lokalne a globalne. W zastosowaniu do rozwiązywania układów równań nieliniowych - istotna jest znajomość funkcji celu punkcie minimalnym. “Numeryczna niejednoznaczność” zera - błąd numeryczny obliczania wartości funkcji. ANiSS 2014/15 - Metody optymalizacji

25 Numeryczne metody optymalizacjiMetody niedeterministyczne: - Monte Carlo, - symulowane wyżarzanie, - algorytmy genetyczne i ewolucyjne, - algorytmy rojowe, - wykorzystujące sztuczne sieci neuronowe. ANiSS 2014/15 - Metody optymalizacji

26 O czym należy pamiętać:Algorytm poszukiwania minimum w kierunku. Podstawowe schematy jednego kroku metod optymalizacji. W których metodach jest obliczany gradient funkcji. W których metodach jest obliczany hesjan. Ogólny schemat algorytmu: - Neldera-Mead’a, - spadku wzdłuż współrzędnych, - najszybszego spadku, - gradientu sprzężonego, - Newtona, - quasi-newtonowskiego (np.BFGS), - trust-region, - Monte-Carlo. Zalety i wady poszczególnych metod. ANiSS 2014/15 - Metody optymalizacji