Subderivative

In mathematics, the concepts of subderivative, subgradient, and subdifferential arise in convex analysis, that is, in the study of convex functions, often in connection to convex optimization.

Let "f":"I"→R be a real-valued convex function defined on an open interval of the real line. Such a function may not necessarily be differentiable at all points, as for example, the absolute value, "f"("x")=|"x"|. However, as seen in the picture on the right (and which can be proved rigorously), for any "x"₀ in the domain of the function one can draw a line which goes through the point ("x"₀, "f"("x"₀)) and which is everywhere either touching or below the graph of "f". The slope of such a line is called a "subderivative" (because the line is under the graph of "f").

Definition

Rigorously, a "subderivative" of a convex function "f":"I"→R at a point "x"₀ in the open interval "I" is a real number "c" such that :$f(x)-f(x\_0)ge\; c(x-x\_0)$for all "x" in "I". One may show that the set of subderivatives at "x"₀ is a nonempty closed interval ["a", "b"] , where "a" and "b" are the one-sided limits

:$a=lim\_\{x\; o\; x\_0^-\}frac\{f(x)-f(x\_0)\}\{x-x\_0\}$

:$b=lim\_\{x\; o\; x\_0^+\}frac\{f(x)-f(x\_0)\}\{x-x\_0\}$

which are guaranteed to exist and satisfy "a" ≤ "b".

The set ["a", "b"] of all subderivatives is called the subdifferential of the function "f" at "x"₀.

Examples

Consider the function "f"("x")=|"x"| which is convex. Then, the subdifferential at the origin is the interval [−1, 1] . The subdifferential at any point "x"₀<0 is the singleton set {−1}, while the subdifferential at any point "x"₀>0 is the singleton {1}.

Properties

* A convex function "f":"I"→R is differentiable at "x"₀ if and only if the subdifferential is made up of only one point, which is the derivative at "x"₀.

* A point "x"₀ is a global minimum of a convex function "f" if and only if zero is contained in the subdifferential, that is, in the figure above, one may draw a horizontal "subtangent line" to the graph of "f" at ("x"₀, "f"("x"₀)). This last property is a generalization of the fact that the derivative of a function differentiable at a local minimum is zero.

The subgradient

The concepts of subderivative and subdifferential can be generalized to functions of several variables. If "f":"U"→ R is a real-valued convex function defined on a convex open set in the Euclidean space R^"n", a vector "v" in that space is called a subgradient at a point "x"₀ in "U" if for any "x" in "U" one has:$f(x)-f(x\_0)ge\; vcdot\; (x-x\_0)$where the dot denotes the dot product. The set of all subgradients at "x"₀ is called the subdifferential at "x"₀ and is denoted &part;"f"("x"₀). The subdifferential is always a nonempty convex compact set.

These concepts generalize further to convex functions "f":"U"→ R on a convex set in a locally convex space "V". A functional "v"^&lowast; in the dual space V^&lowast; is called "subgradient" at "x"₀ in "U" if:$f(x)-f(x\_0)ge\; v^*(x-x\_0).$The set of all subgradients at "x"₀ is called the subdifferential at "x"₀ and is again denoted &part;"f"("x"₀). The subdifferential is always a convex closed set. It can be an empty set; consider for example an unbounded operator, which is convex, but has no subgradient. If "f" is continuous, the subdifferential is nonempty.

ee also

* Weak derivative

References

* Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, "Fundamentals of Convex Analysis", Springer, 2001. ISBN 3-540-42205-6.