Subdifferential

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Sei  f:\mathbb{R}^n\to\mathbb{R} eine konvexe Funktion. Ein Vektor g\in\R^n heißt Subgradient von f an der Stelle x_0, wenn für alle x\in\R^n gilt[1]

 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.[2]

Anschauung[Bearbeiten]

Subgradienten einer konvexen Funktion

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\R^2|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\R^2

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

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

Beispiel[Bearbeiten]

Das Subdifferential der Funktion f:\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[Bearbeiten]

Sei f:\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[Bearbeiten]

Sei f:\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\,|\,{\rm dist}(x,X)\leq1\}. 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.

\Box

Literatur[Bearbeiten]

  1. R. T. Rockafellar Convex analysis 1970., p.214
  2. R. T. Rockafellar Convex analysis 1970., p.215