Distribuzione di probabilità dei punti estremanti di un processo stocastico di Wiener

In alcuni problemi di ottimizzazione globale non è nota una definizione analitica della funzione obiettivo ed è solo possibile una sua valutazione in punti prefissati. Vi sono funzioni obiettivo in cui il costo di una valutazione è molto alto, come ad esempio avviene se la valutazione è il risultato di un esperimento o di una misurazione particolarmente onerosa. In questi casi la ricerca degli estremanti globali (massimi o minimi) deve essere effettuata con metodi denominati di “ottimizzazione bayesiana”, che tendono a ottenere il miglior risultato a priori possibile con un numero prefissato di valutazioni. In sintesi si ipotizza che al di fuori dei punti in cui la funzione è già stata valutata, questa abbia un andamento che può essere rappresentato da un processo stocastico con opportune caratteristiche. Il processo stocastico viene assunto come modello della funzione obiettivo, ipotizzando che la distribuzione di probabilità dei suoi punti estremanti dia la migliore indicazione a priori sui valori dei punti estremanti della funzione obiettivo. Nel caso più semplice della ottimizzazione unidimensionale, posto che la funzione obiettivo sia stata valutata in un certo numero di punti, si pone il problema di scegliere in quali degli intervalli così individuati sia più opportuno investire per l'effettuazione di una nuova valutazione. Se come modello della funzione obiettivo si è scelto un processo stocastico di Wiener, è possibile calcolare la distribuzione di probabilità dei punti estremanti del modello all’ interno di ciascun intervallo, condizionata dai valori noti assunti ai suoi estremi. Il confronto delle distribuzioni ottenute offre un criterio per la scelta dell'intervallo in cui iterare il procedimento. Un valore scelto a priori di probabilità di avere individuato un intervallo in cui cade il punto estremante globale della funzione obiettivo può fungere da criterio di arresto. L'ottimizzazione bayesiana non è un metodo efficiente per la ricerca precisa di estremanti locali per cui, una volta ristretto l'intervallo di ricerca, a seconda delle caratteristiche del problema si procede, se necessario, con metodi specifici per l'ottimizzazione locale.

La formula della distribuzione con un abbozzo di dimostrazione è indicata nell'articolo di H.J. Kushner (appendix 3, pagina 106) pubblicato nel 1964, la dimostrazione costruttiva dettagliata è ripresa da , sviluppata nel contesto della ricerca nel campo degli algoritmi di ottimizzazione bayesiana.

Enunciato

Sia la funzione reale di variabile reale $X(t)$ definita sull'intervallo $[a,b]$ un processo stocastico di Wiener e sia inoltre $X(a)=X_a.$

Per le proprietà dei processi di Wiener, gli incrementi hanno distribuzione normale: $a\le t_1<t_2\le b\Rightarrow$ $X(t_2)-X(t_1)\sim N(0;{\sigma }^2(t_2-t_1))$

Sia $F(z)=P(\underset{a\le t\le b}{\min }X(t)\le z|X(b)=X_b)$ la distribuzione di probabilità del valore minimo della funzione $X(t)$ nell'intervallo $[a,b]$ condizionata dal valore $X(b)=X_b$ .

Si dimostra che :

$F(z)=\{\begin{array}{cc}1& \text{per }z\ge \min \{X_a,X_b\},\\ \exp (-2\frac{(z-X_b)(z-X_a)}{{\sigma }^2(b-a)})& \text{per }z<\min (X_a,X_b).\end{array}$

Dimostrazione costruttiva

Il caso $z\ge \min (X_a,X_b)$ è immediata conseguenza della definizione di minimo, nel seguito si supporrà sempre $z<\min (X_a,X_b)$ e si escluderà il caso limite $\underset{a\le t\le b}{\min }X(t)=\min (X_a,X_b)$.

Si consideri $X(t)$ definita in un numero finito di punti $t_k\in [a,b],0\le k\le n,t_0=a$.

Posto $T_n\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{t_k,0\le k\le n,\}$ al variare di $n$ la successione di insiemi $\{T_n\}$ sia tale che $T_n\subset T_{n+1}$ e che $\bigcup _{n=0}^{+\mathrm{\infty }}{T}_n$ sia un insieme denso in $[a,b]$,

per cui ogni intorno di ogni punto di $[a,b]$ contiene un elemento di uno degli insiemi $T_n$.

Sia $\mathrm{\Delta }z$ un numero reale positivo tale che $z+\mathrm{\Delta }z<\min (X_a,X_b).$

Sia $E$ l'evento così definito: $E\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}(\underset{a\le t\le b}{\min }X(t)<z+\mathrm{\Delta }z)$ $⟺$ $(\mathrm{\exists }t\in [a,b]:X(t)<z+\mathrm{\Delta }z)$ .

Avendo escluso il caso limite$\underset{a\le t\le b}{\min }X(t)=\min (X_a,X_b)$ è sicuramente $P(E)>0$.

Siano $E_n,n=0,1,2,\dots$ gli eventi così definiti: $E_n\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}(\mathrm{\exists }{t}_k\in T_n:z<X(t_k)<z+\mathrm{\Delta }z)$ e sia $\nu$ il primo k fra i $t_k\in T_n$ che definiscono $E_n$.

dato che $T_n\subset T_{n+1}$ è evidentemente $E_n\subset E_{n+1}$. Si dimostrerà ora la (2.1):

(2.1) $E=\bigcup _{n=0}^{+\mathrm{\infty }}{E}_n$

Dalla definizione degli eventi $E_n$, $\mathrm{\forall }n{E}_n\Rightarrow E$, per cui $\bigcup _{n=0}^{+\mathrm{\infty }}{E}_n\subset E$ . Si verificherà ora che vale anche la relazione $E\subset \bigcup _{n=0}^{+\mathrm{\infty }}{E}_n$ per cui resterà provata la (2.1).

La definizione di $E$, la continuità di $X(t)$ e l'ipotesi $z<X_a=X(a)$ implicano, per il teorema dei valori intermedi, $(\mathrm{\exists }\overline{t}\in [a,b]:z<X(\overline{t})<z+\mathrm{\Delta }z)$.

Dalla continuità di $X(t)$ e dall'ipotesi che $\bigcup _{n=0}^{+\mathrm{\infty }}{T}_n$ sia denso in $[a,b]$ si deduce che $\mathrm{\exists }\overline{n}$ tale che per $t_{\nu }\in T_{\overline{n}}$ risulti $z<X(t_{\nu })<z+\mathrm{\Delta }z$ ,

quindi $E\subset E_{\overline{n}}\subset \bigcup _{n=0}^{+\mathrm{\infty }}{E}_n$ da cui la (2.1).

(2.2) $P(E)=\underset{n\to +\mathrm{\infty }}{\lim }P(E_n)$

La (2.2) si deduce dalla (2.1) considerando che $E_n\Rightarrow E_{n+1}$, per cui la successione delle probabilità $P(E_n)$ è monotona non decrescente e quindi converge al suo estremo superiore. Per la definizione degli eventi $E_n$, $\mathrm{\forall }nP(E_n)>0\Rightarrow P(E_n)=P(E_{\nu })$ e per la (2.2) $P(E)=P(E_{\nu })$.

Nel seguito si assume sempre $n\ge \nu$, per cui $t_{\nu }$è ben definito.

(2.3) $P(X(b)⩽-X_b+2z)⩽P(X(b)-X(t_{\nu })<-X_b+z)$

Infatti dato che per definizione di $E_n$ è $z<X(t_{\nu })$, vale la relazione $(X(b)⩽-X_b+2z)\Rightarrow (X(b)-X(t_{\nu })<-X_b+z)$.

In modo analogo dato che per definizione di $E_n$ è $z<X(t_{\nu })$, vale la relazione (2.4):

(2.4) $P(X(b)-X(t_{\nu })>X_b-z)⩽P(X(b)>X_b)$

(2.5)$P(X(b)-X(t_{\nu })<-X_b+z)=P(X(b)-X(t_{\nu })>X_b-z)$

Infatti la variabile casuale $(X(b)-X(t_{\nu }))\sim N(\varnothing ;{\sigma }^2(b-t_{\nu }))$ ha una densità di probabilità simmetrica rispetto alla sua media che è zero.

Mettendo in sequenza le relazioni (2.3), (2.5) e (2.4) si ottiene la (2.6) :

(2.6) $P(X(b)⩽-X_b+2z)⩽P(X(b)>X_b)$

Con lo stesso procedimento usato per ottenere (2.3), (2.4) e (2.5) sfruttando questa volta la relazione $X(t_{\nu })<z+\mathrm{\Delta }z$ si ottiene la (2.7):

(2.7) $P(X(b)>X_b)⩽P(X(b)-X(t_{\nu })>X_b-z-\mathrm{\Delta }z)$$=P(X(b)-X(t_{\nu })<-X_b+z+\mathrm{\Delta }z)⩽P(X(b)<-X_b+2z+2\mathrm{\Delta }z)$

Applicando successivamente (2.6) e (2.7) si ha:

(2.8) $P(X(b)⩽-X_b+2z)⩽P(X(b)>X_b)$ $⩽P(X(b)<-X_b+2z+2\mathrm{\Delta }z)$

Da $X_b>z+\mathrm{\Delta }z>z$, per la continuità di $X(t)$ e il teorema dei valori intermedi $X(b)>X_b>z+\mathrm{\Delta }z>z\Rightarrow E_n$ , da cui $P(X(b)>X_b)=P(E_n,X(b)>X_b)$

Sostituendo in (2.8) e passando ai limiti: $\underset{n\to +\mathrm{\infty }}{\lim }{E}_n(\mathrm{\Delta }z)\to E(\mathrm{\Delta }z)$ mentre per $\mathrm{\Delta }z\to 0$ l'evento $E(\mathrm{\Delta }z)$ converge a $\underset{a\le t\le b}{\min }X(t)⩽z$

(2.9) $P(X(b)⩽-X_b+2z)=$$P(\underset{a\le t\le b}{\min }X(t)⩽z,X(b)>X_b)$

$\mathrm{\forall }d{X}_b>0$, sostituendo $(X_b)$ con $(X_b-d{X}_b)$nella (2.9) si ottiene l'equivalente:

(2.10)$P(X(b)⩽-X_b+2z+d{X}_b)=$$P(\underset{a\le t\le b}{\min }X(t)⩽z,X(b)>X_b-d{X}_b)$

Applicando il teorema di Bayes all'evento congiunto $(\underset{a\le t\le b}{\min }X(t)⩽z,X_b-d{X}_b<X(b)⩽X_b)$

(2.11) $P(\underset{a\le t\le b}{\min }X(t)⩽z\mid X_b-d{X}_b<X(b)⩽X_b)=$$P(\underset{a\le t\le b}{\min }X(t)⩽z,X_b-d{X}_b<X(b)⩽X_b)$ $/P(X_b-d{X}_b<X(b)⩽X_b)$

Ponendo $B\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{X(b)>X_b\},C\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{X_b-d{X}_b<X(b)\le X_b\},D\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{X(b)>X_b-d{X}_b\},A\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{\underset{a\le t\le b}{\min }X(t)⩽z\}$ risulta

$D=B\cup C\Rightarrow P(A,D)=P(A,B\cup C)=P(A,B)+P(A,C)\Rightarrow P(A,C)=P(A,D)-P(A,B)$

(2.12) $P(A,C)=P(A,D)-P(A,B)$

Sostituendo la (2.12) nella (2.11), si ottiene l'equivalente:

(2.13)$P(\underset{a\le t\le b}{\min }X(t)⩽z\mid X_b-d{X}_b<X(b)⩽X_b)=(P(\underset{a⩽t⩽b}{\min }X(t)\le z,X(b)>X_b-d{X}_b)-P(\underset{a⩽t⩽b}{\min }X(t)\le z,X(b)>X_b))/P(X_b-d{X}_b<X(b)⩽X_b)$

Sostituendo (2.9) e (2.10) nella (2.13):

(2.14)$P(\underset{a\le t\le b}{\min }X(t)⩽z\mid X_b-d{X}_b<X(b)⩽X_b)=$$(P(X(b)⩽-X_b+2z+d{X}_b)-P(X(b)⩽-X_b+2z)$$/P(X_b-d{X}_b<X(b)⩽X_b)$

Si osservi che nel secondo membro della (2.14) compare la distribuzione di probabilità della variabile casuale $X(b)$, normale con media $X_a$ e varianza ${\sigma }^2(b-a)$.

Ai valori delle realizzazioni $X_b$ e $-X_b+2z$ della variabile casuale $X(b)$ corrispondono rispettivamente le densità di probabilità:

(2.15) $P(X_b)d{X}_b=\frac{1}{\sigma \sqrt{2\pi (b-a)}}\exp (-\frac{1}{2}\frac{(X_b-X_a{)}^2}{{\sigma }^2(b-a)})d{X}_b$

(2.16) $P(-X_b+2z)d{X}_b=\frac{1}{\sigma \sqrt{2\pi (b-a)}}\exp (-\frac{1}{2}\frac{(-X_b+2z-X_a{)}^2}{{\sigma }^2(b-a)})d{X}_b$

Sostituendo (2.15) e (2.16) nella (2.14) e prendendo il limite per $d{X}_b\to 0$ si è dimostrata la tesi:

$F(z)=P(\underset{a\le t\le b}{\min }X(t)\le z|X(b)=X_b)=$

$=\frac{1}{\sigma \sqrt{2\pi (b-a)}}\exp (-\frac{1}{2}\frac{(-X_b+2z-X_a{)}^2}{{\sigma }^2(b-a)})d{X}_b$$╱\frac{1}{\sigma \sqrt{2\pi (b-a)}}\exp (-\frac{1}{2}\frac{(X_b-X_a{)}^2}{{\sigma }^2(b-a)})d{X}_b=$

$=\exp (-\frac{1}{2}\frac{(-X_b+2z-X_a{)}^2-(X_b-X_a{)}^2}{{\sigma }^2(b-a)})=$$\exp (-2\frac{(z-X_b)(z-X_a)}{{\sigma }^2(b-a)})$

Bibliografia

• A versatile stochastic model of a function of unknown and time varying form - Harold J Kushner - Journal of Mathematical Analysis and Applications Volume 5, Issue 1, August 1962, Pages 150-167.
• The Application of Bayesian Methods for Seeking the Extremum - J. Mockus, J. Tiesis, A. Zilinskas - IFIP Congress 1977, August 8-12 Toronto.

Voci correlate

• Variabile casuale
• Probabilità
• Evento (teoria della probabilità)
• Probabilità condizionata
• Processo stocastico
• Processo di Wiener