Danskin's theorem
In convex analysis, Danskin's theorem is a theorem which provides information about the derivatives of a function of the form [math]\displaystyle{ f(x) = \max_{z \in Z} \phi(x,z). }[/math]
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
The following version is proven in "Nonlinear programming" (1991).[2] Suppose [math]\displaystyle{ \phi(x,z) }[/math] is a continuous function of two arguments, [math]\displaystyle{ \phi : \R^n \times Z \to \R }[/math] where [math]\displaystyle{ Z \subset \R^m }[/math] is a compact set.
Under these conditions, Danskin's theorem provides conclusions regarding the convexity and differentiability of the function [math]\displaystyle{ f(x) = \max_{z \in Z} \phi(x,z). }[/math] To state these results, we define the set of maximizing points [math]\displaystyle{ Z_0(x) }[/math] as [math]\displaystyle{ Z_0(x) = \left\{\overline{z} : \phi(x,\overline{z}) = \max_{z \in Z} \phi(x,z)\right\}. }[/math]
Danskin's theorem then provides the following results.
- Convexity
- [math]\displaystyle{ f(x) }[/math] is convex if [math]\displaystyle{ \phi(x,z) }[/math] is convex in [math]\displaystyle{ x }[/math] for every [math]\displaystyle{ z \in Z }[/math].
- Directional semi-differential
- The semi-differential of [math]\displaystyle{ f(x) }[/math] in the direction [math]\displaystyle{ y }[/math], denoted [math]\displaystyle{ \partial_y\ f(x), }[/math] is given by [math]\displaystyle{ \partial_y f(x) = \max_{z \in Z_0(x)} \phi'(x,z;y), }[/math] where [math]\displaystyle{ \phi'(x,z;y) }[/math] is the directional derivative of the function [math]\displaystyle{ \phi(\cdot,z) }[/math] at [math]\displaystyle{ x }[/math] in the direction [math]\displaystyle{ y. }[/math]
- Derivative
- [math]\displaystyle{ f(x) }[/math] is differentiable at [math]\displaystyle{ x }[/math] if [math]\displaystyle{ Z_0(x) }[/math] consists of a single element [math]\displaystyle{ \overline{z} }[/math]. In this case, the derivative of [math]\displaystyle{ f(x) }[/math] (or the gradient of [math]\displaystyle{ f(x) }[/math] if [math]\displaystyle{ x }[/math] is a vector) is given by [math]\displaystyle{ \frac{\partial f}{\partial x} = \frac{\partial \phi(x,\overline{z})}{\partial x}. }[/math]
Example of no directional derivative
In the statement of Danskin, it is important to conclude semi-differentiability of [math]\displaystyle{ f }[/math] and not directional-derivative as explains this simple example. Set [math]\displaystyle{ Z=\{-1,+1\},\ \phi(x,z)= zx }[/math], we get [math]\displaystyle{ f(x)=|x| }[/math] which is semi-differentiable with [math]\displaystyle{ \partial_-f(0)=-1, \partial_+f(0)=+1 }[/math] but has not a directional derivative at [math]\displaystyle{ x=0 }[/math].
Subdifferential
- If [math]\displaystyle{ \phi(x,z) }[/math] is differentiable with respect to [math]\displaystyle{ x }[/math] for all [math]\displaystyle{ z \in Z, }[/math] and if [math]\displaystyle{ \partial \phi/\partial x }[/math] is continuous with respect to [math]\displaystyle{ z }[/math] for all [math]\displaystyle{ x }[/math], then the subdifferential of [math]\displaystyle{ f(x) }[/math] is given by [math]\displaystyle{ \partial f(x) = \mathrm{conv} \left\{\frac{\partial \phi(x,z)}{\partial x} : z \in Z_0(x)\right\} }[/math] where [math]\displaystyle{ \mathrm{conv} }[/math] indicates the convex hull operation.
Extension
The 1971 Ph.D. Thesis by Dimitri P. Bertsekas (Proposition A.22) [3] proves a more general result, which does not require that [math]\displaystyle{ \phi(\cdot,z) }[/math] is differentiable. Instead it assumes that [math]\displaystyle{ \phi(\cdot,z) }[/math] is an extended real-valued closed proper convex function for each [math]\displaystyle{ z }[/math] in the compact set [math]\displaystyle{ Z, }[/math] that [math]\displaystyle{ \operatorname{int}(\operatorname{dom}(f)), }[/math] the interior of the effective domain of [math]\displaystyle{ f, }[/math] is nonempty, and that [math]\displaystyle{ \phi }[/math] is continuous on the set [math]\displaystyle{ \operatorname{int}(\operatorname{dom}(f)) \times Z. }[/math] Then for all [math]\displaystyle{ x }[/math] in [math]\displaystyle{ \operatorname{int}(\operatorname{dom}(f)), }[/math] the subdifferential of [math]\displaystyle{ f }[/math] at [math]\displaystyle{ x }[/math] is given by [math]\displaystyle{ \partial f(x) = \operatorname{conv} \left\{\partial \phi(x,z) : z \in Z_0(x)\right\} }[/math] where [math]\displaystyle{ \partial \phi(x,z) }[/math] is the subdifferential of [math]\displaystyle{ \phi(\cdot,z) }[/math] at [math]\displaystyle{ x }[/math] for any [math]\displaystyle{ z }[/math] in [math]\displaystyle{ Z. }[/math]
See also
References
- ↑ Danskin, John M. (1967). The theory of Max-Min and its application to weapons allocation problems. New York: Springer.
- ↑ Bertsekas, Dimitri P. (1999). Nonlinear programming (Second ed.). Belmont, Massachusetts. ISBN 1-886529-00-0.
- ↑ Bertsekas, Dimitri P. (1971). Control of Uncertain Systems with a Set-Membership Description of Uncertainty (PDF) (PhD). Cambridge, MA: MIT.
 |  |
