Lezione 16 · Canale 1 · giovedì 22 ottobre 2026

Convessità di funzioni e insiemi

Programmazione Matematica

Come riconoscere una funzione convessa

Verificare la definizione di convessità richiede di controllare ogni coppia di punti, ed è scomodo con molte variabili. Servono criteri che si applicano alla funzione data. Servono anche per decidere se un insieme definito da vincoli è convesso.

Sia $S$ un insieme convesso. Una funzione $f$ è convessa su $S$ se per ogni $x,y\in S$ e $\lambda\in[0,1]$

\begin{aligned} &f\bigl((1-\lambda)x+\lambda y\bigr)\\ &\le(1-\lambda)f(x)+\lambda f(y) \end{aligned}

È strettamente convessa se la disuguaglianza è stretta per $x\neq y$ e $\lambda\in(0,1)$ . La definizione non usa derivate, quindi vale anche per funzioni non differenziabili.

Criterio del primo ordine

Se $f$ è di classe $C^1$ su un aperto che contiene $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)

Il grafico sta sopra il piano tangente in ogni punto. La stretta convessità equivale alla disuguaglianza stretta per $x\neq y$ .

Il criterio è un risultato teorico. Con cento variabili, seni e coseni, controllarlo per ogni coppia di punti non è praticabile. Servirà più avanti.

Criterio della matrice Hessiana

Se $S$ è aperto e convesso e $f$ è di classe $C^2$ su $S$ , esiste la matrice Hessiana $\nabla^2f(x)$ e vale un criterio algebrico, qui senza dimostrazione: $f$ è convessa su $S$ se e solo se $\nabla^2f(x)$ è semidefinita positiva in ogni $x\in S$ .

L'Hessiana è simmetrica, quindi ha autovalori reali. Essere semidefinita positiva equivale ad avere tutti gli autovalori maggiori o uguali a zero, quindi basta studiare il segno degli autovalori. Per la concavità i segni si invertono: l'Hessiana deve essere semidefinita negativa.

Funzioni lineari e quadratiche

Per $f(x)=c^\top x$ il gradiente è costante e l'Hessiana è nulla:

\begin{gathered} \nabla f(x)=c\\ \nabla^2f(x)=0_{n\times n} \end{gathered}

La matrice nulla è semidefinita sia positiva sia negativa, quindi una funzione lineare è convessa e concava. Lo stesso segue dalla definizione, dove vale l'uguaglianza.

Per una funzione quadratica, con $Q$ simmetrica, $c\in\mathbb R^n$ e $b\in\mathbb R$ ,

\begin{aligned} f(x)&=\frac12x^\top Qx+c^\top x+b\\ \nabla f(x)&=Qx+c\\ \nabla^2f(x)&=Q \end{aligned}

L'Hessiana è $Q$ in ogni punto. Quindi $f$ è convessa se e solo se $Q$ è semidefinita positiva, ed è concava se e solo se $Q$ è semidefinita negativa.

Né convessa né concava, dieci variabili. Serve una $Q$ indefinita, con autovalori positivi e negativi. Gli autovalori si leggono subito solo su una matrice diagonale, quindi si prende

Q=\operatorname{diag}(1,-1,0,\dots,0)

di dimensione $10\times10$ , con $c$ e $b$ qualsiasi. Gli autovalori sono $1$ , $-1$ e otto volte $0$ .

Minimi quadrati

Sia $A\in\mathbb R^{m\times n}$ qualsiasi e $b\in\mathbb R^m$ . La funzione ha Hessiana $A^\top A$ :

\begin{gathered} f(x)=\frac12\lVert Ax-b\rVert_2^2\\ \nabla^2f(x)=A^\top A \end{gathered}

Per ogni $v\in\mathbb R^n$ vale $v^\top A^\top Av=\lVert Av\rVert_2^2\ge0$ , quindi $A^\top A$ è semidefinita positiva. La funzione è convessa per ogni scelta di $A$ e $b$ .

Condizione sufficiente di stretta convessità

Con $f$ di classe $C^2$ su un aperto che contiene $S$ convesso, se $\nabla^2f(x)$ è definita positiva per ogni $x\in S$ , allora $f$ è strettamente convessa su $S$ . Per la convessità semplice il criterio è un se e solo se; per la stretta convessità vale solo questa implicazione.

Dimostrazione. Siano $x\neq y$ in $S$ . Per il teorema di Taylor esiste $z=x+\theta(y-x)$ , con $\theta\in(0,1)$ , tale che

\begin{aligned} f(y)&=f(x)+\nabla f(x)^\top(y-x)\\ &\quad+\frac12(y-x)^\top\nabla^2f(z)(y-x) \end{aligned}

Poiché $S$ è convesso, $z\in S$ , e quindi $\nabla^2f(z)$ è definita positiva. Il vettore $y-x$ non è nullo, perciò il termine quadratico è positivo. Per ogni $x\neq y$ in $S$ segue

f(y)>f(x)+\nabla f(x)^\top(y-x)

Questa è la forma stretta del criterio del primo ordine, quindi $f$ è strettamente convessa. $\blacksquare$

La condizione non è necessaria. Si prende $f(x)=x^4$ , di una variabile, dove l'Hessiana è la derivata seconda:

f'(x)=4x^3,\qquad f''(x)=12x^2

Vale $f''(x)\ge0$ ovunque e $f''(0)=0$ : l'Hessiana è semidefinita positiva ma non definita positiva. Eppure $f$ è strettamente convessa, perché per $x\neq y$

\begin{aligned} &y^4-x^4-4x^3(y-x)\\ &=(y-x)^2\bigl((x+y)^2+2x^2\bigr)>0 \end{aligned}

Il primo fattore è positivo perché $x\neq y$ . Il secondo si annulla solo per $x=y=0$ , caso escluso. Quindi vale la forma stretta del criterio del primo ordine.

Curvatura nulla, ma strettamente convessa

$f (x) = x^{4}$ e la tangente

tangenza

x

$f (x)$
tangente in $a$

La derivata seconda

f^{''} (a)

x

$f^{''} (x)$

punto di tangenza

a

−1

La tangente sta sotto il grafico e lo tocca solo nel punto di tangenza, anche in

a = 0

, dove la derivata seconda si annulla.

Per le funzioni quadratiche, invece, la condizione è anche necessaria: $f$ è strettamente convessa se e solo se $Q$ è definita positiva.

Convessa ma non strettamente, cinque variabili. Una funzione quadratica non lineare con $Q$ semidefinita positiva e non definita positiva:

f(x)=\frac12x^\top Qx+c^\top x,\qquad Q=\operatorname{diag}(1,0,1,1,1)

Gli autovalori sono non negativi e uno è nullo, quindi $f$ è convessa ma non strettamente convessa. Il termine lineare non cambia l'Hessiana.

Il ruolo degli autovalori si vede guardando $f(x)=\frac12x^\top Qx$ lungo i due assi, con $Q=\operatorname{diag}(q_1,q_2)$ :

\begin{gathered} f(x_1,0)=\frac12q_1x_1^2\\ f(0,x_2)=\frac12q_2x_2^2 \end{gathered}

Con $q_1=1$ e $q_2=-1$ , come nell'esercizio a dieci variabili, una parabola è rivolta verso l'alto e l'altra verso il basso.

$f$ lungo i due assi

x_{1}

x_{2}

lungo $x_{1}$
lungo $x_{2}$

q_{1}

q_{2}

−1

Ogni autovalore dà la curvatura lungo il proprio asse. Con segni opposti la funzione non è né convessa né concava; con un autovalore nullo è piatta lungo quell'asse.

Insiemi definiti da una disuguaglianza

Gli insiemi dei problemi reali sono dati da equazioni e disequazioni, i vincoli. La convessità si decide dalla forma dei vincoli, senza cercare segmenti. Il caso più semplice è un solo vincolo $g(x)\le0$ , con $g:\mathbb R^n\to\mathbb R$ .

Se $g$ è convessa, l'insieme $S=\{x\in\mathbb R^n:\ g(x)\le0\}$ è convesso. Non serve che $g$ sia differenziabile. Siano $x,y\in S$ , cioè $g(x)\le0$ e $g(y)\le0$ . Per $\lambda\in[0,1]$ la convessità di $g$ dà

\begin{aligned} g\bigl((1-\lambda)x+\lambda y\bigr)&\le(1-\lambda)g(x)+\lambda g(y)\\ &\le0 \end{aligned}

L'ultima disuguaglianza vale perché $1-\lambda$ e $\lambda$ non sono negativi e $g(x)$ , $g(y)$ non sono positivi. Quindi la combinazione convessa sta in $S$ .

Esempio in $\mathbb R^4$ . Sia $g(x)=x_1^2+x_2^2+x_3^2+x_4$ . Il gradiente e l'Hessiana sono

\begin{gathered} \nabla g(x)=(2x_1,\,2x_2,\,2x_3,\,1)^\top\\ \nabla^2g(x)=\operatorname{diag}(2,2,2,0) \end{gathered}

L'Hessiana è semidefinita positiva, quindi $g$ è convessa e $S=\{x:\ g(x)\le0\}$ è convesso.

Più vincoli di disuguaglianza

Sia $S=\{x:\ g_i(x)\le0,\ i=1,\dots,N\}$ , con ogni $g_i$ convessa. Ogni insieme $S_i=\{x:\ g_i(x)\le0\}$ è convesso per il risultato precedente. Un punto sta in $S$ se soddisfa tutti i vincoli insieme, quindi

S=\bigcap_{i=1}^{N}S_i

e $S$ è convesso, perché l'intersezione di insiemi convessi è convessa.

Il verso del vincolo conta: il risultato vale per $g_i(x)\le0$ . Un vincolo scritto con $\ge$ si riporta a $\le$ cambiando segno alla funzione, e poi si controlla che la funzione ottenuta sia convessa.

Vincoli di uguaglianza

Per $S=\{x\in\mathbb R^n:\ H(x)=0\}$ la convessità di $H$ non basta. Si prende, in $\mathbb R^2$ con coordinate $(x,y)$ , $H(x,y)=x^2-y$ :

\begin{gathered} \nabla H(x,y)=\begin{pmatrix}2x\\-1\end{pmatrix}\\ \nabla^2H(x,y)=\begin{pmatrix}2&0\\0&0\end{pmatrix} \end{gathered}

L'Hessiana ha autovalori $2$ e $0$ , quindi è semidefinita positiva e $H$ è convessa. Ma l'insieme $H(x,y)=0$ è il grafico della parabola $y=x^2$ , e il segmento fra due suoi punti non resta sulla parabola. Con $H(x,y)\le0$ , invece, l'insieme è la regione sopra la parabola, ed è convesso.

Stessa funzione, disuguaglianza e uguaglianza

$H (x, y) \leq 0$ : convesso

P_{1}

P_{2}

x

y

$H (x, y) \leq 0$
segmento

$H (x, y) = 0$ : non convesso

P_{1}

P_{2}

x

y

$H (x, y) = 0$
segmento

Con

H (x, y) \leq 0

il segmento fra due punti resta nell'insieme. Con

H (x, y) = 0

l'insieme è solo la parabola e il segmento ne esce.

Un vincolo lineare di uguaglianza $A_jx-b_j=0$ , con $A_j$ matrice e $b_j$ vettore, fa eccezione: l'insieme delle soluzioni è un iperpiano, o un'intersezione di iperpiani, quindi è convesso. Sia $T_j$ l'insieme delle soluzioni del $j$ -esimo vincolo, per $j=1,\dots,t$ . Se i vincoli di disuguaglianza sono $g_i(x)\le0$ con $g_i$ convesse, e quelli di uguaglianza sono lineari, l'insieme ammissibile è

S=\bigcap_{i=1}^{N}S_i\ \cap\ \bigcap_{j=1}^{t}T_j

ed è convesso, come intersezione di insiemi convessi.

I vincoli lineari, di uguaglianza o di disuguaglianza e in qualunque verso, danno sempre insiemi convessi: una funzione lineare è convessa e concava, quindi cambiarle segno per passare da $\ge$ a $\le$ la lascia convessa. Un vincolo non lineare va invece scritto come $g(x)\le0$ , e si studia la convessità di $g$ .

Il problema generale

Ogni problema di ottimizzazione ha la stessa forma: il minimo, o il massimo, di una funzione $f$ su un insieme $S$ :

\min_{x\in S}f(x),\qquad\max_{x\in S}f(x)

La convessità dell'insieme e quella della funzione, studiate qui, sono le proprietà che permettono di trattare problemi con moltissimi dati.

Formulario

Funzione convessa su $S$

\begin{aligned} &f((1-\lambda)x+\lambda y)\\ &\le(1-\lambda)f(x)\\ &\quad+\lambda f(y) \end{aligned}

Primo ordine, per ogni $x,y\in S$

\begin{aligned} f(y)&\ge f(x)\\ &\quad+\nabla f(x)^\top(y-x) \end{aligned}

Convessa su $S$ se e solo se, in ogni $x\in S$

\begin{aligned} &\nabla^2f(x)\\ &\text{semidefinita positiva} \end{aligned}

Strettamente convessa, se in ogni $x\in S$

\begin{aligned} &\nabla^2f(x)\\ &\text{definita positiva} \end{aligned}

Funzione lineare: convessa e concava

\begin{aligned} \nabla f(x)&=c\\ \nabla^2f(x)&=0_{n\times n} \end{aligned}

Funzione quadratica, $Q$ simmetrica, $b\in\mathbb R$

\begin{aligned} f(x)&=\frac12x^\top Qx\\ &\quad+c^\top x+b\\ \nabla f(x)&=Qx+c\\ \nabla^2f(x)&=Q \end{aligned}

Quadratica convessa se e solo se

Q\ \text{semidefinita positiva}

Quadratica strettamente convessa se e solo se

Q\ \text{definita positiva}

Minimi quadrati, $A\in\mathbb R^{m\times n}$ , $b\in\mathbb R^m$ : sempre convessa

\begin{aligned} f(x)&=\frac12\lVert Ax-b\rVert_2^2\\ \nabla^2f(x)&=A^\top A \end{aligned}

Un vincolo, con $g$ convessa

S=\{x:\ g(x)\le0\}\ \text{convesso}

Più vincoli, con ogni $g_i$ convessa

\begin{aligned} S&=\bigcap_{i=1}^{N}S_i\\ S_i&=\{x:\ g_i(x)\le0\} \end{aligned}

Uguaglianza lineare: iperpiano

T_j=\{x:\ A_jx-b_j=0\}

Problema di ottimizzazione

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