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 ${\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} }$ eine konvexe Funktion. Ein Vektor ${\displaystyle g\in \mathbb {R} ^{n}}$ heißt Subgradient von ${\displaystyle f}$ an der Stelle ${\displaystyle x_{0}}$, wenn für alle ${\displaystyle x\in \mathbb {R} ^{n}}$ gilt^[1]

${\displaystyle f(x)\geq f(x_{0})+\langle g,x-x_{0}\rangle }$,

wobei ${\displaystyle \langle \cdot ,\cdot \rangle }$ das Standardskalarprodukt bezeichnet.

Das Subdifferential ${\displaystyle \partial f(x_{0})}$ ist die Menge aller Subgradienten von ${\displaystyle f}$ im Punkt ${\displaystyle x_{0}}$.^[2]

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

Für eine konvexe Funktion gilt ${\displaystyle a\leq b}$, für eine nicht konvexe Funktion braucht dies nicht zu gelten und dann ist ${\displaystyle \partial f(x_{0})=\emptyset }$.

Anschauung

Subgradienten einer konvexen Funktion

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

${\displaystyle G=\{(x,y)\in \mathbb {R} ^{2}\mid y=g\cdot (x-x_{0})+f(x_{0})\}}$

Da die Normalengleichung von ${\displaystyle G}$ gerade

${\displaystyle -g\cdot (x-x_{0})+1\cdot (y-f(x_{0}))=0}$

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

Im allgemeinen Fall ${\displaystyle n\geq 1}$ liegt ${\displaystyle f}$ über der Hyperebene, die durch den Fußpunkt ${\displaystyle (x_{0},f(x_{0}))}$ und die Normale ${\displaystyle (-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 ${\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {R} }$, ${\displaystyle x\mapsto |x|}$ ist gegeben durch:

${\displaystyle \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 ${\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$ stetig und sei ${\displaystyle X\subset \mathbb {R} ^{n}}$ beschränkt. Dann ist die Menge ${\displaystyle \bigcup _{x_{0}\in X}\partial f(x_{0})}$ beschränkt.

Beweis

Sei ${\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$ stetig und sei ${\displaystyle X\subset \mathbb {R} ^{n}}$ beschränkt. Setze ${\displaystyle \varepsilon$ :=\sup |f({\overline {U_{1}(X)}})|} wobei ${\displaystyle {\overline {U_{1}(X)}}=\{x\in \mathbb {R} ^{n}\mid {\rm {dist}}(x,X)\leq 1\}}$. Angenommen, ${\displaystyle \bigcup _{x_{0}\in X}\partial f(x_{0})}$ ist nicht beschränkt, dann gibt es für ${\displaystyle R:=2\varepsilon }$ ein ${\displaystyle x_{0}\in X}$ und ein ${\displaystyle g\in \partial f(x_{0})}$ mit ${\displaystyle \|g\|_{2}>R=2\varepsilon }$. Sei ${\displaystyle x:={\frac {1}{\|g\|_{2}}}g+x_{0}}$. Somit sind ${\displaystyle x_{0},x\in {\overline {U_{1}(X)}}}$. Wir erhalten die Abschätzung

${\displaystyle 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})}$.

${\displaystyle g}$ ist also kein Subgradient. Das ist ein Widerspruch.

Differenzierbarkeit

Ist die Funktion differenzierbar in ${\displaystyle x_{0}\in \mathrm {int} \,\mathrm {dom} \,f}$, so gilt:

${\displaystyle \partial f(x_{0})=\left\{\nabla f(x_{0})\right\}}$

Siehe ^[3] für einen Beweis.

Zudem gilt: Ist das Subdifferential ${\displaystyle \partial f(x_{0})}$ einelementig, so ist ${\displaystyle f}$ an der Stelle ${\displaystyle x_{0}}$ differenzierbar.^[4]