Rachunek prawdopodobieństwa 1, 2

12.4 Optymalizacja

Dana jest funkcja \(f : A \longrightarrow \r \). gdzie \(A \subset \rn \).

Należy wyznaczyć efektywnie minimum globalne, to znaczy punt \(a \in A\) taki, że

\[ \forall x \in A \ f(a) \le f(x). \]

lub jego możliwie najlepsze przybliżenie.

Oznaczamy zbiór rozwiązań:

\[ A^{\star } := \{a \in A: \hbox { dla kaÅijdego } x \in A \ \‚f(a) \le f(x)\}. \]

Szukanie maximum globalnego funkcji \(f \rwn \) szukanie minimum globalnego funkcji \(-f\).

Omówimy najprostszy algorytm stochastycznej optymalizacji, Pure Random Search (PRS).

Zakładamy, że \(f : A \to \r \) jest funkcją ciągłą, \(A\) jest zwarty. Dla uproszczenia załóżmy, że \(A = [0,1]^n\).

Algorytm PRS.

• 1. Losujemy punkt ze zbioru \(A\) zgodnie z rozkładem jednostajnym na \(A\). Oznaczamy go jako \(x_0\). Kolejne punkty \(x_1, x_2,x_3 \dots ,\) tworzymy w następujący sposób.

  Dla \(t = 0,1,2,3,\dots \):

• 2. Losujemy punkt \(\by _t \in A\) według rozkładu jednostajnego.

• 3. Jeżeli \(f(\by _t) < f(x_t)\), kładziemy \(x_{t+1} = \by _t\). W przeciwnym przypadku kładziemy \(x_{t+1} = x_t\).

Okazuje się, że punkty \(x_t\) określone powyższym algorytmem zmierzają do zbioru \(A^\star \) z prawdopodobieństwem 1, to znaczy \(dist(x_t,A^\star ) \str 0\), gdy \(t \str \infty \). Bardziej formalnie formułujemy to tak.

Dowód.

Przypominamy drugą część lematu 10.17.

Lemat Borela-Cantellego Niech \((\Omega ,\Sigma ,P)\) będzie przestrzenią probabilistyczną.
Niech \(C_1,C_2,C_3,\dots \in \Sigma \) będzie ciągiem zdarzeń niezależnych:

\[\sum _{i=1}^\infty P(C_i) = \infty \ \imp \‚P\left (\bigcap _{t=1}^\infty \bigcup _{i=t}^\infty C_i \right ) = 1. \]

Oznaczmy \(m = \min _A f\). Wtedy \(A^\star = \{x \in A: f(x) = m\}\).

Ciąg \(f(X_t)\) jest nierosnący i ograniczony z dołu przez \(m\), więc jest zbieżny do pewnej zmiennej losowej \(\eta \ge m\).

Niech \(\bY _t\) będą niezależnymi zmiennymi losowymi o rozkładzie jednostajnym na \(A\), których realizacjami są punkty \(\by _i\).

Ustalmy \(\ve > m\).

Ponieważ funkcja \(f\) jest ciągła, zbiór \(B = \{x \in A: f(x) < \ve \}\) jest niepusty i otwarty, więc jego miara Lebesgue’a, \(\nu (B) = \alpha > 0\).

Określmy:
\(C_t = \{\omega \in \Omega : f(\bY _t(\omega )) < \ve \}\) = \(\bY _t^{-1}(B)\), dla \(t = 1,2,3,\dots \).
\(C_t\) są zdarzeniami niezależnymi.

Ponieważ zmienne losowe \(\bY _t\) mają rozkład \(\nu \), więc \(P(C_t) = P_{\bY _t}(B) = \nu (B) = \alpha \) dla \(t \ge 1\). Jest więc spełnione założenie Lematu Borela-Cantellego.

Na podstawie algorytmu PRS zachodzi implikacja:

\[\eta \ge \ve \‚\imp \ \forall t \ge 1\ f(\bY _t) \ge \eta \ge \ve , \]

czyli

\[\{\eta \ge \ve \} \subset \bigcap _{t=1}^\infty \left (\Omega \setminus C_t\right ) =\Omega \setminus \bigcup _{t=1}^\infty C_t.\]

\[\bigcap _{t=1}^\infty \bigcup _{i=t}^\infty C_i \subset \bigcup _{t=1}^\infty C_t \subset \{\eta < \ve \} \]

Z Lematu Borela-Cantellego: \(P(\{\eta < \ve \}) =1\). Ponieważ, \(\ve >m\) było ustalone dowolnie więc \(\eta = m\). Tak więc: \(P(f(X_t) \to m, \hbox { gdy } t \str \infty ) = 1\).

Z ciągłości \(f\) oraz zwartości \(A\), \(P\,(X_t \str A^\star ,\hbox { gdy } t \str \infty ) = 1\) .   \(\Box \)

Rozwiązywanie równań, bądź układów równań, można sprowadzić do problemu poszukiwania minimum globalnego. Rzeczywiście, zamiast szukać rozwiązania układu \(f_i(x) = 0\), \(i =1,...,n\) można szukać minimum globalnego funkcji \(\di F(x) = \sum _{i=1}^nf_i(x)^2\).