Successioni, Newton e ottimizzazione

Algoritmi come successioni

Un algoritmo numerico genera una successione di punti che, se funziona, si avvicina alla soluzione. Progettarlo significa trovare la regola che passa da un punto al successivo. Qui la regola nasce sempre dallo stesso passo: al posto di $f$ si usa la sua approssimazione lineare, di cui si sa risolvere il problema.

Il metodo di Newton per uno zero

Si cerca lo zero di una funzione non lineare $f$ di una variabile. Se $f$ fosse lineare basterebbe un'equazione di primo grado. Da un punto qualsiasi $x_0\in\mathbb R$ si costruisce allora l'approssimazione lineare

$$\hat f(x)=f(x_0)+f'(x_0)(x-x_0)$$

e si chiama $x_1$ il punto che la annulla. Se $f'(x_0)\neq 0$:

$$x_1=x_0-\frac{f(x_0)}{f'(x_0)}$$

Si ripete da $x_1$, poi da $x_2$, e così via. Per l'iterazione generica:

$$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)},\qquad k=0,1,2,\dots$$

Geometricamente l'approssimazione lineare è la tangente al grafico: $x_{k+1}$ è l'intersezione della tangente in $x_k$ con l'asse $x$. Il metodo si generalizza ai sistemi di $n$ equazioni non lineari in $n$ variabili.

Minimizzare: il metodo del gradiente

Si vuole risolvere

$$\min_{x\in\mathbb R} f(x),\qquad f\in C^1(\mathbb R)$$

cioè $f'$ esiste ed è continua. Per una funzione complicata lo studio di crescenza e decrescenza non porta al minimo: serve una regola che generi una successione di punti verso di esso.

Da $x_0\in\mathbb R$ si usa la stessa approssimazione lineare $\hat f$. Si vuole $x_1$ tale che $\hat f(x_1)<\hat f(x_0)=f(x_0)$, cioè

$$f'(x_0)\,(x_1-x_0)<0$$

Il segno di $f'(x_0)$ dice da che parte andare:

• se $f'(x_0)>0$ serve $x_1<x_0$;
• se $f'(x_0)<0$ serve $x_1>x_0$.

Le due regole si riuniscono in una sola: ci si sposta nel verso opposto alla derivata,

$$x_1=x_0-\alpha f'(x_0),\qquad \alpha>0$$

Con questa scelta, se $f'(x_0)\neq 0$, si ha $f'(x_0)(x_1-x_0)=-\alpha f'(x_0)^2<0$ per ogni $\alpha>0$. Ma $f$ non è lineare: la retta scende, la funzione vera può risalire. Il passo $\alpha$ deve essere abbastanza piccolo da avere $f(x_1)<f(x_0)$.

Lo si trova per tentativi, a ogni iterazione:

1. si parte da $\alpha_k=1/(k+1)$, cioè da $\alpha_0=1$ alla prima iterazione;
2. se $f(x_k-\alpha_k f'(x_k))<f(x_k)$ lo si tiene;
3. altrimenti $\alpha_k\leftarrow\alpha_k/2$ e si riprova.

Si dimostra che, con $f'(x_k)\neq 0$, un passo sufficientemente piccolo produce la diminuzione: il dimezzamento prima o poi la ottiene. La successione è

$$x_{k+1}=x_k-\alpha_k f'(x_k),\qquad \alpha_k>0$$

e il procedimento si chiama metodo del gradiente: in una variabile il gradiente è la derivata.

Il metodo del gradiente a più passi

$x$

• $f(x)$
• $x_k$

$k$

0

$x_0$

1,2

$\alpha$

1,4

Nell'addestramento delle reti neurali i pesi si aggiornano con questa regola, e il passo si chiama anche learning rate. Backpropagation indica soltanto le formule ricorsive che calcolano le derivate prime di una funzione complessa, non la regola di ottimizzazione.

Bolzano-Weierstrass per successioni in $\mathbb R^n$

Per $n=1$ è noto: una successione limitata ha almeno una sottosuccessione convergente. Per $n>1$ si considerano successioni $\mathbb N\to\mathbb R^n$. Per semplicità $n=3$, con $x_k^{(i)}$ la componente $i$ di $x_k$.

Se $\{x_k\}$ è limitata, lo è ciascuna componente. Si estrae una sottosuccessione per volta, ognuna dentro la precedente:

• $\{x_k^{(1)}\}$ limitata $\Rightarrow$ esiste $K_1\subseteq\mathbb N$ con $\lim_{k\in K_1,\,k\to\infty}x_k^{(1)}=\bar x^{(1)}$, per esempio $K_1=\{0,4,8,12,\dots\}$;
• $\{x_k^{(2)}\}$ limitata $\Rightarrow$ esiste $K_2\subseteq K_1$ con $\lim_{k\in K_2,\,k\to\infty}x_k^{(2)}=\bar x^{(2)}$, per esempio $K_2=\{0,8,16,24,\dots\}$;
• $\{x_k^{(3)}\}$ limitata $\Rightarrow$ esiste $K_3\subseteq K_2$ con $\lim_{k\in K_3,\,k\to\infty}x_k^{(3)}=\bar x^{(3)}$, per esempio $K_3=\{16,32,48,\dots\}$.

Una sottosuccessione di una successione convergente converge allo stesso limite. Lungo $K_3\subseteq K_2\subseteq K_1$ le tre componenti convergono insieme:

$$\begin{aligned} \lim_{k\in K_3,\,k\to\infty}x_k&=\bar x\\ &=\bigl(\bar x^{(1)},\bar x^{(2)},\bar x^{(3)}\bigr) \end{aligned}$$

Lo stesso argomento vale per un numero qualunque di componenti, in qualsiasi ordine.

Corollario (senza dimostrazione). Se $\{x_k\}\subset E$ e $E$ è compatto, cioè chiuso e limitato, esiste una sottosuccessione che converge a un $\bar x\in E$. La limitatezza dà la sottosuccessione convergente, la chiusura dà $\bar x\in E$.

Versione per insiemi

$\bar x$ è un punto di accumulazione per $E$ se ogni intorno $B(\bar x,\varepsilon)$ contiene un punto di $E$ diverso da $\bar x$.

Teorema. Se $E$ è limitato e formato da infiniti punti, esiste $\bar x$ punto di accumulazione per $E$.

Dimostrazione. Per ipotesi esiste una successione $\{x_k\}$ di infiniti punti distinti di $E$, limitata perché $E$ lo è. Per il teorema precedente esiste $K$ con $\lim_{k\in K,\,k\to\infty}x_k=\bar x$. Dunque per ogni $\varepsilon>0$ esiste $k_\varepsilon$ tale che

$$k\in K,\ k>k_\varepsilon\ \Longrightarrow\ \|x_k-\bar x\|<\varepsilon$$

cioè $x_k\in E\cap B(\bar x,\varepsilon)$. I punti sono distinti: al più uno coincide con $\bar x$, quindi per $k$ grande $x_k\neq\bar x$. Ogni $B(\bar x,\varepsilon)$ contiene allora un punto di $E$ diverso da $\bar x$. $\square$

Il teorema ponte

Collega i limiti di funzione a quelli di successione. Senza dimostrazione. Sia $f\colon D\subseteq\mathbb R^n\to\mathbb R$ e $x_0\in\mathbb R^n$ punto di accumulazione per $D$ (così il limite in $x_0$ ha senso). Allora

$$\begin{aligned} &\lim_{x\to x_0}f(x)=\ell\in\mathbb R^*\iff\\ &\forall\{x_k\}\subset D\setminus\{x_0\},\ x_k\to x_0:\\ &\qquad\lim_{k\to\infty}f(x_k)=\ell \end{aligned}$$

dove $\ell\in\mathbb R^*$ può essere finito oppure $\pm\infty$.

Il punto delicato è «per ogni successione»: le successioni possibili sono infinite e non si controllano tutte. Ne seguono due usi:

• Non esistenza. Due successioni che tendono a $x_0$ ma con $f(x_k)$ che tende a valori diversi bastano a escludere il limite.
• Esistenza. Controllare un numero finito di successioni, anche cento, suggerisce il valore del limite ma non lo dimostra. Per dimostrarlo si torna alla definizione, con gli intorni e $\varepsilon$.

Esempio: un limite che non esiste

$$\begin{gathered} f(x,y)=\frac{x-y}{x+y}\\[0.4em] D=\{(x,y)\in\mathbb R^2:\ x+y\neq 0\} \end{gathered}$$

$D$ è tutto $\mathbb R^2$ meno la retta $x+y=0$. È aperto, e ogni punto di $\mathbb R^2$, origine compresa, è di accumulazione per $D$: il limite per $(x,y)\to(0,0)$ ha senso. Si usano

$$\begin{gathered} a_k=\begin{pmatrix}1/k\\0\end{pmatrix},\qquad b_k=\begin{pmatrix}0\\1/k\end{pmatrix}\\[0.4em] k=1,2,\dots \end{gathered}$$

Entrambe stanno in $D$ e tendono a $(0,0)$. Ma

$$\begin{aligned} f(a_k)&=\frac{1/k-0}{1/k+0}=1\\ f(b_k)&=\frac{0-1/k}{0+1/k}=-1 \end{aligned}$$

quindi $\lim_k f(a_k)=1$ e $\lim_k f(b_k)=-1$. Per il teorema ponte il limite di $f$ per $(x,y)\to(0,0)$ non esiste.

Due successioni verso l'origine

$a_k$$b_k$$(0,0)$$x$$y$

• retta $x+y=0$, esclusa dal dominio

$k$

1

Continuità

Sia $f\colon D\subseteq\mathbb R\to\mathbb R$ e $x_0\in D$.

Se $x_0$ è un punto isolato di $D$, per convenzione $f$ è continua in $x_0$: non si può fare il limite. Se $x_0$ è di accumulazione per $D$, $f$ è continua in $x_0$ quando

$$\lim_{x\to x_0}f(x)=f(x_0)$$

Il valore $f(x_0)$ esiste perché $x_0\in D$. Una funzione è continua in $E\subseteq D$ se è continua in ogni punto di $E$.

Per $f\colon\mathbb R^n\to\mathbb R$ non cambia niente: stessa definizione, con punti di $\mathbb R^n$ e intorni in $\mathbb R^n$.