Konveksitet

Konveksitet är ett grundläggande begrepp inom geometri och analys som beskriver hur objekt uppför sig under blandningar av punkter. För en mängd M ⊆ R^n är M konvex om varje linjesegment mellan två punkter i M ligger helt i M. Det uttrycks ofta som: för alla x, y ∈ M och alla t ∈ [0,1] gäller t x + (1−t) y ∈ M. En konvex mängd innebär alltså att det inte uppstår några “hål” när man räknar med linjära blandningar av punkterna i mängden.

En funktion f: D → R med domän D ⊆ R^n är konvex om domänen är konvex och för alla x, y ∈ D samt alla t ∈ [0,1] uppfylls f(t x + (1−t) y) ≤ t f(x) + (1−t) f(y). Epigraphen till f, Epi(f) = { (x, α) | x ∈ D, α ≥ f(x) }, är konvex om och endast om f är konvex. För två gånger differentiabla funktioner är positiv semidefinit Hessian ett villkor för konveksitet över den domänen.

Viktiga egenskaper är att snittet av konvexa mängder är konvext, bild av en konvex mängd genom en affin avbildning är konvex, och att summan av konvexa funktioner är konvex. Dessutom är den punktvisa maxfunktionen av två konvexa funktioner igen konvex. Många konvexa funktioner uppfyller f(x) = f(tx + (1−t) y) ≤ t f(x) + (1−t) f(y).

Användningar finns främst inom konvex optimering och ekonomisk teori, där problem ofta kan formuleras som att minimera en konvex funktion över en konvex mängd och löses effektivt med polynomisk tidteknik. Historiskt har konveksitet varit centralt i geometri och utvecklingen av konvex analys under 1900-talet, med bidrag från bland andra Minkowski och Rockafellar.