Subgradient

analysis optimisation convex-analysis

Definition

Subgradient

Let $f:X\to \mathbb{R}$ be a convex function on a convex set $X\subseteq {\mathbb{R}}^d$, and let $x_0\in X$. A subgradient of $f$ at $x_0$ is a vector $g\in {\mathbb{R}}^d$ such that

$$f(x)\ge f(x_0)+g^{\top }(x-x_0)\text{for all }x\in X.$$

The affine function $x\mapsto f(x_0)+g^{\top }(x-x_0)$ is a global lower supporting plane for $f$ at $x_0$. The set of all such vectors is the subdifferential $\partial f(x_0)$.

Derivation

For a differentiable convex function, the tangent line at $x_0$ lies below the whole function:

$$f(x)\ge f(x_0)+\nabla f(x_0{)}^{\top }(x-x_0).$$

The gradient is therefore the slope of a global affine lower bound. At a corner, there is no single tangent slope, but there may be many supporting slopes. A subgradient keeps exactly the part of the gradient that survives the corner: it is any slope whose affine line still stays below the function everywhere.

This is why the formula is forced. Given convexity, the world is shaped like a bowl; asking for a first-order linear approximation that never cuts through the bowl gives the inequality

$$f(x)\ge f(x_0)+g^{\top }(x-x_0).$$

The vector $g$ is not merely a local hint. It defines a global supporting hyperplane to the epigraph of the function.

Relation to the Gradient

If $f$ is a differentiable convex function at $x_0$, then the subdifferential contains exactly one vector:

$$\partial f(x_0)=\{\nabla f(x_0)\}.$$

So, for differentiable convex functions, the subgradient is the gradient.

The converse intuition needs care. A differentiable non-convex function has a gradient, but that gradient need not satisfy the global subgradient inequality. In that setting, the gradient is a local slope, not necessarily a subgradient in the convex-analysis sense.

Optimisation Meaning

For convex minimisation, a subgradient points toward increase in the linear lower model. Therefore $-g$ is used as a descent direction in subgradient methods.

The optimality condition is especially clean:

$$0\in \partial f(x_0)⟺x_0\text{ is a global minimiser of }f.$$

At a smooth minimum, this says $\nabla f(x_0)=0$. At a corner minimum, it says that the zero vector lies among the supporting slopes.

Example

For $f(x)=|x|$ on $\mathbb{R}$,

$$\partial f(x)=\{\begin{array}{ll}\{-1\}& x<0,\\ [-1,1]& x=0,\\ \{1\}& x>0.\end{array}$$

At the corner $x=0$, every slope between $-1$ and $1$ defines a line that touches the graph at the origin and stays below $|x|$ everywhere.