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

f (x) \geq f (x_{0}) + ⟨ g, x - x_{0} ⟩

,

wobei $⟨ \cdot, \cdot ⟩$ das Standardskalarprodukt bezeichnet.

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

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

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

Anschauung

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 ℝ^{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 ℝ^{2}$ .

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

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

Beispiel

Das Subdifferential der Funktion $f : ℝ \to ℝ$ , $x \mapsto | x |$ ist gegeben durch:

\partial f (x_{0}) = {\begin{matrix} {- 1} & x_{0} < 0 \\ [- 1, 1] & x_{0} = 0 \\ {1} & x_{0} > 0 \end{matrix}

Eine ähnliche Eigenschaft ist bei der Lasso-Regression für die Herleitung der Soft-Threshold-Funktion wichtig.

Beschränktheit

Sei $f : ℝ^{n} \to ℝ$ stetig und sei $X \subset ℝ^{n}$ beschränkt. Dann ist die Menge $⋃_{x_{0} \in X} \partial f (x_{0})$ beschränkt.

Beweis

Sei $f : ℝ^{n} \to ℝ$ stetig und sei $X \subset ℝ^{n}$ beschränkt. Setze $ε := sup | f (\overline{U_{1} (X)}) |$ wobei $\overline{U_{1} (X)} = {x \in ℝ^{n} ∣ d i s t (x, X) \leq 1}$ . Angenommen, $⋃_{x_{0} \in X} \partial f (x_{0})$ ist nicht beschränkt, dann gibt es für $R := 2 ε$ ein $x_{0} \in X$ und ein $g \in \partial f (x_{0})$ mit $‖ g ‖_{2} > R = 2 ε$ . 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 ε \geq | f (x) - f (x_{0}) | \geq f (x) - f (x_{0})

.

$g$ ist also kein Subgradient. Das ist ein Widerspruch.

Differenzierbarkeit

Ist die Funktion differenzierbar in $x_{0} \in i n t d o m f$ , so gilt:

\partial f (x_{0}) = {\nabla f (x_{0})}

Siehe ^[3] für einen Beweis.

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

Literatur

↑ R. T. Rockafellar Convex analysis 1970., p.214
↑ R. T. Rockafellar Convex analysis 1970., p.215
↑ Yaron Singer: Advanced Optimzation. Abgerufen am 27. Januar 2022: „Proposition 4“
↑ R. T. Rockafellar: Convex Analysis. Band 28, 1970: „Theorem 25.1“

[1] R. T. Rockafellar Convex analysis 1970., p.214

[2] R. T. Rockafellar Convex analysis 1970., p.215

[3] Yaron Singer: Advanced Optimzation. Abgerufen am 27. Januar 2022: „Proposition 4“

[4] R. T. Rockafellar: Convex Analysis. Band 28, 1970: „Theorem 25.1“

[1]

[2]

[3]

[4]