Costand step size

Step costante §

La regola più semplice, passo costante:

$$x^{k+1}=x^k+{\alpha }^k{d}^k{\alpha }^k=s$$

Convergenza §

Intuitivamente, se il passo $s$ è troppo grande, il metodo diverge, se è troppo piccolo sarà lento. Troviamo una condizione, legata alla $L$-continuità della funzione, che ci assicura convergenza.

Applicando il Descent Lemma per stimare la differenza della funzione in due passi $x^k$ e $x^{k+1}$ otteniamo:

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

ma $x^{k+1}-x^k={\alpha }^k{d}^k$

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

richiediamo che il passo ${\alpha }^k$ sia compreso tra:

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

con $ϵ>0$.

nel caso più semplice di steepest descent, ovvero $d^k=-\nabla f(x^k)$ e otteniamo:

$$ϵ\le {\alpha }^k\le \frac{2-ϵ}{L}$$

Facciamo vedere come con questi limiti $x^k$ converge ad un punto stazionario. Riscrivendo il lato destro della disuguaglianza ottenuta tramite il Desceng Lemma:

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

ma l’upper bound di ${\alpha }^k$ impliche che:

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

ed usando ${\alpha }^k\ge ϵ$ otteniamo:

$$f(x^{k+1})-f(x^k)\ge \frac{{ϵ}^2}{2}|\nabla f(x^k{)}^T{d}^k|\ge 0$$

prendendo una sottosuccessione che converge ad un punto non stazionario $\overline{x}$, si ottiene:

$$|\nabla f(x^k{)}^T{d}^k|\to 0$$

che va contro l’ipotesi di gradient related. $\square$