Capture Theorem §

Sia $f$ continuamente differenziabile, sia $\{x^k\}$ una sequenza generata da un metodo del gradiente, ovvero $x^{k+1}=x^k+{\alpha }^k{d}^k$, tale che $f(x^{k+1})\le f(x^k)$ e che converga ad un punto stazionario. Si assuma che esistano gli scalari $s,c>0$ tale che per tutti i $k$ vale:

$${\alpha }^k\le s,\Vert d^k\Vert \le c\Vert \nabla f(x^k)\Vert$$

Sia $x^{\ast }$ un minimo locale isolato di $f$ in un certo insieme aperto. Allora esiste un insieme aperto $S$ che contiene $x^{\ast }$ tale che se $x^k\in S$ tutti i punti successivi sono in $S$, e $x^k\to x^{\ast }$, ovvero la sucessione viene catturata.

Dim §

Sia $\rho >0$ tale che $x^{\ast }$ sia il minimo della palla $B_{\rho }(x^{\ast })$:

$$f(x^{\ast })<f(x)\forall x\in B_{\rho }(x^{\ast })$$

definiamo una funzione $\varphi (t)$ per $t\in [0,\rho ]$:

$$\varphi (t):=\underset{\{x|t\le \Vert x-x^{\ast }|\le \rho \}}{\min }f(x)-f(x^{\ast })$$

proprietà di questa funzione:

1. $\varphi (t)>0\forall t\in (0,\rho ]$
2. è monotona non decrescente

Fissato $ϵ\in (0,\rho ]$ sia $r>0$ tale che:

$$\Vert x-x^{\ast }\Vert <r⟹\Vert x-x^{\ast }\Vert +sc\Vert \nabla f(x)\Vert <ϵ$$

questo insieme è ben definito, infatti $\Vert \nabla f(x)\Vert$ vale $0$ in $x^{\ast }$, e dalla continuità ne segue che questo termine può essere reso arbitrariamente piccolo stando abbastanza vicino a $x^{\ast }$.

L’insieme $S$ del teorema è:

$$S:=\left\{x|\Vert x-x^{\ast }\Vert <ϵ,f(x)<f(x^{\ast })+\varphi (r)\right\}$$

alcune osservazioni:

1. $S\subseteq B_{\rho }(x^{\ast })$, ovvero è dentro la palla dove è l’unico minimo.
2. la seconda condizione non permette al metodo di “scappare”

Dimostriamo che se $x^k\in S$ allora $x^{k+1}\in S$, per induzione allora tutta la successione rimane in $S$.

Dalla definizione di $S$ vale:

$$f(x^k)-f(x^{\ast })<\varphi (r)$$

ora sfruttiamo la definizine di $\varphi$, che è il minimo di tutti i vettori nella corona circolare $t\le \Vert x-x^{\ast }\Vert \le \rho$. Siamo certi che $x^k$ appartenga alla corona $\Vert x^k-x^{\ast }\Vert \le \Vert x-x^{\ast }\Vert \le \rho$, quindi:

$$\varphi (\Vert x^k-x^{\ast }\Vert )\le f(x^k)-f(x^{\ast })<\varphi (r)$$

siccome $\varphi$ è monotona non decrescente, questo implica che:

$$\Vert x^k-x^{\ast }\Vert <r$$

quindi rispetta

$$\Vert x^k-x^{\ast }\Vert +sc|\nabla f(x^k)\Vert <ϵ$$

con un’altra semplice relazione otteniamo la tesi. Stimiamo

$$\Vert x^{k+1}-x^{\ast }\Vert =\Vert x^k+{\alpha }^k{d}^k-x^{\ast }\Vert \le \Vert x^k-x^{\ast }\Vert +{\alpha }^k\Vert d^k\Vert$$

usiamo ancora le ipotesi che limitano lo step e la norma della direzione:

$$\le \Vert x^k-x^{\ast }\Vert +sc\Vert \nabla f(x^k)\Vert$$

combinato con il risultato precedente:

$$\Vert x^{k+1}-x^{\ast }\Vert <ϵ$$

siccome $f(x^{k+1})<f(x^k)$, ne segue:

$$f(x^{k+1})-f(x^{\ast })<f(x^k)-f(x^{\ast })<\varphi (r)$$

quindi anche $x^{k+1}\in S$. Siccome la chiusira si $S$ è compatta, la successione converge all’unico punto stazionario $x^{\ast }$. $\square$

Oss §

E’ evidente come ogni per ogni $S^{\prime }\subseteq S$ il teorema continua a valre, ovvero possiamo rendere piccolo a piacere l’insieme di cattura.