Subdifferential

Das Subdifferential ist eine Verallgemeinerung des Gradienten auf nicht differenzierbare konvexe Funktionen. Das Subdifferential spielt eine wichtige Rolle in der konvexen Analysis sowie der konvexen Optimierung.

Definition

Sei $f:{ℝ}^n\to ℝ$ eine konvexe Funktion. Ein Vektor $g\in {ℝ}^n$ heißt Subgradient von $f$ an der Stelle $x_0$, wenn für alle $x\in {ℝ}^n$ gilt

$f(x)\ge f(x_0)+⟨g,x-x_0⟩$,

wobei $⟨\cdot ,\cdot ⟩$ das Standardskalarprodukt bezeichnet.

Das Subdifferential $\partial f(x_0)$ ist die Menge aller Subgradienten von $f$ im Punkt $x_0$.

Existieren die folgenden Grenzwerte $$a=\underset{x\to x_0^{-}}{\lim }\frac{f(x)-f(x_0)}{x-x_0},$$ $$b=\underset{x\to x_0^{+}}{\lim }\frac{f(x)-f(x_0)}{x-x_0},$$ so wird das Intervall $[a,b]$ aller Subgradienten das Subdifferential der Funktion $f$ bei $x_0$ genannt und wird als $\partial f(x_0):=[a,b]$ geschrieben.

Für eine konvexe Funktion gilt $a\le b$, für eine nicht konvexe Funktion braucht dies nicht zu gelten und dann ist $\partial f(x_0)=\mathrm{\varnothing }$.

Anschauung

Subgradienten einer konvexen Funktion

Intuitiv bedeutet diese Definition für $n=1$, dass der Graph der Funktion $f$ überall über der Geraden $G$ liegt, die durch den Punkt $(x_0,f(x_0))$ geht und die Steigung $g$ besitzt:

$G=\{(x,y)\in {ℝ}^2\mid y=g\cdot (x-x_0)+f(x_0)\}$

Da die Normalengleichung von $G$ gerade

$-g\cdot (x-x_0)+1\cdot (y-f(x_0))=0$

ist, ist die Normale an $G$ also $(-g,1)\in {ℝ}^2$.

Im allgemeinen Fall $n\ge 1$ liegt $f$ über der Hyperebene, die durch den Fußpunkt $(x_0,f(x_0))$ und die Normale $(-g,1)\in {ℝ}^{n+1}$ gegeben ist.

Wegen des Trennungssatzes ist das Subdifferential einer stetigen konvexen Funktion überall nichtleer.

Beispiel

Das Subdifferential der Funktion $f:ℝ\to ℝ$, $x\mapsto |x|$ ist gegeben durch:

$\partial f(x_0)=\{\begin{array}{cc}\{-1\}& x_0<0\\ [-1,1]& x_0=0\\ \{1\}& x_0>0\end{array}$

Eine ähnliche Eigenschaft ist bei der Lasso-Regression für die Herleitung der Soft-Threshold-Funktion wichtig.

Beschränktheit

Sei $f:{ℝ}^n\to ℝ$ stetig und sei $X\subset {ℝ}^n$ beschränkt. Dann ist die Menge $\bigcup _{x_0\in X}\partial f(x_0)$ beschränkt.

Beweis

Sei $f:{ℝ}^n\to ℝ$ stetig und sei $X\subset {ℝ}^n$ beschränkt. Setze $\epsilon :=\sup |f(\overline{U_1(X)})|$ wobei $\overline{U_1(X)}=\{x\in {ℝ}^n\mid \mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(x,X)\le 1\}$. Angenommen, $\bigcup _{x_0\in X}\partial f(x_0)$ ist nicht beschränkt, dann gibt es für $R:=2\epsilon$ ein $x_0\in X$ und ein $g\in \partial f(x_0)$ mit $\Vert g{\Vert }_2>R=2\epsilon$. Sei $x:=\frac{1}{\Vert g{\Vert }_2}g+x_0$. Somit sind $x_0,x\in \overline{U_1(X)}$. Wir erhalten die Abschätzung

$g^T(x-x_0)=\frac{1}{\Vert g{\Vert }_2}{g}^{T}g=\Vert g{\Vert }_2>2\epsilon \ge |f(x)-f(x_0)|\ge f(x)-f(x_0)$.

$g$ ist also kein Subgradient. Das ist ein Widerspruch.

Differenzierbarkeit

Ist die Funktion differenzierbar in $x_0\in \mathrm{i}\mathrm{n}\mathrm{t}\mathrm{d}\mathrm{o}\mathrm{m}f$, so gilt:

$\partial f(x_0)=\{\mathrm{\nabla }f(x_0)\}$

Siehe für einen Beweis.

Zudem gilt: Ist das Subdifferential $\partial f(x_0)$ einelementig, so ist $f$ an der Stelle $x_0$ differenzierbar.