Subdifferential


Subdifferential

Das Subdifferential ist eine Verallgemeinerung des Gradienten.

Inhaltsverzeichnis

Definition

Sei f:\mathbb{R}^n\rightarrow\mathbb{R}. Das Subdifferential von f im Punkt \bar x ist gegeben durch:

\partial f(\bar x)=\{g\in\mathbb{R}^n:f(x)-f(\bar x)\geq g^{T}(x-\bar x) für alle x\in\mathbb{R}^n\}

Die Elemente g\in\partial f(\bar x) heißen Subgradient.

Beispiel

Subgradienten einer konvexen Funktion

Das Subdifferential von der Funktion f:\mathbb{R}\rightarrow\mathbb{R}:x\mapsto|x| ist gegeben durch:

\partial f(\bar x)=\begin{cases}\{-1\} & \bar x<0\\
\left[-1,1\right] & \bar x=0\\ \{1\} & \bar x>0\end{cases}

Beschränktheit

Sei f:\mathbb{R}^n\rightarrow\mathbb{R} stetig und sei X\subset\mathbb{R}^n beschränkt. Dann ist die Menge \bigcup_{\bar x\in X}\partial f(\bar x) beschränkt.

Beweis

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_{\bar x\in X}\partial f(\bar x) ist nicht beschränkt, dann gibt es für R: = 2ε ein \bar x\in X und ein g\in\partial f(\bar x) mit \|g\|_2>R=2\varepsilon. Sei x:=\frac{1}{\|g\|_2} g+\bar x. Somit sind \bar x,x\in\overline{U_1(X)}. Wir erhalten die Abschätzung

g^T(x-\bar x)=\frac{1}{\|g\|_2}g^T g=\|g\|_2 > 2\varepsilon\geq\left|f(x)-f(\bar x)\right|\geq f(x)-f(\bar x) .

g ist also kein Subgradient. Das ist ein Widerspruch.

\Box

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Subderivative — In mathematics, the concepts of subderivative, subgradient, and subdifferential arise in convex analysis, that is, in the study of convex functions, often in connection to convex optimization. Let f : I →R be a real valued convex function defined …   Wikipedia

  • Jensen's inequality — In mathematics, Jensen s inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906 [Jensen, J. Sur les fonctions… …   Wikipedia

  • Subgradient — Das Subdifferential ist eine Verallgemeinerung des Gradienten. Für eine Funktion ist das Subdifferential im Punkt gegeben durch für alle Die Elemente heißen …   Deutsch Wikipedia

  • Danskin's theorem — In convex analysis, Danskin s theorem is a theorem which provides information about the derivatives of a function of the form The theorem has applications in optimization, where it sometimes is used to solve minimax problems. Statement The… …   Wikipedia

  • List of convexity topics — This is a list of convexity topics, by Wikipedia page. Alpha blending Barycentric coordinates Borsuk s conjecture Bond convexity Carathéodory s theorem (convex hull) Choquet theory Closed convex function Concavity Convex analysis Convex… …   Wikipedia

  • Viscosity solution — In mathematics, the viscosity solution concept was introduced in the early 1980s by Pierre Louis Lions and Michael Crandall as a generalization of the classical concept of what is meant by a solution to a partial differential equation (PDE). It… …   Wikipedia

  • Subgradient method — Subgradient methods are algorithms for solving convex optimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods can be used with a non differentiable objective function. When the objective… …   Wikipedia