Danskin's theorem

Template:Short description In convex analysis, Danskin's theorem is a theorem which provides information about the derivatives of a function of the form $$f(x)=\underset{z\in Z}{max}\varphi (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 $\varphi (x,z)$ is a continuous function of two arguments, $$\varphi :{ℝ}^n\times Z\to ℝ$$where $Z\subset {ℝ}^m$ is a compact set.

Under these conditions, Danskin's theorem provides conclusions regarding the convexity and differentiability of the function $$f(x)=\underset{z\in Z}{max}\varphi (x,z).$$To state these results, we define the set of maximizing points $Z_0(x)$ as $$Z_0(x)=\arg \underset{z\in Z}{max}\varphi (x,z)=\{\bar{z}:\varphi (x,\bar{z})=\underset{z\in Z}{max}\varphi (x,z)\}.$$Danskin's theorem then provides the following results.

Convexity

If $\varphi (x,z)$ is convex in $x$ for every $z\in Z$, then $f(x)$ is convex in $x$ (this extends the known fact that the maximum of finitely many convex functions is convex).

Derivative

If $Z_0(x)$ consists of a single element $\bar{z}$, then $f(x)$ is differentiable at $x$, and its derivative (or gradient if $x$ is a vector) equals the derivative of $\varphi (x,z)$ at the unique arg-max:$$\frac{\partial f}{\partial x}=\frac{\partial \varphi (x,\bar{z})}{\partial x}.$$

Directional semi-derivative

If $Z_0(x)$ contains more than one element, then $f(x)$ is not differentiable at $x$, but it has a semi-differential. The semi-differential of $f(x)$ in the direction $y$, denoted ${\partial }_{y}f(x),$ is the maximum of different derivatives over all z:$${\partial }_{y}f(x)=\underset{z\in Z_0(x)}{max}{\varphi }^{\prime }(x,z;y),$$ where ${\varphi }^{\prime }(x,z;y)$ is the directional derivative of the function $\varphi (\cdot ,z)$ at $x$ in the direction $y.$

Example of no directional derivative

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

Subdifferential

If $\varphi (x,z)$ is differentiable with respect to $x$ for all $z\in Z,$ and if $\partial \varphi /\partial x$ is continuous with respect to $z$ for all $x$, then the subdifferential of $f(x)$ is given by $$\partial f(x)=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\{\frac{\partial \varphi (x,z)}{\partial x}:z\in Z_0(x)\}$$ where $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}$ 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 $\varphi (\cdot ,z)$ is differentiable. Instead it assumes that $\varphi (\cdot ,z)$ is an extended real-valued closed proper convex function for each $z$ in the compact set $Z,$ that $\mathrm{int}(\mathrm{dom}(f)),$ the interior of the effective domain of $f,$ is nonempty, and that $\varphi$ is continuous on the set $\mathrm{int}(\mathrm{dom}(f))\times Z.$ Then for all $x$ in $\mathrm{int}(\mathrm{dom}(f)),$ the subdifferential of $f$ at $x$ is given by $$\partial f(x)=\mathrm{conv}\{\partial \varphi (x,z):z\in Z_0(x)\}$$ where $\partial \varphi (x,z)$ is the subdifferential of $\varphi (\cdot ,z)$ at $x$ for any $z$ in $Z.$

See also

• Maximum theorem
• Envelope theorem
• Hotelling's lemma