Chapter 16 — Subdifferentiability of Convex Functions

Proofs omitted. Hover over highlighted terms to see their Lean types.

Definition 16.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 16.1: the subdifferential of a function with canonical EReal-valued codomain coercion sends x to the set of vectors u such that the affine function y ↦ ⟪y - x, u⟫ + f x minorizes f everywhere. In particular, the same owner surface applies directly to both EReal-valued and ]-∞,+∞]-valued functions.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] def subdifferential {α : Type*} [CoeTC α EReal] (f : H → α) : SetValuedOperator H H := fun x ↦ {u | ∀ y : H, (⟪y - x, u⟫_ℝ : EReal) + (f x : EReal) ≤ (f y : EReal)}

Remark 16.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 16.2: if f ∈ Γ₀(H), then the domain of the subdifferential of f is nonempty.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: `effectiveDomain f` is nonempty because `hf : f ∈ Γ₀(H)` packages convexity on a -- nonempty domain. Corollary 16.39 says subdifferentiability points are dense in that effective -- domain, hence there exists `p ∈ effectiveDomain f` with `SubdifferentiableAt f p.1`, i.e. -- `p ∈ dom (∂ f)`. theorem subdifferential_dom_nonempty_of_mem_gammaZero {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) : (SetValuedOperator.dom (((∂ (f : H → EReal)) : H → Set H))).Nonempty

Theorem 16.3

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 16.3: Fermat's rule. The global minimizers of an ]-∞,+∞]-valued function are exactly the zeros of its subdifferential.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: this is the direct bridge between the owner declarations `Argmin`, -- `SetValuedOperator.zeros`, and `subdifferential`. At slope `0`, the affine-minorant inequality -- in `mem_subdifferential_iff` is exactly the global minimality condition. theorem argmin_eq_zeros_subdifferential (f : H → Set.Ioi (⊥ : EReal)) : Argmin f.asEReal = (∂ f).zeros

Proposition 16.4

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.4 (1): if f has a nonempty effective domain, then every point at which the subdifferential is nonempty lies in the effective domain. For ]-∞,+∞]-valued functions, this is the remaining properness content after excluding -∞ by the codomain.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: choose a point `y` in the effective domain. If `u ∈ subdifferential f x`, then -- the defining inequality with that `y` forces `(f x : EReal) < ⊤`. theorem subdifferential_domain_subset_effectiveDomain (f : H → Set.Ioi (⊥ : EReal)) (hdom : (effectiveDomain f).Nonempty) : SetValuedOperator.dom (∂ f) ⊆ effectiveDomain f

Proposition 16.5

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.5 (1): if an ]-∞,+∞]-valued function is subdifferentiable at x, then its Fenchel biconjugate agrees with f at x.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable (f : H → Set.Ioi (⊥ : EReal)) (x : H) -- Proof sketch: choose a subgradient `u ∈ (∂ f) x`. The supporting affine minorant through -- `(x, f x)` shows that `f.asEReal` admits a continuous affine minorant, so -- Proposition 13.45 identifies its biconjugate with the lower semicontinuous convex envelope. -- Proposition 16.4 gives lower semicontinuity at `x`, and Corollary 9.10 together with -- Lemma 1.32 turns that local lower semicontinuity into the pointwise equality -- `f** x = f x`. theorem biconjugate_eq_self_at_of_subdifferentiableAt (hxsub : SubdifferentiableAt f x) : f.asEReal∗∗ x = f.asEReal x

Proposition 16.6

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.6 (1): the subdifferential of a positive scalar multiple is the corresponding positive scalar multiple of the subdifferential.

open scoped InnerProductSpace Pointwise universe u v namespace ERealFunction variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: unfold membership in both subdifferentials and rewrite the affine-minorant -- inequality for the canonical positive-real scalar action on `]-∞,+∞]`-valued functions; -- dividing by the positive scalar identifies witnesses on the two sides. theorem subdifferential_posReal_smul_eq_smul (f : H → Set.Ioi (⊥ : EReal)) (γ : PosReal) : ∂ ((γ • f : H → Set.Ioi (⊥ : EReal))) = (γ : ℝ) • (∂ f : SetValuedOperator H H)

Proposition 16.7

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.7: every subgradient of a function on a finite Hilbert direct sum yields coordinatewise subgradients of the slice functions obtained by freezing all but one coordinate.

universe u v namespace ERealFunction variable {I : Type v} [Finite I] variable {H : I → Type u} variable [∀ i, NormedAddCommGroup (H i)] [∀ i, InnerProductSpace ℝ (H i)] -- Proof sketch: if `u ∈ ∂ f x`, then the subgradient inequality for `f` at `x` can be tested on -- the slice `coordinateSlice x i yi`; this yields the subgradient inequality for the scalar slice -- function `f ∘ coordinateSlice x i` at `x i` with slope `u i`, for every `i`. theorem subdifferential_subset_coordinatewise_subdifferential {f : lp H 2 → Set.Ioi (⊥ : EReal)} {x : lp H 2} : (∂ f) x ⊆ {u | ∀ i, u i ∈ (∂ (f ∘ coordinateSlice x i)) (x i)}

Remark 16.8

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 16.8: for the indicator of the closed unit ball in the canonical Euclidean model of ℝ², the coordinatewise subdifferential inclusion from Proposition 16.7 is strict at (1,0).

open scoped EuclideanSpace InnerProductSpace namespace ERealFunction local notation "ℝ²" => EuclideanSpace ℝ (Fin 2) local notation "B" => Metric.closedBall (0 : ℝ²) 1 local notation "x₀" => (!₂[(1 : ℝ), 0] : ℝ²) -- Proof sketch: Example 16.13 rewrites the subdifferential of `ι[B]` as the normal cone of `B`, -- and Example 6.39 identifies that normal cone at the boundary point `x₀ = (1,0)` with the -- nonnegative ray through `x₀`, i.e. `ℝ₊ × {0}`. theorem indicator_closedUnitBall_strict_subset_coordinatewise_subdifferential : (∂ ι[B]) x₀ ⊂ {u : ℝ² | ∀ i, u i ∈ (∂ ((ι[B]) ∘ coordinateSliceEuclidean x₀ i)) (x₀ i)}

Proposition 16.9

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.9: for a finite family of ]-∞,+∞]-valued functions with nonempty effective domains, the subdifferential of the direct-sum function is the coordinatewise Cartesian product of the subdifferentials of the summands.

universe u v namespace ERealFunction variable {I : Type v} [Fintype I] variable {H : I → Type u} variable [∀ i, NormedAddCommGroup (H i)] [∀ i, InnerProductSpace ℝ (H i)] -- Proof sketch: for the forward inclusion, specialize Proposition 16.7 to the direct-sum -- function and identify each coordinate slice with the corresponding summand up to an additive -- constant. For the reverse inclusion, choose one effective-domain point in every frozen -- coordinate, expand the coordinate subgradient inequalities, and sum them to obtain the global -- subgradient inequality for `directSumFunction f`. theorem subdifferential_directSumFunction_eq_coordinatewise (f : ∀ i, H i → Set.Ioi (⊥ : EReal)) (hdom : ∀ i, (effectiveDomain (f i)).Nonempty) (x : lp H 2) : (∂ (directSumFunction f)) x = {u : lp H 2 | ∀ i, u i ∈ (∂ (f i)) (x i)}

Proposition 16.10

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.10: for an ]-∞,+∞]-valued function with nonempty effective domain, u is a subgradient of f at x exactly when equality holds in the Fenchel--Young inequality f(x) + f^*(u) = ⟪x, u⟫.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable (f : H → Set.Ioi (⊥ : EReal)) (hdom : (effectiveDomain f).Nonempty) -- Proof sketch: rewrite `u ∈ ∂ f x` using Definition 16.1, then use Proposition 13.15 on the -- canonical `EReal` coercion of `f`, whose properness is equivalent here to the nonempty -- effective domain hypothesis. Unfold `conjugate f u` as the supremum of the affine defects and -- observe that equality is equivalent to the defining subgradient inequality being tight at `x`. theorem mem_subdifferential_iff_fenchel_young_eq (x u : H) : u ∈ (∂ f) x ↔ (f x : EReal) + f.asEReal∗ u = ((⟪x, u⟫_ℝ : ℝ) : EReal)

Corollary 16.11

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.11: if an ]-∞,+∞]-valued function has nonempty effective domain, then the graph of its subdifferential is contained in the product of the effective domain of f and the domain of its Fenchel conjugate f*.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: if `(x, u)` lies in `(∂ f).graph`, then `u ∈ (∂ f) x`, so Proposition 16.4 puts -- `x` in `effectiveDomain f`. Proposition 16.10 rewrites the same membership as the -- Fenchel--Young equality `(f x : EReal) + f.asEReal∗ u = ((⟪x, u⟫_ℝ : ℝ) : EReal)`. Since the -- right-hand side is finite, the conjugate cannot be `⊤`, so `u ∈ dom f.asEReal∗`. theorem graph_subdifferential_subset_dom_prod_dom_conjugate_of_effectiveDomain_nonempty (f : H → Set.Ioi (⊥ : EReal)) (hdom : (effectiveDomain f).Nonempty) : SetValuedOperator.graph (∂ f) ⊆ (effectiveDomain f) ×ˢ dom (f.asEReal∗)

Example 16.12

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.12: the subdifferential of the quadratic function f = (1 / 2)‖·‖² is the identity set-valued operator, written pointwise as the singleton-valued map x ↦ {x}.

open ERealFunction open scoped InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: apply Proposition 16.10 to `halfSquaredNorm`, use Example 13.6 to -- identify its Fenchel conjugate with itself, and then simplify the Fenchel--Young equality to -- the identity `u = x`. theorem subdifferential_halfSquaredNorm_eq_singleton : ∂ halfSquaredNorm = (fun x : H ↦ ({x} : Set H))

Example 16.13

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.13: for a nonempty subset C of a real Hilbert space, hence in particular for a nonempty convex subset, the subdifferential of the indicator ι_C is exactly the normal cone mapping N_C.

open ERealFunction open scoped InnerProductSpace Pointwise Set universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: for `x ∈ C`, unfold `(∂ ι[C]) x`; the indicator is `0` on `C` and `⊤` off `C`, -- so the subgradient inequality reduces to `⟪y - x, u⟫ ≤ 0` for all `y ∈ C`, which is exactly -- the defining inequality of `N[C] x`. For `x ∉ C`, nonemptiness of `C` furnishes `y ∈ C`, -- forcing the subdifferential to be empty, matching `normalCone_of_not_mem`. theorem subdifferential_setIndicator_eq_normalCone (C : Set H) (hC_nonempty : C.Nonempty) : ∂ ι[C] = N[C]

Example 16.14

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.14 (1): if ξ < 0, the subdifferential of the support function of a nonempty subset Ω ⊆ ℝ is the real slice of the singleton containing the infimum endpoint of Ω.

open scoped InnerProductSpace namespace ERealFunction variable (Ω : Set ℝ) (hΩ : Ω.Nonempty) include hΩ -- Proof sketch: for `ξ < 0`, the support function of `Ω` is the affine map `x ↦ ξ x` maximized at -- the lower endpoint, so the only supporting slope is the infimum endpoint of `Ω` when that -- endpoint is real. theorem subdifferential_supportFunction_eq_lowerEndpoint_of_neg {ξ : ℝ} (hξ : ξ < 0) : (∂ σ[Ω]) ξ = {x : ℝ | (x : EReal) = sInf (Real.toEReal '' Ω)}

Example 16.15

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.15: since |·| = σ[[-1,1]], the subdifferential of the absolute value on ℝ is {-1} on (-∞,0), [-1,1] at 0, and {1} on (0,+∞).

namespace ERealFunction theorem subdifferential_abs_eq_piecewise (ξ : ℝ) : (∂ (fun η : ℝ ↦ |η|).toEReal) ξ = if ξ < 0 then {(-1 : ℝ)} else if ξ = 0 then Set.Icc (-1 : ℝ) 1 else {(1 : ℝ)}

Proposition 16.16

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.16, clauses (i)-(iii): for a convex ]-∞,+∞]-valued function, the following are equivalent: u ∈ ∂ f x, (u, -1) lies in the normal cone to the real-height epigraph of f at (x, f x), and equality holds in the Fenchel--Young identity f(x) + f^*(u) = ⟪x, u⟫.

open scoped InnerProductSpace Pointwise Set universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem subdifferential_normalCone_fenchelYoung_tfae (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f)) (x u : H) : List.TFAE [u ∈ (∂ f) x, (u, (-1 : ℝ)) ∈ N[epigraph f.asEReal] (x, (f x : EReal).toReal), (f x : EReal) + f.asEReal∗ u = ((⟪x, u⟫_ℝ : ℝ) : EReal)]

Proposition 16.17

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.17 (1): clause (i). If the effective domain has nonempty interior and x lies on its boundary, then the subdifferential at x is either empty or unbounded.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem subdifferential_eq_empty_or_unbounded_of_mem_frontier_effectiveDomain (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f)) {x : H} (hx : x ∈ effectiveDomain f) (hinter : (interior (effectiveDomain f)).Nonempty) (hfrontier : x ∈ frontier (effectiveDomain f)) : (∂ f) x = ∅ ∨ ¬Bornology.IsBounded ((∂ f) x)

Corollary 16.18

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.18 (1): clause (i). The relative interior of the effective domain of an ]-∞,+∞]-valued function that is convex on its effective domain is nonempty on a finite-dimensional real Hilbert space.

open Set universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [FiniteDimensional ℝ H] variable (f : H → Set.Ioi (⊥ : EReal)) variable (hconv : ConvexOn f (effectiveDomain f)) -- Proof sketch: `effectiveDomain f` is nonempty and convex because `f` is convex on its -- effective domain. Fact 6.14 then gives nonemptiness of the relative interior of this convex set -- in finite dimension. theorem relativeInterior_effectiveDomain_nonempty_of_convexOn : (ri (effectiveDomain f)).Nonempty

Corollary 16.19

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.19: if h is convex and D is a nonempty open convex subset of the effective-domain continuity set of h, then every Γ₀(H) function whose effective domain is contained in closure D and which agrees with h on D coincides with (h + ι_D)^{**}.

open Set Filter open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable (h : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn h (effectiveDomain h)) variable (D : Set H) (hD_nonempty : D.Nonempty) (hD_open : IsOpen D) (hD_convex : Convex ℝ D) variable (hD_cont : D ⊆ {x : H | ContinuousAtOnEffectiveDomain h x}) -- Proof sketch: pick a continuity point `y ∈ D`, use continuity to identify -- `(h.asEReal + (ι[D]).asEReal)∗∗ y` with `h y`, and then apply the finite-point -- biconjugation theorem to obtain properness of the biconjugate. theorem eq_biconjugate_add_indicator_of_mem_gammaZero_subset_closure_eqOn {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (hdom : effectiveDomain f ⊆ closure D) (hEq : EqOn f h D) : f.asEReal = ((h + ι[D]).asEReal)∗∗

Proposition 16.20

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.20: for a continuous convex real-valued function on a real Hilbert space, the following are equivalent: boundedness on every bounded subset, Lipschitz continuity on every bounded subset, global subdifferentiability with bounded subdifferential image on bounded sets, and supercoercivity of the Fenchel conjugate.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: combine the Chapter 8 local boundedness and local Lipschitz criteria for convex -- real-valued functions on bounded balls with Proposition 16.17 for subdifferentials and -- Proposition 14.15 for Fenchel conjugates. The finite-dimensional conclusion then follows from -- the bounded-set Lipschitz theorem on closed bounded subsets together with the first equivalence. theorem continuous_convex_tfae_boundedOnEveryBoundedSet_lipschitzOnEveryBoundedSet_subdifferential_boundedImage_supercoercive_conjugate (f : H → ℝ) (hcont : Continuous f) (hconv : _root_.ConvexOn ℝ Set.univ f) : List.TFAE [∀ B : Set H, Bornology.IsBounded B → Bornology.IsBounded (f '' B), ∀ B : Set H, Bornology.IsBounded B → ∃ β : NNReal, LipschitzOnWith β f B, (∀ x : H, SubdifferentiableAt f.toEReal x) ∧ ∀ B : Set H, Bornology.IsBounded B → Bornology.IsBounded (SetValuedOperator.image (∂ f.toEReal) B), Supercoercive f.toEReal.asEReal∗]

Corollary 16.21

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.21: for f ∈ Γ₀(H) on a finite-dimensional real Hilbert space, the following are equivalent: f is supercoercive, every linear perturbation f - ⟪·, u⟫ is coercive, and the effective domain of the Fenchel conjugate f* is all of H.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [FiniteDimensional ℝ H] -- Proof sketch: Proposition 14.15 gives `(i) → (iii)`. Theorem 14.17 identifies clause `(ii)` with -- `interior (dom f*) = Set.univ`, which is equivalent to `dom f* = Set.univ`. For `(iii) → (i)`, -- Corollary 13.38 shows that `f* ∈ Γ₀(H)`; since `dom f* = Set.univ`, the conjugate is finite -- everywhere, and Corollary 8.40 makes this finite-dimensional convex function continuous. -- Proposition 16.20 then yields supercoercivity of `(f*)*`, which Corollary 13.38 identifies with -- `f`. theorem supercoercive_tfae_coercive_sub_inner_dom_conjugate_univ_of_mem_gammaZero (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) : List.TFAE [Supercoercive f.asEReal, ∀ u : H, Coercive (f.asEReal - fun x ↦ ((⟪x, u⟫_ℝ : ℝ) : EReal)), dom f.asEReal∗ = Set.univ]

Example 16.22

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.22: for the series f(ξ) = ∑ₙ n * ξₙ^(2n) on ℓ²(ℕ+, ℝ), the Fenchel conjugate f* is not supercoercive.

namespace ERealFunction local notation "L2pos" => lp (fun _ : ℕ+ ↦ ℝ) 2 theorem positiveNatWeightedEvenPowerSeries_conjugate_not_supercoercive : ¬ Supercoercive positiveNatWeightedEvenPowerSeries.asEReal∗

Proposition 16.25

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.25: if f ∈ Γ₀(H) and the interior of its effective domain is nonempty, then f equals the biconjugate of its restriction to interior (effectiveDomain f), encoded by the canonical constrained function f + ι[interior (effectiveDomain f)].

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: use the interior-point hypothesis to obtain supporting affine minorants on -- `interior (effectiveDomain f)`, identify the indicator-augmented function with `f` there, and -- then apply the Fenchel--Moreau reconstruction theorem to recover `f` as the biconjugate of that -- restriction. theorem eq_biconjugate_add_indicator_interior_effectiveDomain {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (hinter : (interior (effectiveDomain f)).Nonempty) : f.asEReal = ((f + ι[interior (effectiveDomain f)]).asEReal)∗∗

Example 16.26

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.26: for the Hilbert-basis coefficient supremum f(x) = sup_n ⟪x,e_n⟫ / α_n and the span C = span{e_n}, the Fenchel biconjugate of f + ι_C does not coincide with f.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] local notation "L2Nat" => lp (fun _ : ℕ ↦ ℝ) 2 variable (b : HilbertBasis ℕ ℝ H) local notation "Cₛ" => (Submodule.span ℝ (Set.range b) : Submodule ℝ H) local notation "C" => (Cₛ : Set H) -- Proof sketch: a vector in the span of the basis has only finitely many nonzero basis -- coordinates, so the supremum of the coordinate ratios is finite there. theorem hilbertBasisCoordinateSupremumWithIndicator_biconjugate_ne (α : L2Nat) (hα_ne : ∀ n : ℕ, α n ≠ 0) : ((affineInnerSupremum (fun n ↦ (α n)⁻¹ • b n) 0).asEReal + (ι[C]).asEReal)∗∗ ≠ (affineInnerSupremum (fun n ↦ (α n)⁻¹ • b n) 0).asEReal

Proposition 16.27

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.27: for f ∈ Γ₀(H), the interior of the effective domain is exactly the set of points where the finite-valued restriction of f to its effective domain is continuous.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: apply Corollary 8.39 to a member of `Γ₀(H)` to identify interior-domain points -- with the canonical continuity set of the finite-valued restriction to `effectiveDomain f`. theorem interior_effectiveDomain_eq_setOf_continuousAtOnEffectiveDomain_of_mem_gammaZero {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) : interior (effectiveDomain f) = {x : H | ContinuousAtOnEffectiveDomain f x}

Remark 16.28

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 16.28: for the function f(ξ₁, ξ₂) = max {g(ξ₁), |ξ₂|} with g(ξ₁) = 1 - √ξ₁ on ℝ₊ and g(ξ₁) = +∞ on (-∞, 0), the domain of the subdifferential is (ℝ₊ × ℝ) \ ({0} × ]-1,1[).

namespace ERealFunction local notation "ℝ²" => EuclideanSpace ℝ (Fin 2) theorem subdifferentialDomain_oneSubSqrtAbsMaxCounterexample_eq : SetValuedOperator.dom (∂ oneSubSqrtAbsMaxCounterexample) = {x : ℝ² | 0 ≤ x 0} \ {x : ℝ² | x 0 = 0 ∧ x 1 ∈ Set.Ioo (-1 : ℝ) 1}

Theorem 16.29

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 16.29: for f ∈ Γ₀(H), membership of (x, u) in the graph of ∂ f, membership of (u, -1) in the normal cone to epi f at (x, f x), equality in the Fenchel--Young identity, and membership of (u, x) in the graph of ∂ f^* are equivalent. In Lean, clauses (i) and (iv) are written as the corresponding subdifferential-membership statements, and clause (ii) uses the real-height epigraph point (x, (f x : EReal).toReal).

open scoped InnerProductSpace Pointwise Set open WithLp universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem subdifferential_normalCone_fenchelYoung_conjugate_tfae (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (x u : H) : List.TFAE [u ∈ (∂ f) x, (u, (-1 : ℝ)) ∈ N[epigraph f.asEReal] (x, (f x : EReal).toReal), (f x : EReal) + f.asEReal∗ u = ((⟪x, u⟫_ℝ : ℝ) : EReal), x ∈ (∂ (gammaZeroConjugate f hf)) u]

Corollary 16.30

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.30: if f ∈ Γ₀(H), then the inverse of the subdifferential of f is the subdifferential of its Fenchel conjugate f*, represented by f∗[hf].

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem inverse_subdifferential_eq_subdifferential_gammaZeroConjugate (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) : ((∂ f).inverse : SetValuedOperator H H) = ∂ (f∗[hf])

Example 16.31

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.31: for an even function φ ∈ Γ₀(ℝ), a vector u belongs to the subdifferential of the radial function x ↦ φ ‖x‖ at x exactly when ‖u‖ belongs to the subdifferential of φ at ‖x‖ and x and u lie on the same nonnegative ray.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: Theorem 16.29 rewrites membership in the subdifferential of `x ↦ φ ‖x‖` as -- Fenchel--Young equality. Example 13.8 identifies the conjugate of this radial function with -- `u ↦ φ^*(‖u‖)`, Proposition 13.15 gives the scalar Fenchel--Young inequality -- `φ(‖x‖) + φ^*(‖u‖) ≥ ‖x‖ * ‖u‖`, and Fact 2.11 bounds `⟪x, u⟫` by `‖x‖ * ‖u‖`. Equality in -- both inequalities is equivalent to `‖u‖ ∈ ∂φ(‖x‖)` and to `x` and `u` lying on the same -- nonnegative ray. theorem mem_subdifferential_comp_norm_iff_norm_mem_subdifferential_and_same_ray (φ : ℝ → Set.Ioi (⊥ : EReal)) (hφ : φ ∈ Γ₀(ℝ)) (heven : Function.Even φ) (x u : H) : u ∈ (∂ (fun y : H ↦ φ ‖y‖)) x ↔ ‖u‖ ∈ (∂ φ) ‖x‖ ∧ SameRay ℝ x u

Example 16.32

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.32: the subdifferential of the norm is the singleton containing the normalized vector away from 0, and the closed unit ball at 0.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem subdifferential_norm_eq_singleton_or_closedBall (x : H) : (∂ (fun y : H ↦ ‖y‖).toEReal) x = if x = 0 then (Metric.closedBall (0 : H) 1 : Set H) else ({‖x‖⁻¹ • x} : Set H)

Proposition 16.33

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.33: for f ∈ Γ₀(H), the set of minimizers of f coincides with the subdifferential of its Fenchel conjugate at 0, represented here by f∗[hf].

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem argmin_eq_subdifferential_gammaZeroConjugate_zero (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) : Argmin f.asEReal = (∂ (f∗[hf])) 0

Example 16.34

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.34: if C is a nonempty closed convex subset of a real Hilbert space, then the subdifferential of its support function at 0 is exactly C.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: apply Proposition 16.33 to the indicator `ι_C`, whose Fenchel conjugate is the -- support function `σ[C]`. The minimizers of `ι_C` are exactly the points of `C`, and the -- nonempty closed convex hypotheses place `ι_C` in `Γ₀(H)`. theorem subdifferential_supportFunction_eq_self_at_zero_of_nonempty_isClosed_convex (C : Set H) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : (∂ σ[C]) 0 = C

Proposition 16.35

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.35: for x ∈ effectiveDomain f, the normal cone to the real-height epigraph of f at the graph point (x, (f x).toReal) is the union of the horizontal slice over the normal cone to effectiveDomain f at x and the positive ray generated by the subdifferential slice (∂ f x) × {-1}.

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: unfold the normal cone to `epigraph f.asEReal` at the finite graph point -- `(x, (f x : EReal).toReal)` and split a normal vector according to whether its scalar component -- is `0` or negative. The zero slice gives the normal cone to `effectiveDomain f`, while the -- negative slice rewrites to a positive multiple of a subgradient at `x`. theorem normalCone_epigraph_eq_effectiveDomain_normal_zero_union_positive_subdifferential {f : H → Set.Ioi (⊥ : EReal)} {x : H} (hx : x ∈ effectiveDomain f) : N[epigraph f.asEReal] (x, (f x : EReal).toReal) = N[effectiveDomain f] x ×ˢ ({0} : Set ℝ) ∪ Ioi (0 : ℝ) • ((∂ f) x ×ˢ ({-1} : Set ℝ))

Proposition 16.36

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.36: for f ∈ Γ₀(H), the graph of the subdifferential is sequentially closed in the mixed weak-strong product topology, encoded as sequential closedness of its image in WeakSpace ℝ H × H.

open SetValuedOperator open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem graph_subdifferential_isSeqClosed_weakStrong_of_mem_gammaZero (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) : IsSeqClosed ((Prod.map (toWeakSpace ℝ H) id) '' (∂ f).graph)

Proposition 16.37

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.37 (1): if the whole segment [u₀,u₁] lies in the subdifferential ∂ f(x), then the Fenchel conjugate f*, represented by gammaZeroConjugate f hf, is finite on that segment, and its finite-valued trace is affine there. In Lean, the affineness clause is expressed by equality with the affine interpolation of the endpoint values along the line-map parameterization of [u₀,u₁], after recording the needed effective-domain control explicitly.

open Set open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) local notation "f⋆" => gammaZeroConjugate f hf theorem gammaZeroConjugate_eq_lineMap_on_segment_of_segment_subset_subdifferential (x u0 u1 : H) (hseg : segment ℝ u0 u1 ⊆ (∂ f) x) : segment ℝ u0 u1 ⊆ effectiveDomain f⋆ ∧ EqOn (fun α : ℝ ↦ (f⋆ (AffineMap.lineMap u0 u1 α) : EReal).toReal) (AffineMap.lineMap ((f⋆ u0 : EReal).toReal) ((f⋆ u1 : EReal).toReal)) (Icc (0 : ℝ) 1)

Proposition 16.38

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.38: for f ∈ Γ₀(H), the graph of the constrained function f + ι[dom (∂ f)] is dense in the graph of f.

open Filter open scoped Topology universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- On the real-height graph of `f`, adding the indicator of `dom (∂ f)` simply cuts out the graph -- points whose base point is subdifferentiable. theorem graph_subdifferentiableAt_dense_in_graph_of_mem_gammaZero {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) : Dense {p : graph f.asEReal | SubdifferentiableAt f p.1.1}

Corollary 16.39

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.39: if f ∈ Γ₀(H), then the points of effectiveDomain f at which f is subdifferentiable form a dense subset of effectiveDomain f.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: fix `x ∈ effectiveDomain f`. Proposition 16.38 gives graph points above -- subdifferentiability points converging to `(x, f x)`, hence base points in `effectiveDomain f` -- with `SubdifferentiableAt f` converging to `x`. This is exactly density of the -- subdifferentiability domain in the subtype `effectiveDomain f`. theorem dense_subdifferentiableAt_in_effectiveDomain_of_mem_gammaZero {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) : Dense {x : effectiveDomain f | SubdifferentiableAt f x.1}

Corollary 16.40

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.40: if f ∈ Γ₀(H), then the Fenchel conjugate of f is unchanged after adding the indicator of the subdifferential domain dom (∂ f).

open Set open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem conjugate_eq_conjugate_add_indicator_subdifferentiabilityDomain_of_mem_gammaZero {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) : f.asEReal∗ = ((f + ι[SetValuedOperator.dom (∂ f)]).asEReal)∗

Corollary 16.41

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.41: if f ∈ Γ₀(H), then f is the Fenchel biconjugate of the function obtained by adding the indicator of the subdifferential domain dom (∂ f).

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: Corollary 16.40 identifies `f.asEReal∗` with the conjugate of the -- canonical constrained function `f + ι[SetValuedOperator.dom (∂ f)]`. Since `hf : f ∈ Γ₀(H)`, -- Corollary 13.38 gives `f = f**`; applying the same biconjugation principle to the common -- conjugate yields the desired equality. theorem eq_biconjugate_add_indicator_subdifferentiabilityDomain_of_mem_gammaZero {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) : f.asEReal = ((f + ι[SetValuedOperator.dom (∂ f)]).asEReal)∗∗

Proposition 16.42

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.42: if f ∈ Γ₀(H), g ∈ Γ₀(K), L (effectiveDomain f) meets effectiveDomain g, and the conjugate formula conjugate (compositePrimalObjective f g L) = f^* □ (L^* ▷ g^*) holds, then the subdifferential of f + g ∘ L is ∂ f + L^* ∂ g L, realized by the canonical owner (∂ f) + adjointImageSubdifferential L g.

open scoped InnerProductSpace Pointwise universe u v namespace ERealFunction open ContinuousLinearMap variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] variable [CompleteSpace H] [CompleteSpace K] -- Proof sketch: Proposition 16.6 already gives the inclusion -- `∂ f + L.adjoint '' (∂ g) (L x) ⊆ ∂ (f + g ∘ L)`. For the reverse inclusion, take -- `u ∈ ∂ (f + g ∘ L) x`, rewrite this by Fenchel--Young equality using Proposition 16.10, and -- use the assumed conjugate formula for the canonical owner `compositePrimalObjective f g L` to -- choose `v` on the adjoint fiber of `u`. Applying the Fenchel--Young characterization again to -- `f` and `g` yields -- `u - L.adjoint v ∈ ∂ f x` and `v ∈ ∂ g (L x)`. theorem subdifferential_add_comp_eq_add_adjoint_image_of_conjugate_formula {f : H → Set.Ioi (⊥ : EReal)} {g : K → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hdom : (L '' effectiveDomain f ∩ effectiveDomain g).Nonempty) (hconj : conjugate (compositePrimalObjective f g L) = f.asEReal∗ □ (L.adjoint ▷ g.asEReal∗)) : ∂ (f + g ∘ L) = (∂ f) + adjointImageSubdifferential L g

Example 16.43

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.43: if f ∈ Γ₀(H) and γ ∈ ℝ_{++}, then the subdifferential of f + (γ / 2) ‖·‖² is ∂ f + γ Id, encoded here as the set-valued map x ↦ (∂ f) x + {γ • x}.

open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: apply the chapter sum rule for the full-domain quadratic perturbation -- `γ • halfSquaredNorm`, then identify its subdifferential via Proposition 16.6 and -- Example 16.12 as the singleton-valued map `x ↦ {γ • x}`. theorem subdifferential_add_scaledHalfSquaredNorm_eq_add_singleton_smul (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (γ : PosReal) : ∂ (f + γ • halfSquaredNorm) = (∂ f) + fun x ↦ ({(γ : ℝ) • x} : Set H)

Proposition 16.44

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.44: for f ∈ Γ₀(H) and x, p ∈ H, the point p equals Prox_f x exactly when the residual x - p belongs to the subdifferential of f at p.

open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem eq_proximityOperator_iff_sub_mem_subdifferential {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (x p : H) : p = Prox[f, hf] x ↔ x - p ∈ (∂ f) p

Proposition 16.45

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.45: if f ∈ Γ₀(H), then the range of the set-valued operator id.toSetValuedOperator + ∂ f, i.e. Id + ∂ f, is all of H.

open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: apply `SetValuedOperator.dom` to the inverse formula from Proposition 16.44, -- rewrite the domain of the singleton-valued proximity operator pointwise as `Set.univ`, and use -- Text 1.0.12 to identify the domain of the inverse with the range of the operator sum -- `(id.toSetValuedOperator + ∂ f)`. theorem range_id_add_subdifferential_eq_univ_of_mem_gammaZero {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) : SetValuedOperator.range ((id : H → H).toSetValuedOperator + ∂ f) = Set.univ

Remark 16.46

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

If f∗[hf] □ g∗[hg] is exact on the domain of the canonical packaged conjugate of f + g, then the subdifferential of f + g splits as the pointwise sum ∂ f + ∂ g. This is the statement displayed as (16.39) in Remark 16.46.

open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: Proposition 16.42 identifies `∂ (f + g)` with `∂ f + ∂ g` once the conjugate -- formula holds. Exactness of `f∗[hf] □ g∗[hg]` on `dom ((f + g)∗[...])` upgrades the ordinary -- infimal convolution to that conjugate formula at precisely the points where -- Proposition 16.42 needs it. theorem subdifferential_add_eq_add_of_infimalConvolution_exactOn_dom_conjugate (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hdom : (effectiveDomain f ∩ effectiveDomain g).Nonempty) (hexact : ∀ ⦃u : H⦄, u ∈ dom ((f + g)∗[pointwiseAdd_mem_gammaZero f g hf hg hdom]) → infimalConvolution.ExactAt (f∗[hf]) (g∗[hg]) u) : (∂ (f + g) : SetValuedOperator H H) = ∂ f + ∂ g

Theorem 16.47

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 16.47: if f ∈ Γ₀(H), g ∈ Γ₀(K), and 0 ∈ sri (effectiveDomain g - L '' effectiveDomain f), then ∂ (x ↦ f x + g (L x)) = ∂ f + L^* ∂ g L, realized as (∂ f) + ERealFunction.ContinuousLinearMap.adjointImageSubdifferential L g.

open Set open scoped InnerProductSpace Pointwise universe u v namespace ERealFunction open ContinuousLinearMap variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] -- Proof sketch: apply Theorem 15.27 under the chapter owner regularity -- `0 ∈ sri (effectiveDomain g - L '' effectiveDomain f)`, then feed the resulting composite -- conjugate formula into Proposition 16.42. theorem subdifferential_add_comp_eq_add_adjoint_image_of_regular {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {g : K → Set.Ioi (⊥ : EReal)} (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hsri : (0 : K) ∈ sri (effectiveDomain g - L '' effectiveDomain f)) : ∂ (f + g ∘ L) = (∂ f) + adjointImageSubdifferential L g

Corollary 16.48

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.48 regularity reduction: clauses (ii) through (iv) of the textbook assumptions imply the canonical regularity hypothesis 0 ∈ sri (effectiveDomain f - effectiveDomain g).

open Set open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem zero_mem_strongRelativeInterior_sub_effectiveDomain_of_inter_dom_or_dom_univ_or_ri {f g : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hregular : (effectiveDomain f ∩ interior (effectiveDomain g)).Nonempty ∨ effectiveDomain g = univ ∨ (FiniteDimensional ℝ H ∧ (ri (effectiveDomain f) ∩ ri (effectiveDomain g)).Nonempty)) : (0 : H) ∈ sri (effectiveDomain f - effectiveDomain g)

Corollary 16.49

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.49 (1) is Proposition 16.27.

open Set open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] #check interior_effectiveDomain_eq_setOf_continuousAtOnEffectiveDomain_of_mem_gammaZero -- Proof sketch: rewrite the continuity set using Proposition 16.27, then use convexity of -- `effectiveDomain f` from `hf` together with the Chapter 6 fact that the interior of a convex set -- is contained in its strong relative interior.

Corollary 16.50

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.50: for a finite family f : Fin (n + 2) → Γ₀(H) corresponding to the textbook index set {1, ..., m} with m ≥ 2, if one of the source regularity conditions (i)--(v) holds for the effective domains, then the subdifferential of the finite sum is the finite sum of the subdifferentials.

open Set open scoped BigOperators InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: prove the statement by induction on the family length. In the inductive step, -- apply Corollary 16.48 to the pair consisting of the last function and the preceding finite sum; -- clause (i) is used directly, while clauses (ii)--(v) reduce to clause (i) through Proposition -- 6.20 together with Proposition 8.2, exactly as in the source proof. theorem subdifferential_sum_eq_sum_of_successiveDomainRegularity (n : ℕ) (f : Fin (n + 2) → H → Set.Ioi (⊥ : EReal)) (hf : ∀ i : Fin (n + 2), f i ∈ Γ₀(H)) (hregular : (0 : H) ∈ successiveStrongRelativeInteriorIntersection n (fun i ↦ effectiveDomain (f i)) ∨ successiveDifferenceRegularity n (fun i ↦ effectiveDomain (f i))) : (∂ (∑ i, f i) : SetValuedOperator H H) = ∑ i, ∂ f i

Example 16.51

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.51: for the closed unit balls centered at (-1,0) and (1,0) in ℝ², the subdifferential of ι[C] + ι[D] at the origin is not the sum of the subdifferentials of ι[C] and ι[D].

open ERealFunction open Set open scoped EuclideanSpace InnerProductSpace Pointwise namespace ERealFunction local notation "ℝ²" => EuclideanSpace ℝ (Fin 2) local notation "C" => Metric.closedBall (!₂[(-1 : ℝ), 0] : ℝ²) 1 local notation "D" => Metric.closedBall (!₂[(1 : ℝ), 0] : ℝ²) 1 -- Proof sketch: expand membership in the two closed balls as distance inequalities to `(-1,0)` -- and `(1,0)`. The two inequalities force both coordinates to vanish, and conversely the origin -- satisfies both. theorem subdifferential_oppositeClosedBallIndicatorSum_at_origin_ne_sum_subdifferentials : (∂ (ι[C] + ι[D])) (0 : ℝ²) ≠ (∂ ι[C]) (0 : ℝ²) + (∂ ι[D]) (0 : ℝ²)

Corollary 16.52

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.52: if f ∈ Γ₀(H) is bounded below, then 0 belongs to the closure of the range of its subdifferential.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: for each `ε > 0`, Corollary 11.16 gives a -- minimizer `z` of `x ↦ f x + ε * ‖x‖`. Fermat's rule from Theorem 16.3 yields -- `0 ∈ (∂ (pointwiseAdd f (ε • normFunctionIoi))) z`, Corollary 16.48 splits this -- subdifferential as a sum, and Example 16.32 identifies the norm subdifferential with the closed -- unit ball. Hence for every `ε > 0` there is `u ∈ SetValuedOperator.range (∂ f)` with -- `‖u‖ ≤ ε`, which implies `0 ∈ closure (SetValuedOperator.range (∂ f))`. theorem zero_mem_closure_range_subdifferential_of_mem_gammaZero_of_bddBelow {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (hbounded : BddBelow (Set.range f)) : (0 : H) ∈ closure (SetValuedOperator.range (∂ f))

Corollary 16.53

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.53: if g ∈ Γ₀(K) and either (i) 0 ∈ sri (effectiveDomain g - Set.range L) or (ii) K is finite-dimensional, g has polyhedral epigraph, and effectiveDomain g meets Set.range L, then ∂ (g ∘ L) = L^* ∘ (∂ g) ∘ L, realized as adjointImageSubdifferential L g.

open Set open scoped InnerProductSpace Pointwise universe u v namespace ERealFunction open ContinuousLinearMap variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem subdifferential_comp_eq_adjoint_image_of_regular (g : K → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hregular : (0 : K) ∈ sri (effectiveDomain g - Set.range L) ∨ (FiniteDimensional ℝ K ∧ Polyhedral g.asEReal ∧ (effectiveDomain g ∩ Set.range L).Nonempty)) : ∂ (g ∘ L) = adjointImageSubdifferential L g

Example 16.54

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.54: for the reflected function fᵛ (the textbook f^∨, i.e. (f.asEReal)ᵛ at the EReal layer), the subdifferential is the negative of the reflected subdifferential operator (∂ f)ᵛ.

open scoped Function InnerProductSpace Pointwise SetValuedOperator universe u namespace ERealFunction open SetValuedOperator variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem subdifferential_reverse_eq_neg_reverse (f : H → Set.Ioi (⊥ : EReal)) : ∂ fᵛ = (-((((∂ f : SetValuedOperator H H)ᵛ) : SetValuedOperator H H)) : SetValuedOperator H H)

Example 16.55

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.55: if z belongs to the finite halfspace intersection {x | ∀ i : s, ⟪x, u i⟫ ≤ β i}, then the normal cone at z is the pointed cone generated by the active normals u i with ⟪z, u i⟫ = β i, which is the Lean form of ∑_{j ∈ J} ℝ₊ u_j.

open Set open scoped InnerProductSpace Pointwise universe u v variable {ι : Type v} variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem normalCone_finiteHalfspaceIntersection_eq_pointedConeHull_activeNormals (s : Finset ι) (u : s → H) (β : s → ℝ) {z : H} (hz : ∀ i : s, ⟪z, u i⟫_ℝ ≤ β i) : N[({x : H | ∀ i : s, ⟪x, u i⟫_ℝ ≤ β i} : Set H)] z = (PointedCone.hull ℝ (u '' {i : s | ⟪z, u i⟫_ℝ = β i}) : Set H)

Theorem 16.56

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 16.56: if f ∈ Γ₀(H), if x₀ and x₁ belong to effectiveDomain f, and if one of the following holds, with the affine line aff{x₀,x₁} represented by the canonical owner line[ℝ, x₀, x₁]: (i) 0 ∈ sri (effectiveDomain f - aff{x₀,x₁}); (ii) aff{x₀,x₁} meets interior (effectiveDomain f); or (iii) H is finite-dimensional and aff{x₀,x₁} meets ri (effectiveDomain f), then the endpoint value difference f x₁ - f x₀ is the inner product of x₁ - x₀ with some subgradient of f at a point of ]x₀,x₁[.

open Set open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem exists_subgradient_on_openSegment_eq_endpoint_value_difference_of_segment_regularity {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {x0 x1 : H} (hx0 : x0 ∈ effectiveDomain f) (hx1 : x1 ∈ effectiveDomain f) (hregular : (0 : H) ∈ sri (effectiveDomain f - (line[ℝ, x0, x1] : Set H)) ∨ ((line[ℝ, x0, x1] : Set H) ∩ interior (effectiveDomain f)).Nonempty ∨ (FiniteDimensional ℝ H ∧ ((line[ℝ, x0, x1] : Set H) ∩ ri (effectiveDomain f)).Nonempty)) : ∃ x ∈ openSegment ℝ x0 x1, ∃ u ∈ (∂ f) x, (f x1 : EReal) - (f x0 : EReal) = (⟪x1 - x0, u⟫_ℝ : EReal)

Corollary 16.57

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.57: a continuous convex real-valued function on a real Hilbert space is β-Lipschitz whenever the range of the subdifferential of its canonical ]-∞,+∞]-valued coercion is contained in B(0;β).

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem lipschitzWith_of_continuous_convexOn_univ_of_range_subdifferential_subset_closedBall (f : H → ℝ) (β : NNReal) (hcont : Continuous f) (hconv : _root_.ConvexOn ℝ Set.univ f) (hsubgrad : SetValuedOperator.range (∂ f.toEReal) ⊆ Metric.closedBall (0 : H) β) : LipschitzWith β f

Theorem 16.58

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 16.58: the Brondsted--Rockafellar approximation theorem. For f ∈ Γ₀(H), if the Fenchel--Young gap at (y, v) is at most λμ, then there exist z and w ∈ (∂ f) z with z within distance λ of y and w within distance μ of v.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem exists_subgradient_point_close_of_fenchelYoung_gap_le (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (y v : H) (lam μ : NNReal) (hgap : (f y : EReal) + (f∗[hf] v : EReal) ≤ ((⟪y, v⟫_ℝ + ((lam * μ : NNReal) : ℝ) : ℝ) : EReal)) : ∃ z w, w ∈ (∂ f) z ∧ ‖z - y‖ ≤ (lam : ℝ) ∧ ‖w - v‖ ≤ (μ : ℝ)

Proposition 16.59

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.59: if the marginal function of F over the second variable is attained at (x, y), then u belongs to the subdifferential of that marginal at x exactly when (u, 0) belongs to the product-space subdifferential of F at (x, y).

open scoped InnerProductSpace universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] theorem mem_subdifferential_marginalFunction_iff_mem_subdifferential_zeroSecond_of_value_eq (F : H × K → Set.Ioi (⊥ : EReal)) (x : H) (y : K) (hxy : marginalFunction F x = (F (x, y) : EReal)) (u : H) : u ∈ (∂ marginalFunction F) x ↔ (u, (0 : K)) ∈ (∂ F) (x, y)

Proposition 16.60

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.60 (1): if y = L x and the infimal postcomposition is exact there through the point x, then formula (16.50) identifies the subdifferential of L ▷ f at y with the adjoint preimage (L^*)⁻¹ (∂ f(x)).

open scoped InnerProductSpace universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem subdifferential_infimalPostcomposition_eq_preimage_adjoint_of_value_eq (f : H → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] K) {x : H} {y : K} (hxy : L x = y) (hEq : (L ▷ f) y = (f x : EReal)) : (∂ (L ▷ f)) y = (L.adjoint) ⁻¹' ((∂ f) x)

Proposition 16.61

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.61 (1): if the infimal convolution f □ g is exact at x, attained by y, then, under f, g ∈ Γ₀(H), the subdifferential of f □ g at x is the intersection of the subdifferentials of f at y and of g at x - y.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [CompleteSpace H] variable (f g : H → Set.Ioi (⊥ : EReal)) (x y : H) -- Proof sketch: rewrite `f □ g` as the infimal postcomposition of the separable sum by the -- addition map, apply Proposition 16.60(i) at the exact point `(y, x - y)`, and identify the -- resulting adjoint preimage with the intersection of the two component subdifferentials via the -- product-space subdifferential formula. theorem subdifferential_infimalConvolution_eq_inter_of_value_eq (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hEq : (f □ g) x = (f y : EReal) + (g (x - y) : EReal)) : (∂ (f □ g)) x = (∂ f) y ∩ (∂ g) (x - y)

Example 16.62

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.62: for a nonempty closed convex subset C of a real Hilbert space, the subdifferential of the distance-to-set function is the singleton containing the normalized projection residual outside C, the intersection N[C] x ∩ Metric.closedBall (0 : H) 1 on the boundary, and {0} off the boundary inside C (equivalently, on interior C).

open scoped InnerProductSpace Pointwise Set universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : Set H} variable (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) local notation "hC_cheb" => isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex local notation "P" => P[C, hC_cheb] theorem subdifferential_distanceToSet_eq_piecewise_of_nonempty_isClosed_convex (x : H) : (∂ (fun y : H ↦ Metric.infDist y C).toEReal) x = if hxC : x ∈ C then if hxbdry : x ∈ frontier C then N[C] x ∩ Metric.closedBall (0 : H) 1 else ({0} : Set H) else ({(Metric.infDist x C)⁻¹ • (x - P x)} : Set H)

Proposition 16.63

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.63: if φ ∈ Γ₀(H) and either (i) μ Set.univ < ∞ or (ii) φ attains its minimum value 0 at the origin, then at every point of the effective domain of the integral functional induced by φ, the subdifferential consists exactly of those L² fields whose values belong almost everywhere to the pointwise subdifferential of φ. The Γ₀-membership clause is the existing theorem integralFunctional_mem_gammaZero.

open MeasureTheory open scoped InnerProductSpace universe u v namespace ERealFunction variable {Ω : Type u} [MeasurableSpace Ω] {μ : Measure Ω} variable {H : Type v} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] [MeasurableSpace H] [BorelSpace H] [TopologicalSpace.SeparableSpace H] [μ.IsComplete] [SigmaFinite μ] theorem subdifferential_integralFunctional_eq_ae_subdifferential (φ : H → Set.Ioi (⊥ : EReal)) (hφ : φ ∈ Γ₀(H)) (hfinite_or_nonneg : μ Set.univ < ⊤ ∨ ((φ 0 : EReal) = 0 ∧ ∀ z : H, (φ 0 : EReal) ≤ (φ z : EReal))) {x : Ω →₂[μ] H} (hx : x ∈ effectiveDomain (integralFunctional μ φ)) : (∂ integralFunctional μ φ) x = {u : Ω →₂[μ] H | ∀ᵐ ω ∂μ, u ω ∈ (∂ φ) (x ω)}

Example 16.64

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.64: every L² field that agrees almost everywhere with the normalized pointwise formula ω ↦ if x ω = 0 then 0 else ‖x ω‖⁻¹ • x ω is a subgradient of the integral norm functional at x. The normalized-field hypothesis already forces x into the effective domain of the integral functional.

open MeasureTheory open scoped InnerProductSpace universe u v namespace ERealFunction variable {Ω : Type u} [MeasurableSpace Ω] {μ : Measure Ω} variable {H : Type v} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] [MeasurableSpace H] [BorelSpace H] [TopologicalSpace.SeparableSpace H] [μ.IsComplete] [SigmaFinite μ] theorem normalizedField_mem_subdifferential_integralFunctional_norm {x u : Ω →₂[μ] H} (hu : ∀ᵐ ω ∂μ, u ω = if x ω = 0 then 0 else ‖x ω‖⁻¹ • x ω) : u ∈ (∂ integralFunctional μ ((norm : H → ℝ).toEReal)) x

Proposition 16.65

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.65: for an autoconjugate member F ∈ Γ₀(H × H), the equality F(x, u) = ⟪x, u⟫, the corresponding equality for the conjugate at (u, x), the subgradient condition (u, x) ∈ ∂F(x, u), and the proximal identity (x, u) = Prox_F (x + u, x + u) are equivalent.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem autoconjugate_tfae_at_pair (F : H × H → Set.Ioi (⊥ : EReal)) (hF : F ∈ Γ₀(H × H)) (hauto : autoconjugate F.asEReal) (x u : H) : List.TFAE [(F (x, u) : EReal) = ((⟪x, u⟫_ℝ : ℝ) : EReal), (F∗[hF] (u, x) : EReal) = ((⟪x, u⟫_ℝ : ℝ) : EReal), (u, x) ∈ (∂ F) (x, u), (x, u) = Prox[F, hF] (x + u, x + u)]

Proposition 16.66

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.66: if F ∈ Γ₀(H × H) and L(x, u) = (u, x), then the proximity operator of F^{*T}, encoded canonically as F∗ᵀ[hF], is Id - L ∘ Prox_F ∘ L, i.e. p ↦ p - (Prox_F (p.swap)).swap.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem proximityOperator_gammaZeroConjugate_transpose_eq_id_sub_swap_proximityOperator_swap (F : H × H → Set.Ioi (⊥ : EReal)) (hF : F ∈ Γ₀(H × H)) : Prox⋆ᵀ[F, hF] = fun p : H × H ↦ p - (Prox[F, hF] p.swap).swap

Definition 16.67

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 16.67: the coderivative of a set-valued operator F at (x, y) sends v to the set of all u such that (u, -v) belongs to the normal cone to graph F at (x, y).

open scoped InnerProductSpace Pointwise Set universe u v namespace SetValuedOperator variable {H : Type u} {K : Type v} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [NormedAddCommGroup K] [InnerProductSpace ℝ K] def coderivative (F : SetValuedOperator H K) (x : H) (y : K) : SetValuedOperator K H := fun v ↦ {u : H | (u, -v) ∈ N[graph F] (x, y)}

Example 16.68

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.68: for the constant set-valued operator F z = C, the graph of D*F(x, y) is -N[C] y × {0}.

open Set open scoped InnerProductSpace Pointwise universe u v namespace SetValuedOperator variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] theorem graph_coderivative_constant_eq_neg_normalCone_prod_singleton_zero {C : Set K} {x : H} {y : K} : ((D* (fun _ : H ↦ C)) x y).graph = (-N[C] y) ×ˢ ({0} : Set H)

Proposition 16.69

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.69: if f is convex on its effective domain and x ∈ dom f, then the coderivative of the epigraphical operator x ↦ {y ∈ ℝ | f x ≤ y} at the graph point (x, (f x).toReal) is v • ∂ f x for v > 0, the normal cone to dom f at x for v = 0, and ∅ for v < 0.

open scoped Pointwise open WithLp universe u namespace ERealFunction open Set open SetValuedOperator variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: identify the graph of `epigraphicalOperator f` with the real-height epigraph of -- `f`, rewrite the left-hand side through the canonical coderivative owner `D*`, and then split on -- the sign of `v`. The case `v > 0` reduces to the epigraph-normal characterization of the -- subdifferential from Proposition 16.16, the case `v = 0` is the horizontal slice giving the -- normal cone to `effectiveDomain f`, and convexity of the epigraph rules out any normal vector -- with negative scalar component. theorem coderivative_epigraphicalOperator_eq_piecewise (f : H → Set.Ioi (⊥ : EReal)) (hconvex : ConvexOn f (effectiveDomain f)) {x : H} (hx : x ∈ effectiveDomain f) : ((D* (epigraphicalOperator f)) x ((f x : EReal).toReal)) = fun v : ℝ ↦ if 0 < v then v • (∂ f) x else if v = 0 then N[effectiveDomain f] x else ∅

Proposition 16.70

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 16.70: at an active graph point for the marginal representation marginalFunction (pointwiseAdd g (ι[gra F])), every active subgradient of g at (xbar, y) together with the coderivative contribution D*F(xbar, y)(v) yields a subgradient of that infimal projection at xbar.

open scoped InnerProductSpace Pointwise universe u v namespace ERealFunction open SetValuedOperator variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] theorem subgradient_coderivative_sum_subset_subdifferential_of_setValuedInfimalProjection (g : H × K → Set.Ioi (⊥ : EReal)) (F : SetValuedOperator H K) {xbar : H} : {w : H | ∃ y ∈ F xbar, marginalFunction (pointwiseAdd g (ι[gra F])) xbar = (g (xbar, y) : EReal) ∧ ∃ p ∈ (∂ g) (xbar, y), w ∈ ({p.1} : Set H) + (((D* F) xbar) y p.2)} ⊆ (∂ marginalFunction (pointwiseAdd g (ι[gra F]))) xbar

Theorem 16.71

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 16.71: if g ∈ Γ₀(H × K), F : H → 2^K has closed convex graph, (xbar, ybar) is an active graph point for the canonical infimal projection marginalFunction (g + ι[gra F]), and ((0 : H), (0 : K)) ∈ sri (gra F - dom g), then the subdifferential of that infimal projection at xbar is exactly ⋃ (u, v) ∈ (∂ g) (xbar, ybar), u + D*F(xbar, ybar)(v).

open Set open scoped InnerProductSpace Pointwise open WithLp universe u v namespace ERealFunction open SetValuedOperator variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem subdifferential_eq_iUnion_add_coderivative_of_setValuedInfimalProjection (g : H × K → Set.Ioi (⊥ : EReal)) (F : SetValuedOperator H K) (xbar : H) (ybar : K) (hg : g ∈ Γ₀(H × K)) (hgraph_closed : IsClosed (gra F)) (hgraph_convex : Convex ℝ (gra F)) (hybar : ybar ∈ F xbar) (hactive : marginalFunction (g + ι[gra F]) xbar = (g (xbar, ybar) : EReal)) (hregular : ((0 : H), (0 : K)) ∈ sri (gra F - effectiveDomain g)) : (∂ marginalFunction (g + ι[gra F])) xbar = ⋃ p ∈ (∂ g) (xbar, ybar), ({p.1} : Set H) + (((D* F) xbar) ybar p.2)

Corollary 16.72

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 16.72: if f : H → ℝ is continuous and convex, φ ∈ Γ₀(ℝ) is increasing on range f, and the regularity condition (ri (range f) + ℝ_{++}) ∩ ri (dom φ) ≠ ∅ holds, then the subdifferential of the scalar composition φ ∘ f at xbar is exactly the union of the scaled subdifferentials α • (∂ f.toEReal) xbar over α ∈ (∂ φ) (f xbar).

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: view the real-valued convex map `f` through `f.toEReal`, use the -- composition result of Proposition 8.21 to place `φ ∘ f` in the convex lsc setting, then apply -- the infimal-projection chain rule from Theorem 16.71 to the epigraphical operator -- `x ↦ {y : ℝ | f x ≤ y}`. Proposition 16.69 identifies the resulting coderivative slice with the -- scaled set `α • (∂ f.toEReal) xbar`. theorem subdifferential_comp_eq_iUnion_smul_of_continuous_convexOn_univ_of_monotoneOn_range (f : H → ℝ) (φ : ℝ → Set.Ioi (⊥ : EReal)) (hcont : Continuous f) (hconv : _root_.ConvexOn ℝ Set.univ f) (hφ : φ ∈ Γ₀(ℝ)) (hmono : MonotoneOn φ (range f)) (hregular : ((ri (range f) + Ioi (0 : ℝ)) ∩ ri (effectiveDomain φ)).Nonempty) (xbar : H) (hxbar : f xbar ∈ effectiveDomain φ) : (∂ (φ ∘ f)) xbar = ⋃ α ∈ (∂ φ) (f xbar), α • ((∂ f.toEReal) xbar)

Example 16.73

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 16.73 (1): if φ : ℝ → ℝ is convex and even, then the scalar subdifferential at 0 is a symmetric interval [-ρ, ρ] for some ρ ∈ ℝ₊.

universe u namespace ERealFunction variable (φ : ℝ → ℝ) theorem exists_symmetric_subdifferential_zero_eq_interval (hconv : _root_.ConvexOn ℝ Set.univ φ) (heven : Function.Even φ) : ∃ ρ : NNReal, (∂ φ.toEReal) 0 = Set.Icc (-(ρ : ℝ)) (ρ : ℝ)