Materiały pomocnicze do ćwiczeń laboratoryjnych T4

Politechnika Gdańska Wydział Elektrotechniki i Automatyki Katedra Inżynierii Systemów Sterowania

Metody optymalizacji Metody bezgradientowe optymalizacji bez ograniczeń Materiały pomocnicze do ćwiczeń laboratoryjnych T4

Opracowanie: Piotr Hirsch, mgr inż. Kazimierz Duzinkiewicz, dr hab. inż. Gdańsk, 05.2016

1.

Wstęp

W ćwiczeniu zapoznamy się z dwiema metodami bezgradientowymi poszukiwania ekstremum bezwarunkowego: metodą Gaussa-Seidla i metodą Neldera-Meada. Metody bezgradientowe nie posiadają wymagania na różniczkowalność funkcji kryterialnej. Do ich zastosowania wystarczająca jest znajomość wartości funkcji w punkcie przy zachowaniu warunku ciągłości.

2.

Metoda Gaussa-Seidla

Metoda Gaussa-Seidla polega na poszukiwaniu minimum w kolejnych kierunkach bazowych. Poczynając od punktu startowego 𝒙0 , poszukujemy minimum w kierunku 𝑥1 . Dojdziemy więc do punktu styczności z pewną poziomicą, od którego rozpoczniemy poszukiwanie minimum funkcji w kierunku 𝑥2 . Postępowanie to powtarzamy aż do ostatniej zmiennej zbioru argumentów, czyli 𝑥𝑛 , a następnie rozpoczynamy cykl poszukiwań od nowa, czyli z osiągniętego punktu poszukujemy minimum w kierunku 𝑥1 . Tak postępujemy aż do spełnienia warunku zakończenia obliczeń. Minimum funkcji w kierunku 𝑥𝑘 poszukujemy jedną z bezgradientowych metod minimalizacji funkcji jednej zmiennej (metodą złotego podziału). x2

x0 x1

Rys. 1. Poszukiwanie minimum metodą Gaussa-Seidla Przyjmujemy kartezjański układ współrzędnych, określonych przez wersory kierunkowe: 𝑒 1 = [1 0 0 … 0] 𝑒 2 = [0 1 0 … 0] ⋮ 𝑛 𝑒 = [0 0 0 … 1] Algorytm metody Gaussa-Seidla: 1. Przyjąć punkt startowy 𝒙0 i dokładność wyznaczenia ekstremum (określana jako zmiana wartości funkcji kryterialnej w kolejnych dwóch krokach) ε (np. 𝜺 = 𝟏𝟎−𝟑). 2. Obliczyć w punkcie 𝑥 𝑖 wartość funkcji celu 𝒇(𝑥 𝑖 ).

3. Wykonać z punktu 𝑥 𝑖,𝑘−1 krok o długości d w kierunku 𝑒 𝑘 , tak, by minimalizować 𝒇(𝒅), przechodząc do punktu: 𝒙𝒊,𝑘 = 𝒙𝑖,𝑘−1 + 𝑑 ∙ 𝑒 𝑘 . 4. Powtórzyć poprzedni punkt (n-1) razy, osiągając punkt 𝑥 𝑖,𝑛 czyli 𝑥 𝑖+1 5. Obliczyć wartość funkcji celu w nowym punkcie. Jeśli |𝒇(𝑥 𝑖+1 ) − 𝒇(𝑥 𝑖 )| < 𝜀, to zakończyć postępowanie. W przeciwnym razie przyjąć 𝑖 = 𝑖 + 1 i wrócić do punktu 2. Przykład: Znaleźć minimum funkcji: 𝑓(𝑥) = 2𝑥12 + 𝑥22 − 2𝑥1 𝑥2 startując w punkcie 𝑥 0 = [2; 3], przyjmując dokładność 𝜀 = 10−2. Na początku wyznaczamy wartość funkcji w punkcie startowym: 𝑓(𝒙𝟎 ) = 5 𝑥 01 = 𝑥 00 + 𝒅 ∙ 𝒆1 Funkcja 𝑓(𝒙) po podstawieniu powyższej zależności przechodzi w funkcję 𝑓(𝑑) – taka postać nazywana jest parametrycznym przedstawieniem funkcji: 2 1 𝑓(𝑑) = 𝑓(𝑥 01 ) = 𝑓 ([ ] + 𝒅 ∙ [ ]) = 5 + 2 ∙ 𝑑 + 2 ∙ 𝑑2 3 0 Następnie poszukujemy minimum funkcji 𝑓(𝑑). Skorzystać możemy z metody złotego podziału (w tym celu należy także wyznaczyć przedział na którym znajduje się minimum). W tym wypadku krok d minimalizujący funkcję 𝑓(𝑥) w kierunku 𝒆1 będzie miał wartość 𝑑 = −0.5. Wyznaczamy współrzędne nowego punktu: 2 1 1.5 𝑥 01 = [ ] − 0.5 ∙ [ ] = [ ] 3 0 3 Z tego punktu wykonujemy minimalizację w kierunku 𝒆2 : 𝑥 02 = 𝑥 01 + 𝒅 ∙ 𝒆2 0 1.5 𝑓(𝑑) = 𝑓(𝑥 02 ) = 𝑓 ([ ] + 𝒅 ∙ [ ]) = 4.5 + 3 ∙ 𝑑 + 𝑑2 1 3 Ponownie obliczamy optymalną długość kroku 𝑑 = −1.5 i kolejny punkt: 1.5 𝑥 02 = [ ] = 𝑥 10 1.5 𝑓(𝑥 10 ) = 2.25. Możemy teraz sprawdzić warunek zakończenia obliczeń:

|2.25 − 5| = 2.75 > 0.01 Przechodzimy do kolejnego kroku obliczeń, startując z punktu 𝑥 10 .

3.

Metoda Powella

Metoda Powella polega na poszukiwaniu minimum w kolejnych kierunkach bazowych. Kierunki bazowe w każdym cyklu poszukiwań ulegają modyfikacji, tak aby prowadziły one do szybszego znalezienia minimum, przy czym w kolejnych cyklach muszą być wzajemnie sprzężone. Metoda Powella pozwala odnaleźć minimum funkcji liniowo-kwadratowej w skończonej liczbie iteracji, w wyniku minimalizacji tej funkcji wzdłuż każdego kierunku tylko raz. Metodę Powella zastosować można nie tylko do funkcji będących formą kwadratową, ale także do dowolnych funkcji analitycznych, przyjmując, że w bliskim otoczeniu minimum można je przybliżyć formą kwadratową. x2

x0 x1

Rys. 2. Poszukiwanie minimum metodą Powella (linia ciągła) i metodą Gaussa-Seidla (linia przerywana) Przyjmujemy kartezjański układ współrzędnych, określonych przez wersory kierunkowe: 𝑒 1 = [1 0 0 … 0] 𝑒 2 = [0 1 0 … 0] ⋮ 𝑒 𝑛 = [0 0 0 … 1]

1. 2. 3. 4.

5.

Algorytm metody Powella: Przyjąć punkt startowy 𝑥 𝟎 i dokładność wyznaczenia ekstremum (określana jako zmiana wartości funkcji kryterialnej w kolejnych dwóch krokach) ε (np. 𝜺 = 𝟏𝟎−𝟑). Obliczyć 𝑥 𝑖,0 , jako wynik minimalizacji funkcji 𝑓(𝒙) w kierunku 𝑒 𝑛 z punktu 𝑥 𝑖 Obliczyć w punkcie 𝑥 𝑖,0 wartość funkcji celu 𝒇(𝑥 𝑖,0 ). Wykonać z punktu 𝑥 𝑖,𝑘−1 krok o długości d w kierunku 𝑒 𝑘 , tak, by minimalizować 𝒇(𝒅), przechodząc do punktu: 𝒙𝒊,𝑘 = 𝒙𝑖,𝑘−1 + 𝑑 ∙ 𝑒 𝑘 . Powtórzyć poprzedni punkt (n-1) razy, osiągając punkt 𝑥 𝑖,𝑛 czyli 𝑥 𝑖+1

6. Obliczyć wartość funkcji celu w nowym punkcie. Jeśli |𝒇(𝑥 𝑖+1 ) − 𝒇(𝑥 𝑖 )| < 𝜀, to zakończyć postępowanie. 7. Zmodyfikować bazę, wykonując podstawienie: 𝑒1 = 𝑒 2 𝑒2 = 𝑒3

⋮ 𝑛−1

𝑒 = 𝑒𝑛 𝑒 𝑛 = 𝑥 𝑖,𝑛 − 𝑥 𝑖,0

8. Podstawić 𝑥 𝑖+1 = 𝑥 𝑖,𝑛 , przyjąć 𝑖 = 𝑖 + 1 i wrócić do punktu 2. Tak więc, w nowej bazie pojawi się na ostatnim miejscu nowy kierunek (sprzężony), a usunięty z bazy zostanie pierwszy kierunek poprzedniego zestawu. Od tego nowego kierunku rozpoczniemy minimalizację w następnym cyklu obliczeń. Przykład: Znaleźć minimum funkcji: 𝑓(𝑥) = 2𝑥12 + 𝑥22 − 2𝑥1 𝑥2 startując w punkcie 𝑥 0 = [2; 3], przyjmując dokładność 𝜀 = 10−2. Obliczamy minimum funkcji 𝑓(𝑥) w kierunku 𝑒 2 z punktu startowego 𝑥 0 . 𝑥 00 = 𝑥 0 + 𝒅 ∙ 𝒆2 2 0 𝑓(𝑑) = 𝑓(𝑥 00 ) = 𝑓 ([ ] + 𝒅 ∙ [ ]) = 5 + 2 ∙ 𝑑 + 𝑑2 3 1 Wartość d wyznaczamy jako: 𝑑 = −1. Wyznaczamy współrzędne nowego punktu i wartość funkcji celu: 2 0 2 𝑥 00 = [ ] − 1 ∙ [ ] = [ ] 3 1 2 𝑓(𝒙0𝟎 ) = 4 Od tego momentu postępujemy zgodnie z metodą Gaussa-Seidla, otrzymując w kierunku 𝒆1 : 𝑥 01 = 𝑥 00 + 𝒅 ∙ 𝒆1 2 1 𝑓(𝑑) = 𝑓(𝑥 01 ) = 𝑓 ([ ] + 𝒅 ∙ [ ]) = 4 + 4 ∙ 𝑑 + 2 ∙ 𝑑2 2 0 2 1 1 01 𝑥 =[ ]−1∙[ ]=[ ] 2 0 2 Wykonujemy minimalizację w kierunku 𝒆2 :

𝑥 02 = 𝑥 01 + 𝒅 ∙ 𝒆2 1 0 𝑓(𝑑) = 𝑓(𝑥 02 ) = 𝑓 ([ ] + 𝒅 ∙ [ ]) = 2 + 2 ∙ 𝑑 + 𝑑2 2 1 1 0 1 02 𝑥 = [ ] − 1 ∙ [ ] = [ ] = 𝑥1 2 1 1 Obliczamy wartość funkcji celu w nowym punkcie i sprawdzamy warunek stopu: 𝑓(𝑥 1 ) = 1. |1 − 4| = 3 > 0.01 Modyfikujemy bazę: 0 𝑒1 = [ ] 1

−1 𝑒 2 = 𝑥 02 − 𝑥 00 = [ ] −1 Podstawiamy 𝑥 1 = 𝑥 02 i przechodzimy do kolejnego cyklu obliczeń. Obliczamy minimum funkcji 𝑓(𝑥) w kierunku 𝑒 2 z punktu 𝑥 1 : 𝑥 10 = 𝑥 1 + 𝒅 ∙ 𝒆2 1 −1 𝑓(𝑑) = 𝑓(𝑥 00 ) = 𝑓 ([ ] + 𝒅 ∙ [ ]) = 1 − 2 ∙ 𝑑 + 𝑑2 1 −1 1 −1 0 10 𝑥 =[ ]+1∙[ ]= [ ] 1 −1 0 1𝟎 𝑓(𝒙 ) = 0 Obliczamy 𝑥 11 i 𝑥 12 jak poprzednio, otrzymując: 𝑥 11 = 𝑥 10 𝑥 12 = 𝑥 11 = 𝑥 10 Ponieważ minimalizacja w kolejnych kierunkach nie zmienia położenia punktu, kończymy obliczenia.

4.

Metoda Neldera-Meada

Metoda Neldera-Meada, zwana też metodą pełzającego simpleksu, polega na kolejnym przekształcaniu wielościanu wypukłego, posiadającego n+1 liniowo niezależnych wierzchołków, w kierunku minimum. Wielościan taki nazywamy simpleksem (sympleksem). W każdej iteracji zmieniane jest położenie jednego punktu wierzchołkowego simpleksu – tego o najgorszej wartości funkcji celu. Hiperpowierzchnia przechodząca przez pozostałe n wierzchołków rozdziela przestrzeń zmiennych na dwie półprzestrzenie. Oczekujemy, że możemy znaleźć punkt o mniejszej wartości funkcji celu w tej półprzestrzeni, która nie zawiera najgorszego punktu z pośród dotychczasowych. Szkielet algorytmu wygląda następująco:

Rys. 2. Ilustracja do algorytmu Neldera-Meada 1. Uporządkuj punkty początkowego simpleksu wg wartości funkcji celu. Punkt W jest najgorszy, więc wyliczamy środek ciężkości M punktów B i G (w przestrzeni dwuwymiarowej jest to po prostu środek odcinka łączącego oba punkty). 2. Wygeneruj odbicie punktu W względem hiperpowierzchni łączącej pozostałe punkty (przechodzące przez M), tworząc punkt R. 3. Jeśli R nie jest najlepszym ani najgorszym z punktów wierzchołkowych nowego simpleksu, to przejdź do kolejnej iteracji algorytmu. 4. Jeśli R jest lepszy od najlepszego z dotychczasowych, to kierunek poszukiwań wydaje się być obiecujący, więc dokonujemy ekspansji simpleksu (rozciągnięcie) w tym kierunku, tworząc punkt E. 5. Jeśli R jest najgorszym z dotychczasowych punktów, to dokonujemy kontrakcji, czyli ściśnięcia simpleksu w tym kierunku, otrzymując punkty C2 lub C1, w zależności od tego, czy f(R) > f(W) czy nie. 6. Możliwa jest też sytuacja, gdy dokonujemy kontrakcji całego simpleksu wokół punktu dotychczas najlepszego. 7. Jako warunek stopu najczęściej stosujemy sprawdzenie, czy maksimum odległości między wierzchołkami simpleksu jest mniejsze od zadanego ε.

Charakter metody wymaga stosowania mechanizmów periodycznej odnowy, to jest zastąpienia aktualnego simpleksu innym, bardziej regularnym, gdy simpleks jest zbyt rozciągnięty w jednym kierunku, a ściśnięty w innym.

Bibliografia: Amborski K., Podstawy metod optymalizacji, Oficyna Wydawnicza Politechniki Warszawskiej, 2009 Stachurski A., Wprowadzenie do optymalizacji, Oficyna Wydawnicza Politechniki Warszawskiej, 2009 Ostanin A., Metody optymalizacji z MATLAB. Ćwiczenia laboratoryjne, NAKOM, 2009