Subgradient Calculus
Rules for computing subdifferentials of sums, maxima, and compositions let algorithms find a valid descent direction even at nondifferentiable points.
The subdifferential
The subdifferential of a convex function f at x, written df(x), is the set of all vectors g satisfying the supporting-line inequality f(y) >= f(x) + g^T(y - x) for every y. Geometrically each subgradient defines a line (or hyperplane) that touches the graph at x and lies below it everywhere. At smooth points the set collapses to the single gradient; at a kink it is an interval or polytope of slopes.
Core rules
Subdifferentials obey a calculus that mirrors ordinary differentiation. The subdifferential of a sum is the sum (Minkowski sum) of subdifferentials. Nonnegative scaling scales the set. For a pointwise maximum of functions, the subdifferential at x is the convex hull of the gradients of whichever functions attain the maximum there. For a composition with an affine map A x + b, the chain rule gives A^T df(A x + b).
- Sum: d(f+h)(x) = df(x) + dh(x)
- Max: d(max f_i)(x) = conv{ grad f_i(x) : f_i(x) is the max }
- Affine composition: d(f(Ax+b)) = A^T df(Ax+b)
- |x| at 0: the interval [-1, 1]
Worked example
Consider f(x) = max(x, -2x). For x > 0 the slope is 1; for x < 0 the slope is -2; at x = 0 both branches tie, so the subdifferential is the whole interval [-2, 1]. Zero lies in that interval, which is exactly the optimality condition: a convex function is minimized precisely where 0 is a subgradient.
The optimality condition
The single most important consequence is the rule that x* minimizes a convex f if and only if 0 belongs to df(x*). This replaces the smooth condition grad f = 0 and covers kinks, absolute values, and hinge losses. It is the foundation of the KKT conditions for nonsmooth constrained problems and of the fixed-point view behind proximal methods.
In practice an algorithm needs only one subgradient, not the whole set, so these rules are applied to pick a convenient member, for example choosing sign(0) = 0 for the L1 term.