Podręcznik

Rozważamy n-wymiarową przestrzeń wariantów $ℝ^n \ni x$. W przestrzeni tej zadana jest funkcja oceniająca (wyboru, celu)

$f:\mathbb{R}^n\rightarrow\ \mathbb{R},$

pozwalająca porównywać warianty, przy czym z dwu wariantów ten jest lepszy dla którego funkcja oceniająca przyjmuje mniejszą wartość, oraz zbiór wariantów dopuszczalnych $D \subseteq ℝ^n,$ gdzie, dla zadania minimalizacji

$D={x\in\mathbb{R}^n|(\forall j\in\overline{1,m})g_j(x)\le0\land(\forall k\in\overline{1,p})h_k(x)=0\land(\forall i\in\overline{1,r})\ x_i\in[x_i^-,x_i^+]}, \qquad(1.9)$

a $g_j:\mathbb{R}^n\rightarrow\ \mathbb{R},j\in\overline{1,m}$ to funkcje  określające  ograniczenia  nierównościowe $D_\leq$ , natomiast $h_k:\mathbb{R}^n\rightarrow\mathbb{R},  k\in\overline{1,p}$ to funkcje określające ograniczenia równościowe $D_=$.  W określeniu zbioru dopuszczalnego wy-różniliśmy jeszcze, często występujące w zdaniach praktycznych, ograniczenia kostkowe $xi \in [xi–,xi+], i\in\overline{1,r}$, oznaczymy je $D_K$ ,  chociaż formalnie rzecz biorąc są to ograniczenia nierównościowe. Zauważmy, że w celu uniknięcia niebezpieczeństwa określenia zbioru pustego, ograniczeń  równościowych  nie może być więcej niż $n \,(p \leq n).$ Z oczywistego powodu, ograniczeń kostkowych też nigdy nie jest więcej niż n. 

Zatem zbiór wariantów dopuszczalnych (1.9) jest iloczynem trzech zbiorów

$D=D_\le\cap D_=\cap D_K$.

Możemy teraz formalnie określić zadanie optymalizacji.

Wiele zadań praktycznych (nie wszystkie!) można w ten sposób zapisać.

Dlaczego zapisaliśmy zadanie minimalizacji?

Wystarczy więc rozważać tylko jeden z dwu operatorów ekstremalizacji. Do systemu definicji przyjętych w matematyce, lepiej pasuje minimalizacja i w zasadzie wszystkie rozważania teoretyczne prezentowane w literaturze dotyczą minimalizacji.

Zwrócimy teraz krótko uwagę na pewne własności funkcji minimalizowanej i konsekwencje przyjętej definicji zbioru dopuszczalnego.

W zapisanym ogólnym zadaniu optymalizacji ZO trzeba 

znaleźć taki wektor $x^o\in D$, że $(\forall x \in D) f (x^o) \leq f (x)$ .

Jest to wymaganie porównania wszystkich wariantów (wektorów) x ze zbioru dopuszczalnego D i znalezienia takiego wariantu dopuszczalnego, $x^o \in D$, którego ocena, $f (x^o)$, w porównaniu ze ocenami wszystkich wariantów dopuszczalnych jest nie większa, $(\forall x \in D) f (x^o) \leq f (x)$. Tak określony wektor, w opracowaniach dotyczących optymalizacji nazywa się punktem minimum globalnego funkcji f na zbiorze D, bo przy jego ustalaniu porównujemy wszystkie punkty dopuszczalne. 

Jaka jest konsekwencja przyjęcia takiej terminologii? Popatrzmy na Rys. 1.6 przedstawiający funkcję jednej zmiennej. Obok minimum globalnego w punkcie $x^o$ma ona tzw. minimum lokalne w punkcie $x^*$. Dokładna definicja jest następująca:

W przedstawionym ogólnym zadaniu optymalizacji szukamy wariantu dopuszczalnego minimalizującego funkcję celu. Takie wymaganie nie występuje w każdym zadaniu optymalizacji. Czasami ważna jest tylko wartość optymalna funkcji oceniającej, natomiast argumenty optymalizujące – nie są interesujące. Rozważa się wtedy zadanie prostsze:

Funkcje minimalizowane mogą być różne, a ich zachowanie zaskakujące. Wygodnym narzędziem pozwalającym zorientować się co nas może czekać w świecie minimalizacji, a także wyrabiającym intuicję są dla funkcji dwu-argumentowych wykresy poziomicowe (mapy).

Takim wykresem posłużymy się do ustalenia ile minimów lokalnych ma funkcja

$x ↦ f (x) = 2(x_1)^2 + 4x_1(x_2)^3 – 10x_2x_1 + (x_2)^2$

w zbiorze

$D = {(x_1,x_2) | x_1 (x_2)^2(2.4 + x_2) \leq 3\wedge {\frac{3}{2}}x_1 + x_2 \geq 0\wedge (–3 \leq x_i \leq 3, i = 1,2)}.$

Zauważmy, że funkcja f i funkcje $g_j$na pierwszy rzut oka nie sprawiają wrażenia, że geometria zbiorów przez nie wyznaczonych jest tak skomplikowana. Zauważmy, że wszystkie minima lokalne (w tym przykładzie) wynikają z obecności ograniczeń, czasami mówi się, że są indukowane przez ograniczenia.

Zastanówmy się teraz przez chwilę nad strukturą zbioru dopuszczalnego (1.9). Jest on iloczynem trzech zbiorów: $D=D_\leq \cap\ D_=\cap\ D_K.$ Naszkicujmy te zbiory.

Narysowany zbiór D zaznaczony na czarno jest „mały” i na dodatek składa się z dwu rozłącznych części, które nie mają wnętrza („nie mają punktów w środku”). Widać, że najbardziej restrykcyjne są ograniczenia równościowe. Bez nich, omawiany zbiór dopuszczalny byłby spójny (składałby się z jednej części) i tak jak zbiór z rysunku poprzedniego miał niepuste wnętrze.