Konvexität — die heilige Eigenschaft
Konvexe Menge: Für je zwei Punkte x, y ∈ K liegt die ganze Strecke {tx + (1-t)y : t ∈ [0,1]} in K.
Konvexe Funktion: f(tx + (1-t)y) ≤ t·f(x) + (1-t)·f(y).
Konvexe Funktion: f(tx + (1-t)y) ≤ t·f(x) + (1-t)·f(y).
Warum ist das so wichtig?
- Lokales Minimum = globales Minimum. Kein Festlaufen in lokalen Mulden.
- Effiziente Algorithmen mit beweisbarer Konvergenz.
- Optimalitätsbedingungen sind hinreichend, nicht nur notwendig.
Wie erkennt man Konvexität?
| Test | Bedeutung |
|---|---|
| f''(x) ≥ 0 (1D) | f konvex |
| Hesse-Matrix positiv semidefinit | f konvex (n-D) |
| Norm, Maximum konvexer Funktionen | konvex |
| affine Funktion ax + b | konvex und konkav |
| Komposition: g(f(x)), g monoton wachsend & konvex | kann konvex sein |
Visuelle IntuitionKonvexe Funktion = "Schale". Die Verbindungsstrecke zweier Punkte des Graphen liegt oberhalb des Graphen. Konkav = "Hügel" (umgekehrt).