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.
Sei
f
:
R
n
→
R
{\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} }
eine konvexe Funktion. Ein Vektor
g
∈
R
n
{\displaystyle g\in \mathbb {R} ^{n}}
heißt Subgradient von
f
{\displaystyle f}
an der Stelle
x
0
{\displaystyle x_{0}}
, wenn für alle
x
∈
R
n
{\displaystyle x\in \mathbb {R} ^{n}}
gilt[1]
f
(
x
)
≥
f
(
x
0
)
+
⟨
g
,
x
−
x
0
⟩
{\displaystyle f(x)\geq f(x_{0})+\langle g,x-x_{0}\rangle }
,
wobei
⟨
⋅
,
⋅
⟩
{\displaystyle \langle \cdot ,\cdot \rangle }
das Standardskalarprodukt bezeichnet.
Das Subdifferential
∂
f
(
x
0
)
{\displaystyle \partial f(x_{0})}
ist die Menge aller Subgradienten von
f
{\displaystyle f}
im Punkt
x
0
{\displaystyle x_{0}}
.[2]
Existieren die folgenden Grenzwerte
a
=
lim
x
→
x
0
−
f
(
x
)
−
f
(
x
0
)
x
−
x
0
,
{\displaystyle a=\lim _{x\to x_{0}^{-}}{\frac {f(x)-f(x_{0})}{x-x_{0}}},}
b
=
lim
x
→
x
0
+
f
(
x
)
−
f
(
x
0
)
x
−
x
0
,
{\displaystyle b=\lim _{x\to x_{0}^{+}}{\frac {f(x)-f(x_{0})}{x-x_{0}}},}
so wird das Intervall
[
a
,
b
]
{\displaystyle [a,b]}
aller Subgradienten das Subdifferential der Funktion
f
{\displaystyle f}
bei
x
0
{\displaystyle x_{0}}
genannt und wird als
∂
f
(
x
0
)
:=
[
a
,
b
]
{\displaystyle \partial f(x_{0}):=[a,b]}
geschrieben.
Für eine konvexe Funktion gilt
a
≤
b
{\displaystyle a\leq b}
, für eine nicht konvexe Funktion braucht dies nicht zu gelten und dann ist
∂
f
(
x
0
)
=
∅
{\displaystyle \partial f(x_{0})=\emptyset }
.
Intuitiv bedeutet diese Definition für
n
=
1
{\displaystyle n=1}
, dass der Graph der Funktion
f
{\displaystyle f}
überall über der Geraden
G
{\displaystyle G}
liegt, die durch den Punkt
(
x
0
,
f
(
x
0
)
)
{\displaystyle (x_{0},f(x_{0}))}
geht und die Steigung
g
{\displaystyle g}
besitzt:
G
=
{
(
x
,
y
)
∈
R
2
∣
y
=
g
⋅
(
x
−
x
0
)
+
f
(
x
0
)
}
{\displaystyle G=\{(x,y)\in \mathbb {R} ^{2}\mid y=g\cdot (x-x_{0})+f(x_{0})\}}
−
g
⋅
(
x
−
x
0
)
+
1
⋅
(
y
−
f
(
x
0
)
)
=
0
{\displaystyle -g\cdot (x-x_{0})+1\cdot (y-f(x_{0}))=0}
ist, ist die Normale an
G
{\displaystyle G}
also
(
−
g
,
1
)
∈
R
2
{\displaystyle (-g,1)\in \mathbb {R} ^{2}}
.
Im allgemeinen Fall
n
≥
1
{\displaystyle n\geq 1}
liegt
f
{\displaystyle f}
über der Hyperebene, die durch den Fußpunkt
(
x
0
,
f
(
x
0
)
)
{\displaystyle (x_{0},f(x_{0}))}
und die Normale
(
−
g
,
1
)
∈
R
n
+
1
{\displaystyle (-g,1)\in \mathbb {R} ^{n+1}}
gegeben ist.
Wegen des Trennungssatzes ist das Subdifferential einer stetigen konvexen Funktion überall nichtleer.
Das Subdifferential der Funktion
f
:
R
→
R
{\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {R} }
,
x
↦
|
x
|
{\displaystyle x\mapsto |x|}
ist gegeben durch:
∂
f
(
x
0
)
=
{
{
−
1
}
x
0
<
0
[
−
1
,
1
]
x
0
=
0
{
1
}
x
0
>
0
{\displaystyle \partial f(x_{0})={\begin{cases}\{-1\}&x_{0}<0\\\left[-1,1\right]&x_{0}=0\\\{1\}&x_{0}>0\end{cases}}}
Sei
f
:
R
n
→
R
{\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }
stetig und sei
X
⊂
R
n
{\displaystyle X\subset \mathbb {R} ^{n}}
beschränkt. Dann ist
die Menge
⋃
x
0
∈
X
∂
f
(
x
0
)
{\displaystyle \bigcup _{x_{0}\in X}\partial f(x_{0})}
beschränkt.
Sei
f
:
R
n
→
R
{\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }
stetig und sei
X
⊂
R
n
{\displaystyle X\subset \mathbb {R} ^{n}}
beschränkt. Setze
ε
:=
sup
|
f
(
U
1
(
X
)
¯
)
|
{\displaystyle \varepsilon :=\sup |f({\overline {U_{1}(X)}})|}
wobei
U
1
(
X
)
¯
=
{
x
∈
R
n
∣
d
i
s
t
(
x
,
X
)
≤
1
}
{\displaystyle {\overline {U_{1}(X)}}=\{x\in \mathbb {R} ^{n}\mid {\rm {dist}}(x,X)\leq 1\}}
.
Angenommen,
⋃
x
0
∈
X
∂
f
(
x
0
)
{\displaystyle \bigcup _{x_{0}\in X}\partial f(x_{0})}
ist nicht beschränkt, dann gibt es für
R
:=
2
ε
{\displaystyle R:=2\varepsilon }
ein
x
0
∈
X
{\displaystyle x_{0}\in X}
und ein
g
∈
∂
f
(
x
0
)
{\displaystyle g\in \partial f(x_{0})}
mit
‖
g
‖
2
>
R
=
2
ε
{\displaystyle \|g\|_{2}>R=2\varepsilon }
.
Sei
x
:=
1
‖
g
‖
2
g
+
x
0
{\displaystyle x:={\frac {1}{\|g\|_{2}}}g+x_{0}}
. Somit sind
x
0
,
x
∈
U
1
(
X
)
¯
{\displaystyle x_{0},x\in {\overline {U_{1}(X)}}}
. Wir erhalten die Abschätzung
g
T
(
x
−
x
0
)
=
1
‖
g
‖
2
g
T
g
=
‖
g
‖
2
>
2
ε
≥
|
f
(
x
)
−
f
(
x
0
)
|
≥
f
(
x
)
−
f
(
x
0
)
{\displaystyle 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
{\displaystyle g}
ist also kein Subgradient. Das ist ein Widerspruch.
Zudem gilt: Ist das Subdifferential
∂
f
(
x
0
)
{\displaystyle \partial f(x_{0})}
einelementig, so ist
f
{\displaystyle f}
an der Stelle
x
0
{\displaystyle x_{0}}
differenzierbar.[4]
![{\displaystyle [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c4b788fc5c637e26ee98b45f89a5c08c85f7935)
![{\displaystyle \partial f(x_{0}):=[a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eef8efa37ce03d6bfec0b3806cf42ed102c5ee31)
![{\displaystyle \partial f(x_{0})={\begin{cases}\{-1\}&x_{0}<0\\\left[-1,1\right]&x_{0}=0\\\{1\}&x_{0}>0\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a99132d53aa509f119f4213b458e1ec44ebce038)
