Rockafellar, §23: Directional Derivatives and Subgradients #
The one-sided directional derivative f'(x; y), the subdifferential ∂f(x), and the duality
x* ∈ ∂f(x) ⟺ f(x) + f*(x*) = ⟨x, x*⟩ that makes the two calculable. This is where Parts II and
III are cashed in: Theorem 23.2 is Corollary 13.2.1 applied to f'(x; ·), Theorem 23.4 is Theorem
7.2 with Corollary 7.4.2, Theorem 23.8 is Theorem 16.4, and Theorem 23.9 is Theorem 16.3.
All sixteen numbered results of §23 are formalized over Rn n = ℝⁿ: Theorems 23.1–23.10 and
Corollaries 23.5.1–23.5.4, 23.7.1, 23.8.1.
Both of the section's objects are backbone definitions. dirDeriv f x y is f'(x; y), defined
as the infimum of the difference quotient over λ > 0; the book defines it as the limit as λ ↓ 0
and proves in Theorem 23.1 that the two agree, which here is theorem_23_1_monotone.
subgradient (pairing n) f x is ∂f(x), and subgradientRel (pairing n) f is the multivalued
mapping ∂f as a SetRel, so that Corollary 23.5.1 is SetRel.inv applied to it. normalCone is
N_C(x) and epsSubgradient is ∂_ε f(x).
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §23.
Theorem 23.1: the one-sided directional derivative #
Theorem 23.1, first assertion. For convex f finite at x, the difference quotient
[f(x + λy) - f(x)] / λ is non-decreasing in λ > 0. This is what identifies the book's
lim_{λ ↓ 0} with the infimum that defines dirDeriv.
Theorem 23.1, the formula f'(x; y) = inf_{λ > 0} [f(x + λy) - f(x)] / λ, which here is
the definition of dirDeriv.
Theorem 23.1: f'(x; ·) is positively homogeneous. This clause needs neither convexity of
f nor finiteness at x, being a reindexing of the infimum.
Theorem 23.1: f'(x; ·) is a convex function of y. Finiteness of f at x is not
removable: off dom f the difference quotient is ⊤ - ⊤ = ⊥ in every direction.
Theorem 23.1: f'(x; 0) = 0.
Theorem 23.1, last assertion: -f'(x; -y) ≤ f'(x; y) for every y.
Theorem 23.2: subgradients and directional derivatives #
Theorem 23.2. For convex f finite at x, x* ∈ ∂f(x) iff f'(x; y) ≥ ⟨x*, y⟩ for
every y. Convexity is not used: the subgradient inequality and the infimum of difference
quotients are two spellings of the same system.
Theorem 23.2, second assertion: the closure of f'(x; ·) as a convex function of y is
the support function of the closed convex set ∂f(x).
Theorem 23.3: when subgradients exist #
Theorem 23.3, first assertion: a function subdifferentiable at a point where it is finite is proper — a subgradient exhibits an affine minorant.
Theorem 23.3, second assertion: if f is not subdifferentiable at x, some direction
has f'(x; y) = -f'(x; -y) = -∞. The book's -f'(x; -y) = -∞ is stated here as
f'(x; -y) = +∞.
Theorem 23.3, last assertion: if f is not subdifferentiable at x then
f'(x; z - x) = -∞ for every z ∈ ri (dom f).
Theorem 23.4: existence, closedness and boundedness #
Theorem 23.4, first assertion: ∂f(x) = ∅ for x ∉ dom f. Convexity is not used.
Theorem 23.4: a proper convex function is subdifferentiable at every point of
ri (dom f).
Theorem 23.4: for x ∈ ri (dom f), f'(x; ·) is proper.
Theorem 23.4: for x ∈ ri (dom f), f'(x; ·) is closed.
Theorem 23.4: for x ∈ ri (dom f), f'(x; y) = δ*(y | ∂f(x)). Because f'(x; ·) is
already closed there no closure appears — this is the sharpening of Theorem 23.2 that the relative
interior buys.
Theorem 23.4, last assertion: ∂f(x) is non-empty and bounded iff
x ∈ int (dom f).
Theorem 23.4, last clause: in that case f'(x; y) is finite for every y. "Finite" is
dom (f'(x; ·)) = ℝⁿ together with properness, which rules out -∞.
dom ∂f need not be convex #
Theorem 23.4 places the set of points at which a proper convex function is subdifferentiable
between ri (dom f) and dom f. Rockafellar observes (p. 218) that it need not be convex, and
gives the example transcribed here.
p. 218. The function f(ξ₁, ξ₂) = max {g(ξ₁), |ξ₂|} on ℝ², where g(ξ₁) = 1 - ξ₁^{1/2}
for ξ₁ ≥ 0 and +∞ for ξ₁ < 0. Its effective domain is the closed right half-plane, and it is
subdifferentiable everywhere on that half-plane except in the relative interior of the segment
joining (0, 1) and (0, -1), so dom ∂f is not convex.
Equations
- Rockafellar.nonsmoothMaxFn = Tdaf.ConvexAnalysis.restrict {x : TdafSurface.Rn 2 | 0 ≤ x.ofLp 0} fun (x : TdafSurface.Rn 2) => ↑(max (1 - √(x.ofLp 0)) |x.ofLp 1|)
Instances For
p. 218: the set of points at which a proper convex function is subdifferentiable need not
be convex. dom ∂f contains (0, 1) and (0, -1) but not their midpoint (0, 0); this is why
Theorem 23.4 can only sandwich dom ∂f between ri (dom f) and dom f.
The example really is a proper convex function, so it witnesses the statement the book makes.
Theorem 23.5: the four conditions, and the three starred ones #
Theorem 23.5, condition (a): x* ∈ ∂f(x), that is f(z) ≥ f(x) + ⟨x*, z - x⟩ for every
z. Recorded as a clause so that the seven conditions read off one list.
Theorem 23.5, condition (b): ⟨z, x*⟩ - f(z) attains its supremum in z at z = x.
Neither convexity nor properness is used, this being the subgradient inequality with the terms
moved across.
Theorem 23.5, condition (c): f(x) + f*(x*) ≤ ⟨x, x*⟩. Since the supremum in (b) is
f*(x*), this is (b) restated; again no hypothesis is needed.
Theorem 23.5, condition (d): f(x) + f*(x*) = ⟨x, x*⟩. This is the one clause of (a)–(d)
that genuinely consumes properness: Fenchel's inequality ⟨x, x*⟩ ≤ f(x) + f*(x*) is false for
f ≡ +∞, since ⊤ + ⊥ = ⊥ in EReal.
Theorem 23.5, condition (a*): x ∈ ∂f*(x*), available when (cl f)(x) = f(x) — which for
convex f is Fenchel–Moreau's f** x = f x.
Theorem 23.5, condition (b*): ⟨x, z*⟩ - f*(z*) attains its supremum in z* at z* = x*,
available when (cl f)(x) = f(x).
Theorem 23.5, condition (a**): x* ∈ ∂(cl f)(x), available when (cl f)(x) = f(x).
Corollary 23.5.1. For a closed proper convex f, the multivalued mapping ∂f* is the
inverse of ∂f — literally SetRel.inv applied to subgradientRel. The book states this
corollary with no proof; it follows from the equivalence of (a) and (a*) in Theorem 23.5, whose
hypothesis (cl f)(x) = f(x) is automatic for a closed f.
Corollary 23.5.1, pointwise: x ∈ ∂f*(x*) iff x* ∈ ∂f(x).
Corollary 23.5.2, first assertion: if f is subdifferentiable at x then
(cl f)(x) = f(x). Properness is not needed.
Corollary 23.5.2, second assertion: and then ∂(cl f)(x) = ∂f(x).
Corollary 23.5.3. For a non-empty closed convex C, ∂δ*(x* | C) consists of the points
of C (if any) at which ⟨·, x*⟩ attains its maximum over C.
Corollary 23.5.4. For a convex cone K, x* ∈ ∂δ(x | K) iff x ∈ K, x* ∈ K° and
⟨x, x*⟩ = 0 — the complementary-slackness form. Rockafellar assumes K non-empty and closed
and neither hypothesis is used: he derives the corollary from δ(· | K)* = δ(· | K°), which needs
closedness, whereas putting z = 0 and z = x + x into the subgradient inequality does not.
Corollary 23.5.4, the duality: for a closed convex cone K, x* ∈ ∂δ(x | K) iff
x ∈ ∂δ(x* | K°). Both sides unfold to the same three conditions once K°° = K (Theorem 14.1)
identifies the polar of K° with K. Closedness is used here and only here.
Theorem 23.6: ε-subgradients #
An unnumbered fact recorded before Theorem 23.6: ∂_ε f(x) is a closed convex set for every
ε, being {x* | h*(x*) ≤ ε} for h(y) = f(x + y) - f(x).
The other unnumbered fact: the nest ∂_ε f(x), ε > 0, has intersection ∂f(x).
Theorem 23.6. For a closed proper convex f finite at x,
f'(x; y) = lim_{ε ↓ 0} δ*(y | ∂_ε f(x)). The sets ∂_ε f(x) increase with ε, so the book's
limit is written here as the infimum it is; and "closed" is spelled as IsClosed (epi f), which
for a proper convex function is the same condition.
Theorem 23.7: normals to a level set #
Theorem 23.7. If f is proper convex and subdifferentiable at x but does not attain its
minimum there, the normal cone at x to C = {z | f(z) ≤ f(x)} is the closure of the convex cone
generated by ∂f(x). The hypothesis ⨅ z, f z < f x is "does not attain its minimum".
Corollary 23.7.1. If x ∈ int (dom f) and f does not attain its minimum there, the
closure in Theorem 23.7 is unnecessary: the normal cone is the convex cone generated by ∂f(x).
What makes the closure redundant is that ∂f(x) is then non-empty, closed, bounded and misses the
origin, so Corollary 9.6.1 applies.
Corollary 23.7.1 in the book's own words: x* is normal to C = {z | f(z) ≤ f(x)} at x
iff x* ∈ λ ∂f(x) for some λ ≥ 0. The convex cone generated by a convex set is the union of
its non-negative multiples (Corollary 9.6.1), and ∂f(x) is non-empty here, which is what turns
λ > 0 into λ ≥ 0.
Theorem 23.8: the sum rule #
Theorem 23.8, the unconditional inclusion: ∂(f₁ + ⋯ + fₘ)(x) ⊇ ∂f₁(x) + ⋯ + ∂fₘ(x), with
no hypothesis — the m subgradient inequalities simply add.
Theorem 23.8. If the sets ri (dom fᵢ) have a point in common, then
∂(f₁ + ⋯ + fₘ)(x) = ∂f₁(x) + ⋯ + ∂fₘ(x) for every x. Stated for a Finset of summands, as the
book states it, and not by induction on m: the constraint qualification is discharged once,
by Theorem 16.4 in the same m-ary form. The book's ALTERNATIVE PROOF (p. 220) is more elementary
— proper separation of {(x, μ) | μ ≥ f₁ x} from {(x, μ) | μ ≤ -f₂ x} in ℝⁿ⁺¹ — but reduces
m to 2 by an induction this route avoids.
Theorem 23.8, last sentence: the condition for equality weakens when some fᵢ are
polyhedral. If f₁, …, f_k are polyhedral it is enough that dom f₁, …, dom f_k,
ri (dom f_{k+1}), …, ri (dom fₘ) have a point in common — Theorem 20.1. Here t is the book's
{1, …, k} and u its complement. The book's ALTERNATIVE PROOF does not cover this clause.
Corollary 23.8.1: normals to an intersection #
Corollary 23.8.1, the unconditional inclusion: the sum of the normal cones is contained in the normal cone to the intersection. Proved directly, so no hypothesis is needed.
Corollary 23.8.1. If the convex sets C₁, …, Cₘ have a common relative interior point, the
normal cone to C₁ ∩ ⋯ ∩ Cₘ at x is the sum of the normal cones to the Cᵢ at x. This is the
indicator instance of Theorem 23.8. The hypothesis x ∈ Cᵢ is not in the book and is not
removable: Rockafellar's N_C(x) is ∂δ(x | C), which is empty off C, whereas normalCone is
defined everywhere and always contains 0; the two agree exactly on C.
Theorem 23.9: composition with a linear transformation #
Theorem 23.9, the unconditional inclusion: for f(x) = h(Ax), ∂f(x) ⊇ A*∂h(Ax). Here
h is arbitrary and only the adjointness is used.
Theorem 23.9. For f(x) = h(Ax) with h proper convex on ℝᵐ: if the range of A
contains a point of ri (dom h), then ∂f(x) = A*∂h(Ax) for every x. This is Theorem 23.5
applied to the exact conjugacy formula of Theorem 16.3; Rockafellar's A* is
LinearMap.adjoint A.
Theorem 23.9, last clause: if h is polyhedral and the range of A merely meets
dom h — no relative interior — then ∂f(x) = A*∂h(Ax). The book's route is Theorem 16.3 via
Corollary 19.3.1, which is the one taken here.
Theorem 23.10: the polyhedral case #
Theorem 23.10, first assertion: a polyhedral convex function is subdifferentiable wherever
it is finite. No relative interior is needed: the cone generated by epi f - (x, f x) is
polyhedral, hence closed (Corollary 19.7.1), so f'(x; ·) is already closed.
Theorem 23.10: and ∂f(x) is a polyhedral convex set.
Theorem 23.10: f'(x; ·) is a polyhedral convex function.
Theorem 23.10: f'(x; ·) is proper. The book's reason: f'(x; 0) = 0, and a polyhedral
convex function taking the value -∞ somewhere has no finite values at all.
Theorem 23.10, last assertion: f'(x; ·) is the support function of ∂f(x), with no
closure operation.