Ottimizzazione non vincolata: condizioni di ottimalità

Convessità ed esistenza

Nel problema $\min_{x\in S}f(x)$ la funzione obiettivo $f$ e l'insieme ammissibile $S$ sono distinti: $S$ lo fissano i vincoli del problema, non il dominio di $f$. Se $S$ e $f$ sono convessi, ogni minimo locale è globale, quindi un algoritmo non rischia di fermarsi in un minimo locale che non sia globale.

La convessità, anche stretta, non dice però nulla sull'esistenza. Per $f(x)=e^{-x}$ vale $f''(x)=e^{-x}>0$ per ogni $x\in\mathbb R$, quindi $f$ è strettamente convessa, ma $\min_{x\in\mathbb R}e^{-x}$ non ha soluzione: l'estremo inferiore $0$ non è assunto.

Convessa ma senza minimo

$x$

• $f(x)=e^{-x}$

Per l'esistenza resta il teorema di Weierstrass, con $f$ continua e $S$ compatto, cioè chiuso e limitato in $\mathbb R^n$. In un problema non vincolato $S=\mathbb R^n$ è chiuso ma non limitato, quindi il teorema non si applica.

Direzioni di discesa

Da qui il problema è non vincolato, con $f\in C^1(\mathbb R^n)$: esiste il gradiente ed è continuo. In alcuni risultati serve $f\in C^2$. Un vettore $d\neq0$ è di discesa per $f$ in $\bar x$ se esiste $\bar t>0$ tale che

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

La definizione non richiede la differenziabilità di $f$.

Proposizione (condizione necessaria generale). Se $\bar x$ è un punto di minimo locale di $f$, in $\bar x$ non esiste una direzione di discesa.

Dimostrazione. Per assurdo sia $d$ di discesa in $\bar x$. Qualunque intorno sferico di $\bar x$ si scelga, per $t>0$ abbastanza piccolo il punto $\bar x+td$ sta nell'intorno e $f(\bar x+td)<f(\bar x)$. Questo contraddice la definizione di minimo locale. $\blacksquare$

Non servono né la differenziabilità né la continuità di $f$.

Proposizione (condizione sufficiente di discesa del primo ordine). Sia $f\in C^1$. Se $\nabla f(\bar x)^\top d<0$, allora $d$ è di discesa per $f$ in $\bar x$.

Dimostrazione. Per $f\in C^1$ la derivata direzionale è il prodotto del gradiente per la direzione:

$$\lim_{t\to0^+}\frac{f(\bar x+td)-f(\bar x)}{t}=\nabla f(\bar x)^\top d$$

Il limite è negativo, quindi per $t>0$ abbastanza piccolo è negativo il rapporto, e così il numeratore. $\blacksquare$

Se il prodotto è positivo, $d$ è di salita. Se è nullo, l'informazione del primo ordine non decide: la condizione è sufficiente ma non necessaria.

Flesso a tangente orizzontale

$\bar{x}$$d=-1$$x$

• $f(x)=x^3$

Se $\nabla f(\bar x)\neq0$, l'antigradiente $d=-\nabla f(\bar x)$ è di discesa, perché

$$\nabla f(\bar x)^\top d=-\|\nabla f(\bar x)\|^2<0$$

Quindi, con il gradiente a disposizione, una direzione di discesa si trova subito.

Proposizione (condizione sufficiente di discesa del secondo ordine). Sia $f\in C^2$. Se $\nabla f(\bar x)^\top d=0$ e $d^\top\nabla^2f(\bar x)\,d<0$, allora $d$ è di discesa per $f$ in $\bar x$.

Dimostrazione. Poiché $f\in C^2$, vale lo sviluppo

$$\begin{aligned} f(\bar x+td)&=f(\bar x)+t\,\nabla f(\bar x)^\top d\\ &\quad+\tfrac12t^2\,d^\top\nabla^2f(\bar x)\,d+\beta(\bar x,td) \end{aligned}$$

con $\beta(\bar x,td)/t^2\to0$ per $t\to0$. Il termine del primo ordine è nullo. Si divide per $t^2>0$:

$$\begin{aligned} \frac{f(\bar x+td)-f(\bar x)}{t^2}&=\frac12\,d^\top\nabla^2f(\bar x)\,d\\ &\quad+\frac{\beta(\bar x,td)}{t^2} \end{aligned}$$

Il primo addendo è negativo e non dipende da $t$, il secondo tende a $0$. Per $t$ abbastanza piccolo il secondo è più piccolo in valore assoluto, quindi il rapporto è negativo, e così $f(\bar x+td)-f(\bar x)$. $\blacksquare$

Condizioni necessarie di minimo locale

Proposizione (condizione necessaria del primo ordine). Sia $f\in C^1$. Se $\bar x$ è un punto di minimo locale di $f$ su $\mathbb R^n$, allora $\nabla f(\bar x)=0$.

Dimostrazione. Per assurdo $\nabla f(\bar x)\neq0$. Allora l'antigradiente è di discesa in $\bar x$, contro la condizione necessaria generale. $\blacksquare$

La condizione vale per i problemi senza vincoli, non per quelli vincolati. Per $\min x^2$ con $1\le x\le2$ la derivata $2x$ non si annulla in nessun punto ammissibile, eppure il minimo esiste, in $x=1$. Con vincoli di intervallo servono condizioni diverse.

Proposizione (condizione necessaria del secondo ordine). Sia $f\in C^2$. Se $\bar x$ è un punto di minimo locale di $f$ su $\mathbb R^n$, allora $\nabla f(\bar x)=0$ e $\nabla^2f(\bar x)$ è semidefinita positiva:

$$d^\top\nabla^2f(\bar x)\,d\ge0\qquad\forall d\in\mathbb R^n$$

Dimostrazione. Il gradiente nullo è la condizione del primo ordine. Per assurdo $\nabla^2f(\bar x)$ non sia semidefinita positiva: esiste $d$ con $d^\top\nabla^2f(\bar x)\,d<0$. Poiché $\nabla f(\bar x)^\top d=0$, per la condizione del secondo ordine $d$ è di discesa in $\bar x$, contro la condizione necessaria generale. $\blacksquare$

Il caso convesso

Proposizione (condizione necessaria e sufficiente di minimo globale). Sia $f\in C^1$ convessa su $\mathbb R^n$. Allora $\bar x$ è un punto di minimo globale se e solo se $\nabla f(\bar x)=0$.

Dimostrazione. Solo se: un minimo globale è anche locale, e vale la condizione del primo ordine. Se: per $f$ convessa e differenziabile il grafico sta sopra il piano tangente, cioè per ogni $y\in\mathbb R^n$

$$f(y)\ge f(\bar x)+\nabla f(\bar x)^\top(y-\bar x)=f(\bar x)$$

perché $\nabla f(\bar x)=0$. Quindi $\bar x$ è di minimo globale. $\blacksquare$

La convessità fa due salti: la condizione diventa necessaria e sufficiente, e il minimo da locale diventa globale. Il risultato però non garantisce che un minimo esista, né che sia unico.

Condizioni sufficienti di minimo locale

Proposizione (senza dimostrazione). Sia $f\in C^2$ con $\nabla f(\bar x)=0$. Il punto $\bar x$ è di minimo locale di $f$ su $\mathbb R^n$ se vale una delle due:

• $\nabla^2f(\bar x)$ è definita positiva;
• $\nabla^2f(x)$ è semidefinita positiva per ogni $x$ in un intorno di $\bar x$.

Entrambe chiedono più della semidefinita positività nel solo $\bar x$, che è soltanto necessaria.

Punti stazionari e criterio d'arresto

I punti con gradiente nullo sono i punti stazionari:

$$\Omega=\{x\in\mathbb R^n:\ \nabla f(x)=0\}$$

Senza ipotesi di convessità, un algoritmo può garantire al più la convergenza a punti che soddisfano le condizioni necessarie del primo o del secondo ordine, non a un minimo locale. Si chiede quindi la convergenza a punti di $\Omega$ che, possibilmente, non siano massimi locali: anche un massimo locale è stazionario.

Un algoritmo genera una successione $x_k$, per esempio $x_{k+1}=x_k-\alpha_k\nabla f(x_k)$, che converge solo per $k\to\infty$. Non potendo iterare all'infinito, ci si ferma quando

$$\|\nabla f(x_k)\|\le\varepsilon$$

La tolleranza $\varepsilon$ è un parametro, scelto secondo la precisione richiesta: $10^{-4}$, $10^{-6}$, $10^{-12}$.

Funzioni quadratiche

Sia $Q$ una matrice simmetrica $n\times n$ e $c\in\mathbb R^n$:

$$f(x)=\tfrac12x^\top Qx+c^\top x$$

Allora $\nabla f(x)=Qx+c$ e $\nabla^2f(x)=Q$, che non dipende dal punto. Se $\bar x$ è un minimo locale, la condizione del secondo ordine chiede $Q$ semidefinita positiva. Ma allora la Hessiana è semidefinita positiva in ogni punto, quindi $f$ è convessa e il minimo è globale. Per una quadratica non esistono minimi locali che non siano globali.

Proposizione (senza dimostrazione). $f$ ha un punto di minimo globale se e solo se $Q$ è semidefinita positiva ed esiste $x^*$ con $Qx^*+c=0$. Il punto di minimo è unico se e solo se $Q$ è definita positiva.

$Q$ può essere singolare: in quel caso, se il sistema $Qx+c=0$ ha una soluzione, ne ha infinite. Se $Q$ è indefinita, il minimo non esiste. Una quadratica quindi non ha punti di minimo, ne ha uno o ne ha infiniti.

I tre casi con una variabile

$x^{\ast }$$x$

• $f(x)$

$Q$

1

$c$

0,5

Dimostrazioni

Dimostrati: condizione necessaria generale; condizioni sufficienti di discesa del primo e del secondo ordine; condizioni necessarie del primo e del secondo ordine; condizione necessaria e sufficiente nel caso convesso.

Senza dimostrazione: condizioni sufficienti di minimo locale; minimo di una funzione quadratica.