Ottimizzazione: minimi, esistenza e direzioni di discesa

Il problema di ottimizzazione

Un problema di ottimizzazione chiede di minimizzare una funzione $f:S\to\mathbb R$ su un insieme $S\subseteq\mathbb R^n$:

$$\min_{x\in S}f(x)$$

$S$ è l'insieme ammissibile, cioè l'insieme in cui vive la variabile: non coincide con il dominio della formula di $f$. Ogni $x\in S$ è un punto ammissibile, un candidato a essere la soluzione, e $f$ è la funzione obiettivo. Se $S=\mathbb R^n$ il problema è non vincolato. Se $S$ è un sottoinsieme proprio è vincolato: da un punto di $S$ non ci si può spostare dove si vuole, e cambiano sia gli algoritmi sia le condizioni di ottimalità.

Cambiando $S$ cambia il problema, anche con la stessa $f$. Per $f(x)=x^2$:

• su $S=\mathbb R$ il minimo è $0$, in $x=0$, dove $f'(0)=0$;
• su $S=[1,2]$ il minimo è $1$, in $x=1$, dove $f'(1)=2>0$;
• su $S=(0,1]$ il minimo non esiste: $0$ è l'estremo inferiore dei valori, ma non è assunto.

$f(x)=x^2$ su tre insiemi

Insieme ammissibile $S$

$\mathbb{R}$$[1,2]$$(0,1]$

$x^{\ast }$$x$

• $f(x)=x^2$
• $f$ su $S$

Su $[1,2]$ il minimo ha derivata positiva: in un problema vincolato un punto di minimo non annulla necessariamente la derivata.

Minimi e massimi, locali e globali

Un punto $x^*\in S$ è di minimo globale di $f$ su $S$ se

$$f(x^*)\le f(x)\qquad\forall x\in S$$

Il valore $f(x^*)$ è il minimo globale. Il punto e il valore sono cose diverse: $x^*$ è il punto di minimo, $f(x^*)$ è il minimo. I punti di minimo globale possono essere più d'uno, e il loro insieme è $\operatorname{argmin}_{x\in S}f(x)$. Il minimo globale è stretto se $f(x^*)<f(x)$ per ogni $x\in S$ con $x\neq x^*$, e allora il punto è unico.

Un punto $x^*\in S$ è di minimo locale se esiste $\rho>0$ tale che

$$f(x^*)\le f(x)\qquad\forall x\in B_\rho(x^*)\cap S$$

dove $B_\rho(x^*)=\{y\in\mathbb R^n:\ \|x^*-y\|<\rho\}$ è l'intorno. Si interseca con $S$ perché l'intorno può uscire da $S$. Il minimo locale è stretto se vale $<$ per $x\neq x^*$. Ogni punto di minimo globale è anche di minimo locale, perché la disuguaglianza vale su tutto $S$. Il viceversa in generale è falso.

Minimo locale e minimo globale

$x^{\ast }$$\bar{x}$$x$

• $f$
• $f(\bar{x})$
• $B_{\rho }(\bar{x})$

$\rho$

0,5

Massimi. Le definizioni di massimo si ottengono invertendo le disuguaglianze. Massimizzare $f$ equivale a minimizzare $-f$, con gli stessi punti, e

$$\max_{x\in S}f(x)=-\min_{x\in S}\bigl(-f(x)\bigr)$$

Per questo la teoria si scrive per i minimi. I risolutori numerici minimizzano, e per un massimo basta cambiare segno all'obiettivo.

Esistenza: il teorema di Weierstrass

Esistenza e unicità del punto di minimo sono due questioni distinte, con ipotesi diverse, e si trattano una dopo l'altra. L'esistenza si ottiene con la continuità e la compattezza, l'unicità con la convessità.

Teorema. Siano $S\subseteq\mathbb R^n$ non vuoto e compatto e $f:\mathbb R^n\to\mathbb R$ continua. Allora $f$ ha su $S$ un punto di minimo globale e un punto di massimo globale.

Dimostrazione. Basta il minimo: il massimo di $f$ è il minimo di $-f$. Sia $L=\inf_{x\in S}f(x)$, con $L=-\infty$ se $f$ non è limitata inferiormente su $S$. Per la definizione di estremo inferiore esiste una successione $x_k\in S$ con $f(x_k)\to L$. Poiché $S$ è compatto, esistono un insieme di indici $K$ e un punto $x^*\in S$ tali che

$$\lim_{\substack{k\to\infty\\k\in K}}x_k=x^*$$

Converge solo la sottosuccessione, non l'intera successione. Per la continuità di $f$ vale $f(x_k)\to f(x^*)$ lungo $K$, e lungo $K$ vale anche $f(x_k)\to L$. Per l'unicità del limite $f(x^*)=L$. Quindi $L$ è finito ed è un minorante dei valori di $f$ su $S$:

$$f(x^*)=L\le f(x)\qquad\forall x\in S$$

Allora $x^*$ è un punto di minimo globale. $\blacksquare$

La compattezza serve in entrambe le sue parti. Se $S$ non è limitato i valori possono scendere senza fine. Se $S$ non è chiuso l'estremo inferiore può cadere sul bordo escluso, come per $x^2$ su $(0,1]$.

Il teorema dà solo una condizione sufficiente. Per $f(x)=x^4+x^2$ su $S=(-2,10)$, che è aperto e quindi non compatto, il minimo esiste: è $0$, in $x=0$.

Unicità: la convessità

Se $S$ è convesso e $f$ è convessa su $S$, ogni punto di minimo locale è anche di minimo globale, e l'insieme dei punti di minimo globale è convesso. Servono entrambe le convessità: di $f$ conta solo ciò che fa su $S$. Il risultato è utile perché certificare un minimo locale è molto più facile che certificare un minimo globale. Non dice però che il minimo esista: la convessità non assicura l'esistenza.

Se $S$ è convesso e $f$ è strettamente convessa su $S$, un punto di minimo locale è l'unico punto di minimo locale e l'unico punto di minimo globale. Per l'unicità serve la stretta convessità: con un tratto piatto i minimi sono infiniti.

$f(x)=\max (|x|-w,0{)}^2$: tratto piatto e minimo non unico

$x$

• $f$
• punti di minimo

$w$

0,8

La stretta convessità è sufficiente ma non necessaria: una funzione convessa con tratti rettilinei non è strettamente convessa, eppure può avere un solo punto di minimo.

Direzioni di discesa

Una condizione necessaria seleziona i punti candidati. Una condizione sufficiente certifica che un punto è di minimo. In un problema non vincolato da un minimo non si può scendere, quindi si guardano le direzioni lungo cui la funzione diminuisce.

Un vettore $d\neq0$ è una direzione di discesa per $f$ in $x$ se esiste $\bar t>0$ tale che

$$f(x+td)<f(x)\qquad\forall t\in(0,\bar t)$$

La definizione dipende dal punto $x$.

Un passo lungo una direzione di discesa

$x$$x+td$$x$

• $f$
• $f(x)$ di partenza

$t$

0,3

Se $f$ è differenziabile e $\nabla f(x)^\top d<0$, allora $d$ è di discesa. In particolare, se $\nabla f(x)\neq0$ lo è l'antigradiente $d=-\nabla f(x)$, perché

$$\nabla f(x)^\top\bigl(-\nabla f(x)\bigr)=-\|\nabla f(x)\|^2<0$$

Se $\nabla f(x)=0$ l'antigradiente è il vettore nullo, che non è una direzione. L'antigradiente è la direzione da cui parte quasi ogni algoritmo.

Proposizione (senza dimostrazione; l'argomento che segue è un'aggiunta). Se $f$ è di classe $C^1$ e convessa su una palla di centro $x$, e $d$ è una direzione di discesa per $f$ in $x$, allora $\nabla f(x)^\top d<0$.

Argomento. Per $t>0$ piccolo il punto $x+td$ sta nella palla e $f(x+td)<f(x)$. Il criterio del primo ordine per le funzioni convesse dà $f(x+td)\ge f(x)+t\,\nabla f(x)^\top d$. Insieme alla discesa segue $t\,\nabla f(x)^\top d<0$, cioè $\nabla f(x)^\top d<0$.

Senza la convessità la condizione $\nabla f(x)^\top d<0$ è solo sufficiente.

Dimostrazioni

Dimostrati: teorema di Weierstrass.

Senza dimostrazione: discesa e segno della derivata direzionale, per $f$ convessa.