Danskin's theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 by J. M. Danskin, given in his 1967, monograph "The Theory of Max-Min and its Applications to Weapons Allocation Problems," Springer, NY, provides a formula for the directional derivative of the maximum of a (not necessarily convex) directionally differentiable function. When adapted to the case of a convex function, this formula yields the following theorem given in somewhat more general form as Proposition A.22 in the 1971 Ph.D. Thesis by D. P. Bertsekas, "Control of Uncertain Systems with a Set-Membership Description of the Uncertainty". A proof of the following version can be found in the 1999 book "Nonlinear Programming" by Bertsekas (Section B.5).

Statement[edit]

The theorem applies to the following situation. Suppose is a continuous function of two arguments,

where is a compact set. Further assume that is convex in for every .

Under these conditions, Danskin's theorem provides conclusions regarding the 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.
Directional derivatives
The directional derivative 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
Subdifferential
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

The 1971 Ph.D. Thesis by Bertsekas [1] (Proposition A.22) 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]

  • Danskin, John M. (1967). The Theory of Max-Min and its Applications to Weapons Allocation Problems. NY: Springer.
  • Bertsekas, Dimitri P. (1971). Control of Uncertain Systems with a Set-Membership Description of Uncertainty. Cambridge, MA: PhD Thesis, MIT.
  • Bertsekas, Dimitri P. (1999). Nonlinear Programming. Belmont, MA: Athena Scientific. p. 737. ISBN 1-886529-00-0.