Chapter 10 — Convex Functions: Variants

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

Definition 10.1

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

Source header · Attribution source

Definition 10.1: positive homogeneity is the canonical owner PositivelyHomogeneous; for EReal-valued functions, the codomain scalar action is the real multiplication action on EReal recalled in Chapter 1.

universe u recall PositivelyHomogeneous

Proposition 10.2

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

Source header · Attribution source

Proposition 10.2: an extended-real-valued function is positively homogeneous if and only if its epigraph is a cone.

universe u namespace ERealFunction variable {H : Type u} [AddCommGroup H] [Module ℝ H] theorem positivelyHomogeneous_iff_isCone_epigraph (f : H → EReal) : PositivelyHomogeneous f ↔ IsCone (epigraph f)

Proposition 10.3

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

Source header · Attribution source

Proposition 10.3: a positively homogeneous ]-∞,+∞]-valued function on a real vector space is sublinear if and only if it is Jensen convex.

universe u open scoped Pointwise namespace ERealFunction variable {H : Type u} [AddCommGroup H] [Module ℝ H] theorem sublinear_iff_isConvex_of_positivelyHomogeneous (f : H → Set.Ioi (⊥ : EReal)) (hf : PositivelyHomogeneous fun x : H ↦ (f x : EReal)) : Sublinear (fun x : H ↦ (f x : EReal)) ↔ IsConvex (fun x : H ↦ (f x : EReal))

Example 10.4

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

Source header · Attribution source

Example 10.4 (i): the norm function is sublinear.

universe u open ERealFunction variable {H : Type u} [SeminormedAddCommGroup H] [NormedSpace ℝ H] -- Proof sketch: the norm is positively homogeneous for positive real scalars, and -- `sublinear_iff_isConvex_of_positivelyHomogeneous` upgrades the canonical convexity theorem -- `convexOn_univ_norm` to sublinearity. theorem norm_sublinear : Sublinear (fun x : H ↦ (‖x‖ : EReal))

Example 10.5

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

Source header · Attribution source

Example 10.5: the perspective of a convex extended-real-valued function is sublinear.

universe u open ERealFunction variable {H : Type u} [AddCommGroup H] [Module ℝ H] -- Proof sketch: convert Jensen convexity of `φ` into convexity of its real-height epigraph using -- Proposition 8.4. Proposition 8.25 packages the epigraph of `perspective φ` as both a cone and a -- convex set. Proposition 10.2 turns that cone description into positive homogeneity, and -- Proposition 10.3 upgrades positive homogeneity plus convex epigraph to sublinearity. theorem perspective_sublinear (φ : H → EReal) (hφ : IsConvex φ) : Sublinear (perspective φ)

Example 10.6

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

Source header · Attribution source

Example 10.6: the recession function of a Γ₀(H) function is sublinear.

open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [TopologicalSpace H] [AddCommGroup H] [Module ℝ H] theorem recessionFunction_sublinear_of_mem_gammaZero (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) : Sublinear (fun y : H ↦ (recessionFunction f hf.2.nonempty y : EReal))

Definition 10.7

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

Source header · Attribution source

Definition 10.7: a proper ]-∞,+∞]-valued function is uniformly convex with modulus φ when φ is increasing, vanishes only at 0, and the uniform Jensen inequality holds on the effective domain of f.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] def UniformlyConvex (f : H → Set.Ioi (⊥ : EReal)) (φ : NNReal → EReal) : Prop := UniformlyConvexOn f (effectiveDomain f) φ

Proposition 10.8

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

Source header · Attribution source

Proposition 10.8: a proper ]-∞,+∞]-valued function is strongly convex with constant β iff its finite representative on the effective domain becomes convex after subtracting (β / 2)‖·‖².

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem stronglyConvex_iff_convexOn_toReal_sub_sq {f : H → Set.Ioi (⊥ : EReal)} {β : ℝ} (hdom : (effectiveDomain f).Nonempty) : StronglyConvex f β ↔ 0 < β ∧ _root_.ConvexOn ℝ (effectiveDomain f) (fun x ↦ (f x : EReal).toReal - β / 2 * ‖x‖ ^ (2 : ℕ))

Example 10.9

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

Source header · Attribution source

Example 10.9 (1): the norm function is sublinear; this is exactly the earlier norm_sublinear from Example 10.4.

universe u variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] recall norm_sublinear

Example 10.10

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

Source header · Attribution source

Example 10.10 correction: monotonicity of φ alone does not force bounded-set uniform convexity. For the constant choice φ ≡ 1, the radial primitive is not uniformly convex on any nontrivial segment.

universe u open Set variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem radialIntegral_const_not_uniformlyConvexOn_segment {u : E} (hu : u ≠ 0) : ¬ ∃ ψ : ℝ → ℝ, (∀ ⦃r : ℝ⦄, r ≠ 0 → 0 < ψ r) ∧ UniformConvexOn (segment ℝ (0 : E) u) ψ (fun x : E ↦ ∫ t in 0..‖x‖, (1 : ℝ))

Definition 10.11

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

Source header · Attribution source

Definition 10.11: for a proper convex ]-∞,+∞]-valued function, the exact modulus of convexity assigns to each radius t ≥ 0 the infimum of the normalized Jensen gaps over all effective-domain pairs at distance t and all coefficients α ∈ ]0,1[.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] noncomputable def exactModulusOfConvexity (f : H → Set.Ioi (⊥ : EReal)) : NNReal → EReal := fun t ↦ sInf {δ : EReal | ∃ x ∈ effectiveDomain f, ∃ y ∈ effectiveDomain f, ‖x - y‖₊ = t ∧ ∃ α : ℝ, α ∈ Set.Ioo (0 : ℝ) 1 ∧ δ = jensenGap f α x y / (α * (1 - α) : ℝ)}

Proposition 10.12

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

Source header · Attribution source

Proposition 10.12 (1): for a proper convex ]-∞,+∞]-valued function, the exact modulus of convexity vanishes at 0.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] variable (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f)) -- Proof sketch: use `hconv.nonempty` to pick a point of the effective domain, then evaluate the -- defining infimum at the diagonal pair `x = y`; convexity gives the opposite inequality for every -- normalized Jensen gap, so the infimum at radius `0` is exactly `0`. theorem exactModulusOfConvexity_zero : exactModulusOfConvexity f 0 = 0

Corollary 10.13

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

Source header · Attribution source

Corollary 10.13, canonical owner form: the exact modulus of convexity is itself a modulus of uniform convexity precisely when it vanishes only at 0.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] -- Proof sketch: the forward implication is `UniformlyConvex.modulus_eq_zero_iff` specialized to -- the exact modulus. For the reverse implication, use Proposition 10.12 to obtain monotonicity -- and the value at `0`, then verify the defining Jensen inequality for -- `UniformlyConvex f (exactModulusOfConvexity f)` from the infimum property of -- `exactModulusOfConvexity`. theorem exactModulusOfConvexity_uniformlyConvex_iff (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f)) : UniformlyConvex f (exactModulusOfConvexity f) ↔ ∀ r : NNReal, exactModulusOfConvexity f r = 0 ↔ r = 0

Proposition 10.14

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

Source header · Attribution source

Proposition 10.14 (1): twice the midpoint Jensen-gap modulus is bounded above by the exact modulus of convexity.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] variable (f : H → Set.Ioi (⊥ : EReal)) theorem two_mul_midpointModulusOfConvexity_le_exactModulusOfConvexity (hconv : ConvexOn f (effectiveDomain f)) (t : NNReal) : 2 * midpointModulusOfConvexity f t ≤ exactModulusOfConvexity f t

Proposition 10.15

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

Source header · Attribution source

Proposition 10.15: for a uniformly convex nonnegative real-valued function g, the exact modulus of convexity of the pointwise power g^p is bounded below by 2^(1 - 2p) * min (p * 2^(1 - p)) (1 - 2^(-p)) * φ^p, where φ is the exact modulus of convexity of g.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] variable (g : H → NNReal) (p : ℝ) local notation "gE" => Function.toEReal (fun x : H ↦ (g x : ℝ)) local notation "gPow" => Function.toEReal (fun x : H ↦ (g x : ℝ) ^ p) local notation "φ" => exactModulusOfConvexity gE local notation "χ" => exactModulusOfConvexity gPow -- Proof sketch: apply the midpoint Jensen-gap estimate from the textbook proof to the finite -- `EReal` models `(fun x ↦ (g x : ℝ)).toEReal` and `(fun x ↦ (g x : ℝ) ^ p).toEReal`, then use -- Proposition 10.14 to pass from midpoint gaps to the exact modulus of convexity. The owner -- modulus is `EReal`-valued, while the textbook lower bound uses the nonnegative power `φ(t)^p`; -- `EReal.nnrpow` is the thin bridge/view that keeps the theorem surface at the exact-modulus -- level and hides the `toENNReal`/`toEReal` conversion bookkeeping. theorem exactModulusOfConvexity_nnreal_rpow_lower_bound (hp : 1 ≤ p) (hg : UniformlyConvex gE φ) (t : NNReal) : ((((2 : ℝ) ^ (1 - 2 * p) * min (p * (2 : ℝ) ^ (1 - p)) (1 - (2 : ℝ) ^ (-p))) : ℝ) : EReal) * (φ t).nnrpow p ≤ χ t

Example 10.16

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

Source header · Attribution source

Example 10.16: if p ∈ [2,+∞[, then the p-power of the norm is uniformly convex.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: Example 10.9(3) gives uniform convexity of `x ↦ ‖x‖^2` via strong convexity with -- constant `2`. Since `p / 2 ≥ 1` when `2 ≤ p`, apply Proposition 10.15 to the nonnegative -- function `x ↦ ‖x‖₊ ^ 2` to obtain uniform convexity of `x ↦ ‖x‖^p = (‖x‖^2)^(p/2)`, then use -- the exact modulus provided by that proposition. theorem norm_rpow_uniformlyConvex (p : ℝ) (hp : 2 ≤ p) : UniformlyConvex ((fun x : H ↦ ‖x‖ ^ p).toEReal) (exactModulusOfConvexity ((fun x : H ↦ ‖x‖ ^ p).toEReal))

Proposition 10.17

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

Source header · Attribution source

Proposition 10.17: if C is compact, f is strictly convex on C, and f|_C is continuous, then f admits a modulus positive away from 0 making it uniformly convex on C.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] theorem exists_uniformConvexOn_of_isCompact_of_strictConvexOn_of_continuousOn (f : H → ℝ) (C : Set H) (hC_compact : IsCompact C) (hstrict : StrictConvexOn ℝ C f) (hcont : ContinuousOn f C) : ∃ ψ : ℝ → ℝ, (∀ ⦃r : ℝ⦄, r ≠ 0 → 0 < ψ r) ∧ UniformConvexOn C ψ f

Corollary 10.18

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

Source header · Attribution source

Corollary 10.18: on a finite-dimensional real normed space, every strictly convex real-valued function is uniformly convex on each bounded closed convex subset.

universe u open ERealFunction -- Proof sketch: strict convexity on `Set.univ` gives continuity via -- `ConvexOn.locallyLipschitz`, finite dimensionality upgrades bounded closed subsets to compact -- ones, and Proposition 10.17 then supplies a modulus positive away from `0` on `C`. theorem uniformConvexOn_of_finiteDimensional_of_strictConvexOn_univ {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] [FiniteDimensional ℝ H] (f : H → ℝ) (hstrict : StrictConvexOn ℝ Set.univ f) (C : Set H) (hC_bounded : Bornology.IsBounded C) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : ∃ ψ : ℝ → ℝ, (∀ ⦃r : ℝ⦄, r ≠ 0 → 0 < ψ r) ∧ UniformConvexOn C ψ f

Example 10.19

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

Source header · Attribution source

Example 10.19 (1): the explicit function on ℝ² is strictly convex.

open Set namespace ERealFunction variable (ρ : Set.Ioi (0 : ℝ)) -- Proof sketch: analyze the explicit formula on the positive orthant, where the Hessian is -- positive definite, and note that the value `⊤` outside the effective domain forces the strict -- Jensen inequality whenever one endpoint leaves the domain. theorem example10_19Function_strictlyConvex : StrictlyConvex example10_19Function

Definition 10.20

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

Source header · Attribution source

Definition 10.20: the textbook notion of a quasiconvex ]-∞,+∞]-valued function is the canonical mathlib predicate QuasiconvexOn 𝕜 Set.univ f; the textbook real-vector-space version is the specialization 𝕜 = ℝ.

universe u v namespace ERealFunction variable (𝕜 : Type u) [Semiring 𝕜] [PartialOrder 𝕜] variable {H : Type v} [AddCommMonoid H] [SMul 𝕜 H] variable (f : H → EReal) #check QuasiconvexOn 𝕜 Set.univ f

Example 10.21

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

Source header · Attribution source

Example 10.21: every convex extended-real-valued function on the whole space is quasiconvex on the whole space.

universe u namespace ERealFunction theorem quasiconvexOn_univ_of_convex {H : Type u} [AddCommMonoid H] [Module ℝ H] {f : H → EReal} (hf : IsConvex f) : QuasiconvexOn ℝ Set.univ f

Example 10.22

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

Source header · Attribution source

Example 10.22: a monotone or antitone function on a linearly ordered module is quasiconvex on the whole space. The textbook extended-real-valued statement on a real vector space is the specialization 𝕜 = ℝ and β = EReal.

universe u v w variable {𝕜 : Type u} {E : Type v} {β : Type w} variable [Semiring 𝕜] [PartialOrder 𝕜] variable [AddCommMonoid E] [LinearOrder E] [IsOrderedAddMonoid E] [Module 𝕜 E] variable [PosSMulMono 𝕜 E] [PartialOrder β] theorem quasiconvexOn_univ_of_monotone_or_antitone {f : E → β} (hf : Monotone f ∨ Antitone f) : QuasiconvexOn 𝕜 Set.univ f

Example 10.23

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

Source header · Attribution source

Example 10.23: truncating a quasiconvex function on the whole space from above by a constant preserves quasiconvexity. The textbook statement for an extended-real-valued function on a real vector space is the specialization 𝕜 = ℝ and β = EReal.

universe u v w variable {𝕜 : Type u} {E : Type v} {β : Type w} variable [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] [LinearOrder β] theorem quasiconvexOn_univ_min_const {f : E → β} (hf : QuasiconvexOn 𝕜 Set.univ f) (η : β) : QuasiconvexOn 𝕜 Set.univ (fun x ↦ min (f x) η)

Proposition 10.24

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

Source header · Attribution source

Proposition 10.24: the pointwise supremum of a family of quasiconvex functions is quasiconvex on the whole space. The textbook extended-real-valued real-vector-space statement is the specialization 𝕜 = ℝ and β = EReal.

universe u v w x variable {𝕜 : Type u} {E : Type v} {β : Type w} variable [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] [CompleteLattice β] theorem quasiconvexOn_univ_iSup {I : Type x} {f : I → E → β} (hf : ∀ i, QuasiconvexOn 𝕜 Set.univ (f i)) : QuasiconvexOn 𝕜 Set.univ (fun x ↦ ⨆ i, f i x)

Proposition 10.25

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

Source header · Attribution source

Proposition 10.25: for a quasiconvex extended-real-valued function on a real Hilbert space, weak sequential lower semicontinuity, sequential lower semicontinuity, lower semicontinuity, and weak lower semicontinuity are equivalent.

open Filter open scoped InnerProductSpace Topology universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem quasiconvexOn_univ_lowerSemicontinuity_tfae {f : H → EReal} (hf : QuasiconvexOn ℝ Set.univ f) : List.TFAE [ (∀ ⦃xₙ : ℕ → H⦄ ⦃x : H⦄, Tendsto (fun n ↦ toWeakSpace ℝ H (xₙ n)) atTop (𝓝 (toWeakSpace ℝ H x)) → f x ≤ liminf (f ∘ xₙ) atTop), (∀ ⦃xₙ : ℕ → H⦄ ⦃x : H⦄, Tendsto xₙ atTop (𝓝 x) → f x ≤ liminf (f ∘ xₙ) atTop), LowerSemicontinuous f, WeaklyLowerSemicontinuous f ]

Proposition 10.26

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

Source header · Attribution source

Proposition 10.26: an extended-real-valued function is quasiconvex exactly when every strict convex combination of two points in its domain has value bounded above by the maximum of the two endpoint values.

universe u namespace ERealFunction variable {H : Type u} [AddCommMonoid H] [Module ℝ H] theorem quasiconvexOn_univ_iff_le_max_on_dom {f : H → EReal} : QuasiconvexOn ℝ Set.univ f ↔ ∀ ⦃x y : H⦄, x ∈ dom f → y ∈ dom f → ∀ ⦃α : ℝ⦄, α ∈ Set.Ioo (0 : ℝ) 1 → f (α • x + (1 - α) • y) ≤ max (f x) (f y)

Definition 10.27

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

Source header · Attribution source

Definition 10.27 (1): a proper function is strictly quasiconvex when every strict convex combination of two distinct points of dom f has value strictly below the larger endpoint value.

universe u namespace ERealFunction variable {H : Type u} [AddCommMonoid H] [Module ℝ H] variable {f : H → EReal} def StrictlyQuasiconvex (f : H → EReal) : Prop := IsProper f ∧ ∀ ⦃x y : H⦄, x ∈ dom f → y ∈ dom f → x ≠ y → ∀ ⦃α : ℝ⦄, 0 < α → α < 1 → f (α • x + (1 - α) • y) < max (f x) (f y)

Example 10.29

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

Source header · Attribution source

Example 10.29: for a proper function, strict monotonicity or strict antitonicity on a convex effective domain implies strict quasiconvexity.

open ERealFunction open AffineMap variable {f : ℝ → EReal} theorem strictlyQuasiconvex_of_strictMonoOn_dom_or_strictAntiOn_dom (hproper : IsProper f) (hdom : Convex ℝ (dom f)) (hf : StrictMonoOn f (dom f) ∨ StrictAntiOn f (dom f)) : StrictlyQuasiconvex f

Example 10.30

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

Source header · Attribution source

Example 10.30 (1): composing a strictly quasiconvex real-valued function with a strictly increasing function on its range preserves strict quasiconvexity.

universe u open ERealFunction variable {H : Type u} [AddCommMonoid H] [Module ℝ H] theorem strictlyQuasiconvex_comp_strictMono_range {f : H → ℝ} {φ : Set.range f → ℝ} (hf : StrictlyQuasiconvex f.toEReal.asEReal) (hφ : StrictMono φ) : StrictlyQuasiconvex (φ ∘ Set.rangeFactorization f).toEReal.asEReal

Example 10.31

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

Source header · Attribution source

Example 10.31 (1): clause (i). For p > 0, the norm-power function is strictly quasiconvex.

universe u open ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] [StrictConvexSpace ℝ H] -- Proof sketch: apply Example 10.30(2) to the norm with the monotone range map `t ↦ t ^ 2`. -- The resulting composition is exactly `x ↦ ‖x‖ ^ 2`, which is strictly convex by Example 8.23. theorem strictlyQuasiconvex_norm_rpow (p : ℝ) (hp : 0 < p) : StrictlyQuasiconvex ((fun x : H ↦ ‖x‖ ^ p).toEReal.asEReal)

Example 10.32

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

Source header · Attribution source

Example 10.32 (1): the linear function x ↦ ν x on ℝ is convex on the whole line.

open ERealFunction -- Proof sketch: an affine real-valued map on a real vector space is convex on every convex set; in -- particular, on `Set.univ` the Jensen inequality is an equality for `x ↦ νx`. theorem convexOn_univ_real_smul (ν : ℝ) : ConvexOn ℝ Set.univ (fun x : ℝ ↦ ν • x)