Jump to content

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

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.

Statement

[edit]

The following version is proven in "Nonlinear programming" (1991).[2] Suppose is a continuous function of two arguments, where is a compact set.

Under these conditions, Danskin's theorem provides conclusions regarding the convexity and differentiability of the function To state these results, we define the set of maximizing points as

Danskin's theorem then provides the following results.

Convexity
is convex if is convex in for every .
Directional semi-differential
The semi-differential of in the direction , denoted is given by where is the directional derivative of the function at in the direction
Derivative
is differentiable at if consists of a single element . In this case, the derivative of (or the gradient of if is a vector) is given by

In the statement of Danskin, it is important to conclude semi-differentiability of and not directional-derivative as explains this simple example. Set , we get which is semi-differentiable with but has not a directional derivative at .

Subdifferential

[edit]
If is differentiable with respect to for all and if is continuous with respect to for all , then the subdifferential of is given by where indicates the convex hull operation.

Extension

[edit]

The 1971 Ph.D. Thesis by Dimitri P. Bertsekas (Proposition A.22) [3] proves a more general result, which does not require that is differentiable. Instead it assumes that is an extended real-valued closed proper convex function for each in the compact set that the interior of the effective domain of is nonempty, and that is continuous on the set Then for all in the subdifferential of at is given by where is the subdifferential of at for any in

See also

[edit]

References

[edit]
  1. ^ Danskin, John M. (1967). The theory of Max-Min and its application to weapons allocation problems. New York: Springer.
  2. ^ Bertsekas, Dimitri P. (1999). Nonlinear programming (Second ed.). Belmont, Massachusetts. ISBN 1-886529-00-0.{{cite book}}: CS1 maint: location missing publisher (link)
  3. ^ Bertsekas, Dimitri P. (1971). Control of Uncertain Systems with a Set-Membership Description of Uncertainty (PDF) (PhD). Cambridge, MA: MIT.