Information ratio: Difference between revisions
Jump to navigation
Jump to search
en>Zfeinst Undid revision 509346693 by 69.114.241.229 (talk) |
en>RJSutter m Spacing |
||
| Line 1: | Line 1: | ||
[[File:Subderivative illustration.png|right|thumb|A convex function (blue) and "subtangent lines" at ''x''<sub>0</sub> (red).]] | |||
In [[mathematics]], the '''subderivative''', '''subgradient''', and '''subdifferential''' generalize the [[derivative]] to functions which are not differentiable. The subdifferential of a function is set-valued. Subderivatives arise in [[convex analysis]], the study of [[convex functions]], often in connection to [[convex optimization]]. | |||
Let ''f'':''I''→'''R''' be a [[real number|real]]-valued convex function defined on an [[open interval]] of the real line. Such a function need not be differentiable at all points: For example, the [[absolute value]] function ''f''(''x'')=|''x''| is nondifferentiable when ''x''=0. However, as seen in the picture on the right, for any ''x''<sub>0</sub> in the domain of the function one can draw a line which goes through the point (''x''<sub>0</sub>, ''f''(''x''<sub>0</sub>)) 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 function ''f'':''I''→'''R''' at a point ''x''<sub>0</sub> in the open interval ''I'' is a real number ''c'' such that | |||
:<math>f(x)-f(x_0)\ge c(x-x_0)</math> | |||
for all ''x'' in ''I''. One may show that the [[Set (mathematics)|set]] of subderivatives at ''x''<sub>0</sub> for a convex function is a [[empty set|nonempty]] [[closed interval]] [''a'', ''b''], where ''a'' and ''b'' are the [[one-sided limit]]s | |||
:<math>a=\lim_{x\to x_0^-}\frac{f(x)-f(x_0)}{x-x_0}</math> | |||
:<math>b=\lim_{x\to x_0^+}\frac{f(x)-f(x_0)}{x-x_0}</math> | |||
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''<sub>0</sub>. If ''f'' is convex and its subdifferential at <math>x_0</math> contains exactly one subderivative, then ''f'' is differentiable at <math>x_0</math>.<ref>[[R. T. Rockafellar]] ''Convex analysis'' 1970. Theorem 25.1, p.242</ref> | |||
==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''<sub>0</sub><0 is the [[singleton set]] {−1}, while the subdifferential at any point ''x''<sub>0</sub>>0 is the singleton {1}. | |||
==Properties== | |||
* A convex function ''f'':''I''→'''R''' is differentiable at ''x''<sub>0</sub> [[if and only if]] the subdifferential is made up of only one point, which is the derivative at ''x''<sub>0</sub>. | |||
* A point ''x''<sub>0</sub> 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''<sub>0</sub>, ''f''(''x''<sub>0</sub>)). 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 set|convex]] [[open set]] in the [[Euclidean space]] '''R'''<sup>''n''</sup>, a vector ''v'' in that space is called a '''subgradient''' at a point ''x''<sub>0</sub> in ''U'' if for any ''x'' in ''U'' one has | |||
:<math>f(x)-f(x_0)\ge v\cdot (x-x_0)</math> | |||
where the dot denotes the [[dot product]]. | |||
The set of all subgradients at ''x''<sub>0</sub> is called the '''subdifferential''' at ''x''<sub>0</sub> and is denoted ∂''f''(''x''<sub>0</sub>). 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''<sup>∗</sup> in the [[dual space]] V<sup>∗</sup> is called ''subgradient'' at ''x''<sub>0</sub> in ''U'' if | |||
:<math>f(x)-f(x_0)\ge v^*(x-x_0).</math> | |||
The set of all subgradients at ''x''<sub>0</sub> is called the subdifferential at ''x''<sub>0</sub> and is again denoted ∂''f''(''x''<sub>0</sub>). 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. | |||
==History== | |||
The subdifferential on convex functions was introduced by [[Jean Jacques Moreau]] and [[R. Tyrrell Rockafellar]] in the early 1960s. The ''generalized subdifferential'' for nonconvex functions was introduced by F.H. Clarke and R.T. Rockafellar in the early 1980s.<ref> | |||
{{cite book|last=Clarke|first=Frank H.|title=Optimization and nonsmooth analysis|publisher=[[John Wiley & Sons]]|location=New York|year=1983|pages=xiii+308|isbn=0-471-87504-X |mr=0709590}}</ref> | |||
<!-- this reference is not recognized by the optimization community | |||
<ref> | |||
Georgios Stavroulakis, "Quasidifferentiable optimization" in Christodoulos A. Floudas, P.M. Pardalos, eds., ''Encyclopedia of Optimization'' 2001, ISBN 0-7923-6932-7, [http://books.google.com/books?id=gtoTkL7heS0C&pg=PA452#v=snippet&q=subdifferential%20moreau&f=false p. 452''ff'']</ref> | |||
--> | |||
==See also== | |||
* [[Weak derivative]] | |||
* [[Subgradient method]] | |||
==References== | |||
<references/> | |||
* Jean-Baptiste Hiriart-Urruty, [[Claude Lemaréchal]], ''Fundamentals of Convex Analysis'', Springer, 2001. ISBN 3-540-42205-6. | |||
* {{cite book|last=Zălinescu|first=C.|title=Convex analysis in general vector spaces|publisher=World Scientific Publishing Co., Inc|year=2002|pages=xx+367|isbn=981-238-067-1|mr=1921556}} | |||
[[Category:Convex analysis]] | |||
[[Category:Generalizations of the derivative]] | |||
[[Category:Mathematical optimization]] | |||
[[Category:Variational analysis]] | |||
Revision as of 02:00, 30 July 2013
In mathematics, the subderivative, subgradient, and subdifferential generalize the derivative to functions which are not differentiable. The subdifferential of a function is set-valued. Subderivatives arise in convex analysis, 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 need not be differentiable at all points: For example, the absolute value function f(x)=|x| is nondifferentiable when x=0. However, as seen in the picture on the right, for any x0 in the domain of the function one can draw a line which goes through the point (x0, f(x0)) 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 function f:I→R at a point x0 in the open interval I is a real number c such that
for all x in I. One may show that the set of subderivatives at x0 for a convex function is a nonempty closed interval [a, b], where a and b are the one-sided limits
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 x0. If f is convex and its subdifferential at contains exactly one subderivative, then f is differentiable at .[1]
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 x0<0 is the singleton set {−1}, while the subdifferential at any point x0>0 is the singleton {1}.
Properties
- A convex function f:I→R is differentiable at x0 if and only if the subdifferential is made up of only one point, which is the derivative at x0.
- A point x0 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 (x0, f(x0)). 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 Rn, a vector v in that space is called a subgradient at a point x0 in U if for any x in U one has
where the dot denotes the dot product. The set of all subgradients at x0 is called the subdifferential at x0 and is denoted ∂f(x0). 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∗ in the dual space V∗ is called subgradient at x0 in U if
The set of all subgradients at x0 is called the subdifferential at x0 and is again denoted ∂f(x0). 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.
History
The subdifferential on convex functions was introduced by Jean Jacques Moreau and R. Tyrrell Rockafellar in the early 1960s. The generalized subdifferential for nonconvex functions was introduced by F.H. Clarke and R.T. Rockafellar in the early 1980s.[2]
See also
References
- ↑ R. T. Rockafellar Convex analysis 1970. Theorem 25.1, p.242
- ↑
20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
- Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, Fundamentals of Convex Analysis, Springer, 2001. ISBN 3-540-42205-6.
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534