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 an der Stelle $x_{0}$ , wenn für alle $x\in\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 im Punkt $x_{0}$ .

Anschauung

Subgradienten einer konvexen Funktion

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

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

Da die Normalengleichung von gerade

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

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

Im allgemeinen Fall $n\geq 1$ liegt über der Hyperebenen, 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 nicht leer.

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}}$

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

ist also kein Subgradient. Das ist ein Widerspruch.

Basierend auf einem Artikel in:

Wikipedia.de