MO Moduł 2

---

W zadaniu prostszym szukamy tylko minimalnej wartości funkcji kryterialnej, wektor (wektory) przy którym ta minimalna wartość jest osiągana nas nie interesuje. Dalej będziemy zadanie optymalizacji (minimalizacji) traktowali zawsze jako zadanie znalezienia argumentu minimalizującego

---

W sformułowaniu zadania minimalizacji jest polecenie “znaleźć”. Ale matematyka nie dostarcza nam narzędzi pozwalających bezpośrednio to polecenie wypełnić. Brak bezpośrednich narzędzi pozwalających wprost znaleźć rozwiązanie zadania optymalizacji oznacza, że wtedy gdy chcemy je znaleźć drogą rachunkową musimy oryginalne sformułowanie przekształcić do postaci pozwalającej na wykonanie stosownych rachunków. Jak się o tym przekonamy w wykładach następnych jest to najczęściej odpowiednio określony układ równań i nierówności (obecność nierówności jest kłopotliwa), którego rozwiązanie jest (lub może być, warunek konieczny!) rozwiązaniem wyjściowego zadania optymalizacji.

---

Zauważmy, że wiele algorytmów rozwiązywania zadań optymalizacji podobnych jest do algorytmów rozwiązywania równań i nierówności, bo przecież nie każde równanie potrafimy rozwiązać rachunkowo.

---

---

---

---

Twórcy i badający algorytmy optymalizacji traktują obiekty swoich zainteresowań jak stworzenia, co przy opisie oznacza, że ich funkcjonowanie jest przestawiane jako wynik ich rozmyślnego działania. I ja też przyjmę taką konwencję.

---

Wyobraźmy więc sobie, jak może rozumować Algorytm (komputerowy), postawiony na schodach, którego zadaniem jest zejście do najniższego poziomu schodów. Przyjmujemy, że Algorytm całych schodów nie widzi, natomiast potrafi ocenić położenie każdego stopnia w stosunku do ustalonego poziomu odniesienia, nazwiemy je wysokością (dla każdego wariantu potrafi obliczyć wartość funkcji celu).

---

Algorytm wie, że stoi na jakimś stopniu i może się ruszać w jedną ze stron, przyjmijmy, że prawą i lewą. Jeżeli założymy, że jest “sprawny fizycznie” to może przeskakiwać kilka stopni na raz. Stopnie na schodach, nawet nieskończonych, można policzyć, każdy stopień to wariant, a więc zbiór wariantów jest przeliczalny. Jeżeli liczba stopni jest skończona (zbiór dopuszczalny jest skończony, a więc ograniczony) i nie jest zbyt duża w stosunku do szybkości poruszania się po nich Algorytmu, to przy założeniu, że jest on w stanie powiązać w pary stopień i jego wysokość i zapamiętać te pary, postępowanie jest oczywiste: być na wszystkich stopniach, określić ich wysokość i wybrać ten o wysokości najmniejszej (przeszukać wszystkie warianty). Gdy stopni jest bardzo dużo, Algorytm może odwiedzać np. co dziesiąty stopień (przeszukanie wybranych punktów węzłowych), albo wybierać je w sposób przypadkowy zgodnie z rozkładem równomiernym (równomierne przeszukanie przypadkowe). Takie postępowanie nie gwarantuje jednak znalezienia rozwiązania – Algorytm może przeskoczyć nad stopniem najniższym. Powstaje więc problem dokładności znalezionego rozwiązania, ściśle związany z ilością odwiedzonych stopni (ilością punktów próbnych) ale też i ze sposobem wybierania stopni do odwiedzenia.

---

Może, startując ze stopnia na którym stoi wykonać krok (ustaloną liczbę kroków) w prawo, wrócić i wykonać krok w lewo. W ten sposób ustali, że lokalnie schody opadają w prawo. Wyciągnie stąd wniosek, że należy schodzić w prawo. Gdy ma dużo czasu będzie schodził stopień po stopniu, aż zacznie się wspinać – wycofa się do poprzedniego stopnia i wie, że znalazł lokalne minimum. Gdy jest leniwy to go to zadowoli.

---

---

---

Pytania, które trzeba teraz postawić: Jak Algorytm ma zabrać się za poszukiwania aby znaleźć minimum globalne ? Algorytm wie że musi się ruszyć w prawo, ale jak długi skok ma wykonać ? Naukowcy i praktycy pracują nad odpowiedzią na to pytanie od mniej więcej 50 lat, i dalsza część tych wykładów jest poświecona zwięzłemu przedstawieniu najistotniejszych, zdaniem ich autora, dokonań w tej dziedzinie.

---

---

---

---

---

---

Przedstawione rysunki są trójwymiarowymi wykresami tej samej funkcji dwu zmiennych, wykreślonymi na podstawie wartości obliczonych w węzłach równomiernej siatki prostokątnej o: $30x30=900$ węzłach i $33x33=1089$ węzłach. Tam gdzie było minimum – pojawiło się maksimum lokalne!

---

---

Przedstawiony rysunek został wykonany na siatce o $70x70=4900$ węzłach i zgodnie z teorią pokazuje właściwe przybliżenie tej funkcji. Zauważmy tu, że dokładna analiza pokazała, że minimalna wartość funkcji oceniającej określona dla tych trzech siatek różni się nieznacznie. Oczywiście nie można tego powiedzieć o punktach w których ta wartość jest osiągana.

---

---