Esistenza dei minimi e funzioni coercive

Quando un minimo esiste

Il problema $\min_{x\in S}f(x)$ chiede un punto $x^*\in S$ con $f(x^*)\le f(x)$ per ogni $x\in S$. Prima di cercarlo bisogna sapere se esiste. Il primo risultato è il teorema di Weierstrass.

Teorema di Weierstrass (senza dimostrazione). Se $S$ è non vuoto e compatto e $f$ è continua, esiste un punto di minimo globale di $f$ su $S$.

Nel problema non vincolato $S=\mathbb R^n$ non è compatto, quindi il teorema non si applica. Lo si usa su un sottoinsieme di $\mathbb R^n$ scelto bene: un insieme di livello.

Insiemi di livello

Per $\alpha\in\mathbb R$ l'insieme di livello di $f$ è, se non è vuoto,

$$\mathcal L_\alpha=\{x\in\mathbb R^n:\ f(x)\le\alpha\}$$

Con $\alpha=f(x_0)$ si ha il livello di $x_0$, non vuoto perché contiene $x_0$:

$$\mathcal L_0=\{x\in\mathbb R^n:\ f(x)\le f(x_0)\}$$

La notazione $\mathcal L_0$ indica questo livello, non quello numerico zero.

Proposizione. Se $f$ è continua e per un $x_0$ l'insieme $\mathcal L_0$ è compatto, il problema $\min_{x\in\mathbb R^n}f(x)$ ha un punto di minimo globale.

Dimostrazione. Per Weierstrass su $\mathcal L_0$ esiste $x^*\in\mathcal L_0$ con $f(x^*)\le f(x)$ per ogni $x\in\mathcal L_0$, in particolare $f(x^*)\le f(x_0)$. Se $x\notin\mathcal L_0$, per definizione $f(x)>f(x_0)\ge f(x^*)$. Quindi $f(x^*)\le f(x)$ per ogni $x\in\mathbb R^n$. $\blacksquare$

Coercività

La proposizione chiede di trovare un $x_0$ con $\mathcal L_0$ compatto. Serve invece una proprietà di $f$ che valga per ogni $x_0$. In $\mathbb R$ basta che $f$ tenda a $+\infty$ sia per $x\to-\infty$ sia per $x\to+\infty$. In $\mathbb R^n$ le direzioni sono infinite, quindi si usano le successioni: $f$ è coerciva se per ogni $\{x_k\}$

$$\|x_k\|\to+\infty\quad\Longrightarrow\quad f(x_k)\to+\infty$$

La norma è coerciva. In $\mathbb R$ non lo sono $f(x)=x$, che tende a $-\infty$ per $x\to-\infty$, ed $e^{-x}$, che tende a $0$ per $x\to+\infty$.

Un livello illimitato

$x$

• $f(x)=e^{-x}$
• livello $\alpha$
• ${\mathcal{L}}_{\alpha }$

$\alpha$

1

Proposizione (senza dimostrazione). Se $f$ è continua, tutti gli insiemi di livello di $f$ sono compatti se e solo se $f$ è coerciva.

Corollario. Se $f$ è continua e coerciva, il problema $\min_{x\in\mathbb R^n}f(x)$ ha un punto di minimo globale.

Dimostrazione. Per la proposizione appena enunciata ogni livello non vuoto è compatto, in particolare $\mathcal L_0$ per un $x_0$ qualsiasi. La prima proposizione dà allora il minimo. $\blacksquare$

Per questo nei problemi non vincolati l'esistenza si assicura di solito provando che $f$ è coerciva.

Esempio. Sia $f(x)=g(x)+\tau\|x\|$, con $g:\mathbb R^n\to\mathbb R$ e $\tau>0$. Se $g$ è limitata inferiormente, $g(x)\ge m$, allora $f(x)\ge m+\tau\|x\|\to+\infty$: $f$ è coerciva anche se $g$ non lo è. Il termine $\tau\|x\|$ è di regolarizzazione e si usa nell'addestramento delle reti neurali, dove $\tau$ è un peso che aiuta a evitare l'overfitting.

Funzioni quadratiche

Sia

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

con $Q$ simmetrica, come si può sempre supporre.

Proposizione. $f$ è coerciva se e solo se $Q$ è definita positiva.

Dimostrazione. Se $Q$ è definita positiva, la decomposizione spettrale $Q=\sum_i\lambda_iu_iu_i^\top$, con $u_i$ ortonormali, dà, perché $\sum_i(u_i^\top x)^2=\|x\|^2$,

$$\begin{aligned} x^\top Qx&=\sum_{i=1}^n\lambda_i(u_i^\top x)^2\\ &\ge\lambda_{\min}(Q)\|x\|^2 \end{aligned}$$

Per Cauchy-Schwarz $c^\top x\ge-\|c\|\|x\|$, quindi

$$\begin{aligned} f(x)&\ge\tfrac12\lambda_{\min}(Q)\|x\|^2-\|c\|\|x\|\\ &=\|x\|\Bigl(\tfrac12\lambda_{\min}(Q)\|x\|-\|c\|\Bigr) \end{aligned}$$

Se $\|x_k\|\to+\infty$ il secondo membro tende a $+\infty$, perché $\lambda_{\min}(Q)>0$.

Se $Q$ non è definita positiva esiste $v\ne0$ con $v^\top Qv\le0$. Per $x_k=kv$ si ha $\|x_k\|\to+\infty$ e

$$f(kv)=\frac{k^2}2v^\top Qv+k\,c^\top v$$

Se $v^\top Qv<0$ il termine quadratico domina e $f(kv)\to-\infty$. Se $v^\top Qv=0$ si sceglie fra $v$ e $-v$ il verso con $c^\top v\le0$, e allora $f(kv)\le0$ per ogni $k$. In entrambi i casi $f$ non tende a $+\infty$. $\blacksquare$

Il livello di $\frac{1}{2}(x_1^2+q{x}_2^2)$

$x_1$$x_2$

• ${\mathcal{L}}_1$

$q$

2

Minimi quadrati lineari

Per $A\in\mathbb R^{m\times n}$ qualsiasi e $b\in\mathbb R^m$ il problema è

$$\min_{x\in\mathbb R^n}\tfrac12\|Ax-b\|^2$$

Sviluppando il quadrato:

$$\begin{aligned} \tfrac12\|Ax-b\|^2&=\tfrac12(Ax-b)^\top(Ax-b)\\ &=\tfrac12x^\top A^\top Ax-b^\top Ax+\tfrac12\|b\|^2 \end{aligned}$$

È una quadratica con $Q=A^\top A$ e $c^\top=-b^\top A$. La costante $\tfrac12\|b\|^2$ non cambia i punti di minimo. $Q$ è semidefinita positiva e $x^\top Qx=\|Ax\|^2$ si annulla per un $x\ne0$ se e solo se $Ax=0$. Quindi $Q$ è definita positiva se e solo se $\operatorname{rank}A=n$.

Con $\operatorname{rank}A=n$ la funzione è coerciva e strettamente convessa, quindi il minimo esiste ed è unico. Con $\operatorname{rank}A<n$ non è coerciva, ma una soluzione c'è comunque.

Proposizione. Anche con $\operatorname{rank}A<n$ il problema ai minimi quadrati ammette soluzione.

Dimostrazione. Si riordinano le colonne: $A=(A_1\ \ A_2)$, con $A_1\in\mathbb R^{m\times n_1}$ formata da colonne linearmente indipendenti e $A_2\in\mathbb R^{m\times n_2}$ dalle altre. Le colonne di $A_2$ sono combinazioni di quelle di $A_1$:

$$A_2=A_1B,\qquad B\in\mathbb R^{n_1\times n_2}$$

Poiché $A_1$ ha rango massimo per colonne, il problema $\min_y\tfrac12\|A_1y-b\|^2$ ha un'unica soluzione $y^*$. Si pone $x^*=(y^*,0)$, con $0\in\mathbb R^{n_2}$. Per ogni $x=(x_1,x_2)$

$$Ax=A_1x_1+A_2x_2=A_1(x_1+Bx_2)$$

Se un $\hat x=(\hat x_1,\hat x_2)$ avesse $\|A\hat x-b\|<\|Ax^*-b\|$, il vettore $\hat y=\hat x_1+B\hat x_2$ darebbe $\|A_1\hat y-b\|<\|A_1y^*-b\|$, contro l'ottimalità di $y^*$. Quindi $x^*$ è una soluzione. $\blacksquare$

Minimi quadrati con $A=(1B)$ e $b=1$

$x^{\ast }=(y^{\ast },0)$$x_1$$x_2$

• soluzioni

$B$

1

Dimostrazioni

Dimostrati: esistenza con un livello compatto; esistenza per le funzioni coercive; coercività della quadratica se e solo se $Q$ è definita positiva; esistenza ai minimi quadrati con rango minore di $n$.

Senza dimostrazione: teorema di Weierstrass; livelli tutti compatti se e solo se $f$ è coerciva.