Subderivative

<h2 id="definition">Definition</h2>
<p>Rigorously, a <i>subderivative</i> of a convex function 
  
    
      
        f
        :
        I
        →
        
          R
        
      
    
    {\displaystyle f:I\to \mathbb {R} }
  
 at a point Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle x_0}
 in the open interval 
  
    
      
        I
      
    
    {\displaystyle I}
  
 is a real number 
  
    
      
        c
      
    
    {\displaystyle c}
  
 such that

f
        (
        x
        )
        −
        f
        (
        
          x
          
            0
          
        
        )
        ≥
        c
        (
        x
        −
        
          x
          
            0
          
        
        )
      
    
    {\displaystyle f(x)-f(x_{0})\geq c(x-x_{0})}

for all 
  
    
      
        x
        ∈
        I
      
    
    {\displaystyle x\in I}
  
. By the converse of the <a href="/facts/Mean_value_theorem/JnjkzQb4">mean value theorem</a>, the <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of subderivatives at 
  
    
      
        
          x
          
            0
          
        
      
    
    {\displaystyle x_{0}}
  
 for a convex function is a <a href="/facts/Empty_set/ffEk3eA6">nonempty</a> <a href="/facts/Closed_interval/e9se3vTe">closed interval</a> 
  
    
      
        [
        a
        ,
        b
        ]
      
    
    {\displaystyle [a,b]}
  
, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle a}
 and 
  
    
      
        b
      
    
    {\displaystyle b}
  
 are the <a href="/facts/One-sided_limit/zLfr8gc5">one-sided limits</a>

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 <a href="/facts/Interval_(mathematics)/e9se3vTe">interval</a> 
  
    
      
        [
        a
        ,
        b
        ]
      
    
    {\displaystyle [a,b]}
  
 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})\}}
  
.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h2 id="example">Example</h2>
<p>Consider the function 
  
    
      
        f
        (
        x
        )
        =
        
          |
        
        x
        
          |
        
      
    
    {\displaystyle f(x)=|x|}
  
 which is convex. Then, the subdifferential at the origin is the <a href="/facts/Interval_(mathematics)/e9se3vTe">interval</a> 
  
    
      
        [
        −
        1
        ,
        1
        ]
      
    
    {\displaystyle [-1,1]}
  
. The subdifferential at any point 
  
    
      
        
          x
          
            0
          
        
        <
        0
      
    
    {\displaystyle x_{0}<0}
  
 is the <a href="/facts/Singleton_set/LtNVfujT">singleton set</a> 
  
    
      
        {
        −
        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 <a href="/facts/Sign_function/VADy9zQq">sign function</a>, but is not single-valued at 
  
    
      
        0
      
    
    {\displaystyle 0}
  
, instead including all possible subderivatives.
</p>
<h2 id="properties">Properties</h2>
<ul><li>A convex function 
  
    
      
        f
        :
        I
        →
        
          R
        
      
    
    {\displaystyle f:I\to \mathbb {R} }
  
 is differentiable at 
  
    
      
        
          x
          
            0
          
        
      
    
    {\displaystyle x_{0}}
  
 <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> the subdifferential is a singleton set, which is 
  
    
      
        {
        
          f
          ′
        
        (
        
          x
          
            0
          
        
        )
        }
      
    
    {\displaystyle \{f'(x_{0})\}}
  
.</li>
<li>A point 
  
    
      
        
          x
          
            0
          
        
      
    
    {\displaystyle x_{0}}
  
 is a <a href="/facts/Global_minimum/ADlgnyzV">global minimum</a> of a convex function 
  
    
      
        f
      
    
    {\displaystyle f}
  
 if and only if zero is contained in the subdifferential. For instance, in the figure above, one may draw a horizontal "subtangent line" to the graph of 
  
    
      
        f
      
    
    {\displaystyle f}
  
 at 
  
    
      
        (
        
          x
          
            0
          
        
        ,
        f
        (
        
          x
          
            0
          
        
        )
        )
      
    
    {\displaystyle (x_{0},f(x_{0}))}
  
. This last property is a generalization of the fact that the derivative of a function differentiable at a local minimum is zero.</li>
<li>If 
  
    
      
        f
      
    
    {\displaystyle f}
  
 and 
  
    
      
        g
      
    
    {\displaystyle g}
  
 are convex functions with subdifferentials 
  
    
      
        ∂
        f
        (
        x
        )
      
    
    {\displaystyle \partial f(x)}
  
 and 
  
    
      
        ∂
        g
        (
        x
        )
      
    
    {\displaystyle \partial g(x)}
  
 with 
  
    
      
        x
      
    
    {\displaystyle x}
  
 being the interior point of one of the functions, then the subdifferential of 
  
    
      
        f
        +
        g
      
    
    {\displaystyle f+g}
  
 is 
  
    
      
        ∂
        (
        f
        +
        g
        )
        (
        x
        )
        =
        ∂
        f
        (
        x
        )
        +
        ∂
        g
        (
        x
        )
      
    
    {\displaystyle \partial (f+g)(x)=\partial f(x)+\partial g(x)}
  
 (where the addition operator denotes the <a href="/facts/Minkowski_sum/dEQfoJ1A">Minkowski sum</a>). This reads as "the subdifferential of a sum is the sum of the subdifferentials."<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ul>
<h2 id="the-subgradient">The subgradient</h2>
<p>The concepts of subderivative and subdifferential can be generalized to functions of several variables. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle f:U\to\mathbb{R}}
 is a real-valued convex function defined on a <a href="/facts/Convex_set/vdAuJRJl">convex</a> <a href="/facts/Open_set/QfTCIqMu">open set</a> in the <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> 
  
    
      
        
          
            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
</p>

f
        (
        x
        )
        −
        f
        (
        
          x
          
            0
          
        
        )
        ≥
        v
        ⋅
        (
        x
        −
        
          x
          
            0
          
        
        )
        ,
      
    
    {\displaystyle f(x)-f(x_{0})\geq v\cdot (x-x_{0}),}

<p>where the dot denotes the <a href="/facts/Dot_product/tNz8MLjT">dot product</a>. 
The set of all subgradients at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\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 <a href="/facts/Compact_set/d0cgXJH7">compact set</a>.
</p><p>These concepts generalize further to convex functions 
  
    
      
        f
        :
        U
        →
        
          R
        
      
    
    {\displaystyle f:U\to \mathbb {R} }
  
 on a <a href="/facts/Convex_set/vdAuJRJl">convex set</a> in a <a href="/facts/Locally_convex_space/AGrPrayC">locally convex space</a> 
  
    
      
        V
      
    
    {\displaystyle V}
  
. A functional 
  
    
      
        
          v
          
            ∗
          
        
      
    
    {\displaystyle v^{*}}
  
 in the <a href="/facts/Dual_space/4Uw4Knz1">dual space</a> 
  
    
      
        
          V
          
            ∗
          
        
      
    
    {\displaystyle V^{*}}
  
 is called a <i>subgradient</i> at 
  
    
      
        
          x
          
            0
          
        
      
    
    {\displaystyle x_{0}}
  
 in 
  
    
      
        U
      
    
    {\displaystyle U}
  
 if for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle x\in U}
,
</p>

f
        (
        x
        )
        −
        f
        (
        
          x
          
            0
          
        
        )
        ≥
        
          v
          
            ∗
          
        
        (
        x
        −
        
          x
          
            0
          
        
        )
        .
      
    
    {\displaystyle f(x)-f(x_{0})\geq v^{*}(x-x_{0}).}

<p>The set of all subgradients at 
  
    
      
        
          x
          
            0
          
        
      
    
    {\displaystyle x_{0}}
  
 is called the subdifferential at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle x_0}
 and is again denoted 
  
    
      
        ∂
        f
        (
        
          x
          
            0
          
        
        )
      
    
    {\displaystyle \partial f(x_{0})}
  
. The subdifferential is always a convex <a href="/facts/Closed_set/upYnRTUj">closed set</a>. It can be an empty set; consider for example an <a href="/facts/Unbounded_operator/5u2njqHt">unbounded operator</a>, which is convex, but has no subgradient. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle f}
 is continuous, the subdifferential is nonempty.
</p>
<h2 id="history">History</h2>
<p>The subdifferential on convex functions was introduced by <a href="/facts/Jean_Jacques_Moreau/hLB8T1xY">Jean Jacques Moreau</a> and <a href="/facts/R._Tyrrell_Rockafellar/Jzj3n73g">R. Tyrrell Rockafellar</a> in the early 1960s. The <i>generalized subdifferential</i> for nonconvex functions was introduced by <a href="/facts/Francis_Clarke_(mathematician)/JRPRJtvm">Francis H. Clarke</a> and R. Tyrrell Rockafellar in the early 1980s.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Weak_derivative/oehSmSMg">Weak derivative</a></li>
<li><a href="/facts/Subgradient_method/XTYlovxm">Subgradient method</a></li>
<li><a href="/facts/Clarke_generalized_derivative/eNxUw804">Clarke generalized derivative</a></li></ul>

<ul><li>Borwein, Jonathan; Lewis, Adrian S. (2010). <i>Convex Analysis and Nonlinear Optimization : Theory and Examples</i> (2nd ed.). New York: Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-31256-9.</li>
<li>Hiriart-Urruty, Jean-Baptiste; <a href="/facts/Claude_Lemar%C3%A9chal/aMcoIXVJ">Lemaréchal, Claude</a> (2001). <i>Fundamentals of Convex Analysis</i>. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-42205-6.</li>
<li>Zălinescu, C. (2002). <i>Convex analysis in general vector spaces</i>. World Scientific Publishing  Co., Inc. pp. xx+367. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 981-238-067-1. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1921556">1921556</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://math.stackexchange.com/q/65569">"Uses of 
  
    
      
        
          lim
          
            h
            →
            0
          
        
        
          
            
              f
              (
              x
              +
              h
              )
              −
              f
              (
              x
              −
              h
              )
            
            
              2
              h
            
          
        
      
    
    {\displaystyle \lim \limits _{h\to 0}{\frac {f(x+h)-f(x-h)}{2h}}}
  
"</a>. <i><a href="/facts/Stack_Exchange/VQvJKJMh">Stack Exchange</a></i>. September 18, 2011.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Bubeck, S. (2014). Theory of Convex Optimization for Machine Learning. ArXiv, abs/1405.4980. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press. p. 242 [Theorem 25.1]. ISBN 0-691-08069-0. <a href="0-691-08069-0" target="_blank">0-691-08069-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Lemaréchal, Claude; Hiriart-Urruty, Jean-Baptiste (2001). Fundamentals of Convex Analysis. Springer-Verlag Berlin Heidelberg. p. 183. ISBN 978-3-642-56468-0. <a href="978-3-642-56468-0" target="_blank">978-3-642-56468-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Clarke, Frank H. (1983). Optimization and nonsmooth analysis. New York: John Wiley & Sons. pp. xiii+308. ISBN 0-471-87504-X. MR 0709590. <a href="0-471-87504-X" target="_blank">0-471-87504-X</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Subderivative open-in-new

Subderivative