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 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). 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. 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 ) = arg max z ∈ Z ϕ ( x , z ) = { z ¯ : ϕ ( x , z ¯ ) = max z ∈ Z ϕ ( x , z ) } . {\displaystyle Z_{0}(x)=\arg \max _{z\in Z}\phi (x,z)=\left\{{\overline {z}}:\phi (x,{\overline {z}})=\max _{z\in Z}\phi (x,z)\right\}.} Danskin's theorem then provides the following results.
Convexity If ϕ ( x , z ) {\displaystyle \phi (x,z)} is convex in x {\displaystyle x} for every z ∈ Z {\displaystyle z\in Z} , then f ( x ) {\displaystyle f(x)} is convex in x {\displaystyle x} (this extends the known fact that the maximum of finitely many convex functions is convex).
Derivative If Z 0 ( x ) {\displaystyle Z_{0}(x)} consists of a single element z ¯ {\displaystyle {\overline {z}}} , then f ( x ) {\displaystyle f(x)} is differentiable at x {\displaystyle x} , and its derivative (or gradient if x {\displaystyle x} is a vector) equals the derivative of ϕ ( x , z ) {\displaystyle \phi (x,z)} at the unique arg-max: ∂ f ∂ x = ∂ ϕ ( x , z ¯ ) ∂ x . {\displaystyle {\frac {\partial f}{\partial x}}={\frac {\partial \phi (x,{\overline {z}})}{\partial x}}.}
Directional semi-derivative If Z 0 ( x ) {\displaystyle Z_{0}(x)} contains more than one element, then f ( x ) {\displaystyle f(x)} is not differentiable at x {\displaystyle x} , but it has a semi-differential. The semi-differential of f ( x ) {\displaystyle f(x)} in the direction y {\displaystyle y} , denoted ∂ y f ( x ) , {\displaystyle \partial _{y}\ f(x),} is the maximum of different derivatives over all z: ∂ y f ( x ) = max z ∈ Z 0 ( x ) ϕ ′ ( x , z ; y ) , {\displaystyle \partial _{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.}
Example of no directional derivative In the statement of Danskin, it is important to conclude semi-differentiability of f {\displaystyle f} and not directional-derivative as explains this simple example. Set Z = { − 1 , + 1 } , ϕ ( x , z ) = z x {\displaystyle Z=\{-1,+1\},\ \phi (x,z)=zx} , we get f ( x ) = | x | {\displaystyle f(x)=|x|} which is semi-differentiable with ∂ − f ( 0 ) = − 1 , ∂ + f ( 0 ) = + 1 {\displaystyle \partial _{-}f(0)=-1,\partial _{+}f(0)=+1} but has not a directional derivative at x = 0 {\displaystyle x=0} .
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 Dimitri P. Bertsekas (Proposition A.22) 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 Maximum theorem Envelope theorem Hotelling's lemma
References