Subdifferential

劣微分

Advanced (Graduate level)

1. Introduction: no tangent at a kink

The heart of differentiation is drawing the tangent line that best approximates a function locally. But convex functions often have kinks where they are not differentiable, such as the origin of the absolute value $f(x)=|x|$, the $\ell_1$ norm, or a $\max$ function. There the tangent is not uniquely determined and the gradient $\nabla f$ does not exist.

Yet convex functions offer a remedy even at non-differentiable points. At a corner, the lines that support the graph from below are not a single line but a whole fan of supporting lines. Using this "set of slopes of the supporting lines" in place of the gradient is the idea of the subdifferential. It extends the gradient from a single vector to a set: at differentiable points it coincides with the ordinary gradient, and at kinks it becomes a set of several slopes. This provides the optimality condition $\partial f\ni 0$ for nonsmooth convex optimization, replacing "$\nabla f=0$".

2. Definition (subgradient and subdifferential)

Subgradient and subdifferential

Let $f:\mathbb{R}^n\to\mathbb{R}\cup\{+\infty\}$ be a proper convex function and let $x$ be a point with $f(x)<+\infty$. A vector $g\in\mathbb{R}^n$ satisfying

$$f(p)\ \ge\ f(x)+\langle g,\,p-x\rangle\qquad(\forall p\in\mathbb{R}^n)$$

is called a subgradient of $f$ at $x$. The set of all subgradients,

$$\partial f(x)=\bigl\{\,g\in\mathbb{R}^n\ :\ f(p)\ge f(x)+\langle g,\,p-x\rangle\ \ (\forall p)\,\bigr\}$$

is the subdifferential of $f$ at $x$.

The inequality $f(p)\ge f(x)+\langle g,p-x\rangle$ says that the linear function $\ell(p)=f(x)+\langle g,p-x\rangle$ with slope $g$, passing through $(x,f(x))$, lies below (supports from beneath) the entire graph. The essential point is that the first-order approximation $f(p)\approx f(x)+\langle\nabla f(x),p-x\rangle$ of the differentiable case becomes, thanks to convexity, a global lower bound rather than a mere approximation. A tangent is a local approximation that merely touches the graph, whereas a supporting line satisfies the global condition of staying below the entire graph. Such a global lower bound always exists precisely because the function is convex; for a non-convex function there are points where no line can stay below the graph, and there the subdifferential is empty.

p x p ⟨g, p−x⟩ f ℓ(p)=f(x)+⟨g,p−x⟩ (x, f(x)) f(p) ≥ ℓ(p) the line stays below the graph
Figure 1. Geometric meaning of the subgradient inequality. A linear function $\ell(p)=f(x)+\langle g,p-x\rangle$ that touches the graph of a convex function $f$ at $(x,f(x))$ and supports the whole graph from below is called a supporting line. Saying that the slope $g$ is a subgradient at $x$ is the same as $f(p)\ge\ell(p)$ (the graph lies above the supporting line) for every $p$, which is the subgradient inequality $f(p)\ge f(x)+\langle g,p-x\rangle$. The green segment $\langle g,p-x\rangle$ is the rise of the supporting line from $x$ to $p$ ($\ell(p)-f(x)$), while the red segment is $f(p)-\ell(p)$ (the gap by which the graph exceeds the supporting line); the two are different quantities.

⟨·,·⟩ is the inner product (degree of alignment)

The symbol $\langle g, v\rangle$ is the inner product (dot product) of the vectors $g$ and $v$, the sum of componentwise products $\langle g,v\rangle=g_1 v_1+\cdots+g_n v_n$, and geometrically $\langle g,v\rangle=\lVert g\rVert\,\lVert v\rVert\cos\theta$ (where $\theta$ is the angle between $g$ and $v$). It measures "how much $v$ points along $g$": positive when they point the same way, $0$ when orthogonal, negative when opposite.

Here $v=p-x$ (the displacement from $x$ to $p$), so $\langle g,p-x\rangle$ is the size of that displacement along the direction of the subgradient $g$. In one dimension ($n=1$), $\langle g,p-x\rangle=g\,(p-x)$ is slope $\times$ horizontal displacement, that is the rise of the supporting line in Figure 1 from $x$ to $p$ (the length of the green segment).

θ x (base point) g (subgradient) v = p − x projection of v: |v|cos θ ⟨g, v⟩ = |g| · |v| cos θ (alignment of g and v)
Figure 2. Meaning of the inner product $\langle g,\,p-x\rangle$. Starting at $x$, draw the subgradient vector $g$ and the displacement vector $v=p-x$, and project $v$ orthogonally onto the direction of $g$. The inner product is $\langle g,v\rangle=\lVert g\rVert\,\lVert v\rVert\cos\theta$, that is $\lVert g\rVert$ times "the projection $\lVert v\rVert\cos\theta$ of $v$ onto $g$", expressing how well $g$ and $v$ are aligned.

In one dimension it is an interval

For $n=1$, the subdifferential can be written as the closed interval bounded by the left and right one-sided derivatives:

$$\partial f(x)=\bigl[\,f'_-(x),\ f'_+(x)\,\bigr],\qquad f'_-(x)=\lim_{t\uparrow 0}\frac{f(x+t)-f(x)}{t},\quad f'_+(x)=\lim_{t\downarrow 0}\frac{f(x+t)-f(x)}{t}.$$

If the left derivative $f'_-$ and the right derivative $f'_+$ agree, the interval collapses to a single point (the ordinary derivative); at a kink $f'_-<f'_+$, so the interval has positive width. By convexity the difference quotient increases monotonically, so $f'_-\le f'_+$ always holds and the interval $[f'_-,f'_+]$ is never reversed ($f'_->f'_+$). A reversal $f'_->f'_+$ occurs only at a concave (upward-pointing) corner such as $-\lvert x\rvert$, where no line supports from below and the subdifferential is empty.

3. Geometric meaning: a fan of supporting lines

Take the absolute value $f(x)=|x|$. For $x\neq 0$ the graph is a straight line and the only supporting line is that line itself (slope $\pm1$), so $\partial f(x)=\{\operatorname{sign}(x)\}$ is a single point. At the origin, however, every line with slope between $-1$ and $+1$ supports the graph from below, so $\partial f(0)=[-1,1]$ is an interval.

x y O f(x)=|x| slope −1 to +1 ∂f(0)=[−1,1] for x>0 ∂f={+1} (single)
Figure 3. Geometric meaning of the subdifferential. Consider the lines that support the convex function $f(x)=|x|$ from below (supporting hyperplanes). At a smooth point $x>0$ the supporting line is the unique tangent, so $\partial f(x)=\{+1\}$. At the corner at the origin, every line with slope from $-1$ to $+1$ fans out and supports the graph from below, so the set of all those slopes is the subdifferential $\partial f(0)=[-1,1]$. The downward orange dashed lines are the slope $\pm1$ supporting lines (extensions of the blue V). Supporting lines sweep the left and right wedges (the near-horizontal region); in the right wedge the slope turns continuously from $+1$ (the blue right arm) to $-1$ (the lower-right dashed line). The double-headed arc represents this variable range. The subdifferential is "the set of slopes of the supporting lines".

4. Basic properties

Basic properties of the subdifferential

Let $f,g$ be proper convex functions.

  1. Closed convex set: $\partial f(x)$ is always a closed convex set (possibly empty). If $x$ lies in the relative interior of the domain it is nonempty and bounded.
  2. Equivalence with differentiability: $f$ is differentiable at $x$ $\iff$ $\partial f(x)=\{\nabla f(x)\}$ (a singleton). Hence the subdifferential is a genuine extension of the gradient.
  3. Monotonicity: if $g_x\in\partial f(x)$ and $g_p\in\partial f(p)$ then $\langle g_x-g_p,\ x-p\rangle\ge 0$. This generalizes "the slope of a convex function is nondecreasing" in one variable.
  4. Scaling: for $\alpha>0$, $\partial(\alpha f)(x)=\alpha\,\partial f(x)$.
  5. Sum rule: $\partial(f+g)(x)\supseteq\partial f(x)+\partial g(x)$. Under a suitable constraint qualification (for example, that the relative interiors of the domains intersect) equality $\partial(f+g)=\partial f+\partial g$ holds (Moreau–Rockafellar theorem).

What "becoming a set" means

The subdifferential is a set-valued map $\partial f:\mathbb{R}^n\rightrightarrows\mathbb{R}^n$ that returns a set of vectors for each point $x$. Monotonicity leads to the structural fact that this set-valued map is a maximal monotone operator, which underlies the theory of proximal-point and operator-splitting methods.

5. Representative examples

Example 5.1: absolute value and the $\ell_1$ norm

The subdifferential of the absolute value $f(x)=|x|$ (with $x\in\mathbb{R}$) is

$$\partial |x|=\begin{cases}\{+1\} & x>0,\\[2pt] [-1,1] & x=0,\\[2pt] \{-1\} & x<0.\end{cases}$$

Because it separates componentwise, the subdifferential of the $\ell_1$ norm $\|x\|_1=\sum_i|x_i|$ is the Cartesian product of the componentwise sets: $g\in\partial\|x\|_1$ is given by $g_i=\operatorname{sign}(x_i)$ (for $x_i\neq0$) and $g_i\in[-1,1]$ (for $x_i=0$). This is the source of the sparsity of the Lasso.

Example 5.2: a general norm and the $\max$

For a norm $f(x)=\|x\|$, the subdifferential at the origin is the unit ball of the dual norm $\partial\|\cdot\|(0)=\{g:\|g\|_*\le1\}$, while for $x\neq0$ it is the set of $g$ with $\|g\|_*=1$ and $\langle g,x\rangle=\|x\|$.

For the $\max$ of finitely many smooth functions, $f(x)=\max_i f_i(x)$, using the active index set $I(x)=\{i:f_i(x)=f(x)\}$ that attains the maximum,

$$\partial f(x)=\operatorname{conv}\{\nabla f_i(x):i\in I(x)\}$$

(the convex hull of the attaining gradients). A point where several functions attain the maximum simultaneously is a kink, and there the subdifferential spreads out.

Example 5.3: indicator function and normal cone

The subdifferential of the indicator function $\iota_C(x)$ of a convex set $C$ ($0$ for $x\in C$, $+\infty$ otherwise) coincides with the normal cone $N_C(x)$ at $x\in C$:

$$\partial\iota_C(x)=N_C(x)=\{\,g:\langle g,\,p-x\rangle\le0\ \ (\forall p\in C)\,\}.$$

This lets the optimality conditions (KKT conditions) of constrained optimization be written uniformly in the language of subdifferentials.

In several variables the subdifferential becomes a region ($\ell_1$–$\ell_\infty$ duality)

For $|x|$ in one variable the subdifferential was the interval $[-1,1]$; in several variables it becomes a region. The subdifferential of a norm at the origin is the unit ball of the dual norm (Example 5.2): for the $\ell_1$ norm $|x|+|y|$ it is the square $[-1,1]^2$, and for the $\ell_\infty$ norm $\max(|x|,|y|)$ it is a diamond. The 3D figures below pair the corner of the graph (the non-differentiable point) with the subdifferential region.

x y z g₁ g₂ (1,1) (−1,−1) z = |x| + |y| ∂f(0) = [−1,1] × [−1,1] → slopes of supporting planes
Figure 4. 3D view of $f(x,y)=|x|+|y|$ (the $\ell_1$ norm) and its subdifferential at the origin. The left graph is a valley where four planes meet at the corner at the origin; the slopes $(g_1,g_2)$ of the planes supporting it from below can range independently over $[-1,1]$, so the subdifferential $\partial f(0)=[-1,1]\times[-1,1]$ is a square region (right, semi-transparent).
x y z g₁ g₂ (1,0) (0,1) z = max(|x|, |y|) ∂f(0) : |g₁| + |g₂| ≤ 1 → slopes of supporting planes
Figure 5. 3D view of $f(x,y)=\max(|x|,|y|)$ (the $\ell_\infty$ norm) and its subdifferential at the origin. The slopes of the supporting planes form the convex hull of the four vertices $(\pm1,0),(0,\pm1)$, that is the diamond $\{|g_1|+|g_2|\le1\}$ (right, semi-transparent). Since $\ell_1$ and $\ell_\infty$ are dual, the shape of the subdifferential swaps dually (square $\leftrightarrow$ diamond).

6. Optimality condition and applications

Theorem (Fermat's rule for subdifferentials)

For a proper convex function $f$, that $x^\star$ is a global minimizer of $f$ is equivalent to

$$\partial f(x^\star)\ni 0.$$

The proof is the definition itself. $\partial f(x^\star)\ni 0$ means the subgradient inequality can be taken with $g=0$, i.e. $f(p)\ge f(x^\star)$ for every $p$, which is exactly the statement that $x^\star$ is a minimizer. It extends the differentiable condition $\nabla f(x^\star)=0$ directly to functions with kinks.

This condition lies at the center of nonsmooth optimization. In the unconstrained case the subgradient method converges to a minimizer via $x_{k+1}=x_k-\eta_k g_k$ (with $g_k\in\partial f(x_k)$). For composite minimization $\min f(x)+g(x)$, the optimality condition $\nabla f(x^\star)+\partial g(x^\star)\ni 0$ can be rewritten as a fixed point of the proximal operator, from which the proximal gradient method (ISTA/FISTA) is derived. For constrained problems, the subdifferential of the indicator function, the normal cone (Example 5.3), expresses the KKT conditions in subdifferential form.

7. Place among generalizations of the derivative

The subdifferential is one direction of "generalizing the derivative". Whereas the directional derivative, Gâteaux derivative and Fréchet derivative track "how far differentiability can be weakened (how the limit is taken)", the subdifferential is a different direction: "how to handle a non-differentiable convex function through a set of linear approximations that act as lower bounds". From the dual viewpoint it is closely tied to the Legendre–Fenchel transform, with the beautiful correspondence $g\in\partial f(x)\iff x\in\partial f^\ast(g)\iff f(x)+f^\ast(g)=\langle g,x\rangle$. For the overall picture, see the map of generalized derivatives.

8. Frequently asked questions

Q1. What is the subdifferential?

It generalizes the gradient to convex functions that are not differentiable. It is the set $\partial f(x)$ of all $g$ (subgradients) satisfying $f(p)\ge f(x)+\langle g,p-x\rangle$ for every $p$. Geometrically it is the set of slopes of the lines that support the graph from below at $(x,f(x))$.

Q2. How does the subdifferential differ from the gradient?

The gradient $\nabla f(x)$ is one vector, the slope of the unique tangent, while the subdifferential $\partial f(x)$ is a set, the slopes of all lines supporting from below. That $f$ is differentiable at $x$ is equivalent to $\partial f(x)=\{\nabla f(x)\}$ being a single point, and at points of differentiability the two agree. At a kink several slopes fan out and the subdifferential spreads into a set.

Q3. Why is $\partial f(x)\ni 0$ the condition for a minimum?

$\partial f(x)\ni 0$ means the subgradient inequality can be taken with $g=0$, i.e. $f(p)\ge f(x)$ for every $p$, which is exactly the statement that $x$ is a global minimizer. It extends the differentiable condition $\nabla f(x)=0$ (Fermat's rule) to nonsmooth convex functions and underlies the subgradient method and proximal operators.

9. References

  • Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
  • Hiriart-Urruty, J.-B., & Lemaréchal, C. (2001). Fundamentals of Convex Analysis. Springer.
  • Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
  • Beck, A. (2017). First-Order Methods in Optimization. SIAM.
  • Wikipedia: Subderivative (English)