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.
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.
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))).NonemptyTheorem 16.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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).zerosProposition 16.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 fProposition 16.5
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 xProposition 16.6
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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)).NonemptyCorollary 16.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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).asERealProposition 16.27
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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 uExample 16.32
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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])) 0Example 16.34
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 = CProposition 16.35
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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 gExample 16.43
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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) pProposition 16.45
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.univRemark 16.46
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 + ∂ gTheorem 16.47
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 gCorollary 16.48
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 iExample 16.51
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 gExample 16.54
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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 β fTheorem 16.58
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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)) xProposition 16.65
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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).swapDefinition 16.67
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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]))) xbarTheorem 16.71
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 (-(ρ : ℝ)) (ρ : ℝ)