Podręcznik

Poprzednie punkty poświęciliśmy przedstawieniu podstawowych własności matematycznych obiektów składających się na zadania optymalizacji. Teraz wracamy do głównego nurtu tego podręcznika – poszukiwania odpowiedzi na pytanie jak konstruować algorytmy rozwiązujące zadania optymalizacji (algorytmy optymalizacji).

Jak już wiemy wynikająca z twierdzenia Férmaty (Twierdzenia 3.4) Procedura rozwiązywania zadania optymalizacji bez ograniczeń przez redukcję do układu równań ma ograniczone zastosowanie. Zatem: jeżeli nie procedura redukcji, to jakimi sposobami możemy konstruować algorytmy optymalizacji?

Powróćmy do naszych rozważań z punktu 1.4 Modułu pierwszego. Jak pamiętamy, Algorytm jest ślepy – nie może zobaczyć rzeźby trenu na którym się znajduje. Na schodach szedł w prawo, potem w lewo – sprawdzał swoje otoczenie. W ogólnym przypadku otoczenie ma więcej wymiarów, ale pomysł może być ten sam – sprawdzać zachowanie funkcji wyboru w sąsiedztwie punktu bieżącego, x, w którym się aktualnie znajduje. Natychmiast pojawia się pytanie – jak duże powinno być to sąsiedztwo? Udzielenie przemyślanej odpowiedzi nie jest zagadnieniem łatwym, ponieważ wielkość przeszukiwanego obszaru ma, intuicyjnie wpływ, z jednej strony na szybkość znalezienia ekstremum mierzoną ilością sprawdzanych obszarów (im większy tym szybciej), a z drugiej na dokładność Algorytmu (przy ograniczonych możliwościach przeszukiwania – im mniejszy tym dokładniej).

Przyjmijmy, że zagadnienie to zostało jakoś rozwiązane i wybrano sąsiedztwo \(S(x)\) punktu \(x,\) dla ustalenia uwagi, może to być kula o promieniu \(r : \mathfrak{K}(x, r)\). „Sprawdzenie” zdefiniowanego sąsiedztwa Algorytm może robić na dwa sposoby:

• w pierwszym, przyjmuje, że nic nie wie o kształcie funkcji wyboru.
• w drugim w oparciu o wiedzę „lokalną” buduje sobie model zachowania funkcji wyboru w dużo większym obszarze.