MO Moduł 4

From Studia Informatyczne

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Z rozważań geometrycznych wiadomo, że iloczyn skalarny dwu wektorów jest ujemny wtedy gdy kąt miedzy nimi jest rozwarty. Tak też jest na rysunku dla wybranego wektora d.

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Uwaga: intuicyjnie wydaje się, że tezy powinny być zamienione miejscami! Konieczność sformułowania jak w lemacie wynika z faktu, że dla macierzy zerowej 0 mamy dla każdego x: x^{\mathrm T}\mathbf{0}x^{\mathrm T} = 0 \ge 0, zatem macierz ta jest dodatnio (i ujemnie też!) półokreślona.

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Zatem, dla funkcji dostatecznie gładkich możemy sobie poradzić z zagadnieniem punktu szóstego procedury (teraz powinno być jasne, dlaczego jest tam wstawiona uwaga „gdy wiemy, że nasze zadanie ma rozwiązanie”).

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Piękny rezultat teoretyczny, sprowadzający procedurę redukcji do układu równań wyłącznie do rachunków: liczenia pochodnych i rozwiązywania równań, czyli do takiego postępowania, które zastosowaliśmy z ochotą lecz błędnie w przykładzie. Trzeba tylko policzyć macierz Hessego by stwierdzić wypukłość funkcji celu i zastanowić się nad sposobem rozwiązania stosownych równań, ale odpadają zagadnienia związane z dowodem istnienia rozwiązania.

Enlarge
Napisaliśmy, w zasadzie, ponieważ opracowano procedury automatycznego różniczkowania (nie mylić z procedurami symbolicznego różniczkowania), które przetwarzają kod wyliczający funkcję wyboru na kod wyliczający jej pochodne. Zatem wymaganie znajomości wzoru nie jest już takie kategoryczne

Enlarge
Zauważmy, że jednym z plusów tej metody jest to, że idealnie nadaje się do, nazwijmy to tak, sprawdzania wiadomości i zdolności rachunkowych studentów.

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Widać, że otoczenie, w którym aproksymację uznalibyśmy za dobrą nie jest duże i jego kształt jest zbliżony do elipsy o osiach nierównoległych do osi współrzędnych kartezjańskich.

Enlarge

Enlarge

Enlarge
Korzystać z aproksymacji – nie korzystać ?
Tego rodzaju dylemat jest typowy dla sytuacji, w której znajduje się twórca nowych rozwiązań konstrukcyjnych – magister, a więc mistrz – a także twórca nowych teorii naukowych. Za podejściem optymisty opowiedział się Albert Einstein, który stwierdził, że "God is subtle but he is not malicious". Co w naszym przypadku przekłada się na przeświadczenie, że nieliniowe zadania optymalizacji związane z rozwiązywaniem zagadnień praktycznych, są takie, że zręczne wykorzystanie możliwości jakie daje posługiwanie się aproksymacją (APR) pozwoli opracować skuteczne algorytmy ich rozwiązywania. Współcześni optymiści mają sławnego poprzednika – Izaaka Newtona, który wymyślił metodę stycznych rozwiązywania równań nieliniowych opartą o jeszcze prostszą aproksymację, bo ograniczoną tylko do składnika afinicznego.

Enlarge

Enlarge
Intuicyjnie – dodanie członu afinicznego “przesuwa” formę kwadratową nie zmieniając jej kształtu, tzn. nie zmienia jej podstawowych własności

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Wektory własne nie są wyznaczone jednoznacznie, i nie jest to przypadek. W terminologii używanej w teorii metod optymalizacji wektory własne wyznaczają tylko kierunki (proste).

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Niestety, możemy narysować tylko funkcję dwu zmiennych (jak często mówimy, na płaszczyźnie). Przedstawmy zatem wykresy trójwymiarowe i poziomicowe dla pierwszych trzech przypadków, ponieważ funkcje określone ujemnie to “odwrócone w dół” funkcje określone dodatnio.

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge

Enlarge
Widać, ze funkcja Rosenbrocka jest dobrze dobrana jako “tor badania sprawności” dla różnych algorytmów. Tylko w centralnej części (tam gdzie nie ma minimum) jej uwarunkowanie jest mniejsze od pięciu, a w okolicy minimum jest większe od 500.