Danskin's theorem

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.

Statement

The theorem applies to the following situation. Suppose ϕ(x,z) is a continuous function of two arguments,

\phi: {\mathbb R}^n \times Z \rightarrow {\mathbb R}

where Z \subset {\mathbb R}^m is a compact set. Further assume that ϕ(x,z) is convex in x for every z \in Z.

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

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

To state these results, we define the set of maximizing points Z0(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.
Directional derivatives
The directional derivative of f(x) in the direction y, denoted D_y\ f(x), is given by
D_y f(x) = \max_{z \in Z_0(x)} \phi'(x,z;y),
where ϕ'(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 Z0(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}.
Subdifferential
If ϕ(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 conv indicates the convex hull operation.

References

  • Bertsekas, Dimitri P. (1999). Nonlinear Programming. Belmont, MA: Athena Scientific. pp. 717. ISBN 1-886529-00-0. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”