Un problema di ottimizzazione cerca il minimo di una funzione su un insieme. La convessità è una proprietà importante da riconoscere, perché rende più favorevole il problema. Sono due proprietà distinte: quella dell'insieme su cui la funzione è definita e quella della funzione. Possono essere convessi entrambi, uno solo o nessuno. Qui si studia soprattutto la prima.
Un insieme del piano è convesso se, presi due suoi punti, contiene tutto il segmento che li unisce. La definizione deve valere in Rn, dove le coordinate non sono sempre lunghezze: possono essere peso, altezza ed età di una persona. Servono quindi formule, che si costruiscono partendo dai sottospazi.
Sottospazi lineari e affini
Un sottoinsieme non vuoto S⊆Rn è un sottospazio lineare se contiene ogni combinazione lineare di due suoi punti:
x,y∈S,α,β∈R⇒αx+βy∈S
Con α=β=0 segue che il vettore nullo sta in ogni sottospazio lineare.
In R2 una retta che non passa per l'origine non lo è, perché non contiene il vettore nullo. Nemmeno la parabola y=x2 lo è: la somma di (s,s2) e (r,r2) è (s+r,s2+r2), ma (s+r)2=s2+r2+2sr è diverso da s2+r2 se sr=0. La retta y=2x lo è: α(s,2s)+β(r,2r)=(αs+βr,2(αs+βr)) sta ancora sulla retta. I sottospazi lineari di R2 sono l'origine, le rette per l'origine e tutto R2. L'insieme vuoto no, perché per definizione non è vuoto.
Un insieme non vuoto è un sottospazio lineare se e solo se è l'insieme delle soluzioni di un sistema omogeneo, e la sua dimensione è n meno il rango:
I sottospazi lineari sono troppo pochi per descrivere gli insiemi convessi, quindi si passa ai sottospazi affini, definiti da un sistema non omogeneo:
T={x∈Rn:Ax=b}
Il termine noto b trasla l'insieme, che non deve più passare per l'origine. Con b=0 si ritrova un sottospazio lineare. Le rette sono sottospazi affini.
Retta e segmento
La retta per x0∈Rn con direzione d=0 è l'insieme dei punti che si ottengono muovendosi da x0 lungo d:
{x∈Rn:x=x0+λd,λ∈R}
Per due punti distinti x1 e x2 la direzione è la loro differenza, d=x2−x1:
{x∈Rn:x=x1+λ(x2−x1),λ∈R}
Il parametro λ è l'unica cosa su cui si può agire per limitare la retta. Se si impone λ∈[0,1] resta la parte fra x1 e x2, cioè il segmento. Mettendo in evidenza x1:
[x1,x2]={(1−λ)x1+λx2:λ∈[0,1]}
Con λ=0 si ottiene x1, con λ=1 si ottiene x2, e i valori intermedi danno i punti fra i due. Un punto del segmento si indica con z=(1−λ)x1+λx2.
Retta e segmento per due punti
x1x2zxy
retta: λ∈R
segmento: λ∈[0,1]
Per λ∈[0,1] il punto z percorre il segmento da x1 a x2. Per gli altri valori resta sulla retta, oltre gli estremi.
Insiemi convessi
Un insieme C⊆Rn è convesso se contiene il segmento fra ogni coppia dei suoi punti:
In R sono convesse le rette, le semirette e i segmenti. In R2 lo sono il cerchio pieno, il triangolo, i poligoni regolari e i semipiani. Non lo è un insieme che lascia uscire alcuni segmenti.
Convesso e non convesso
Convesso: un cerchio
x1x2xy
cerchio pieno
segmento
Non convesso: due cerchi uniti
x1x2xy
C1
C2
segmento
In un insieme convesso il segmento fra due suoi punti resta dentro. L'unione di due cerchi non è convessa: il segmento fra un punto di ciascuno può uscire.
Iperpiani e semispazi
In R3 un piano è l'insieme dei punti (x,y,z) con a1x+a2y+a3z=β. In Rn la stessa equazione si scrive con il prodotto scalare e il piano diventa un iperpiano:
H={x∈Rn:a⊤x=β}
con a∈Rn non nullo e β∈R. Con a=0 l'equazione 0=β non dipende più da x.
Un semispazio sostituisce l'uguaglianza con una disuguaglianza:
Il primo è chiuso, perché contiene l'iperpiano che lo delimita. Il secondo è aperto, perché la disuguaglianza è stretta e l'iperpiano resta fuori. Il verso opposto non va definito a parte: a⊤x≤β equivale a (−a)⊤x≥−β.
Un semispazio è convesso. Si prendono due punti x1,x2∈S≥, un λ∈[0,1] e il punto z=(1−λ)x1+λx2 del segmento. Si deve mostrare che z∈S≥. I coefficienti 1−λ e λ sono non negativi, quindi mantengono il verso delle disuguaglianze a⊤x1≥β e a⊤x2≥β:
Per S> le disuguaglianze sono strette, e 1−λ e λ non sono mai entrambi nulli: il risultato resta >β.
Perché un semispazio è convesso
Il semispazio x+y≥1
x1x2zxy
semispazio chiuso
segmento
a⊤z al variare di λ
λ
a⊤z
β=1
Lungo il segmento a⊤z varia in modo lineare fra a⊤x1 e a⊤x2: se entrambi sono almeno β, lo è anche a⊤z. Trascinando x2 fuori dal semispazio, il segmento esce.
Intersezioni e unioni
Un iperpiano è l'intersezione dei due semispazi chiusi che ha come bordo:
H={x:a⊤x≥β}∩{x:a⊤x≤β}
L'intersezione di insiemi convessi è convessa, anche se la famiglia {Ci}i∈I è infinita. Sia C=⋂i∈ICi e siano x,y∈C. I due punti stanno in ogni Ci, e ogni Ci è convesso, quindi z=(1−λ)x+λy sta in ogni Ci. Dunque z∈C. In particolare ogni iperpiano è convesso, perché intersezione di due semispazi convessi.
L'unione in generale non conserva la convessità. I due cerchi della figura «Convesso e non convesso» sono convessi e si intersecano, ma il segmento fra un punto del primo e uno del secondo esce dalla loro unione.
Poliedri
Un poliedro è l'intersezione di un numero finito di semispazi chiusi. Un'uguaglianza è l'intersezione di due semispazi chiusi, quindi un poliedro è l'insieme delle soluzioni di un sistema finito di vincoli lineari:
Alcuni dei tre gruppi possono mancare. I semispazi devono essere chiusi: con quelli aperti il bordo resterebbe fuori. Un poliedro è convesso, perché i semispazi sono convessi e l'intersezione di convessi è convessa. Nel piano ogni poligono convesso è un poliedro.
Un poligono come intersezione di semispazi
xy
poliedro
a1⊤x=b1
a2⊤x=b2
a3⊤x=b3
a4⊤x=b4
Un poligono convesso è l'intersezione dei semispazi chiusi delimitati dalle rette dei suoi lati: il bordo è incluso.
Sfere aperte e chiuse
Dati un centro xˉ∈Rn, un raggio ρ>0 e una norma qualsiasi, la sfera aperta è
B(xˉ,ρ)={x∈Rn:∥x−xˉ∥<ρ}
La sfera chiusa si ottiene con ≤ al posto di <: è l'insieme dei punti con ∥x−xˉ∥≤ρ.
Le due sfere sono convesse. Per x,y nella sfera chiusa e λ∈[0,1] si aggiunge e si toglie λxˉ, cioè si scrive xˉ=(1−λ)xˉ+λxˉ, e si raccoglie. Poi si usano la disuguaglianza triangolare e l'omogeneità della norma (1−λ e λ sono non negativi, quindi escono dalla norma):
Per la sfera aperta le due norme sono minori di ρ e il risultato è minore di ρ.
Insiemi convessi: riepilogo
Sono convessi l'insieme vuoto, perché la condizione vale a vuoto, e un punto, perché la combinazione di un punto con sé stesso è ancora quel punto. Lo sono le rette, i sottospazi lineari e affini, i semispazi, gli iperpiani, i poliedri, le sfere aperte e chiuse e tutto Rn.
Convessità di una funzione
Una funzione f definita su un insieme convesso è convessa se il suo grafico sta sotto il segmento che unisce due suoi punti, e concava se sta sopra:
per ogni x1,x2 del dominio e λ∈[0,1]. Per una funzione concava vale ≥. Se f è di una variabile e due volte derivabile su un intervallo, è convessa se e solo se f′′(x)≥0 sull'intervallo. La convessità del dominio non implica quella della funzione: una funzione non convessa può essere definita su un insieme convesso, e le due proprietà vanno distinte.