Konvexe Funktion

Beschreibung

Die Konvexität verallgemeinert die Idee, dass die zweite Ableitung einer Funktion streng positiv ist.

Definition

Konvexität

Eine Funktion $f:C\to R^n$ auf einer konvexen Menge $C\subseteq {\mathbb{R}}^n$ heißt konvex, g.d.w. wenn für alle $x,y\in C$ und für alle $t\in [0,1]$: $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$

Q: Konvexe Funktion A: $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$

Strenge Konvexität

Eine Funktion $f:C\to R^n$ auf einer konvexen Menge $C\subseteq {\mathbb{R}}^n$ heißt streng konvex, g.d.w. wenn für alle $x,y\in C$ und für alle $t\in [0,1]$: $f(tx+(1-t)y)<tf(x)+(1-t)f(y)$

Starke Konvexität

Eine Funktion $f:C\to R^n$ auf einer konvexen Menge $C\subseteq {\mathbb{R}}^n$ heißt stark konvex, g.d.w. wenn ein $\mu >0$ existiert, sodass für alle $x,y\in C$ und für alle $t\in [0,1]$: $f(tx+(1-t)y)+\mu t(1-t)\Vert y-x{\Vert }^2\le tf(x)+(1-t)f(y)$

Das heißt, man kann eine Parabel auf die Funktion draufaddieren und die Funktion bleibt konvex. D.h. im Grunde: Die gegebene Funktion ist “konvexer” als eine bestimmte quadratische Funktion.

Q: Stark Konvexe Funktion A: $f(tx+(1-t)y)+\mu t(1-t)\Vert y-x{\Vert }^2\le tf(x)+(1-t)f(y)$

Charakterisierungen

Gradient

Eine Funktion $f:C\to \mathbb{R}$ ist konvex g.d.w. für alle $x,y\in C$: $f(x)-f(y)\ge \nabla f(y)(x-y)$

Sie ist streng konvex g.d.w. $f(x)-f(y)>\nabla f(y)(x-y)$

Sie ist stark konvex g.d.w. $f(x)-f(y)>\nabla f(y)(x-y)+\mu \Vert x-y{\Vert }^2$

Wobei $\nabla$ hier für den Gradient steht.

Q: Charakterisierung von Konvexität durch den Gradienten A: Eine Funktion $f:C\to \mathbb{R}$ ist konvex g.d.w. für alle $x,y\in C$: $f(y)-f(x)\ge \nabla f(x)(y-x)$

Q: Charakterisierung von starker Konvexität durch den Gradienten A: Eine Funktion $f:C\to \mathbb{R}$ ist streng konvex g.d.w. für alle $x,y\in C$: $f(y)-f(x)\ge \nabla f(x)(y-x)+\mu \Vert y-x{\Vert }^2$

Eigenschaften

Lokale Minima sind globale Minima

Sei $C\subseteq X$ konvex und $f:C\to \mathbb{R}$ konvex. Dann gilt:

• Die lokalen Minima sind genau die globalen Minima
• Die Menge der Minima bilden eine Konvexe Menge

Sei nun $f:C\to \mathbb{R}$ streng konvex. Ist $x_0$ ein lokales Minimum, so ist es das einzige lokale und in Folge globale Minimum.

Abschätzung zum Minimum

Sei $C\subseteq {\mathbb{R}}^n$ konvex und $f:C\to \mathbb{R}$ differenzierbar. Ist $f$ stark konvex und $x_{\ast }\in C$ ein Minimum von $f$.

Dann existiert ein $\mu \in {\mathbb{R}}^{+}$ sodass: $\mu \Vert x-x_{\ast }{\Vert }^2\le f(x)-f(x_{\ast })$

Q: Abschätzung von Funktionswerten bei stark konvexen Funktionen. A: Es gibt $\mu >0$: $\mu \Vert x-x_{\ast }{\Vert }^2\le f(x)-f(x_{\ast })$