Funzioni convesse di più variabili e minimi globali

La convessità è la proprietà che permette di dire "questo punto critico è il minimo assoluto" senza studiare il comportamento all'infinito. In una variabile è nota (Funzioni convesse, concave e punti di flessof è convessa se ogni corda sta sopra il grafico (concava se sta sotto). Una funzione convessa è continua e ha derivate destra e sinistra in ogni punto interno. Per f derivabile: convessa ⇔ grafico sopra ogni tangente ⇔ f' crescente ⇔ (se esiste) f'' ≥ 0. f'' > 0 ⇒ strettamente convessa, non viceversa (x⁴). Flesso: punto in cui f passa da convessa a concava; lì, se esiste, f''(x0) = 0, ma non basta (x⁴ in 0).Funzioni convesse, concave e punti di flesso →); qui si estende a $\mathbb{R}^n$ e si lega alla matrice hessiana (Derivate seconde, teorema di Schwarz e formula di Taylor del secondo ordineLe derivate seconde f_{x_i x_j} = (f_{x_i}){x_j} formano la matrice hessiana H_f; se f è C² l'hessiana è simmetrica (teorema di Schwarz: le derivate miste, continue, non dipendono dall'ordine). Il differenziale secondo d²f(x0)(h) = h^T H_f(x0) h = Σ f{x_i x_j} h_i h_j è una forma quadratica. Formula di Taylor del secondo ordine con resto di Peano (D): f(x0 + h) = f(x0) + ∇f(x0)·h + ½ h^T H_f(x0) h + o(|h|²) per f ∈ C². Serve per i punti critici e per calcolare limiti.Derivate seconde, teorema di Schwarz e formula di Taylor del secondo ordine →, Forme quadratiche e criteri di definitezzaUna forma quadratica q(h) = h^T M h (M simmetrica) è definita positiva se q>0 per h ≠ 0, semidefinita positiva se q ≥ 0, definita/semidefinita negativa con segni opposti, indefinita se cambia segno. In due variabili, con M = [[a,b],[b,c]]: definita positiva ⇔ det M > 0 e a > 0, definita negativa ⇔ det M > 0 e a < 0, indefinita ⇔ det M < 0 (D, completando il quadrato). In generale: segno degli autovalori di M (D, teorema spettrale): tutti > 0 definita positiva, tutti < 0 definita negativa, di segno diverso indefinita; inoltre q(h) ≥ λ_min |h|². Per n = 3 si usano i minori principali di Sylvester. È lo strumento per classificare i punti critici.Forme quadratiche e criteri di definitezza →). Gli estremi liberi sono in Massimi e minimi liberi e natura dei punti criticiEstremo assoluto = vale in tutto il dominio, relativo = vale in un intorno; "libero" = il dominio è aperto. Fermat (D): in un punto interno di estremo locale dove f è derivabile, ∇f = 0 (punto critico); non basta (x³, −y³, sella x² − y²). Taylor al secondo ordine (D): con f in C² e ∇f(P) = 0, l'Hessiana definita positiva dà minimo locale stretto, definita negativa massimo locale stretto, indefinita sella; per n = 2: det H > 0 e f_xx > 0 minimo, det H > 0 e f_xx < 0 massimo, det H < 0 sella, det H = 0 non decide (x⁴ + y⁴, −x⁴ − y⁴, x⁴ − y⁴). Estremi globali: Weierstrass in un chiuso illimitato se f → +∞ (o −∞) all'infinito (D), da verificare in coordinate polari con una stima che non dipende dall'angolo.Massimi e minimi liberi e natura dei punti critici →.

1. Insiemi convessi

Dati $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$, il segmento di estremi $\mathbf{x}$ e $\mathbf{y}$ è $$[\mathbf{x}, \mathbf{y}] = \{(1-t)\mathbf{x} + t\mathbf{y} : t \in [0,1]\}.$$ I punti $(1-t)\mathbf{x} + t\mathbf{y}$ sono le combinazioni convesse di $\mathbf{x}$ e $\mathbf{y}$: due pesi $1 - t$ e $t$ non negativi con somma $1$. Per $t = 0$ si ottiene $\mathbf{x}$, per $t = 1$ si ottiene $\mathbf{y}$, per $t = \frac12$ il punto medio.

Definizione (insieme convesso). $A \subseteq \mathbb{R}^n$ è convesso se per ogni $\mathbf{x}, \mathbf{y} \in A$ il segmento $[\mathbf{x}, \mathbf{y}]$ è contenuto in $A$. È strettamente convesso se, per $\mathbf{x} \ne \mathbf{y}$ in $A$, il segmento aperto (senza estremi) sta nella parte interna di $A$.

Esempio. Il disco $x^2 + y^2 \le 1$ è convesso; il semidisco $\{x^2 + y^2 \le 1,\ y \ge 0\}$ è convesso ma non strettamente: due punti sul diametro sono uniti da un segmento che sta sul bordo.

Esempi e controesempi.

• In $\mathbb{R}$: convesso $\iff$ intervallo.
• La palla aperta $B_r(\mathbf{x}_0)$ è strettamente convessa. Dimostrazione. Se $\|\mathbf{x} - \mathbf{x}_0\| < r$, $\|\mathbf{y} - \mathbf{x}_0\| < r$ e $t \in (0,1)$, allora $(1-t)\mathbf{x} + t\mathbf{y} - \mathbf{x}_0 = (1-t)(\mathbf{x} - \mathbf{x}_0) + t(\mathbf{y} - \mathbf{x}_0)$ e per la disuguaglianza triangolare la sua norma è $< (1-t)r + tr = r$.
• I semipiani e i quadranti chiusi sono convessi (non strettamente: contengono segmenti sul bordo).
• Il piano privato del terzo quadrante aperto, $\mathbb{R}^2 \setminus \{x < 0,\ y < 0\}$, non è convesso: i punti $(-3, 1)$ e $(1, -3)$ appartengono all'insieme, ma il loro punto medio $(-1,-1)$ ha $x < 0$ e $y < 0$ ed è stato tolto.
• Convesso $\Rightarrow$ connesso (per archi: il segmento è il cammino). Il viceversa è falso per $n > 1$: l'insieme appena descritto è connesso ma non convesso.
• L'intersezione di insiemi convessi è convessa (un insieme definito da più disequazioni "lineari" o "convesse" si controlla una per una).

2. Funzioni convesse

Definizione (funzione convessa). Sia $A \subseteq \mathbb{R}^n$ convesso e $f : A \to \mathbb{R}$. $f$ è convessa se per ogni $\mathbf{x}, \mathbf{y} \in A$ e ogni $t \in [0,1]$ $$f\big((1-t)\mathbf{x} + t\mathbf{y}\big) \le (1-t)\,f(\mathbf{x}) + t\,f(\mathbf{y}).$$ È strettamente convessa se per $\mathbf{x} \ne \mathbf{y}$ e $t \in (0,1)$ vale la disuguaglianza stretta. $f$ è concava se $-f$ è convessa (disuguaglianza rovesciata).

Significato. A sinistra c'è il valore di $f$ nel punto $(1-t)\mathbf{x} + t\mathbf{y}$ del segmento; a destra l'altezza della corda che unisce i punti $(\mathbf{x}, f(\mathbf{x}))$ e $(\mathbf{y}, f(\mathbf{y}))$ del grafico. Convessa = il grafico sta sotto o sulla corda; per $n = 2$ la superficie è una "ciotola" rivolta verso l'alto. Equivalentemente: $f$ è convessa se e solo se il suo epigrafo $\{(\mathbf{x}, z) : \mathbf{x} \in A,\ z \ge f(\mathbf{x})\}\subseteq \mathbb{R}^{n+1}$ è un insieme convesso.

Esempio. $f(x) = x^2$ è strettamente convessa: per $x = 0$, $y = 2$, $t = \frac12$ si ha $f(1) = 1 < \frac12 f(0) + \frac12 f(2) = 2$.

Esempi notevoli.

1. Funzioni affini $f(\mathbf{x}) = \mathbf{m}\cdot\mathbf{x} + b$. Per linearità del prodotto scalare e $(1-t) + t = 1$, $$f((1-t)\mathbf{x} + t\mathbf{y}) = (1-t)(\mathbf{m}\cdot\mathbf{x} + b) + t(\mathbf{m}\cdot\mathbf{y} + b) = (1-t)f(\mathbf{x}) + tf(\mathbf{y}),$$ con uguaglianza: sono sia convesse sia concave, ma mai strettamente.
2. La norma $f(\mathbf{x}) = \|\mathbf{x}\|$ è convessa: per la disuguaglianza triangolare e l'omogeneità, $\|(1-t)\mathbf{x} + t\mathbf{y}\| \le (1-t)\|\mathbf{x}\| + t\|\mathbf{y}\|$. Non è strettamente convessa: se $\mathbf{y} = 2\mathbf{x}$ con $\mathbf{x} \ne \mathbf{0}$ si ha uguaglianza (il grafico è un cono, che contiene segmenti: le generatrici).
3. $f(x,y) = x^4 + y^4 - 4xy$ non è convessa: nei due minimi $(1,1)$ e $(-1,-1)$ vale $-2$, nel punto medio $(0,0)$ vale $0 > -2$, cioè sta sopra la corda.

Regole utili: la somma di funzioni convesse è convessa; un multiplo positivo di una convessa è convessa; la composizione di una convessa con una funzione affine è convessa; il massimo di due convesse è convessa.

3. Caratterizzazione con il piano tangente

Teorema (primo ordine). Sia $A$ aperto e convesso e $f : A \to \mathbb{R}$ differenziabile. Allora $f$ è convessa se e solo se per ogni $\mathbf{x}, \mathbf{x}_0 \in A$ $$f(\mathbf{x}) \ge f(\mathbf{x}_0) + \nabla f(\mathbf{x}_0)\cdot(\mathbf{x} - \mathbf{x}_0).$$ Inoltre $f$ è strettamente convessa se e solo se la disuguaglianza è stretta per $\mathbf{x} \ne \mathbf{x}_0$.

Il membro destro è l'equazione del piano (iperpiano) tangente nel punto $\mathbf{x}_0$: il teorema dice che il grafico di una funzione convessa sta sopra tutti i suoi piani tangenti (in una variabile: sopra tutte le sue rette tangenti).

Esempio. $f(x,y) = x^2 + y^2$ in $\mathbf{x}_0 = (1,0)$: il piano tangente è $z = 1 + 2(x - 1) = 2x - 1$, e $x^2 + y^2 - (2x - 1) = (x-1)^2 + y^2 \ge 0$: il grafico sta sopra.

Dimostrazione della condizione necessaria (D). Sia $f$ convessa. Fissiamo $\mathbf{x}, \mathbf{y} \in A$ e $t \in (0,1)$. Per convessità $$f(\mathbf{x} + t(\mathbf{y} - \mathbf{x})) = f((1-t)\mathbf{x} + t\mathbf{y}) \le (1-t)f(\mathbf{x}) + tf(\mathbf{y}).$$ Sottraendo $f(\mathbf{x})$ da entrambi i membri, il membro destro diventa $t\big(f(\mathbf{y}) - f(\mathbf{x})\big)$, e dividendo per $t > 0$: $$\frac{f(\mathbf{x} + t(\mathbf{y} - \mathbf{x})) - f(\mathbf{x})}{t} \le f(\mathbf{y}) - f(\mathbf{x}).$$ Facciamo tendere $t \to 0^+$. Poiché $f$ è differenziabile in $\mathbf{x}$, il limite a sinistra è la derivata direzionale lungo $\mathbf{y} - \mathbf{x}$, che per la formula del gradiente (Derivate direzionali, formula del gradiente e curve di livelloLa derivata direzionale D_v f(x0) = lim [f(x0 + t v) − f(x0)]/t (v versore) è la pendenza di f lungo la retta per x0 con direzione v. Se f è differenziabile in x0 vale la formula del gradiente D_v f = ∇f(x0)·v (D); l'esistenza di tutte le D_v non basta (anche a f discontinua). Quindi la massima crescita è nella direzione di ∇f, con pendenza |∇f| (D), la minima in −∇f, e D_v f = 0 per v ⊥ ∇f. Il gradiente è ortogonale alle curve di livello (D): la tangente alla curva di livello in (x0,y0) è f_x(x−x0) + f_y(y−y0) = 0, a patto che ∇f ≠ 0.Derivate direzionali, formula del gradiente e curve di livello →) vale $\nabla f(\mathbf{x})\cdot(\mathbf{y} - \mathbf{x})$. Quindi $$\nabla f(\mathbf{x})\cdot(\mathbf{y} - \mathbf{x}) \le f(\mathbf{y}) - f(\mathbf{x}),$$ cioè la tesi con $\mathbf{x} = \mathbf{x}_0$ e $\mathbf{y} = \mathbf{x}$. $\blacksquare$

Il viceversa (non richiesto con dimostrazione, ma breve): se vale la disuguaglianza del piano tangente, sia $\mathbf{z} = (1-t)\mathbf{x} + t\mathbf{y}$. Applicandola con punto base $\mathbf{z}$ a $\mathbf{x}$ e a $\mathbf{y}$: $$f(\mathbf{x}) \ge f(\mathbf{z}) + \nabla f(\mathbf{z})\cdot(\mathbf{x} - \mathbf{z}), \qquad f(\mathbf{y}) \ge f(\mathbf{z}) + \nabla f(\mathbf{z})\cdot(\mathbf{y} - \mathbf{z}).$$ Si moltiplica la prima per $1 - t$, la seconda per $t$ e si somma: i termini col gradiente danno $\nabla f(\mathbf{z})\cdot[(1-t)(\mathbf{x} - \mathbf{z}) + t(\mathbf{y} - \mathbf{z})] = \nabla f(\mathbf{z})\cdot[(1-t)\mathbf{x} + t\mathbf{y} - \mathbf{z}] = 0$, quindi $(1-t)f(\mathbf{x}) + tf(\mathbf{y}) \ge f(\mathbf{z})$.

4. Convessità e matrice hessiana

È il criterio che si usa quasi sempre.

Teorema (secondo ordine). Sia $A$ aperto e convesso e $f \in C^2(A)$.

1. $f$ è convessa in $A$ $\iff$ $H_f(\mathbf{x})$ è semidefinita positiva per ogni $\mathbf{x} \in A$.
2. Se $H_f(\mathbf{x})$ è definita positiva per ogni $\mathbf{x} \in A$, allora $f$ è strettamente convessa. Il viceversa è falso.

In una variabile è "$f'' \ge 0$ implica convessa" e "$f'' > 0$ implica strettamente convessa" (Funzioni convesse, concave e punti di flessof è convessa se ogni corda sta sopra il grafico (concava se sta sotto). Una funzione convessa è continua e ha derivate destra e sinistra in ogni punto interno. Per f derivabile: convessa ⇔ grafico sopra ogni tangente ⇔ f' crescente ⇔ (se esiste) f'' ≥ 0. f'' > 0 ⇒ strettamente convessa, non viceversa (x⁴). Flesso: punto in cui f passa da convessa a concava; lì, se esiste, f''(x0) = 0, ma non basta (x⁴ in 0).Funzioni convesse, concave e punti di flesso →); $f(x) = x^4$ è strettamente convessa ma $f''(0) = 0$. In due variabili lo stesso fa $x^4 + y^4$, con $H = \operatorname{diag}(12x^2, 12y^2)$ solo semidefinita nell'origine.

Perché la hessiana (idea della dimostrazione di "$\Leftarrow$"). Siano $\mathbf{x}_0, \mathbf{x} \in A$ e $\mathbf{h} = \mathbf{x} - \mathbf{x}_0$. La funzione di una variabile $g(s) = f(\mathbf{x}_0 + s\mathbf{h})$, $s \in [0,1]$, ha $g'(0) = \nabla f(\mathbf{x}_0)\cdot\mathbf{h}$ e $g''(s) = \mathbf{h}^T H_f(\mathbf{x}_0 + s\mathbf{h})\,\mathbf{h}$. Dal teorema di Taylor con resto di Lagrange in una variabile (Formula di Taylor con resto di LagrangeSe f ha n+1 derivate continue su [a,b], l'errore tra f e il suo polinomio di Taylor si scrive esattamente come f^(n+1)(c)(x-x0)^(n+1)/(n+1)! per un c opportuno: serve a stimare l'errore su tutto un intervallo e a scegliere il grado del polinomio.Formula di Taylor con resto di Lagrange →) esiste $\tau \in (0,1)$ con $$f(\mathbf{x}) = g(1) = g(0) + g'(0) + \tfrac12 g''(\tau) = f(\mathbf{x}_0) + \nabla f(\mathbf{x}_0)\cdot\mathbf{h} + \tfrac12\mathbf{h}^T H_f(\mathbf{x}_0 + \tau\mathbf{h})\mathbf{h}.$$ Se $H_f$ è semidefinita positiva l'ultimo termine è $\ge 0$ e si ottiene la disuguaglianza del piano tangente, cioè la convessità; se è definita positiva è $> 0$ per $\mathbf{h} \ne \mathbf{0}$ e la convessità è stretta.

Come si applica ($n = 2$). Con $H = \begin{pmatrix} f_{xx} & f_{xy} \\ f_{xy} & f_{yy}\end{pmatrix}$:

• Definita positiva in ogni punto (strettamente convessa): $f_{xx} > 0$ e $\det H > 0$ (di conseguenza anche $f_{yy} > 0$).
• Semidefinita positiva in ogni punto (convessa): $f_{xx} \ge 0$, $f_{yy} \ge 0$ e $\det H \ge 0$. Attenzione: $\det H \ge 0$ da solo non basta (la matrice $-I$ ha $\det = 1$ ma è definita negativa), e $f_{xx} \ge 0$ con $\det H \ge 0$ non basta se $f_{xx} = 0$.
• Concava: la stessa cosa per $-f$.
• Se in qualche punto $\det H < 0$, la hessiana è indefinita lì e $f$ non è né convessa né concava.

Il criterio vale su un aperto convesso: va quindi controllato prima che il dominio lo sia, e la condizione deve valere in tutti i punti.

Esempi.

• $f(\mathbf{x}) = \|\mathbf{x}\|^2$ ha $H = 2I_n$ (autovalori tutti uguali a $2 > 0$): strettamente convessa in $\mathbb{R}^n$.
• $f(x,y) = x^2 - y$ ha $\nabla f = (2x, -1)$ e $H = \begin{pmatrix} 2 & 0 \\ 0 & 0\end{pmatrix}$, semidefinita positiva: convessa. Non è strettamente convessa: sulle rette $x = \text{cost}$ è lineare in $y$ (il grafico è un cilindro parabolico, formato da rette parallele all'asse $y$).
• $f(x,y) = x^3 + y^3 - 3xy$: $H = \begin{pmatrix} 6x & -3 \\ -3 & 6y\end{pmatrix}$ ha $\det H = 36xy - 9 < 0$ nell'origine: non è convessa su $\mathbb{R}^2$.

5. Estremi di funzioni convesse

Teorema (minimi globali). Sia $A$ aperto e convesso, $f : A \to \mathbb{R}$ convessa e differenziabile, e $\mathbf{x}_0 \in A$ con $\nabla f(\mathbf{x}_0) = \mathbf{0}$. Allora $\mathbf{x}_0$ è un punto di minimo globale. Se $f$ è strettamente convessa, $\mathbf{x}_0$ è l'unico punto di minimo globale (e un punto critico, se esiste, è unico). Per $f$ concava: massimo globale.

Dimostrazione (D). Per il teorema del piano tangente, per ogni $\mathbf{x} \in A$: $$f(\mathbf{x}) \ge f(\mathbf{x}_0) + \nabla f(\mathbf{x}_0)\cdot(\mathbf{x} - \mathbf{x}_0) = f(\mathbf{x}_0) + 0 = f(\mathbf{x}_0),$$ quindi $\mathbf{x}_0$ è un minimo globale. Se $f$ è strettamente convessa la disuguaglianza è stretta per $\mathbf{x} \ne \mathbf{x}_0$: $f(\mathbf{x}) > f(\mathbf{x}_0)$, perciò nessun altro punto può essere di minimo. $\blacksquare$

Così, se $H_f$ è definita positiva su tutto il dominio (aperto e convesso), basta trovare il punto critico: è il minimo assoluto, senza nessuno studio all'infinito.

Esempio. $f(x,y,z) = x^2 + y^2 + z^2 - 2x - 2z - 5$. Il gradiente $(2x - 2,\ 2y,\ 2z - 2)$ si annulla in $(1,0,1)$; $H = 2I_3$ è definita positiva ovunque. Quindi $(1,0,1)$ è l'unico minimo globale e $\min f = 1 + 0 + 1 - 2 - 2 - 5 = -7$. Non c'è massimo, perché $f \to +\infty$ lungo ogni retta.

Un'applicazione: il punto che minimizza le distanze. Dati $N$ punti $P_i = (x_i, y_i)$ del piano, si cerca il punto $(x,y)$ che rende minima la somma dei quadrati delle distanze $$f(x,y) = \sum_{i=1}^N \big[(x - x_i)^2 + (y - y_i)^2\big].$$ Le derivate sono $f_x = 2Nx - 2\sum x_i$ e $f_y = 2Ny - 2\sum y_i$: l'unico punto critico è il baricentro $\left(\frac1N\sum x_i,\ \frac1N\sum y_i\right)$. La hessiana è $2N\cdot I_2$, definita positiva ovunque: $f$ è strettamente convessa e il baricentro è l'unico minimo globale.

6. Procedura

1. Il dominio è aperto e convesso? (Si disegna e si controlla; per un semipiano definito da $ax + by < c$ è immediato: la combinazione convessa di due soluzioni è soluzione.)
2. Calcolare $H_f$ e studiarne il segno in tutti i punti del dominio.
3. Se $H_f > 0$ ovunque: strettamente convessa, il punto critico (se esiste) è il minimo globale unico. Se esiste un punto con $\det H_f < 0$: non è convessa e si ricade nello studio dei punti critici e dell'infinito (Massimi e minimi liberi e natura dei punti criticiEstremo assoluto = vale in tutto il dominio, relativo = vale in un intorno; "libero" = il dominio è aperto. Fermat (D): in un punto interno di estremo locale dove f è derivabile, ∇f = 0 (punto critico); non basta (x³, −y³, sella x² − y²). Taylor al secondo ordine (D): con f in C² e ∇f(P) = 0, l'Hessiana definita positiva dà minimo locale stretto, definita negativa massimo locale stretto, indefinita sella; per n = 2: det H > 0 e f_xx > 0 minimo, det H > 0 e f_xx < 0 massimo, det H < 0 sella, det H = 0 non decide (x⁴ + y⁴, −x⁴ − y⁴, x⁴ − y⁴). Estremi globali: Weierstrass in un chiuso illimitato se f → +∞ (o −∞) all'infinito (D), da verificare in coordinate polari con una stima che non dipende dall'angolo.Massimi e minimi liberi e natura dei punti critici →).

7. Errori da evitare

• Pensare che $\det H > 0$ in un punto basti: serve il segno della hessiana in tutti i punti dell'insieme convesso.
• Dedurre "non strettamente convessa" da $H$ solo semidefinita: $x^4$ è strettamente convessa. Per escluderla serve un segmento su cui è affine (come l'asse $y$ per $x^2 - y$).
• Scambiare convessità e connessione di un insieme.
• Applicare il teorema del minimo globale su un dominio non aperto: sul bordo il gradiente non deve annullarsi.

Esercizi: Esercizio - Dominio convesso e minimo globale di un logaritmo (foglio 4), Esercizio - Convessità di una cubica su R2 e sul primo quadrante (foglio 4).

Domande d'esame

1. Definire funzione convessa su $\mathbb{R}^n$. Enunciare il legame con la matrice hessiana. Dimostrare che per una funzione convessa e differenziabile un punto critico è di minimo globale. Traccia. Definizione con le corde; hessiana semidefinita positiva ovunque $\iff$ convessa (definita positiva $\Rightarrow$ strettamente convessa, non viceversa: $x^4$). Dimostrazione: dal piano tangente $f(\mathbf{x}) \ge f(\mathbf{x}_0) + \nabla f(\mathbf{x}_0)\cdot(\mathbf{x} - \mathbf{x}_0)$ con $\nabla f(\mathbf{x}_0) = \mathbf{0}$ si ha $f(\mathbf{x}) \ge f(\mathbf{x}_0)$.
2. Enunciare e dimostrare la condizione necessaria di convessità con il piano tangente. Traccia. Rapporto incrementale su $\mathbf{x} + t(\mathbf{y} - \mathbf{x})$ con la disuguaglianza di convessità, poi $t \to 0^+$ e formula del gradiente.
3. Dare un esempio di funzione convessa ma non strettamente convessa, e uno di funzione strettamente convessa con hessiana non definita positiva. Traccia. $\|\mathbf{x}\|$ oppure $x^2 - y$; $x^4$ (o $x^4 + y^4$).