44.02.05 · optimization-control / 02-convex-duality-kkt

Subdifferential Calculus: Sum Rule, Chain Rule, and Danskin's Theorem

shipped3 tiersLean: none

Anchor (Master): Rockafellar 1970 Convex Analysis (Princeton) §23-§25, §27; Hiriart-Urruty & Lemaréchal 1993 Convex Analysis and Minimization Algorithms (Springer) Ch. VI, Ch. D; Bertsekas 1971/2009 Convex Optimization Theory on the Danskin theorem

Intuition Beginner

Picture a smooth valley floor. At any point there is one definite downhill direction and one tangent line that just touches the curve. Calculus calls the slope of that line the derivative, and it is a single number. Now bend the floor into a sharp V, like the graph of the absolute-value function. Right at the kink, there is no single tangent line. Instead there is a whole fan of straight lines you can lay underneath the corner, each one touching only at the tip and staying below the curve everywhere else. The set of all their slopes is the subdifferential.

So the subdifferential is the honest replacement for the derivative when a convex function has a corner. Where the function is smooth it gives back the usual single slope. Where there is a kink it gives an entire interval of allowed slopes. Each allowed slope defines a supporting line that under-estimates the function everywhere, which is exactly the property that makes the corner usable.

Why care about corners? Because the functions we most want to minimise are full of them. The largest of several costs, the absolute error, the penalty that switches on at a threshold — all have kinks precisely at the interesting points, often right at the optimum. A method that only knows about smooth slopes stalls there. The subdifferential lets us keep going.

There is one beautifully simple payoff. For a smooth bowl, the lowest point is where the slope is zero. For a convex function with corners, the lowest point is where zero is one of the allowed slopes — where the flat line is among the supporting lines you can slide under the graph. That single rule, "zero belongs to the fan of slopes," tells you that you have found the minimum, kink or no kink.

The rest of this unit is bookkeeping: rules for finding the fan of slopes of a sum, of a stretched-and-shifted function, and of a maximum, so you never have to draw the picture.

Visual Beginner

Figure: the V-shaped graph of the absolute-value function. At the kink at the origin a whole fan of straight lines is drawn, each passing through the origin and lying entirely on or below the V. The shallowest has slope minus one (matching the left arm), the steepest has slope plus one (matching the right arm), and every slope in between is allowed. A side panel shows a smooth bowl where only a single tangent line fits, so the fan collapses to one slope.

   f(x) = |x|                         smooth case: one tangent
      \         /                          .  *  .
       \       /                         *    |    *
        \     /                         *     |     *
   ......\.../......  <- fan of           *   |   *
     line slope -1     supporting          *.....*
     ...  line slope +1   lines at          one slope only:
        \ / kink            the kink         the derivative
   ------V------- x      slopes fill        ----------------
       origin            [-1, +1]           f smooth -> df = {f'(x)}
   any line with slope in [-1,1]
   stays on or below the V

Worked example Beginner

Take the absolute-value function $f (x) = ∣ x ∣$ and find its fan of allowed slopes at three places by hand.

Step 1. A point on the right arm. At $x = 2$ the graph is the straight line $y = x$ , smooth, with slope $1$ . A supporting line must touch at $(2, 2)$ and stay below the V; only the line of slope $1$ does this. So the only allowed slope is $1$ .

Step 2. A point on the left arm. At $x = - 3$ the graph is the line $y = - x$ , smooth, with slope $- 1$ . The same reasoning gives a single allowed slope, $- 1$ .

Step 3. The kink. At $x = 0$ the value is $f (0) = 0$ . A line through the origin with slope $m$ is $y = m x$ ; it stays on or below $∣ x ∣$ exactly when $m x \leq ∣ x ∣$ for every $x$ , which holds precisely for $- 1 \leq m \leq 1$ . So the fan of allowed slopes at the kink is the whole interval from $- 1$ to $1$ .

Step 4. Read off the minimum. The lowest point of $∣ x ∣$ is at $x = 0$ . Check the rule: is the flat slope $0$ among the allowed slopes at $x = 0$ ? The allowed slopes there run from $- 1$ to $1$ , and $0$ is inside, so yes. The rule correctly flags $x = 0$ as the minimum.

What this tells us. Away from the kink the subdifferential is just the ordinary slope, a single number. At the kink it spreads into an interval, and the minimum is detected by the flat slope $0$ sitting inside that interval — the corner-friendly version of "set the derivative to zero."

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $f : R^{n} \to (- \infty, + \infty]$ is proper convex (notation from 44.01.01 and 37.07.03): $dom f = {x : f (x) < + \infty}$ is nonempty and $f$ never equals $- \infty$ . The pairing is $⟨ g, d ⟩ = \sum_{i} g_{i} d_{i}$ .

Definition (subgradient and subdifferential). A vector $g \in R^{n}$ is a subgradient of $f$ at $x \in dom f$ if

f (y) \geq f (x) + ⟨ g, y - x ⟩ for all y \in R^{n} .

The subdifferential $\partial f (x)$ is the set of all such $g$ ; it is empty for $x \in / dom f$ , and by convention also where no subgradient exists. Geometrically, $g \in \partial f (x)$ iff the affine function $y \mapsto f (x) + ⟨ g, y - x ⟩$ is a supporting (under-estimating) hyperplane to $epi f$ at $(x, f (x))$ ^{[Rockafellar §23]}. As an intersection of the closed halfspaces ${g : ⟨ g, y - x ⟩ \leq f (y) - f (x)}$ over $y$ , the set $\partial f (x)$ is always closed and convex.

Definition (directional derivative). The one-sided directional derivative of $f$ at $x \in dom f$ in direction $d$ is

f^{'} (x; d) = t ↓ 0 lim \frac{f ( x + t d ) - f ( x )}{t} .

For convex $f$ the difference quotient is nondecreasing in $t > 0$ , so the limit exists in $[- \infty, + \infty]$ and equals the infimum over $t > 0$ . The map $d \mapsto f^{'} (x; d)$ is positively homogeneous and convex — a sublinear function — whenever $x \in relint (dom f)$ (relative interior, 44.01.02).

Definition (Fermat / stationarity). A point $x^{*}$ is a (global) minimiser of $f$ iff $0 \in \partial f (x^{*})$ : the zero vector is a subgradient, i.e. the flat affine function under-estimates $f$ everywhere.

A normal example fixes the picture: for $f (x) = ∥ x ∥_{2}$ on $R^{n}$ , the subdifferential is $\partial f (x) = {x /∥ x ∥}$ for $x \neq = 0$ and $\partial f (0) = {g : ∥ g ∥ \leq 1}$ , the closed unit ball — a single gradient away from the kink, a fat convex body at it.

Counterexamples to common slips

The subdifferential can be empty on the boundary of the domain. For $f (x) = - x$ on $[0, \infty)$ (extended by $+ \infty$ for $x < 0$ ), at $x = 0$ the difference quotient $f^{'} (0; 1) = lim_{t ↓ 0} (- t) / t = - \infty$ , so no finite supporting slope exists and $\partial f (0) = \emptyset$ . Nonemptiness is guaranteed on $relint (dom f)$ , not on all of $dom f$ .
The sum rule needs a qualification. With $f = ι_{[0, \infty)}$ and $g = ι_{(- \infty, 0]}$ (indicators of the two halflines), $f + g = ι_{{0}}$ , so $\partial (f + g) (0) = R$ , while $\partial f (0) + \partial g (0) = (- \infty, 0] + [0, \infty) = R$ here — the inclusion $\partial f + \partial g \subseteq \partial (f + g)$ is automatic, but equality can fail when relative interiors of the domains do not meet.
$\nabla f$ exists pointwise does not mean $f$ is smooth as a map. A convex function differentiable at every point of an open set is automatically $C^{1}$ there; but a single-point gradient does not control nearby behaviour. Differentiability at $x$ is equivalent to $\partial f (x)$ being a singleton, not to $f$ being smooth near $x$ .

Key theorem with proof Intermediate+

The structural core is the identification of the subdifferential as the set whose support function is the directional derivative, from which compactness on the relative interior and the Fermat rule both follow.

Theorem (support-function formula and the Moreau-Rockafellar sum rule). Let $f, g$ be proper convex on $R^{n}$ .

(i) (Directional-derivative duality.) For $x \in relint (dom f)$ , the set $\partial f (x)$ is nonempty, compact, and convex, and the directional derivative is its support function:

f^{'} (x; d) = g \in \partial f (x) max ⟨ g, d ⟩ for all d \in R^{n} .

(ii) (Fermat's rule.) $x^{*}$ minimises $f$ if and only if $0 \in \partial f (x^{*})$ .

(iii) (Sum rule.) Always $\partial f (x) + \partial g (x) \subseteq \partial (f + g) (x)$ . If $relint (dom f) \cap relint (dom g) \neq = \emptyset$ , then for all $x$ ,

\partial (f + g) (x) = \partial f (x) + \partial g (x) .

Proof of (i). Fix $x \in relint (dom f)$ . The function $p (d) := f^{'} (x; d)$ is sublinear (positively homogeneous and convex) and finite on the subspace parallel to $aff (dom f)$ , because at a relative-interior point the difference quotients are bounded below. A finite sublinear function is the support function of a unique nonempty compact convex set $C$ , namely $C = {g : ⟨ g, d ⟩ \leq p (d) \forall d}$ (the subdifferential of $p$ at $0$ ; this is the support-function/sublinearity correspondence of 44.01.01). It remains to identify $C$ with $\partial f (x)$ . If $g \in \partial f (x)$ , then for every $d$ and $t > 0$ , $f (x + t d) \geq f (x) + t ⟨ g, d ⟩$ , so dividing by $t$ and letting $t ↓ 0$ gives $p (d) \geq ⟨ g, d ⟩$ ; hence $g \in C$ . Conversely if $g \in C$ , then $⟨ g, d ⟩ \leq p (d) \leq (f (x + d) - f (x))$ for $d = y - x$ (using monotonicity of the quotient at $t = 1$ ), which is the subgradient inequality; hence $g \in \partial f (x)$ . So $\partial f (x) = C$ , nonempty compact convex, with support function $p$ . $□$

Proof of (ii). By definition $0 \in \partial f (x^{*})$ means $f (y) \geq f (x^{*}) + ⟨ 0, y - x^{*} ⟩ = f (x^{*})$ for all $y$ , which is exactly the statement that $x^{*}$ is a global minimiser. There is no separate local-versus-global gap: the subgradient inequality is global. $□$

Proof of (iii). The inclusion is immediate: if $g_{1} \in \partial f (x)$ and $g_{2} \in \partial g (x)$ , adding the two subgradient inequalities gives $(f + g) (y) \geq (f + g) (x) + ⟨ g_{1} + g_{2}, y - x ⟩$ , so $g_{1} + g_{2} \in \partial (f + g) (x)$ . For the reverse inclusion under the qualification, take $h \in \partial (f + g) (x)$ . Consider in $R^{n + 1}$ the two convex sets

A = {(y, s) : s \geq f (y) - f (x) - ⟨ h, y - x ⟩}, B = {(y, s) : s \leq g (x) - g (y)},

the (shifted) epigraph of $f - ⟨ h, \cdot ⟩$ and the (shifted) hypograph of $g$ . The subgradient inequality $h \in \partial (f + g) (x)$ says $f (y) - f (x) - ⟨ h, y - x ⟩ \geq g (x) - g (y)$ , i.e. $int A$ and $B$ do not overlap; the relative-interior qualification makes the relative interiors of the projections meet, so the proper separation theorem (geometric Hahn-Banach, 02.11.02, in the finite-dimensional relative-interior form) supplies a hyperplane. Its normal, normalised in the last coordinate, is a vector $g_{2}$ with $g (y) \geq g (x) + ⟨ g_{2}, y - x ⟩$ for all $y$ (so $g_{2} \in \partial g (x)$ ) and $f (y) - ⟨ h, y ⟩ \geq f (x) - ⟨ h, x ⟩ + ⟨ - g_{2}, y - x ⟩$ , i.e. $h - g_{2} \in \partial f (x)$ . Then $h = (h - g_{2}) + g_{2} \in \partial f (x) + \partial g (x)$ . $□$

Bridge. This theorem builds toward the entire first-order algorithmic layer and appears again in the convergence analysis of subgradient and proximal methods 44.06.01, where each step evaluates an element of $\partial f$ . This is exactly the nonsmooth completion of the first-order characterisation of convexity from 44.01.01: where smoothness gave a single supporting hyperplane $\nabla f (x)$ , the subdifferential gives the whole set of them, and the central insight is that this set is precisely the one whose support function is the directional derivative. The Fermat rule generalises the smooth condition $\nabla f (x^{*}) = 0$ to $0 \in \partial f (x^{*})$ , and the sum rule is dual to the conjugate-of-a-sum (infimal-convolution) identity, since $\partial f (x) = {g : f (x) + f^{*} (g) = ⟨ g, x ⟩}$ ties subgradients to the Fenchel-Young equality of 37.07.03. Putting these together, separation supplies the multiplier in the sum rule exactly as it supplied the supporting hyperplane behind biconjugation, so the constrained-optimisation calculus rests on one geometric fact.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Use the sum rule and Exercise 2 to derive the constrained optimality condition: $x^{*}$ minimises a convex $f$ over a closed convex set $C$ (with $relint (dom f) \cap relint C \neq = \emptyset$ ) iff $0 \in \partial f (x^{*}) + N_{C} (x^{*})$ .

Hint

Minimising $f$ over $C$ is the same as minimising $f + ι_{C}$ over $R^{n}$ ; apply Fermat then the sum rule.

Answer

The constrained problem $min_{x \in C} f (x)$ equals the unconstrained $min_{x} (f + ι_{C}) (x)$ . By Fermat (Key theorem (ii)), $x^{*}$ is optimal iff $0 \in \partial (f + ι_{C}) (x^{*})$ . The qualification lets the sum rule (iii) apply: $\partial (f + ι_{C}) (x^{*}) = \partial f (x^{*}) + \partial ι_{C} (x^{*}) = \partial f (x^{*}) + N_{C} (x^{*})$ . Hence optimality is $0 \in \partial f (x^{*}) + N_{C} (x^{*})$ , i.e. some $- g \in N_{C} (x^{*})$ with $g \in \partial f (x^{*})$ : the negative subgradient points along an outward normal. This is the variational-inequality form of constrained optimality.

Exercise 6 (hard, symbolic).

Let $f_{1}, \dots, f_{m}$ be convex and differentiable, and $F (x) = max_{i} f_{i} (x)$ . Let $I (x) = {i : f_{i} (x) = F (x)}$ be the active set. Prove $\partial F (x) = conv {\nabla f_{i} (x) : i \in I (x)}$ .

Hint

Show $F^{'} (x; d) = max_{i \in I (x)} ⟨ \nabla f_{i} (x), d ⟩$ , then identify the set whose support function this is.

Answer

For small $t > 0$ only active indices can attain the max, so $F (x + t d) = max_{i \in I (x)} f_{i} (x + t d) + o (t)$ , and dividing by $t$ , $F^{'} (x; d) = max_{i \in I (x)} ⟨ \nabla f_{i} (x), d ⟩$ . The right side is the support function of the finite set ${\nabla f_{i} (x) : i \in I (x)}$ , hence of its convex hull $K = conv {\nabla f_{i} (x)}$ . By the support-function formula (Key theorem (i)), the directional derivative is the support function of $\partial F (x)$ ; a compact convex set is determined by its support function, so $\partial F (x) = K$ . This is the smooth case of Danskin's theorem.

Exercise 8 (hard, symbolic).

Give an example of two proper convex functions $f, g$ on $R$ with $\partial (f + g) (x_{0}) \neq = \partial f (x_{0}) + \partial g (x_{0})$ at some point, and explain which hypothesis of the sum rule fails.

Hint

Use indicators of two convex sets whose interiors are disjoint but which touch at one point.

Answer

Take $f = ι_{(- \infty, 0]}$ and $g = ι_{[0, \infty)}$ . Then $dom f = (- \infty, 0]$ and $dom g = [0, \infty)$ meet only at $0$ , so $relint (dom f) \cap relint (dom g) = (- \infty, 0) \cap (0, \infty) = \emptyset$ — the qualification fails. Here $f + g = ι_{{0}}$ , so $\partial (f + g) (0) = R$ (every slope supports a single point). Meanwhile $\partial f (0) = N_{(- \infty, 0]} (0) = [0, \infty)$ and $\partial g (0) = N_{[0, \infty)} (0) = (- \infty, 0]$ , so $\partial f (0) + \partial g (0) = R$ here — equality holds by accident in dimension one. To force strict failure, embed in $R^{2}$ with $f = ι_{{x_{2} \leq 0}}$ touching $g = ι_{{x_{2} \geq 0, x_{1} \leq 0}}$ ... the clean one-dimensional lesson is that without the relative-interior overlap the proof breaks (no proper separating hyperplane is guaranteed), and in higher dimension the inclusion is then generally strict.

Advanced results Master

Danskin's theorem: differentiating a parametric maximum

Let $ϕ : R^{n} \times U \to R$ with $U$ compact, $ϕ (\cdot, u)$ convex for each $u$ , $ϕ (x, \cdot)$ continuous, and define $F (x) = max_{u \in U} ϕ (x, u)$ . Then $F$ is convex, and with the maximiser set $U (x) = {u : ϕ (x, u) = F (x)}$ ,

\partial F (x) = conv u \in U (x) ⋃ \partial_{x} ϕ (x, u) .

When each $ϕ (\cdot, u)$ is differentiable and the maximiser $u (x)$ is unique, $F$ is differentiable with $\nabla F (x) = \nabla_{x} ϕ (x, u (x))$ — one differentiates through the maximisation, evaluating the gradient at the active maximiser and ignoring its dependence on $x$ . The directional-derivative form $F^{'} (x; d) = max_{u \in U (x)} ⟨ \nabla_{x} ϕ (x, u), d ⟩$ is the operative statement for descent methods on minimax problems and for the value functions of two-player games ^{[Danskin 1966]}. The finite-index special case is Exercise 6; the integral analogue (max over a measure) underlies the subdifferential of expected-value and risk functionals.

The Moreau-Rockafellar sum rule as the engine of duality

The sum rule $\partial (f + g) = \partial f + \partial g$ is the differential shadow of the Fenchel duality theorem: under the relative-interior qualification, $in f_{x} (f (x) + g (x)) = sup_{λ} (- f^{*} (λ) - g^{*} (- λ))$ , and a primal-dual optimal pair $(x^{*}, λ^{*})$ satisfies $λ^{*} \in \partial f (x^{*})$ and $- λ^{*} \in \partial g (x^{*})$ ^{[Rockafellar §31]}. Writing the constrained program $min {f_{0} (x) : f_{i} (x) \leq 0}$ as $min_{x} (f_{0} + ι_{{f_{i} \leq 0}})$ and applying the sum rule plus the chain rule to the constraint indicator reproduces the KKT system: $0 \in \partial f_{0} (x^{*}) + \sum_{i} λ_{i}^{*} \partial f_{i} (x^{*})$ with $λ_{i}^{*} \geq 0$ and complementary slackness, the constraint qualification being precisely the relative-interior (Slater) condition that lets the sum rule fire. The Fermat rule of Exercise 3 specialises this to a single feasible-set indicator 44.02.04.

Differentiability, the gradient, and Alexandrov's theorem

A convex function on an open set is differentiable at $x$ iff $\partial f (x)$ is a singleton, and then $\partial f (x) = {\nabla f (x)}$ ^{[Rockafellar §25]}. By Rademacher's theorem a finite convex function is differentiable Lebesgue-almost everywhere; the gradient map $x \mapsto \nabla f (x)$ is continuous on the (open, full-measure) set of differentiability, so a convex function on an open set is automatically $C^{1}$ where it is differentiable. Sharper, Alexandrov's theorem gives a second-order Taylor expansion with a symmetric positive-semidefinite Hessian almost everywhere, even when $f$ is not twice differentiable in the classical sense. The set-valued map $\partial f$ is maximal monotone: $⟨ g_{1} - g_{2}, x_{1} - x_{2} ⟩ \geq 0$ for $g_{i} \in \partial f (x_{i})$ , and no monotone relation strictly contains its graph — the property that the resolvent $(I + t \partial f)^{- 1}$ (the proximal map) is single-valued and nonexpansive, the analytic foundation of proximal algorithms.

Subdifferential of the conjugate and the inverse correspondence

For closed proper convex $f$ , $\partial f^{*} = (\partial f)^{- 1}$ as relations on $R^{n} \times R^{n}$ (Exercise 7). Single-valuedness of $\partial f$ at $x$ — differentiability of $f$ — corresponds to $\partial f^{*}$ being constant along an exposed face, i.e. strict convexity of $f^{*}$ in that direction, and vice versa; differentiability of $f$ is dual to strict convexity of $f^{*}$ . When $f$ is a Legendre function (essentially smooth and essentially strictly convex, 37.07.03), $\partial f = {\nabla f}$ everywhere on the interior of its domain and the inverse map is $\nabla f^{*} = (\nabla f)^{- 1}$ , recovering the classical Legendre transform as the smooth core of the subdifferential calculus.

Synthesis. The subdifferential is exactly the set whose support function is the directional derivative, and this single identification generalises the gradient to the nonsmooth convex world while keeping every first-order fact intact: the Fermat rule $0 \in \partial f (x^{*})$ is exactly the corner-aware version of $\nabla f (x^{*}) = 0$ , and the sum, chain, and max rules are the calculus that makes it computable. The central insight is that all three rules are one separation theorem in disguise — the relative-interior qualification is what guarantees the proper separating hyperplane whose normal is the missing multiplier, so the Moreau-Rockafellar sum rule is dual to Fenchel duality and the chain rule is dual to the conjugate-of-a-composition formula. The foundational reason these matter is that $\partial f^{*} = (\partial f)^{- 1}$ ties the whole apparatus to the conjugacy of 37.07.03: subgradient inversion is conjugate inversion, the proximal map is a resolvent of a maximal monotone operator, and putting these together the engine that drives subgradient and proximal methods 44.06.01 and the KKT multiplier theory 44.02.04 appears again in every nonsmooth optimisation algorithm, with Danskin's theorem the bridge from static convexity to the parametric value functions of games and control.

Full proof set Master

Proposition 1 (nonemptiness and local boundedness on the relative interior). If $f$ is proper convex and $x \in relint (dom f)$ , then $\partial f (x)$ is nonempty, convex, and compact.

Proof. Convexity and closedness hold for any $x$ (intersection of halfspaces). For nonemptiness, $(x, f (x))$ is a boundary point of the convex set $epi f$ , which has nonempty interior relative to its affine hull; the supporting-hyperplane theorem 44.01.01 (a finite-dimensional consequence of separation, 02.11.02) supplies a supporting hyperplane to $epi f$ at $(x, f (x))$ . Because $x$ is in the relative interior of $dom f$ , this hyperplane is non-vertical (its last coordinate is nonzero), so normalising the last coordinate to $1$ yields $(g, - 1)$ with $f (y) \geq f (x) + ⟨ g, y - x ⟩$ , i.e. $g \in \partial f (x)$ . Boundedness: by the support-function formula (Key theorem (i)) and finiteness of $f^{'} (x; d)$ for all $d$ in the parallel subspace, $sup_{g \in \partial f (x)} ⟨ g, d ⟩ = f^{'} (x; d) < \infty$ for every unit $d$ , so $\partial f (x)$ is bounded; closed and bounded in $R^{n}$ gives compact. $□$

Proposition 2 (chain rule for a linear map). Let $f$ be proper convex on $R^{n}$ , $A : R^{m} \to R^{n}$ linear, and $h = f \circ A$ . Then $A^{*} \partial f (A x) \subseteq \partial h (x)$ always, with equality whenever $range (A) \cap relint (dom f) \neq = \emptyset$ .

Proof. The inclusion is the computation of Exercise 5. For equality, let $u \in \partial h (x)$ , so $f (A w) \geq f (A x) + ⟨ u, w - x ⟩$ for all $w$ . Define on $range (A)$ the functional that we wish to extend; concretely, consider the convex function $k (y) = f (y)$ restricted to the affine flat $A x + range (A)$ and the linear functional $ℓ$ on $range (A)$ given by $ℓ (A w - A x) = ⟨ u, w - x ⟩$ (well-defined modulo $ker A$ : if $A w = A x$ then $h (w) = h (x)$ and the subgradient inequality forces $⟨ u, w - x ⟩ \leq 0$ and, by symmetry $w \leftrightarrow 2 x - w$ , equality, so $ℓ$ depends only on $A w - A x$ ). The qualification places $A x$ in the relative interior of $dom f$ along $range (A)$ , so the one-step separation/extension (the sum-rule separation applied to $f$ and $ι_{A x + range A}$ ) produces $g \in \partial f (A x)$ extending $ℓ$ , meaning $⟨ g, A w - A x ⟩ = ⟨ u, w - x ⟩$ , i.e. $A^{*} g = u$ . Hence $u \in A^{*} \partial f (A x)$ . $□$

Proposition 3 (Danskin's theorem, finite-index form). Let $f_{1}, \dots, f_{m}$ be proper convex and finite near $x$ , $F = max_{i} f_{i}$ , and $I (x) = {i : f_{i} (x) = F (x)}$ . Then $F$ is convex and $\partial F (x) = conv ⋃_{i \in I (x)} \partial f_{i} (x)$ .

Proof. Convexity of $F$ : a pointwise maximum of convex functions has epigraph $⋂_{i} epi f_{i}$ , an intersection of convex sets, hence convex 44.01.01. For the subdifferential, first compute the directional derivative. For small $t > 0$ and any inactive $j \in / I (x)$ , continuity gives $f_{j} (x + t d) < F (x) \leq F (x + t d)$ , so the max over $t ↓ 0$ is governed by active indices: $F^{'} (x; d) = max_{i \in I (x)} f_{i}^{'} (x; d)$ . By the support-function formula each $f_{i}^{'} (x; d) = max_{g \in \partial f_{i} (x)} ⟨ g, d ⟩$ is the support function of $\partial f_{i} (x)$ , and a maximum of support functions is the support function of the convex hull of the union: $max_{i \in I (x)} sup_{g \in \partial f_{i} (x)} ⟨ g, d ⟩ = sup_{g \in K} ⟨ g, d ⟩$ with $K = conv ⋃_{i \in I (x)} \partial f_{i} (x)$ (the hull is compact as a convex hull of finitely many compact sets in $R^{n}$ ). Thus $F^{'} (x; \cdot)$ is the support function of $K$ , and also of $\partial F (x)$ by Key theorem (i); two compact convex sets with the same support function coincide, so $\partial F (x) = K$ . $□$

Proposition 4 ( $\partial f$ is maximal monotone). For proper convex lsc $f$ , the graph ${(x, g) : g \in \partial f (x)}$ is monotone, and is not properly contained in the graph of any monotone relation.

Proof. Monotonicity: for $g_{i} \in \partial f (x_{i})$ , the two subgradient inequalities $f (x_{2}) \geq f (x_{1}) + ⟨ g_{1}, x_{2} - x_{1} ⟩$ and $f (x_{1}) \geq f (x_{2}) + ⟨ g_{2}, x_{1} - x_{2} ⟩$ add to $0 \geq ⟨ g_{1} - g_{2}, x_{2} - x_{1} ⟩$ , i.e. $⟨ g_{1} - g_{2}, x_{1} - x_{2} ⟩ \geq 0$ . For maximality, suppose $(x_{0}, g_{0})$ is monotonically related to every $(x, g)$ in the graph but is not itself in it. Consider the Moreau-Yosida proximal point: the strongly convex function $y \mapsto f (y) + \frac{1}{2} ∥ y - (x_{0} + g_{0}) ∥^{2}$ has a unique minimiser $\overset{x}{ˉ}$ , characterised by Fermat as $0 \in \partial f (\overset{x}{ˉ}) + (\overset{x}{ˉ} - x_{0} - g_{0})$ , i.e. $x_{0} + g_{0} - \overset{x}{ˉ} \in \partial f (\overset{x}{ˉ})$ . Set $\overset{g}{ˉ} = x_{0} + g_{0} - \overset{x}{ˉ}$ , so $(\overset{x}{ˉ}, \overset{g}{ˉ})$ is in the graph. Monotonicity of the candidate against $(\overset{x}{ˉ}, \overset{g}{ˉ})$ gives $⟨ g_{0} - \overset{g}{ˉ}, x_{0} - \overset{x}{ˉ} ⟩ \geq 0$ . But $g_{0} - \overset{g}{ˉ} = \overset{x}{ˉ} - x_{0}$ , so this reads $- ∥ \overset{x}{ˉ} - x_{0} ∥^{2} \geq 0$ , forcing $\overset{x}{ˉ} = x_{0}$ and then $\overset{g}{ˉ} = g_{0}$ , so $(x_{0}, g_{0}) = (\overset{x}{ˉ}, \overset{g}{ˉ}) \in \partial f$ , a contradiction. Hence the graph is maximal. $□$

Connections Master

The Fenchel-Young equality of 37.07.03 is the source of the conjugacy inversion $g \in \partial f (x) ⟺ x \in \partial f^{*} (g)$ : subgradients of $f$ and of its conjugate $f^{*}$ are inverse relations, so the subdifferential calculus and the Legendre-Fenchel transform are two descriptions of one duality, and the smooth Legendre transform is recovered when $f$ is a Legendre function with $\partial f = {\nabla f}$ .
The supporting-hyperplane and separation theory of 44.01.01 and 02.11.02 is the single geometric engine behind nonemptiness of $\partial f$ on the relative interior, the Moreau-Rockafellar sum rule, and the chain rule; each "equality under a relative-interior qualification" is one application of proper separation, the same construction that underlies biconjugation.
The relative interior and Carathéodory material of 44.01.02 supplies the precise qualification condition $relint (dom f) \cap relint (dom g) \neq = \emptyset$ under which the sum rule holds with equality, and Carathéodory bounds the number of active subgradients needed to express any element of $\partial (max_{i} f_{i})$ as a convex combination.
The Fermat rule $0 \in \partial f (x^{*})$ and the sum/chain calculus are exactly what the subgradient and proximal methods of 44.06.01 evaluate, while the constrained form $0 \in \partial f_{0} (x^{*}) + \sum_{i} λ_{i}^{*} \partial f_{i} (x^{*})$ is the KKT system whose multiplier existence rests on the Farkas/separation theory of 44.02.04.

Historical & philosophical context Master

The subgradient inequality and the systematic calculus of subdifferentials were developed in the early 1960s by Jean-Jacques Moreau and R. Tyrrell Rockafellar, working in parallel on the variational and convex-analytic sides. Moreau's Fonctionnelles convexes lectures ^{[Moreau 1966]} at the Collège de France introduced the proximal map and the inf-convolution regularisation now bearing his name, and established the subdifferential as a maximal monotone operator whose resolvent is the proximal mapping. Rockafellar's Convex Analysis (Princeton, 1970) ^{[Rockafellar §23, §25]} gave the definitive account of §23-§25: the directional-derivative duality, the differentiability characterisation, and the sum and chain rules under relative-interior qualifications, organised around the conjugacy inversion $\partial f^{*} = (\partial f)^{- 1}$ .

The max-rule for differentiating a parametric supremum was proved in its modern generality by John M. Danskin ^{[Danskin 1966]} in his 1966 SIAM Journal on Applied Mathematics paper on the theory of max-min, motivated by military allocation games; it had antecedents in the minimax work of von Neumann and in Valentine's and Fenchel's earlier convex-analytic notes. The encyclopaedic treatment of the calculus, with the support-function and maximal-monotone viewpoints made central, is due to Hiriart-Urruty and Lemaréchal ^{[Hiriart-Urruty & Lemaréchal 1993]} in Convex Analysis and Minimization Algorithms (Springer, 1993), the source that tied the subdifferential calculus to the bundle and proximal algorithms it now serves.

Bibliography Master

@book{rockafellar1970convex,
  author    = {Rockafellar, R. Tyrrell},
  title     = {Convex Analysis},
  series    = {Princeton Mathematical Series},
  number    = {28},
  publisher = {Princeton University Press},
  year      = {1970}
}

@article{danskin1966maxmin,
  author  = {Danskin, John M.},
  title   = {The theory of max-min, with applications},
  journal = {SIAM Journal on Applied Mathematics},
  volume  = {14},
  number  = {4},
  pages   = {641--664},
  year    = {1966}
}

@book{hiriarturruty1993convex,
  author    = {Hiriart-Urruty, Jean-Baptiste and Lemar\'echal, Claude},
  title     = {Convex Analysis and Minimization Algorithms I},
  series    = {Grundlehren der mathematischen Wissenschaften},
  number    = {305},
  publisher = {Springer},
  year      = {1993}
}

@book{hiriarturruty2001fundamentals,
  author    = {Hiriart-Urruty, Jean-Baptiste and Lemar\'echal, Claude},
  title     = {Fundamentals of Convex Analysis},
  series    = {Grundlehren Text Editions},
  publisher = {Springer},
  year      = {2001}
}

@incollection{moreau1967fonctionnelles,
  author    = {Moreau, Jean-Jacques},
  title     = {Fonctionnelles convexes},
  booktitle = {S\'eminaire Jean Leray sur les \'equations aux d\'eriv\'ees partielles},
  publisher = {Coll\`ege de France},
  year      = {1966--1967}
}

@book{bertsekas2009convex,
  author    = {Bertsekas, Dimitri P.},
  title     = {Convex Optimization Theory},
  publisher = {Athena Scientific},
  year      = {2009}
}

Prerequisites

44.01.01
44.01.02
37.07.03
02.11.02

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.1.3 and the EE364b subgradient notes — the supporting-line picture
intermediate: Rockafellar 1970 Convex Analysis (Princeton) §23-§25; Hiriart-Urruty & Lemaréchal 2001 Fundamentals of Convex Analysis (Springer) Ch. D
master: Rockafellar 1970 Convex Analysis (Princeton) §23-§25, §27; Hiriart-Urruty & Lemaréchal 1993 Convex Analysis and Minimization Algorithms (Springer) Ch. VI, Ch. D; Bertsekas 1971/2009 Convex Optimization Theory on the Danskin theorem

References

Rockafellar, R. T. — Convex Analysis (Princeton University Press, 1970) · §23 subgradients and directional derivatives; §24 differentiability; §25 the calculus of subgradients (sum and chain rules); §27 the maximum of convex functions
Hiriart-Urruty, J.-B. & Lemaréchal, C. — Convex Analysis and Minimization Algorithms I-II (Springer, 1993) · Ch. VI subdifferentiability; Ch. D the calculus of subdifferentials and the max-rule
Hiriart-Urruty, J.-B. & Lemaréchal, C. — Fundamentals of Convex Analysis (Springer, 2001) · Ch. D subdifferential calculus; the Moreau-Rockafellar sum theorem and Danskin's theorem
Danskin, J. M. — The theory of max-min, with applications · SIAM Journal on Applied Mathematics 14 (1966), 641-664
Moreau, J. J. — Fonctionnelles convexes · Séminaire Jean Leray sur les équations aux dérivées partielles, Collège de France (1966-1967)

Estimated time

beginner: 18m
intermediate: 45m
master: 80m