Danskin's theorem

In convex analysis, Danskin's theorem is a theorem which provides information about the derivatives of a function of the form $${\displaystyle f(x)=\max _{z\in Z}\phi (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.

The following version is proven in "Nonlinear programming" (1991).^[2] Suppose ${\displaystyle \phi (x,z)}${\displaystyle \phi (x,z)} is a continuous function of two arguments, $${\displaystyle \phi :\mathbb {R} ^{n}\times Z\to \mathbb {R} }$${\displaystyle \phi :\mathbb {R} ^{n}\times Z\to \mathbb {R} } where ${\displaystyle Z\subset \mathbb {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 $${\displaystyle f(x)=\max _{z\in Z}\phi (x,z).}$${\displaystyle f(x)=\max _{z\in Z}\phi (x,z).} To state these results, we define the set of maximizing points ${\displaystyle Z_{0}(x)}${\displaystyle Z_{0}(x)} as $${\displaystyle Z_{0}(x)=\left\{{\overline {z}}:\phi (x,{\overline {z}})=\max _{z\in Z}\phi (x,z)\right\}.}$${\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

${\displaystyle f(x)}${\displaystyle f(x)} is convex if ${\displaystyle \phi (x,z)}${\displaystyle \phi (x,z)} is convex in ${\displaystyle x}${\displaystyle x} for every ${\displaystyle z\in Z}${\displaystyle z\in Z}.

Directional semi-differential

The semi-differential of ${\displaystyle f(x)}${\displaystyle f(x)} in the direction ${\displaystyle y}${\displaystyle y}, denoted ${\displaystyle \partial _{y}\ f(x),}${\displaystyle \partial _{y}\ f(x),} is given by $${\displaystyle \partial _{y}f(x)=\max _{z\in Z_{0}(x)}\phi '(x,z;y),}$${\displaystyle \partial _{y}f(x)=\max _{z\in Z_{0}(x)}\phi '(x,z;y),} where ${\displaystyle \phi '(x,z;y)}${\displaystyle \phi '(x,z;y)} is the directional derivative of the function ${\displaystyle \phi (\cdot ,z)}${\displaystyle \phi (\cdot ,z)} at ${\displaystyle x}${\displaystyle x} in the direction ${\displaystyle y.}${\displaystyle y.}

Derivative

${\displaystyle f(x)}${\displaystyle f(x)} is differentiable at ${\displaystyle x}${\displaystyle x} if ${\displaystyle Z_{0}(x)}${\displaystyle Z_{0}(x)} consists of a single element ${\displaystyle {\overline {z}}}${\displaystyle {\overline {z}}}. In this case, the derivative of ${\displaystyle f(x)}${\displaystyle f(x)} (or the gradient of ${\displaystyle f(x)}${\displaystyle f(x)} if ${\displaystyle x}${\displaystyle x} is a vector) is given by $${\displaystyle {\frac {\partial f}{\partial x}}={\frac {\partial \phi (x,{\overline {z}})}{\partial x}}.}$${\displaystyle {\frac {\partial f}{\partial x}}={\frac {\partial \phi (x,{\overline {z}})}{\partial x}}.}

In the statement of Danskin, it is important to conclude semi-differentiability of ${\displaystyle f}${\displaystyle f} and not directional-derivative as explains this simple example. Set ${\displaystyle Z=\{-1,+1\},\ \phi (x,z)=zx}${\displaystyle Z=\{-1,+1\},\ \phi (x,z)=zx}, we get ${\displaystyle f(x)=|x|}${\displaystyle f(x)=|x|} which is semi-differentiable with ${\displaystyle \partial _{-}f(0)=-1,\partial _{+}f(0)=+1}${\displaystyle \partial _{-}f(0)=-1,\partial _{+}f(0)=+1} but has not a directional derivative at ${\displaystyle x=0}${\displaystyle x=0}.

If ${\displaystyle \phi (x,z)}${\displaystyle \phi (x,z)} is differentiable with respect to ${\displaystyle x}${\displaystyle x} for all ${\displaystyle z\in Z,}${\displaystyle z\in Z,} and if ${\displaystyle \partial \phi /\partial x}${\displaystyle \partial \phi /\partial x} is continuous with respect to ${\displaystyle z}${\displaystyle z} for all ${\displaystyle x}${\displaystyle x}, then the subdifferential of ${\displaystyle f(x)}${\displaystyle f(x)} is given by $${\displaystyle \partial f(x)=\mathrm {conv} \left\{{\frac {\partial \phi (x,z)}{\partial x}}:z\in Z_{0}(x)\right\}}$${\displaystyle \partial f(x)=\mathrm {conv} \left\{{\frac {\partial \phi (x,z)}{\partial x}}:z\in Z_{0}(x)\right\}} where ${\displaystyle \mathrm {conv} }${\displaystyle \mathrm {conv} } indicates the convex hull operation.

The 1971 Ph.D. Thesis by Dimitri P. Bertsekas (Proposition A.22) ^[3] proves a more general result, which does not require that ${\displaystyle \phi (\cdot ,z)}${\displaystyle \phi (\cdot ,z)} is differentiable. Instead it assumes that ${\displaystyle \phi (\cdot ,z)}${\displaystyle \phi (\cdot ,z)} is an extended real-valued closed proper convex function for each ${\displaystyle z}${\displaystyle z} in the compact set ${\displaystyle Z,}${\displaystyle Z,} that ${\displaystyle \operatorname {int} (\operatorname {dom} (f)),}${\displaystyle \operatorname {int} (\operatorname {dom} (f)),} the interior of the effective domain of ${\displaystyle f,}${\displaystyle f,} is nonempty, and that ${\displaystyle \phi }${\displaystyle \phi } is continuous on the set ${\displaystyle \operatorname {int} (\operatorname {dom} (f))\times Z.}${\displaystyle \operatorname {int} (\operatorname {dom} (f))\times Z.} Then for all ${\displaystyle x}${\displaystyle x} in ${\displaystyle \operatorname {int} (\operatorname {dom} (f)),}${\displaystyle \operatorname {int} (\operatorname {dom} (f)),} the subdifferential of ${\displaystyle f}${\displaystyle f} at ${\displaystyle x}${\displaystyle x} is given by $${\displaystyle \partial f(x)=\operatorname {conv} \left\{\partial \phi (x,z):z\in Z_{0}(x)\right\}}$${\displaystyle \partial f(x)=\operatorname {conv} \left\{\partial \phi (x,z):z\in Z_{0}(x)\right\}} where ${\displaystyle \partial \phi (x,z)}${\displaystyle \partial \phi (x,z)} is the subdifferential of ${\displaystyle \phi (\cdot ,z)}${\displaystyle \phi (\cdot ,z)} at ${\displaystyle x}${\displaystyle x} for any ${\displaystyle z}${\displaystyle z} in ${\displaystyle Z.}${\displaystyle Z.}

• Maximum theorem
• Envelope theorem
• Hotelling's lemma

• Convex optimization
• Theorems in analysis

• CS1 maint: location missing publisher