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.
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 PositivelyHomogeneousProposition 10.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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_sublinearExample 10.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 = 0Corollary 10.13
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 = 0Proposition 10.14
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 tProposition 10.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 ≤
χ tExample 10.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 ψ fCorollary 10.18
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 ψ fExample 10.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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_19FunctionDefinition 10.20
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 fExample 10.21
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 fExample 10.22
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 fExample 10.23
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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 fExample 10.30
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.asERealExample 10.31
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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)