Podręcznik

1. Wprowadzenie

Tytuł podręcznika «Metody optymalizacji» powinien mówić sam za siebie, ale czy mówi?
Najpierw trzeba ustalić co tak naprawdę znaczy optymalizacja.
Współcześnie, najczęściej nadaje mu się znaczenie wprowadzone przez G.W. Leibniza w znamienitej pracy „Nova Methodus pro Maximis et Minimis”, 1 opublikowanej w 1684 r., której autor nazywał wartości największe lub najmniejsze jakie przybiera pewna funkcja – optymalnymi.
Wielu ludzi uważa, że w dzisiejszych czasach wszystko jest, albo co najmniej powinno być, optymalne. Człowieka tak myślącego i działającego często nazywa się homo oeconomicus. Optymalizacja więc nas otacza:

optymalizują ludzie w życiu codziennym, np. student tak dobiera sobie program studiowania aby spełniając wymagania narzucone przez władze oraz w zgodzie z własnymi potrzebami minimalizować swoje nakłady(mierzone np. zużytym czasem) potrzebne do uzyskania dyplomu;

optymalizują konstruktorzy – np. projektując most starają się dobrać parametry jego elementów tak, aby przy spełnieniu ograniczeń wymiarowych, sztywnościowych, wytrzymałościowych itp. sumaryczny koszt tych elementów był jak najmniejszy;

optymalizują ludzie w organizacjach, np. zarząd korporacji podejmuje decyzje, które w aktualnej sytuacji mają przynieść maksymalny zysk;

optymalizuje też przyroda, –ożywiona: np. mrówki wybierają najkrótsze, z dopuszczalnych, drogi powrotu z miejsc pracy/żerowania do mrowiska; –nieożywiona: np. łańcuch układa się tak, że jego energia potencjalna jest najmniejsza, a promienie światła biegną tak aby minimalizować czas podróży itd.

Podsumowując powyższe przykłady i nieco rozszerzając rozważania Leibniza, można powiedzieć, że optymalizacja polega na dążeniu do znalezienia wariantu (działania), ocenianego według ustalonego kryterium wyboru jako najlepszy spośród wariantów rozpatrywanych (porównywanych/możliwych). Szukamy wariantu ocenionego optymalnie a nie optymalnej wartości funkcji oceniającej.
Z drugiej jednak strony można zadać pytanie, czy dążenie za wszelką cenę do tego aby zrealizować wariant najlepszy z możliwych jest zawsze uzasadnione, a co ważniejsze, możliwe?
Zostawmy odpowiedź na pierwszą część pytania dla filozofów. Analiza możliwości poruszanej w jego drugiej części zostanie ograniczona do pokazania jak można w zbiorze wariantów uznanych za dopuszczalne poszukiwać wariantu, ocenianego według ustalonego kryterium wyboru jako najlepszy tj. otrzymującego najwyższą albo najniższą wartość oceny (możemy szukać rzeczy „najcenniejszej” albo „najmniej cennej”, porównujemy „cenność”). Będziemy zatem poszukiwać odpowiedzi na pytanie: jak rozwiązać zadanie optymalizacji? Przyrodzie „jest łatwiej” bo „sama z siebie” znajduje wariant optymalny, człowiek musi tego wariantu szukać. Gdy wariantów jest niewiele i przyjmiemy, że kryterium porównywania jest ustalone, to można je parami porównać i wybrać najlepszy. Ale co robić gdy wariantów jest wiele, nieskończenie wiele?
1
W tej pracy Leibniz przestawił swoją teorię rachunków (calculi) różniczkowych łącznie z używaną do dziś notacją, df(x)/dx, ułatwiającą jej zrozumienie.

Jak zawsze, w rozwiązywaniu trudnych problemów pomagają usystematyzowane i mniej lub bardziej sformalizowane rozważania – teoria – prowadzące do określenia praktycznych sposobów postępowania, w przypadku optymalizacji zwanych algorytmami, pozwalających wyznaczyć warianty najlepsze.
Tematem podręcznika jest więc – teoria optymalizacji, którą zaczął tworzyć Leibniz i algorytmy optymalizacji, których bujny rozwój zaczął się 250 lat później – w czasie II Wojny Światowej.
Jednak moim założeniem, nie jest uczynienie z Państwa specjalistów w zakresie tworzenia nowych algorytmów optymalizacji, a tylko wyjaśnienie "jak to działa" po to by potrafili Państwo świadomie z algorytmów istniejących korzystać.
Niewątpliwie najwięcej traktatów napisano o Bogu, następnie o miłości, ale jaki temat jest na trzecim miejscu? Patrioci optymalizacji twierdzą, że o optymalizacji. Sam mam ponad trzydzieści książek papierowych i ze cztery razy tyle elektronicznych poświęconych tej tematyce, a jest to tylko niewielki ułamek ich zbioru. Zatem (optymalny?) wybór tego co najistotniejsze z tej przywalającej człowieka góry informacji nie jest łatwy. W kolejnych rozdziałach tego podręcznika prezentuję swój punkt widzenia na to co ważne, a co można pominąć z nagromadzonej wiedzy związanej z metodami rozwiązywania zadania optymalizacji to jest algorytmami znajdowania takiego elementu/elementów ustalonego zbioru dla którego wybrana funkcja oceniająca przyjmuje najmniejszą/największą wartość z wartości przyjmowanych na tym zbiorze. Mam nadzieję, że spotka się on, podobnie jak jego poprzednie warianty, z pozytywnym odbiorem Czytelników.
Prezentację zacznę od przykładów różnych zadań optymalizacji. Pozwolą one na formalne zdefiniowanie i klasyfikację zadań optymalizacji, w tym m. in. podział na tzw. zadania optymalizacji statycznej i dynamicznej. Dalsze rozważania będą poświęcone przedstawieniu różnych metod rozwiązywania zadań optymalizacji statycznej, tylko którą zajmiemy się w tym podręczniku.
Pierwszymi zdaniami optymalizacji statycznej dla których opracowano efektywny algorytm znajdowania rozwiązania są tzw. zadania programowania liniowego. Moduł drugi to zwięzły opis tych zadań oraz metody Simplex służącej ich rozwiązywaniu. Moduł trzeci przedstawia podstawy matematyczne niezbędne do zrozumienia tak teorii optymalizacji jak i zasad budowy i działania algorytmów optymalizacji tzw. zadań programowania nieliniowego. W module tym także opisano podstawowe iteracyjne schematy (algorytmy) optymalizacji bez ograniczeń: metodę rozsiewania punktów próbnych, metodę obszaru zaufania i metodę kierunków poprawy. Omówiono też pojęcie zbieżności algorytmu optymalizacji. Moduł czwarty to przedstawienie problemów związanych z rozwiązywaniem tzw. zadania poprawy oraz szczegółowy opis gradientowych algorytmów rozwiązywania zadań optymalizacji bez ograniczeń. Analizie matematycznej zadań z ograniczeniami jest poświęcony moduł piąty. Przedstawiono w nim, po niezbędnym przygotowaniu, podstawowe dla teorii tych zadań Twierdzenie Karusha–Kuhna–Tuckera. Ostatni, szósty moduł to prezentacja podstawowych metod znajdowania rozwiązania zadania optymalizacji z ograniczeniami: metod funkcji kary oraz rozszerzonego lagranżianu.