Danskin's Theorem
   HOME

TheInfoList



OR:

In
convex analysis Convex analysis is the branch of mathematics devoted to the study of properties of convex functions and convex sets, often with applications in convex optimization, convex minimization, a subdomain of optimization (mathematics), optimization theor ...
, Danskin's theorem is a
theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
which provides information about the
derivative In mathematics, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is t ...
s of a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orie ...
of the form f(x) = \max_ \phi(x,z). The theorem has applications in
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
, where it sometimes is used to solve
minimax Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for ''minimizing'' the possible loss function, loss for a Worst-case scenari ...
problems. The original theorem given by J. M. Danskin in his 1967 monograph 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). Suppose \phi(x,z) is a
continuous function In mathematics, a continuous function is a function such that a small variation of the argument induces a small variation of the value of the function. This implies there are no abrupt changes in value, known as '' discontinuities''. More preci ...
of two arguments, \phi : \R^n \times Z \to \R where Z \subset \R^m is a
compact set In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., i ...
. Under these conditions, Danskin's theorem provides conclusions regarding the convexity and
differentiability In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non- vertical tangent line at each interior point in ...
of the function f(x) = \max_ \phi(x,z). To state these results, we define the set of maximizing points Z_0(x) as Z_0(x) = \left\. Danskin's theorem then provides the following results. ;Convexity : f(x) is
convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...
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_ \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 In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non- vertical tangent line at each interior point in ...
at x if Z_0(x) consists of a single element \overline. In this case, the
derivative In mathematics, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is t ...
of f(x) (or the
gradient In vector calculus, the gradient of a scalar-valued differentiable function f of several variables is the vector field (or vector-valued function) \nabla f whose value at a point p gives the direction and the rate of fastest increase. The g ...
of f(x) if x is a vector) is given by \frac = \frac.


Example of no

directional derivative In multivariable calculus, the directional derivative measures the rate at which a function changes in a particular direction at a given point. The directional derivative of a multivariable differentiable (scalar) function along a given vect ...

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=\,\ \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 In mathematics, the subderivative (or subgradient) generalizes the derivative to convex functions which are not necessarily Differentiable function, differentiable. The set of subderivatives at a point is called the subdifferential at that point. ...
of f(x) is given by \partial f(x) = \mathrm \left\ where \mathrm indicates the
convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
operation.


Extension

The 1971 Ph.D. Thesis by Dimitri P. Bertsekas (Proposition A.22) 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(\operatorname(f)), the interior of the effective domain of f, is nonempty, and that \phi is continuous on the set \operatorname(\operatorname(f)) \times Z. Then for all x in \operatorname(\operatorname(f)), the subdifferential of f at x is given by \partial f(x) = \operatorname \left\ where \partial \phi(x,z) is the subdifferential of \phi(\cdot,z) at x for any z in Z.


See also

* Maximum theorem *
Envelope theorem In mathematics and economics, the envelope theorem is a major result about the differentiability properties of the value function of a parameterized optimization problem. As we change parameters of the objective, the envelope theorem shows that, in ...
* Hotelling's lemma


References

{{Convex analysis and variational analysis Convex optimization Theorems in mathematical analysis