A convex function may be nonsmooth, may encode constraints by taking the value \(+\infty\), and may have many minimizers. Subgradients replace the gradient without sacrificing global first-order optimality.
Epigraphs and extended-real convexity
Definition. A function \(f:\mathbb R^d\to(-\infty,+\infty]\) is proper if \(\operatorname{dom}f\ne\varnothing\) and it never equals \(-\infty\). It is convex if \[ f(\lambda x+(1-\lambda)y) \le\lambda f(x)+(1-\lambda)f(y) \quad(0\le\lambda\le1). \] Its epigraph is \(\operatorname{epi}f=\{(x,r):r\ge f(x)\}\).
Epigraph characterization. A function \(f\) is convex if and only if \(\operatorname{epi}f\) is a convex subset of \(\mathbb R^{d+1}\). It is lower semicontinuous if and only if its epigraph is closed.
Proof. If \((x,r),(y,s)\in\operatorname{epi}f\), convexity gives \[ f(\lambda x+(1-\lambda)y) \le\lambda f(x)+(1-\lambda)f(y) \le\lambda r+(1-\lambda)s, \] so the convex combination remains in the epigraph. Conversely, apply epigraph convexity to \((x,f(x))\) and \((y,f(y))\). The closed-epigraph equivalence follows from \(\{x:f(x)\le a\}=\{x:(x,a)\in\operatorname{epi}f\}\) together with the sequential characterization of lower semicontinuity in Euclidean space.
The extended-real formulation is structural: the indicator \(\iota_C\) is proper, lower semicontinuous, and convex exactly when \(C\) is nonempty, closed, and convex. Constraints can therefore enter the same calculus as penalties.
Supporting affine functions
Definition. For a proper convex function and \(x\in\operatorname{dom}f\), a vector \(g\in\mathbb R^d\) is a subgradient at \(x\) if \[ f(y)\ge f(x)+\langle g,y-x\rangle \qquad(y\in\mathbb R^d). \] The set of subgradients is the subdifferential \(\partial f(x)\).
Thus \(g\) is the slope of an affine function supporting the epigraph at \((x,f(x))\). If \(f\) is differentiable at an interior point of its domain, then \(\partial f(x)=\{\nabla f(x)\}\). The converse need not hold at boundary points of the domain.
Absolute value. For \(f(t)=|t|\), \[ \partial f(t)= \begin{cases} \{1\},&t>0,\\ [-1,1],&t=0,\\ \{-1\},&t<0. \end{cases} \] Indeed, \(g\in\partial f(0)\) precisely when \(|y|\ge gy\) for every \(y\), which is equivalent to \(|g|\le1\).
Norm and maximum. For the Euclidean norm, \[ \partial\|x\|= \begin{cases} \{x/\|x\|\},&x\ne0,\\ \{g:\|g\|\le1\},&x=0. \end{cases} \] If \(f(x)=\max_{1\le i\le m}f_i(x)\) with differentiable convex \(f_i\), then \[ \partial f(x)= \operatorname{conv}\{\nabla f_i(x):f_i(x)=f(x)\}. \] Only the active functions contribute.
Global optimality from a local inequality
Fermat rule for convex functions. Let \(f\) be proper and convex. A point \(x^\star\in\operatorname{dom}f\) minimizes \(f\) if and only if \[ 0\in\partial f(x^\star). \]
Proof. If \(0\in\partial f(x^\star)\), the subgradient inequality gives \(f(y)\ge f(x^\star)\) for every \(y\). Conversely, if \(x^\star\) minimizes \(f\), then the same inequality holds with \(g=0\), so \(0\in\partial f(x^\star)\).
For minimizing \(f\) over a closed convex set \(C\), apply the rule to \(f+\iota_C\). This yields \[ 0\in\partial f(x^\star)+N_C(x^\star), \] under a standard qualification condition, where the normal cone \(N_C(x^\star)=\{v:\langle v,y-x^\star\rangle\le0\ \forall y\in C\}\). This is the common ancestor of projected optimality and the KKT equations.
Sum and affine-composition rules
Subdifferential calculus. Let \(f,g\) be proper convex functions and suppose \(\operatorname{ri}(\operatorname{dom}f)\cap \operatorname{ri}(\operatorname{dom}g)\ne\varnothing\). Then \[ \partial(f+g)(x)=\partial f(x)+\partial g(x). \] If \(A:\mathbb R^d\to\mathbb R^m\) is linear and \(h\) is proper convex and continuous at some point of \(A(\mathbb R^d)\), then \[ \partial(h\circ A)(x)=A^\top\partial h(Ax). \]
Proof outline. The inclusions from right to left follow immediately by adding or composing subgradient inequalities. For the reverse inclusions, separate the epigraph of the relevant perturbation function from a point strictly below it. The relative interior or continuity assumption prevents an abnormal separating hyperplane with zero vertical component. Normalizing the vertical component produces the required decomposition of the supporting slope.
The qualification is substantive. Without it, the right side can be strictly smaller than the subdifferential of the sum. Later duality and KKT results use the same interiority principle in a more recognizable form.