Danskin's theorem

From Wikipedia, the free encyclopedia

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.

[edit] 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 Z0(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 Z0(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.

[edit] References

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