Konvexität und warum sie zählt

Ein Tal, eine Antwort

Eine Funktion ist konvex, wenn die Strecke zwischen zwei Punkten ihres Graphen auf oder über dem Graphen liegt: $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$ für alle $\theta\in[0,1]$. Für zweimal differenzierbare Funktionen gibt es einen praktischen Test: $f$ ist genau dann konvex, wenn ihre Hesse-Matrix überall positiv semidefinit ist, also alle Eigenwerte $\ge0$ sind. Summen konvexer Funktionen, positive Vielfache und das Maximum konvexer Funktionen sind wieder konvex, so entstehen große konvexe Zielfunktionen aus kleinen Bausteinen.

Konvexität macht Optimierung verlässlich. Jedes lokale Minimum ist ein globales, ein Nullgradient genügt zum Anhalten, und die Antwort hängt nicht davon ab, wo der Löser startet. Ist die Funktion streng konvex, ist der Minimierer zudem eindeutig, und ist sie stark konvex, mit Krümmung mindestens $\mu>0$ in jeder Richtung, konvergiert das Gradientenverfahren mit der zuvor gesehenen geometrischen Rate. Ohne Konvexität ist nichts davon garantiert: Der Löser kann in einem Tal stehen bleiben, das nicht das tiefste ist.

In der Finanzwelt sind konvexe Zielfunktionen unter anderem die Portfoliovarianz $\mathbf w^{T}\Sigma\mathbf w$ (eine Kovarianzmatrix ist positiv semidefinit), Kleinste-Quadrate-Verluste, die $\ell_1$-Norm $\lVert\mathbf w\rVert_1$ und der Expected Shortfall (CVaR) als Funktion der Gewichte. Value-at-Risk, eine Obergrenze für die Zahl der Gewichte ungleich null und die Sharpe-Ratio in ihrer üblichen Form sind nicht konvex. Eine Stichprobenkovarianzmatrix aus weniger Beobachtungen als Assets ist positiv semidefinit, aber singulär, die Varianz ist also konvex ohne streng konvex zu sein, und viele Gewichtsvektoren sind beim Minimum gleichauf.

• Hesse-Test: überall alle Eigenwerte $\ge0$ heißt konvex; ein negativer Eigenwert heißt nicht konvex.
• Nutzen: Jedes lokale Minimum ist global, der Startpunkt spielt keine Rolle.
• Bausteine: Summen, positive Vielfache und Maxima konvexer Funktionen bleiben konvex.

Lab: Was bewertet wird

• Eine Konvexitätslücke15 Pkt.
• Der Eigenwert, der die Konvexität zerstört15 Pkt.
• Welche Hesse-Matrix ist konvex15 Pkt.
• Konvexe Zielfunktionen in der Finanzwelt15 Pkt.
• Ein Nullgradient10 Pkt.
• Konvexitätsvokabular15 Pkt.
• Warum Löser konvexe Probleme mögen15 Pkt.