Subdifferential
# 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\colon \mathbb {R} ^{n}\to \mathbb {R}$ eine konvexe Funktion. Ein Vektor $g\in \mathbb {R} ^{n}$ heißt Subgradient von $f$ an der Stelle $x_{0}$, wenn für alle $x\in \mathbb {R} ^{n}$ gilt
    $f(x)\geq f(x_{0})+\langle g,x-x_{0}\rangle$,
wobei $\langle \cdot ,\cdot \rangle$ 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=\lim _{x\to x_{0}^{-}}{\frac {f(x)-f(x_{0})}{x-x_{0}}},$ $b=\lim _{x\to x_{0}^{+}}{\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\leq b$, für eine nicht konvexe Funktion braucht dies nicht zu gelten und dann ist $\partial f(x_{0})=\emptyset$.

## Anschauung

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 \mathbb {R} ^{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 \mathbb {R} ^{2}$.
Im allgemeinen Fall $n\geq 1$ liegt $f$ über der Hyperebene, die durch den Fußpunkt $(x_{0},f(x_{0}))$ und die Normale $(-g,1)\in \mathbb {R} ^{n+1}$ gegeben ist.
Wegen des Trennungssatzes ist das Subdifferential einer stetigen konvexen Funktion überall nichtleer.

## Beispiel

Das Subdifferential der Funktion $f\colon \mathbb {R} \rightarrow \mathbb {R}$, $x\mapsto |x|$ ist gegeben durch:
    $\partial f(x_{0})={\begin{cases}\{-1\}&x_{0}<0\\\left[-1,1\right]&x_{0}=0\\\{1\}&x_{0}>0\end{cases}}$
Eine ähnliche Eigenschaft ist bei der Lasso-Regression für die Herleitung der Soft-Threshold-Funktion wichtig.

## Beschränktheit

Sei $f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R}$ stetig und sei $X\subset \mathbb {R} ^{n}$ beschränkt. Dann ist die Menge $\bigcup _{x_{0}\in X}\partial f(x_{0})$ beschränkt.

### Beweis

Sei $f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R}$ stetig und sei $X\subset \mathbb {R} ^{n}$ beschränkt. Setze $\varepsilon :=\sup |f({\overline {U_{1}(X)}})|$ wobei ${\overline {U_{1}(X)}}=\{x\in \mathbb {R} ^{n}\mid {\rm {dist}}(x,X)\leq 1\}$. Angenommen, $\bigcup _{x_{0}\in X}\partial f(x_{0})$ ist nicht beschränkt, dann gibt es für $R:=2\varepsilon$ ein $x_{0}\in X$ und ein $g\in \partial f(x_{0})$ mit $\|g\|_{2}>R=2\varepsilon$. Sei $x:={\frac {1}{\|g\|_{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}{\|g\|_{2}}}g^{T}g=\|g\|_{2}>2\varepsilon \geq \left|f(x)-f(x_{0})\right|\geq f(x)-f(x_{0})$.
$g$ ist also kein Subgradient. Das ist ein Widerspruch.

## Differenzierbarkeit

Ist die Funktion differenzierbar in $x_{0}\in \mathrm {int} \,\mathrm {dom} \,f$, so gilt:
    $\partial f(x_{0})=\left\{\nabla f(x_{0})\right\}$
Siehe für einen Beweis.
Zudem gilt: Ist das Subdifferential $\partial f(x_{0})$ einelementig, so ist $f$ an der Stelle $x_{0}$ differenzierbar.