Danskin's theorem

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 \in Z} \phi(x,z).$

The theorem has applications in optimization, where it sometimes is used to solve minimax problems.

Statement

The theorem applies to the following situation. Suppose ϕ(x,z) is a continuous function of two arguments,

$\phi: {\mathbb R}^n \times Z \rightarrow {\mathbb R}$

where $Z \subset {\mathbb R}^m$ is a compact set. Further assume that ϕ(x,z) is convex in x for every $z \in Z$.

Under these conditions, Danskin's theorem provides conclusions regarding the differentiability of the function

$f(x) = \max_{z \in Z} \phi(x,z).$

To state these results, we define the set of maximizing points Z₀(x) as

$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) is convex.

Directional derivatives

The directional derivative of f(x) in the direction y, denoted $D_y\ f(x)$, is given by

$D_y f(x) = \max_{z \in Z_0(x)} \phi'(x,z;y),$

where ϕ'(x,z;y) is the directional derivative of the function $\phi(\cdot,z)$ at x in the direction y.

Derivative

f(x) is differentiable at x if Z₀(x) consists of a single element $\overline{z}$. In this case, the derivative of f(x) (or the gradient of f(x) if x is a vector) is given by

$\frac{\partial f}{\partial x} = \frac{\partial \phi(x,\overline{z})}{\partial x}.$

Subdifferential

If ϕ(x,z) is differentiable with respect to x for all $z \in Z$, and if $\partial \phi/\partial x$ is continuous with respect to z for all x, then the subdifferential of f(x) is given by

$\partial f(x) = \mathrm{conv} \left\{ \frac{\partial \phi(x,z)}{\partial x} : z \in Z_0(x) \right\}$

where conv indicates the convex hull operation.

References

• Bertsekas, Dimitri P. (1999). Nonlinear Programming. Belmont, MA: Athena Scientific. pp. 717. ISBN 1-886529-00-0.