imported>일성김: /* Definition */

2024-09-03T15:57:11Z

Definition

Neue Seite

Das '''Subdifferential''' ist eine Verallgemeinerung des [[Gradient (Mathematik)|Gradienten]] auf nicht [[Differenzierbarkeit|differenzierbare]] [[Konvexe und konkave Funktionen|konvexe Funktionen]]. Das Subdifferential spielt eine wichtige Rolle in der [[Konvexe und konkave Funktionen|konvexen Analysis]] sowie der [[Konvexe Optimierung|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 (Mathematik)|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|mini|300px|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:
:<math>G=\{(x,y)\in\R^2\mid y=g\cdot(x-x_0)+f(x_0)\}</math>
Da die [[Normalengleichung]] von <math>G</math> gerade
:<math>-g\cdot(x-x_0)+1\cdot(y-f(x_0))=0</math>
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 [[Trennungssatz]]es 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 [[Differenzierbarkeit|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>{{Internetquelle |autor=Yaron Singer |url=https://people.seas.harvard.edu/~yaron/AM221-S16/sections/sec6.pdf |titel=Advanced Optimzation |abruf=2022-01-27 |zitat=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>{{Literatur |Autor=R. T. Rockafellar |Titel=Convex Analysis |Band=28 |Datum=1970 |Zitat=Theorem 25.1}}</ref>

== Literatur ==
<references />

[[Kategorie:Analysis]]
[[Kategorie:Konvexe Optimierung]]

Subdifferential - Versionsgeschichte

imported>일성김: /* Definition */