Diminiscing step size §

Si fanno due richieste ragionevoli:

$${\alpha }^k\to 0\sum _k{\alpha }^k=+\infty$$

quindi una successione infinitesima non sommabile, ad esempio $\frac{1}{k}$, l’idea è di consentire al metodo di arrivare ovunque. Infatti la seconda condizione garantisce che non converge ad un punto non stazionario: Sia $x^k\to \overline{x}$, allora scelti $m>n$ abbastanza grandi:

$$|x^m-\overline{x}|<ϵ|x^n-\overline{x}|<ϵ$$

il che implica

$$|x^n-x^m|<2ϵ$$

ma la distanza è pari a:

$$|x^m-x^n|=|\sum _{k=n}^{m-1}{\alpha }^k(-\nabla f(x^k))|\approx \sum _{k=n}^{m-1}{\alpha }^k(-\nabla f(\overline{x}))\square$$

che diverge se il gradiente non si annulla.

Convergenza §

Richiediamo che il gradiente di $f$ sia L-continuo, ed inoltre due limiti per la direzione:

$$c_1\Vert \nabla f(x^k){\Vert }^2\le -\nabla f(x^k{)}^T{d}^k$$ $$\Vert d^k{\Vert }^2\le c_2\Vert \nabla f(x^k){\Vert }^2$$

con $c_1,c_2>0$, sia $x^k\to \overline{x}$. Allora $\nabla f(\overline{x})=0$.

Dim §

Usiamo il Descent Lemma, otteniamo:

$$f(x^k)-f(x^{k+1})\le {\alpha }^k\nabla f(x^k{)}^T{d}^k+\frac{L{{\alpha }^k}^2}{2}\Vert d^k{\Vert }^2$$

usando i bound sulla direzione otteniamo:

$$f(x^k)-f(x^{k+1})\le {\alpha }^k\left[\frac{L}{2}{c}_2\Vert \nabla f(x^k)\Vert -c_1\Vert \nabla f(x^k){\Vert }^2\right]$$

siccome ${\alpha }^k\to 0$, il termine quadratico diventa trascurabile per $k$ abbastanza grande:

$$f(x^k)-f(x^{k+1})\le -{\alpha }^k{c}_1\Vert \nabla f(x^k){\Vert }^2\forall k\ge \overline{k}$$

sommando queste disequazioni a partire da $\overline{k}$ ottengo (si cancellano i termini in mezzo):

$$c_1\sum _{k=\overline{k}}^{\infty }{\alpha }^k\Vert \nabla f(x^k){\Vert }^2\le \underset{k\to \infty }{\lim }f(x^k)-f(x^{\overline{k}})$$

siccome la disuguaglianza precedente ci assicura che la successione è definitivamente monotona, o diverge a $-\infty$ o ad un punto $\overline{x}$. In questo caso il termine di destra è limitato, di conseguenza la serie a sinistra è convergente:

$$\sum _{k=\overline{k}}^{\infty }{\alpha }^k\Vert \nabla f(x^k){\Vert }^2<+\infty$$

ma questo implica $\Vert \nabla f(x^k)\Vert \to 0$, siccome ${\sum }_k{\alpha }^k=+\infty$. $\square$