In mathematics, subderivatives (or subgradient) generalizes the derivative to convex functions which are not necessarily differentiable. The set of subderivatives at a point is called the subdifferential at that point. Subderivatives arise in convex analysis, the study of convex functions, often in connection to convex optimization.
Let f : I → R {\displaystyle f:I\to \mathbb {R} } 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 | {\displaystyle f(x)=|x|} is non-differentiable when x = 0 {\displaystyle x=0} . However, as seen in the graph on the right (where f ( x ) {\displaystyle f(x)} in blue has non-differentiable kinks similar to the absolute value function), for any x 0 {\displaystyle x_{0}} in the domain of the function one can draw a line which goes through the point ( x 0 , f ( x 0 ) ) {\displaystyle (x_{0},f(x_{0}))} and which is everywhere either touching or below the graph of f. The slope of such a line is called a subderivative.
be aRigorously, a subderivative of a convex function f : I → R {\displaystyle f:I\to \mathbb {R} }
f ( x ) − f ( x 0 ) ≥ c ( x − x 0 ) {\displaystyle f(x)-f(x_{0})\geq c(x-x_{0})} at a point x 0 {\displaystyle x_{0}} in the open interval I {\displaystyle I} is a real number c {\displaystyle c} such that for all x ∈ I {\displaystyle x\in I} . By the converse of the mean value theorem, the set of subderivatives at x 0 {\displaystyle x_{0}} for a convex function is a nonempty closed interval {\displaystyle } , where a {\displaystyle a} and b {\displaystyle b} are the one-sided limits a = lim x → x 0 − f ( x ) − f ( x 0 ) x − x 0 , {\displaystyle a=\lim _{x\to x_{0}^{-}}{\frac {f(x)-f(x_{0})}{x-x_{0}}},} b = lim x → x 0 + f ( x ) − f ( x 0 ) x − x 0 . {\displaystyle b=\lim _{x\to x_{0}^{+}}{\frac {f(x)-f(x_{0})}{x-x_{0}}}.} The interval {\displaystyle } of all subderivatives is called the subdifferential of the function f {\displaystyle f} at x 0 {\displaystyle x_{0}} , denoted by ∂ f ( x 0 ) {\displaystyle \partial f(x_{0})} . If f {\displaystyle f} is convex, then its subdifferential at any point is non-empty. Moreover, if its subdifferential at x 0 {\displaystyle x_{0}} contains exactly one subderivative, then f {\displaystyle f} is differentiable at x 0 {\displaystyle x_{0}} and ∂ f ( x 0 ) = { f ′ ( x 0 ) } {\displaystyle \partial f(x_{0})=\{f'(x_{0})\}} .Consider the function f ( x ) = | x | {\displaystyle f(x)=|x|} interval {\displaystyle } . The subdifferential at any point x 0 < 0 {\displaystyle x_{0}<0} is the singleton set { − 1 } {\displaystyle \{-1\}} , while the subdifferential at any point x 0 > 0 {\displaystyle x_{0}>0} is the singleton set { 1 } {\displaystyle \{1\}} . This is similar to the sign function, but is not single-valued at 0 {\displaystyle 0} , instead including all possible subderivatives.
which is convex. Then, the subdifferential at the origin is theThe concepts of subderivative and subdifferential can be generalized to functions of several variables. If f : U → R {\displaystyle f:U\to \mathbb {R} } convex open set in the Euclidean space R n {\displaystyle \mathbb {R} ^{n}} , a vector v {\displaystyle v} in that space is called a subgradient at x 0 ∈ U {\displaystyle x_{0}\in U} if for any x ∈ U {\displaystyle x\in U} one has that
f ( x ) − f ( x 0 ) ≥ v ⋅ ( x − x 0 ) , {\displaystyle f(x)-f(x_{0})\geq v\cdot (x-x_{0}),} is a real-valued convex function defined on awhere the dot denotes the dot product. The set of all subgradients at x 0 {\displaystyle x_{0}} is called the subdifferential at x 0 {\displaystyle x_{0}} and is denoted ∂ f ( x 0 ) {\displaystyle \partial f(x_{0})} . The subdifferential is always a nonempty convex compact set.
These concepts generalize further to convex functions f : U → R {\displaystyle f:U\to \mathbb {R} } convex set in a locally convex space V {\displaystyle V} . A functional v ∗ {\displaystyle v^{*}} in the dual space V ∗ {\displaystyle V^{*}} is called the subgradient at x 0 {\displaystyle x_{0}} in U {\displaystyle U} if for all x ∈ U {\displaystyle x\in U} ,
f ( x ) − f ( x 0 ) ≥ v ∗ ( x − x 0 ) . {\displaystyle f(x)-f(x_{0})\geq v^{*}(x-x_{0}).} on aThe set of all subgradients at x 0 {\displaystyle x_{0}} closed set. It can be an empty set; consider for example an unbounded operator, which is convex, but has no subgradient. If f {\displaystyle f} is continuous, the subdifferential is nonempty.
is called the subdifferential at x 0 {\displaystyle x_{0}} and is again denoted ∂ f ( x 0 ) {\displaystyle \partial f(x_{0})} . The subdifferential is always a convexThe 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.