Danskin's theorem

Summary

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
 

Example of no directional derivative edit

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.