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
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
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,
where
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
To state these results, we define the set of maximizing points
as
Danskin's theorem then provides the following results.
;Convexity
:
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
is convex in
for every
.
;Directional semi-differential
: The
semi-differential of
in the direction
, denoted
is given by
where
is the directional derivative of the function
at
in the direction
;Derivative
:
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
if
consists of a single element
. 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
(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
if
is a vector) is given by
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
and not directional-derivative as explains this simple example.
Set
, we get
which is semi-differentiable with
but has not a directional derivative at
.
Subdifferential
:If
is differentiable with respect to
for all
and if
is continuous with respect to
for all
, 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
is given by
where
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
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
*
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