Danskin's theorem

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. The original theorem given by J. M. Danskin in his 1967 monograph {{cite book |last1=Danskin |first1=John M. |title=The theory of Max-Min and its application to weapons allocation problems |date=1967 |publisher=Springer |location=New York}} 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).{{cite book |last1=Bertsekas |first1=Dimitri P. |title=Nonlinear programming |date=1999 |location=Belmont, Massachusetts |isbn=1-886529-00-0 |edition=Second}} Suppose $\phi(x,z)$ is a continuous function of two arguments,

$\phi : \R^n \times Z \to \R$

where $Z \subset \R^m$ is a compact set.

Under these conditions, Danskin's theorem provides conclusions regarding the convexity and differentiability of the function

$f(x) = \max_{z \in Z} \phi(x,z).$

To state these results, we define the set of maximizing points $Z_0(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 if $\phi(x,z)$ is convex in $x$ for every $z \in Z$ .

;Directional semi-differential

: The semi-differential of $f(x)$ in the direction $y$ , denoted $\partial_y\ f(x),$ is given by $\partial_y f(x) = \max_{z \in Z_0(x)} \phi'(x,z;y),$ where $\phi'(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 $Z_0(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}.$

= Example of no [[directional derivative]] =

In the statement of Danskin, it is important to conclude semi-differentiability of $f$ and not directional-derivative as explains this simple example.

Set $Z=\{-1,+1\},\ \phi(x,z)= zx$ , we get $f(x)=|x|$ which is semi-differentiable with $\partial_-f(0)=-1, \partial_+f(0)=+1$ but has not a directional derivative at $x=0$ .

= Subdifferential =

:If $\phi(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 $\mathrm{conv}$ indicates the convex hull operation.

Extension

The 1971 Ph.D. Thesis by Dimitri P. Bertsekas (Proposition A.22)

{{cite thesis

| last = Bertsekas

| first = Dimitri P.

| type = PhD

| title = Control of Uncertain Systems with a Set-Membership Description of Uncertainty

| publisher = MIT

| date = 1971

| location = Cambridge, MA

| url=http://web.mit.edu/dimitrib/www/phdthesis.pdf}}

proves a more general result, which does not require that $\phi(\cdot,z)$ is differentiable. Instead it assumes that $\phi(\cdot,z)$ is an extended real-valued closed proper convex function for each $z$ in the compact set $Z,$ that $\operatorname{int}(\operatorname{dom}(f)),$ the interior of the effective domain of $f,$ is nonempty, and that $\phi$ is continuous on the set $\operatorname{int}(\operatorname{dom}(f)) \times Z.$ Then for all $x$ in $\operatorname{int}(\operatorname{dom}(f)),$ the subdifferential of $f$ at $x$ is given by

$\partial f(x) = \operatorname{conv} \left\{\partial \phi(x,z) : z \in Z_0(x)\right\}$

where $\partial \phi(x,z)$ is the subdifferential of $\phi(\cdot,z)$ at $x$ for any $z$ in $Z.$

References

Category:Convex optimization

Category:Theorems in analysis