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 <math> f\colon\mathbb{R}^n\to\mathbb{R}</math> eine konvexe Funktion. Ein Vektor <math>g\in\R^n</math> heißt Subgradient von <math>f</math> an der Stelle <math>x_0</math>, wenn für alle <math>x\in\R^n</math> gilt<ref>R. T. Rockafellar Convex analysis 1970., p.214</ref>

<math> f(x) \geq f(x_0) + \langle g, x-x_0 \rangle </math>,

wobei <math>\langle \cdot , \cdot \rangle</math> das Standardskalarprodukt bezeichnet.

Das Subdifferential <math>\partial f(x_0) </math> ist die Menge aller Subgradienten von <math>f</math> im Punkt <math>x_0</math>.<ref>R. T. Rockafellar Convex analysis 1970., p.215</ref>

Existieren die folgenden Grenzwerte <math display="block">a=\lim_{x\to x_0^-} \frac{f(x)-f(x_0)}{x-x_0},</math> <math display="block">b=\lim_{x\to x_0^+} \frac{f(x)-f(x_0)}{x-x_0},</math> so wird das Intervall <math>[a,b]</math> aller Subgradienten das Subdifferential der Funktion <math>f</math> bei <math>x_0</math> genannt und wird als <math>\partial f(x_0) :=[a,b]</math> geschrieben.

Für eine konvexe Funktion gilt <math>a\leq b</math>, für eine nicht konvexe Funktion braucht dies nicht zu gelten und dann ist <math>\partial f(x_0)=\emptyset</math>.

Anschauung

Datei:Subgradienten.svg

Subgradienten einer konvexen Funktion

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

Da die Normalengleichung von <math>G</math> gerade

ist, ist die Normale an <math>G</math> also <math>(-g,1)\in\R^2</math>.

Im allgemeinen Fall <math>n\geq 1</math> liegt <math>f</math> über der Hyperebene, die durch den Fußpunkt <math>(x_0,f(x_0))</math> und die Normale <math>(-g,1)\in\R^{n+1}</math> gegeben ist.

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

Beispiel

Das Subdifferential der Funktion <math>f\colon\mathbb{R}\rightarrow\mathbb{R}</math>, <math>x\mapsto|x|</math> ist gegeben durch:

<math>\partial f(x_0)=\begin{cases}\{-1\} & x_0<0\\

\left[-1,1\right] & x_0=0\\ \{1\} & x_0>0\end{cases}</math> Eine ähnliche Eigenschaft ist bei der Lasso-Regression für die Herleitung der Soft-Threshold-Funktion wichtig.

Beschränktheit

Sei <math>f\colon\mathbb{R}^n\rightarrow\mathbb{R}</math> stetig und sei <math>X\subset\mathbb{R}^n</math> beschränkt. Dann ist die Menge <math>\bigcup_{x_0\in X}\partial f(x_0)</math> beschränkt.

Beweis

Sei <math>f\colon\mathbb{R}^n\rightarrow\mathbb{R}</math> stetig und sei <math>X\subset\mathbb{R}^n</math> beschränkt. Setze <math>\varepsilon:=\sup |f(\overline{U_1(X)})|</math> wobei <math>\overline{U_1(X)}=\{x\in\mathbb{R}^n\mid{\rm dist}(x,X)\leq1\}</math>. Angenommen, <math>\bigcup_{x_0\in X}\partial f(x_0)</math> ist nicht beschränkt, dann gibt es für <math>R:=2\varepsilon</math> ein <math>x_0\in X</math> und ein <math>g\in\partial f(x_0)</math> mit <math>\|g\|_2>R=2\varepsilon</math>. Sei <math>x:=\frac{1}{\|g\|_2} g+x_0</math>. Somit sind <math>x_0,x\in\overline{U_1(X)}</math>. Wir erhalten die Abschätzung

<math>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)</math>.

<math>g</math> ist also kein Subgradient. Das ist ein Widerspruch.

Differenzierbarkeit

Ist die Funktion differenzierbar in <math>x_0 \in \mathrm{int}\,\mathrm{dom}\,f</math>, so gilt:

<math>\partial f(x_0) = \left\{\nabla f(x_0)\right\}</math>

Siehe <ref>Yaron Singer: Advanced Optimzation. Abgerufen am 27. Januar 2022: „Proposition 4“ </ref> für einen Beweis.

Zudem gilt: Ist das Subdifferential <math>\partial f(x_0)</math> einelementig, so ist <math>f</math> an der Stelle <math>x_0</math> differenzierbar.<ref>R. T. Rockafellar: Convex Analysis. Band 28, 1970: „Theorem 25.1“ </ref>

Literatur