Minimi globali, insiemi di livello e convessità

Il teorema di Weierstrass

Dati $S\subseteq\mathbb R^n$ e $f:\mathbb R^n\to\mathbb R$, come si può essere sicuri che $\min\{f(x):x\in S\}$ abbia senso, cioè che esista un minimo globale? Con $S\ne\mathbb R^n$ il problema è vincolato, con $S=\mathbb R^n$ è non vincolato.

Teorema (Weierstrass). Se $S\subseteq\mathbb R^n$ è non vuoto e compatto e $f$ è continua su $S$, allora $f$ ammette su $S$ minimo e massimo globale.

Dimostrazione. Basta il minimo, perché il massimo di $f$ è il minimo di $-f$. Sia $f^*=\inf_Sf$ e sia $\eta_k>f^*$ con $\eta_k\to f^*$ (per esempio $\eta_k=-k$ se $f^*=-\infty$). Per ogni $k$ esiste $x_k\in S$ con $f^*\le f(x_k)<\eta_k$, quindi $f(x_k)\to f^*$. Poiché $S$ è compatto, una sottosuccessione $x_{k_j}$ converge a un punto $x^*$, che sta in $S$ perché $S$ è chiuso. Per continuità $f(x_{k_j})\to f(x^*)$, e anche $f(x_{k_j})\to f^*$. Quindi $f(x^*)=f^*$: l'estremo inferiore è finito e raggiunto. $\blacksquare$

Se $S=\mathbb R^n$ il teorema non si applica, perché $\mathbb R^n$ non è limitato.

Insiemi di livello

Dato $\alpha\in\mathbb R$ si pone

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

Se $L_\alpha$ non è vuoto, è un insieme di livello di $f$.

Teorema. Sia $f$ continua su $\mathbb R^n$. Se esiste un insieme di livello compatto, $f$ ammette minimo globale su $\mathbb R^n$.

Dimostrazione. Sia $L_\alpha$ non vuoto e compatto. Per Weierstrass esiste $x^*\in L_\alpha$ con $f(x^*)\le f(x)$ per ogni $x\in L_\alpha$, e $f(x^*)\le\alpha$. Se $y\notin L_\alpha$, allora $f(y)>\alpha\ge f(x^*)$. Quindi $x^*$ è un minimo globale su $\mathbb R^n$. $\blacksquare$

Esempio. Per $f(x,y)=x^2+y^2$ è $L_{-1}=\emptyset$, mentre $L_1=\{x^2+y^2\le1\}$ è il disco unitario, compatto. Il minimo globale esiste, ed è l'origine, perché $f\ge0$ e $f(0,0)=0$.

Funzioni convesse

Un insieme $S$ è convesso se contiene il segmento fra due suoi punti qualsiasi. Per una funzione si confronta il grafico con le corde.

Definizione. Una funzione $f$ definita su un insieme convesso $S$ è convessa se per ogni $x,y\in S$

$$f((1-\lambda)x+\lambda y)\le(1-\lambda)f(x)+\lambda f(y),\qquad\forall\lambda\in[0,1]$$

I punti $P=(x,f(x))$ e $Q=(y,f(y))$ del grafico sono uniti da un segmento di punti $(1-\lambda)P+\lambda Q$, con ascissa $(1-\lambda)x+\lambda y$ e ordinata $(1-\lambda)f(x)+\lambda f(y)$. La definizione dice che il grafico sta sotto la corda. È strettamente convessa se la disuguaglianza è stretta per $x\ne y$ e $\lambda\in(0,1)$. È concava, o strettamente concava, se vale la disuguaglianza opposta. Per esempio $x^2$ è strettamente convessa e $-x^2$ strettamente concava.

La corda sopra e sotto il grafico

$f(x)=x^2$

$P$$Q$$x$$f(x)$

• $f$
• corda $PQ$

$g(x)=x^4-2x^2$

$P$$Q$$x$$g(x)$

• $g$
• corda $PQ$

ascissa di $P$

−1

ascissa di $Q$

1

Verificare la definizione richiede di considerare ogni coppia di punti. Con la regolarità di $f$ si hanno criteri più comodi.

Teorema (senza dimostrazione). Sia $S$ aperto e convesso e sia $f\in C^1(S)$. Allora $f$ è convessa su $S$ se e solo se per ogni $x,y\in S$

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

cioè se il grafico sta sopra ogni iperpiano tangente. Con $>$ per $y\ne x$ si ha la convessità stretta.

Teorema (senza dimostrazione). Sia $S$ aperto e convesso e sia $f\in C^2(S)$. Allora $f$ è convessa su $S$ se e solo se $\nabla^2f(x)$ è semidefinita positiva per ogni $x\in S$. Se $\nabla^2f(x)$ è definita positiva per ogni $x\in S$, $f$ è strettamente convessa. Il viceversa non vale.

Esempio. Per $f(x,y)=x^4+y^4$ si ha $\nabla f=(4x^3,4y^3)$ e

$$\nabla^2f=\begin{pmatrix}12x^2&0\\0&12y^2\end{pmatrix}$$

Gli autovalori $12x^2$ e $12y^2$ non sono negativi, quindi $f$ è convessa su $\mathbb R^2$. È anche strettamente convessa, ma nell'origine l'hessiana è nulla, non definita positiva: il criterio sufficiente non lo mostra.

Funzioni quadratiche

Sia $f(x)=\frac12x^\top Qx+c^\top x+d$, con $Q$ simmetrica, come si può sempre supporre.

Proposizione (senza dimostrazione). $f$ è convessa se e solo se $Q$ è semidefinita positiva, ed è strettamente convessa se e solo se $Q$ è definita positiva.

Per $n=2$ si pone

$$Q=\begin{pmatrix}a&b\\b&\bar a\end{pmatrix}$$

I suoi autovalori $\lambda_1,\lambda_2$ sono reali, con $\lambda_1+\lambda_2=a+\bar a$ e $\lambda_1\lambda_2=\det Q$.

Proposizione.

• se $\det Q<0$, $Q$ è indefinita;
• se $\det Q=0$, $Q$ è semidefinita positiva per $a+\bar a\ge0$ e semidefinita negativa per $a+\bar a\le0$;
• se $\det Q>0$, $Q$ è definita positiva per $a+\bar a>0$ e definita negativa per $a+\bar a<0$.

Dimostrazione. Con $\det Q<0$ i due autovalori hanno segno opposto. Con $\det Q=0$ almeno uno è nullo e l'altro vale $a+\bar a$; se sono entrambi nulli la matrice è sia semidefinita positiva sia semidefinita negativa. Con $\det Q>0$ nessuno è nullo e hanno lo stesso segno, che è quello della somma $a+\bar a$. $\blacksquare$

Il segno di $x^{\top }Qx$ con $\Vert x\Vert =1$

$\theta$

• $x^{\top }Qx$ con $\Vert x\Vert =1$
• zero

$a$

2

$b$

0,5

$\bar{a}$

1

Convessità e minimi

Un minimo locale di $f$ su $S$ è un punto $\bar x\in S$ per cui esiste $\varepsilon>0$ con $f(\bar x)\le f(x)$ per ogni $x\in S\cap B(\bar x,\varepsilon)$. È globale se $f(\bar x)\le f(x)$ per ogni $x\in S$.

Teorema. Se $f$ è convessa su un insieme convesso $S$, ogni minimo locale di $f$ su $S$ è globale.

Dimostrazione. Sia $\bar x$ un minimo locale e sia $x\in S$. Se $x\in B(\bar x,\varepsilon)$ si ha $f(\bar x)\le f(x)$ per definizione. Se $x$ è fuori dall'intorno, il segmento fra $\bar x$ e $x$ sta in $S$, perché $S$ è convesso, e per qualche $\lambda\in(0,1)$ il punto $z=(1-\lambda)\bar x+\lambda x$ è nell'intorno. Per il minimo locale e per la convessità

$$f(\bar x)\le f(z)\le(1-\lambda)f(\bar x)+\lambda f(x)$$

Si porta $(1-\lambda)f(\bar x)$ a sinistra e si divide per $\lambda>0$: $f(\bar x)\le f(x)$. Quindi $\bar x$ è globale. $\blacksquare$

Una funzione convessa non ha dunque minimi locali che non siano globali. Ma questo non garantisce che il minimo esista.

Convesse, con e senza minimo

$f_1(x)=x^2$

$x^{\ast }=0$$x$$f(x)$

• $f_1$

$f_2(x)=e^x$

$x$$f(x)$

• $f_2$
• estremo inferiore $0$

Un modello: le unità di raffreddamento

Un data center sceglie quante unità di raffreddamento usare, di tre tipi, con capacità in kW e costo per unità:

• tipo A: $5$ kW, costo $100$;
• tipo B: $7$ kW, costo $150$;
• tipo C: $10$ kW, costo $200$.

Servono almeno $500$ kW, le unità A non sono più del $25\%$ del totale e le unità C almeno il $15\%$. Le incognite $x_A$, $x_B$ e $x_C$ sono i numeri di unità dei tre tipi, quindi interi non negativi. Con capacità proporzionali al numero di unità il problema è

$$\begin{aligned} \min\ &100x_A+150x_B+200x_C\\ &5x_A+7x_B+10x_C\ge500\\ &x_A\le0{,}25\,(x_A+x_B+x_C)\\ &x_C\ge0{,}15\,(x_A+x_B+x_C)\\ &x_A,x_B,x_C\ge0\ \text{interi} \end{aligned}$$

Dimostrazioni

Dimostrati: teorema di Weierstrass; esistenza con un insieme di livello compatto; segno di una matrice $2\times2$ da determinante e traccia; ogni minimo locale di una funzione convessa è globale.

Senza dimostrazione: convessità del primo ordine, anche stretta; convessità del secondo ordine e stretta convessità con hessiana definita positiva; convessità delle funzioni quadratiche.