In convex analysis , Danskin's theorem is a theorem which provides information about the derivatives of a function of the form
f
(
x
)
=
max
z
∈
Z
ϕ
(
x
,
z
)
.
{\displaystyle f(x)=\max _{z\in Z}\phi (x,z).}
The theorem has applications in optimization , where it sometimes is used to solve minimax problems. The original theorem given by J. M. Danskin in his 1967 monograph [1] provides a formula for the directional derivative of the maximum of a (not necessarily convex) directionally differentiable function.
An extension to more general conditions was proven 1971 by Dimitri Bertsekas.
Statement [ ]
The following version is proven in "Nonlinear programming" (1991).[2] Suppose
ϕ
(
x
,
z
)
{\displaystyle \phi (x,z)}
is a continuous function of two arguments,
ϕ
:
R
n
×
Z
→
R
{\displaystyle \phi :\mathbb {R} ^{n}\times Z\to \mathbb {R} }
where
Z
⊂
R
m
{\displaystyle Z\subset \mathbb {R} ^{m}}
is a
compact set . Further assume that
ϕ
(
x
,
z
)
{\displaystyle \phi (x,z)}
is
convex in
x
{\displaystyle x}
for every
z
∈
Z
.
{\displaystyle z\in Z.}
Under these conditions, Danskin's theorem provides conclusions regarding the convexity and differentiability of the function
f
(
x
)
=
max
z
∈
Z
ϕ
(
x
,
z
)
.
{\displaystyle f(x)=\max _{z\in Z}\phi (x,z).}
To state these results, we define the set of maximizing points
Z
0
(
x
)
{\displaystyle Z_{0}(x)}
as
Z
0
(
x
)
=
{
z
¯
:
ϕ
(
x
,
z
¯
)
=
max
z
∈
Z
ϕ
(
x
,
z
)
}
.
{\displaystyle Z_{0}(x)=\left\{{\overline {z}}:\phi (x,{\overline {z}})=\max _{z\in Z}\phi (x,z)\right\}.}
Danskin's theorem then provides the following results.
Convexity
f
(
x
)
{\displaystyle f(x)}
is convex .
Directional derivatives
The directional derivative of
f
(
x
)
{\displaystyle f(x)}
in the direction
y
{\displaystyle y}
, denoted
D
y
f
(
x
)
,
{\displaystyle D_{y}\ f(x),}
is given by
D
y
f
(
x
)
=
max
z
∈
Z
0
(
x
)
ϕ
′
(
x
,
z
;
y
)
,
{\displaystyle D_{y}f(x)=\max _{z\in Z_{0}(x)}\phi '(x,z;y),}
where
ϕ
′
(
x
,
z
;
y
)
{\displaystyle \phi '(x,z;y)}
is the directional derivative of the function
ϕ
(
⋅
,
z
)
{\displaystyle \phi (\cdot ,z)}
at
x
{\displaystyle x}
in the direction
y
.
{\displaystyle y.}
Derivative
f
(
x
)
{\displaystyle f(x)}
is differentiable at
x
{\displaystyle x}
if
Z
0
(
x
)
{\displaystyle Z_{0}(x)}
consists of a single element
z
¯
{\displaystyle {\overline {z}}}
. In this case, the derivative of
f
(
x
)
{\displaystyle f(x)}
(or the gradient of
f
(
x
)
{\displaystyle f(x)}
if
x
{\displaystyle x}
is a vector) is given by
∂
f
∂
x
=
∂
ϕ
(
x
,
z
¯
)
∂
x
.
{\displaystyle {\frac {\partial f}{\partial x}}={\frac {\partial \phi (x,{\overline {z}})}{\partial x}}.}
Subdifferential
If
ϕ
(
x
,
z
)
{\displaystyle \phi (x,z)}
is differentiable with respect to
x
{\displaystyle x}
for all
z
∈
Z
,
{\displaystyle z\in Z,}
and if
∂
ϕ
/
∂
x
{\displaystyle \partial \phi /\partial x}
is continuous with respect to
z
{\displaystyle z}
for all
x
{\displaystyle x}
, then the subdifferential of
f
(
x
)
{\displaystyle f(x)}
is given by
∂
f
(
x
)
=
c
o
n
v
{
∂
ϕ
(
x
,
z
)
∂
x
:
z
∈
Z
0
(
x
)
}
{\displaystyle \partial f(x)=\mathrm {conv} \left\{{\frac {\partial \phi (x,z)}{\partial x}}:z\in Z_{0}(x)\right\}}
where
c
o
n
v
{\displaystyle \mathrm {conv} }
indicates the convex hull operation.
Extension [ ]
The 1971 Ph.D. Thesis by Bertsekas (Proposition A.22) [3] proves a more general result, which does not require that
ϕ
(
⋅
,
z
)
{\displaystyle \phi (\cdot ,z)}
is differentiable. Instead it assumes that
ϕ
(
⋅
,
z
)
{\displaystyle \phi (\cdot ,z)}
is an extended real-valued closed proper convex function for each
z
{\displaystyle z}
in the compact set
Z
,
{\displaystyle Z,}
that
int
(
dom
(
f
)
)
,
{\displaystyle \operatorname {int} (\operatorname {dom} (f)),}
the interior of the effective domain of
f
,
{\displaystyle f,}
is nonempty, and that
ϕ
{\displaystyle \phi }
is continuous on the set
int
(
dom
(
f
)
)
×
Z
.
{\displaystyle \operatorname {int} (\operatorname {dom} (f))\times Z.}
Then for all
x
{\displaystyle x}
in
int
(
dom
(
f
)
)
,
{\displaystyle \operatorname {int} (\operatorname {dom} (f)),}
the subdifferential of
f
{\displaystyle f}
at
x
{\displaystyle x}
is given by
∂
f
(
x
)
=
conv
{
∂
ϕ
(
x
,
z
)
:
z
∈
Z
0
(
x
)
}
{\displaystyle \partial f(x)=\operatorname {conv} \left\{\partial \phi (x,z):z\in Z_{0}(x)\right\}}
where
∂
ϕ
(
x
,
z
)
{\displaystyle \partial \phi (x,z)}
is the subdifferential of
ϕ
(
⋅
,
z
)
{\displaystyle \phi (\cdot ,z)}
at
x
{\displaystyle x}
for any
z
{\displaystyle z}
in
Z
.
{\displaystyle Z.}
See also [ ]
References [ ]
Topics (list) Maps Main results (list) Sets Series
Convex series related ((cs, lcs)-closed , (cs, bcs)-complete , (lower) ideally convex , (Hx ) , and (Hwx ) )
Duality