Chapter 08 — Convex Functions
Proofs omitted. Hover over highlighted terms to see their Lean types.
Text 8.0.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Text 8.0.1: the adjoint of φ : ℝ → ]-∞,+∞] is the function φ* defined by φ*(ξ) = ξ φ(1 / ξ) for ξ > 0 and φ*(ξ) = +∞ otherwise.
namespace ERealFunction
noncomputable def adjoint (φ : ℝ → Set.Ioi (⊥ : EReal)) : ℝ → Set.Ioi (⊥ : EReal) :=
fun ξ ↦
if hξ : 0 < ξ then
⟨(ξ : EReal) * (φ (1 / ξ) : EReal), adjoint_mul_mem_Ioi_bot ξ hξ (φ (1 / ξ))⟩
else
⟨(⊤ : EReal), top_mem_Ioi_bot⟩Text 8.0.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Text 8.0.2: the Minkowski gauge of a subset C is the ]-∞,+∞]-valued function sending x to the infimum of the positive real numbers ξ such that x ∈ ξ C.
universe u
open scoped Pointwise
variable {H : Type u} [SMul ℝ H]
noncomputable def minkowskiGauge (C : Set H) : H → EReal :=
fun x ↦ sInf (Real.toEReal '' {ξ : ℝ | 0 < ξ ∧ x ∈ ξ • C})Text 8.0.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Text 8.0.3: the Huber function with threshold ρ ∈ ℝ_{++} is quadratic on |x| ≤ ρ and affine in |x| on ρ < |x|.
open Set
noncomputable def huberFunction (ρ : Ioi (0 : ℝ)) : ℝ → ℝ :=
{x : ℝ | (ρ : ℝ) < |x|}.piecewise
(fun x ↦ (ρ : ℝ) * |x| - (ρ : ℝ) ^ 2 / 2)
(fun x ↦ |x| ^ 2 / 2)Definition 8.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Definition 8.1: the textbook real-height epigraph of an extended-real-valued function is the canonical set epigraph f already introduced in Definition 1.4; concretely, it consists of the pairs (x, ξ) : H × ℝ with f x ≤ ξ. In this chapter, convexity of f is expressed by Convex ℝ (epigraph f), and concavity by convexity of the epigraph of -f.
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
variable (f : H → EReal)
recall epigraphProposition 8.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.2: if an extended-real-valued function on a real vector space has convex epigraph, then its effective domain dom f = {x | f x < ⊤} is a convex subset of the ambient space.
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
theorem convex_dom_of_convex_epigraph (f : H → EReal) (hconv : Convex ℝ (epigraph f)) :
Convex ℝ (dom f)Example 8.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.3 (1): the epigraph of the extended-real indicator of C is exactly C × ℝ_+.
universe u
open Set
variable {X : Type u}
-- Proof sketch: unfold the real-height epigraph, split on whether `x ∈ C`, and use that the
-- indicator is `0` on `C` and `⊤` on `Cᶜ`.
theorem epigraph_indicator_eq_prod_nonneg (C : Set X) :
{ p : X × ℝ | (indicator Cᶜ fun _ : X ↦ (⊤ : EReal)) p.1 ≤ (p.2 : EReal) } =
C ×ˢ Set.Ici (0 : ℝ)Proposition 8.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.4: the real-height epigraph of an extended-real-valued function is convex if and only if Jensen's inequality holds for every two points of the effective domain `dom f = {x | f x < ⊤}and every coefficientα ∈ ]0,1[`.
universe u
namespace ERealFunction
variable {H : Type u} [AddCommMonoid H] [Module ℝ H]
theorem convex_epigraph_iff_jensen_on_dom (f : H → EReal) :
Convex ℝ (epigraph f) ↔
∀ ⦃x y : H⦄, x ∈ dom f → y ∈ dom f → ∀ ⦃α : ℝ⦄, 0 < α → α < 1 →
f (α • x + (1 - α) • y) ≤
(α : EReal) * f x + (((1 - α : ℝ) : EReal) * f y)Corollary 8.5
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 8.5: for an extended-real-valued convex function on a real vector space, every lower level set lev_{≤ ξ} f = {x | f x ≤ ξ} is convex.
universe u
namespace ERealFunction
variable {H : Type u} [AddCommMonoid H] [Module ℝ H]
theorem convex_lowerLevelSet_of_convex_epigraph (f : H → EReal)
(hconv : Convex ℝ (epigraph f)) (ξ : ℝ) :
Convex ℝ (lowerLevelSet f ξ)Proposition 8.6
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.6: if each coordinate function on a family of real Hilbert spaces has convex epigraph, then the function on the Hilbert sum lp H 2 obtained by summing the coordinate values is convex provided either the index type is finite or every coordinate function is bounded below by 0.
open Set
open scoped BigOperators
universe u v
namespace ERealFunction
variable {I : Type v} {H : I → Type u}
variable [∀ i, NormedAddCommGroup (H i)] [∀ i, InnerProductSpace ℝ (H i)]
theorem convex_epigraph_hilbertSumFunction
(f : ∀ i, H i → EReal)
(hnoBot : ∀ i x, f i x ≠ ⊥)
(hconv : ∀ i, Convex ℝ (epigraph (f i)))
(hfinite_or_nonneg : Finite I ∨ ∀ i, 0 ≤ sInf (Set.range (f i))) :
Convex ℝ (epigraph (hilbertSumFunction f))Definition 8.7
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Definition 8.7 (1): a proper ]-∞,+∞]-valued function is strictly convex when the strict Jensen inequality holds on its effective domain for every distinct pair of domain points and every coefficient α ∈ ]0,1[.
open Set
universe u
namespace ERealFunction
variable [AddCommGroup H] [Module ℝ H]
def StrictlyConvex (f : H → Set.Ioi (⊥ : EReal)) : Prop :=
∀ ⦃x : H⦄, x ∈ effectiveDomain f → ∀ ⦃y : H⦄, y ∈ effectiveDomain f → x ≠ y →
∀ ⦃α : ℝ⦄, 0 < α → α < 1 →
(f (α • x + (1 - α) • y) : EReal) <
(α : EReal) * (f x : EReal) + (1 - α : EReal) * (f y : EReal)Remark 8.8
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Remark 8.8: for an extended-real-valued function f with no -∞ values and finite on C (the part of properness and C ⊆ dom f used in the argument), the function f + ι_C is convex exactly when C is convex and f satisfies the convexity inequality on C. Here ι_C is written as the complement indicator Cᶜ.indicator (fun _ ↦ (⊤ : EReal)).
universe u
open Set
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
theorem convex_add_indicator_compl_top_iff
(f : E → EReal) (C : Set E) (hbot : ∀ x, f x ≠ ⊥)
(hCdom : ∀ ⦃x : E⦄, x ∈ C → f x < ⊤) :
(∀ ⦃x y : E⦄, ∀ ⦃t : ℝ⦄, t ∈ Set.Icc (0 : ℝ) 1 →
(f + Cᶜ.indicator (fun _ : E ↦ (⊤ : EReal))) (t • x + (1 - t) • y) ≤
(t : EReal) * (f + Cᶜ.indicator (fun _ : E ↦ (⊤ : EReal))) x +
((1 - t : ℝ) : EReal) * (f + Cᶜ.indicator (fun _ : E ↦ (⊤ : EReal))) y) ↔
Convex ℝ C ∧
∀ ⦃x : E⦄, x ∈ C → ∀ ⦃y : E⦄, y ∈ C → ∀ ⦃t : ℝ⦄, t ∈ Set.Icc (0 : ℝ) 1 →
f (t • x + (1 - t) • y) ≤ (t : EReal) * f x + ((1 - t : ℝ) : EReal) * f yExample 8.9
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.9: the norm function on a real normed vector space is convex, equivalently, for all x y : H and all λ ∈ [0,1], ‖λ • x + (1 - λ) • y‖ ≤ λ * ‖x‖ + (1 - λ) * ‖y‖.
universe u
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
recall convexOn_univ_norm
-- Proof sketch: choose a nonzero vector `x` and compare it with `0`. For any positive
-- coefficients `a` and `b` with `a + b = 1`, homogeneity and `‖0‖ = 0` give
-- `‖a • x + b • 0‖ = a * ‖x‖ = a * ‖x‖ + b * ‖0‖`, so the strict inequality required by
-- `StrictConvexOn` fails.Example 8.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.10: the squared norm function x ↦ ‖x‖ ^ 2 is strictly convex on the whole space of a real inner product space.
universe u
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
theorem strictConvexOn_norm_sq : StrictConvexOn ℝ Set.univ (fun x : H ↦ ‖x‖ ^ 2)Proposition 8.11
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.11: an extended-real-valued function is convex if and only if every finite convex combination of effective-domain points with positive coefficients summing to 1 satisfies Jensen's inequality.
universe u v
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
theorem convex_epigraph_iff_finite_jensen_on_dom (f : H → EReal) :
Convex ℝ (epigraph f) ↔
∀ {ι : Type v} (t : Finset ι) (w : ι → ℝ) (x : ι → H),
(∀ i ∈ t, 0 < w i) →
(∑ i ∈ t, w i = 1) →
(∀ i ∈ t, x i ∈ dom f) →
f (∑ i ∈ t, w i • x i) ≤
∑ i ∈ t, (w i : EReal) * f (x i)Corrollary 8.12
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corrollary 8.12: the canonical convexity condition Convex ℝ (epigraph f), the finite Jensen inequality for positive coefficients in ]0,1[ summing to 1, and the two-point Jensen inequality for coefficients in ]0,1[ are equivalent formulations of convexity for an extended-real-valued function.
open scoped BigOperators
universe u v
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
theorem tfae_convex_epigraph_finset_jensen_openSegment_jensen (f : H → EReal) :
List.TFAE [
Convex ℝ (epigraph f),
∀ {ι : Type v} (s : Finset ι) (α : ι → ℝ) (x : ι → H),
(∀ i ∈ s, α i ∈ Set.Ioo (0 : ℝ) 1) →
(∑ i ∈ s, α i = 1) →
(∀ i ∈ s, x i ∈ dom f) →
f (∑ i ∈ s, α i • x i) ≤
∑ i ∈ s, (α i : EReal) * f (x i),
∀ x y : H, ∀ α : ℝ, α ∈ Set.Ioo (0 : ℝ) 1 →
x ∈ dom f → y ∈ dom f →
f (α • x + (1 - α) • y) ≤
(α : EReal) * f x + (((1 - α : ℝ) : EReal) * f y)
]Proposition 8.13
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.13: strict convexity is equivalent to the finite Jensen inequality on the effective domain together with the equality characterization that forces the weighted family to be constant, equivalently to have singleton image.
open scoped BigOperators
universe u v
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
theorem strictlyConvex_iff_finset_jensen_le_and_eq_iff_constant
(f : H → Set.Ioi (⊥ : EReal)) :
StrictlyConvex f ↔
∀ {I : Type v} (s : Finset I) (α : I → ℝ) (x : I → H),
(∀ i ∈ s, α i ∈ Set.Ioo (0 : ℝ) 1) →
(∑ i ∈ s, α i = 1) →
(∀ i ∈ s, x i ∈ effectiveDomain f) →
(f (∑ i ∈ s, α i • x i) : EReal) ≤
∑ i ∈ s, (α i : EReal) * (f (x i) : EReal) ∧
((f (∑ i ∈ s, α i • x i) : EReal) =
∑ i ∈ s, (α i : EReal) * (f (x i) : EReal) ↔
∃ y, ∀ i ∈ s, x i = y)Proposition 8.14
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.14 (1): if the derivative of a real-valued function is increasing on an open convex subset I ⊆ ℝ (the formalization of the textbook's open interval), then the function is convex on I. This is the canonical ConvexOn formulation of the textbook Jensen inequality for the finite restriction of the proper ]-∞,+∞]-valued function to I.
theorem convexOn_of_monotoneOn_deriv_openInterval (I : Set ℝ) (φ : ℝ → ℝ)
(hI_convex : Convex ℝ I) (hI_open : IsOpen I) (hφ_diff : DifferentiableOn ℝ φ I)
(hφ'_mono : MonotoneOn (deriv φ) I) :
ConvexOn ℝ I φExample 8.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.15 (1): if ψ is increasing, then the extended-real function that equals ∫ t in α..x, ψ t on [α,+∞) and +∞ on (-∞, α) has a convex epigraph.
open ERealFunction
namespace ERealFunction
theorem convex_epigraph_integralIciExtension (ψ : ℝ → ℝ) (α : ℝ) (hψ : Monotone ψ) :
Convex ℝ (epigraph fun x : ℝ ↦ (integralIciExtension ψ α x : EReal))Proposition 8.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.16: the pointwise supremum of a family of extended-real-valued functions with convex epigraphs again has convex epigraph, hence is convex.
universe u v
namespace ERealFunction
variable {H : Type u} {I : Type v} [AddCommGroup H] [Module ℝ H]
-- Proof sketch: use `epigraph_iSup` to rewrite the epigraph of the pointwise supremum as the
-- intersection of the epigraphs of the family members, then apply `convex_iInter`.
theorem convex_epigraph_iSup (f : I → H → EReal)
(hconv : ∀ i, Convex ℝ (epigraph (f i))) :
Convex ℝ (epigraph (⨆ i, f i))Proposition 8.17
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.17 (1): the pointwise sum of two convex ]-∞,+∞]-valued functions, defined using the usual extended-real addition convention, is convex.
universe u
namespace ERealFunction
variable {H : Type u}
variable [AddCommGroup H] [Module ℝ H]
-- Proof sketch: use Proposition 8.4 to rewrite convexity as Jensen inequalities on effective
-- domains. For points where both `f` and `g` are finite, apply the Jensen inequalities for `f` and
-- `g` separately and add the resulting `EReal` inequalities.
theorem convex_epigraph_pointwiseAdd
{f g : H → Set.Ioi (⊥ : EReal)}
(hf : Convex ℝ (epigraph fun x : H ↦ (f x : EReal)))
(hg : Convex ℝ (epigraph fun x : H ↦ (g x : EReal))) :
Convex ℝ (epigraph fun x : H ↦ (pointwiseAdd f g x : EReal))Proposition 8.18
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.18: if a sequence of extended-real-valued functions has convex epigraphs and converges pointwise, then the limit function also has a convex epigraph, hence is convex.
universe u
variable {X : Type u} [AddCommMonoid X] [Module ℝ X]
namespace ERealFunction
theorem convex_epigraph_of_pointwise_tendsto
(fSeq : ℕ → X → EReal) (f : X → EReal)
(hconv : ∀ n, Convex ℝ (epigraph (fSeq n)))
(hlim : ∀ x, Filter.Tendsto (fun n ↦ fSeq n x) Filter.atTop (nhds (f x))) :
Convex ℝ (epigraph f)Example 8.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.19: for a bounded sequence z, the function x ↦ limsup_n ‖x - z n‖ is convex on the whole space and is 1-Lipschitz.
open Filter
universe u
variable {H : Type u} [SeminormedAddCommGroup H] [NormedSpace ℝ H]
theorem limsupDistanceFunction_convexOn_univ_and_lipschitzWith_one
(z : ℕ → H) (hbounded : Bornology.IsBounded (Set.range z)) :
ConvexOn ℝ Set.univ (limsupDistanceFunction z) ∧
LipschitzWith 1 (limsupDistanceFunction z)Proposition 8.20
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.20: if g : 𝓚 → ]-∞,+∞] is convex and L : 𝓗 → 𝓚 is affine, then the composition g ∘ L is convex; equivalently, the real-height epigraph of x ↦ g (L x) is convex whenever the real-height epigraph of g is convex.
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [AddCommGroup H] [Module ℝ H]
variable [AddCommGroup K] [Module ℝ K]
theorem convex_epigraph_comp_affineMap
(g : K → Set.Ioi (⊥ : EReal)) (L : H →ᵃ[ℝ] K)
(hconv : Convex ℝ (epigraph (fun y : K ↦ (g y : EReal)))) :
Convex ℝ (epigraph (fun x : H ↦ (g (L x) : EReal)))Proposition 8.21
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.21: let f : 𝓗 → ]-∞,+∞] and φ : ℝ → ]-∞,+∞]. If f has convex epigraph, φ has convex epigraph on ℝ, every point of the convex hull of the real values attained by f lies in the effective domain of φ, and φ is increasing on that convex hull, then the composition of f with the extension of φ sending +∞ to +∞ again has convex epigraph.
open Set
universe u
namespace ERealFunction
variable {H : Type u}
variable [AddCommGroup H] [Module ℝ H]
-- Proof sketch: use Proposition 8.4 to reduce convexity of the composition to Jensen's
-- inequality on its effective domain. For `x` and `y` in the domain of the composition, the values
-- `f x` and `f y` are finite real points of `realRange f`, hence their convex combinations lie in
-- `convexHull ℝ (realRange f)`. Apply convexity of `f`, monotonicity of `φ` on that convex hull,
-- and then convexity of `φ` to obtain the Jensen inequality for `topExtensionEReal φ ∘ f`.
theorem convex_epigraph_comp_topExtension
(f : H → Set.Ioi (⊥ : EReal)) (φ : ℝ → Set.Ioi (⊥ : EReal))
(hf : Convex ℝ (epigraph fun x : H ↦ (f x : EReal)))
(hφ : Convex ℝ (epigraph fun t : ℝ ↦ (φ t : EReal)))
(hdom : convexHull ℝ (realRange f) ⊆ effectiveDomain φ)
(hmono : MonotoneOn (fun t ↦ (φ t : EReal)) (convexHull ℝ (realRange f))) :
Convex ℝ (epigraph fun x : H ↦ topExtensionEReal φ (f x))Example 8.22
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
If ψ is increasing with ψ 0 ≥ 0, then the radial primitive x ↦ ∫ t in 0..‖x‖, ψ t is convex on the whole space.
universe u
variable {E : Type u} [SeminormedAddCommGroup E] [NormedSpace ℝ E]
theorem convexOn_univ_radialIntegral (ψ : ℝ → ℝ) (hψmono : Monotone ψ) (hψ0 : 0 ≤ ψ 0) :
ConvexOn ℝ Set.univ (fun x : E ↦ ∫ t in 0..‖x‖, ψ t)Example 8.23
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.23 (1): for p > 1, the function x ↦ ‖x‖ ^ p is strictly convex on the whole space of a strictly convex real normed space.
universe u
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] [StrictConvexSpace ℝ H]
-- Proof sketch: combine the strict convexity of `t ↦ t ^ p` on `[0,+∞)` from
-- `strictConvexOn_rpow hp` with the strict convexity of the norm geometry encoded by
-- `StrictConvexSpace`; equivalently, this is the `ψ(t) = p * t ^ (p - 1)` radial-integral
-- specialization of Example 8.22.
theorem strictConvexOn_norm_rpow (p : ℝ) (hp : 1 < p) :
StrictConvexOn ℝ Set.univ (fun x : H ↦ ‖x‖ ^ p)Proposition 8.24
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.24 (1): the integral functional defined from φ is well defined as an ]-∞,+∞]-valued map on L², in the sense that it never takes the value -∞.
open MeasureTheory
open scoped Classical
universe u v
variable {Ω : Type u} [MeasurableSpace Ω] {μ : Measure Ω}
variable {H : Type v} [MeasurableSpace H] [NormedAddCommGroup H] [NormedSpace ℝ H]
[BorelSpace H]
theorem pointwiseIntegralFunctional_ne_bot (φ : H → Set.Ioi (⊥ : EReal))
(x : Ω →₂[μ] H) :
pointwiseIntegralFunctional φ x ≠ ⊥Proposition 8.25
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.25: if φ has convex epigraph, then the epigraph of its perspective is the cone generated by the unit slice C = {((1, x), η) | (x, η) ∈ epi φ}, and this epigraph is convex.
open Set
open scoped Pointwise
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
theorem perspective_epigraph_eq_cone_and_convex (φ : H → EReal)
(hφ_convex : Convex ℝ (epigraph φ)) :
epigraph (perspective φ) = cone (perspectiveEpigraphSlice φ) ∧
Convex ℝ (epigraph (perspective φ))Example 8.26
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.26: if φ : ℝ → ]-∞,+∞] is convex, then the function on a finite family (ι → ℝ) × (ι → ℝ) defined by (x, y) ↦ ∑ i, y i * φ (x i / y i) on the positive orthant and to +∞ otherwise has convex real-height epigraph.
open scoped BigOperators
namespace ERealFunction
variable {ι : Type*} [Fintype ι]
theorem convex_coordinatePerspectiveSum (ι : Type*) [Fintype ι] (φ : ℝ → EReal)
(hφ_noBot : ∀ t, φ t ≠ ⊥)
(hφ_convex : Convex ℝ {p : ℝ × ℝ | φ p.1 ≤ (p.2 : EReal)}) :
Convex ℝ {p : (((ι → ℝ) × (ι → ℝ)) × ℝ) |
coordinatePerspectiveSum ι φ p.1 ≤ (p.2 : EReal)}Example 8.27
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.27: on the canonical Fin N → ℝ model of ℝ^N × ℝ^N, the function that equals ∑ i, ξᵢ log (ξᵢ / ηᵢ) on the strictly positive orthant and +∞ otherwise has convex real-height epigraph.
open scoped BigOperators
namespace ERealFunction
theorem convex_epigraph_relativeEntropyFunction (N : ℕ) :
Convex ℝ (epigraph (relativeEntropyFunction N))Example 8.28
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.28: on the canonical Fin N → ℝ model of ℝ^N × ℝ^N, the function equal to ∑ i, (x i - y i) * (log (x i) - log (y i)) when every coordinate of x and y is positive and to +∞ otherwise is convex, expressed canonically as convexity of its epigraph.
open scoped BigOperators
namespace ERealFunction
theorem convex_epigraph_coordinateLogarithmicDifference (N : ℕ) :
Convex ℝ (epigraph (coordinateLogarithmicDifference N))Example 8.29
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.29: the Pearson divergence on ℝ^N × ℝ^N, defined by f(x, y) = ∑ i |x i - y i|^2 / y i for y ∈ ℝ_{++}^N and f(x, y) = +∞ otherwise, has convex epigraph.
open scoped BigOperators
namespace ERealFunction
theorem convex_epigraph_pearsonDivergence (N : ℕ) :
Convex ℝ (epigraph (pearsonDivergence N))Example 8.30
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.30: the Hellinger divergence on the canonical Fin N → ℝ model of ℝ^N × ℝ^N, defined by ∑ i |√(x i) - √(y i)|² on the strictly positive orthant and by +∞ otherwise, has convex epigraph.
open scoped BigOperators
namespace ERealFunction
theorem convex_epigraph_hellingerDivergence (N : ℕ) :
Convex ℝ (epigraph (hellingerDivergence N))Example 8.31
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.31: for α ≥ 1, the finite-index function that equals ∑ i, x i ^ α * y i ^ (1 - α) on the strictly positive orthant and +∞ otherwise has convex real-height epigraph.
open scoped BigOperators
namespace ERealFunction
variable {ι : Type*} [Fintype ι]
theorem convex_epigraph_powerPerspectiveDivergence (ι : Type*) [Fintype ι]
(α : ℝ) (hα : 1 ≤ α) :
Convex ℝ (epigraph (powerPerspectiveDivergence ι α))Example 8.32
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.32: if C is convex, then the function sending (ξ, x) to ξ for ξ > 0 and x ∈ ξ • C, and to +∞ otherwise, has convex epigraph on ℝ × H.
open Set
open scoped Pointwise
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
theorem convex_epigraph_positiveScalingIndicator (C : Set H) (hC : Convex ℝ C) :
Convex ℝ (epigraph (positiveScalingIndicator C))Example 8.33
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.33: if φ : ℝ → ]-∞,+∞] is convex, then the function φ* defined by φ*(ξ) = ξ φ(1 / ξ) for ξ > 0 and φ*(ξ) = +∞ for ξ ≤ 0 is convex in the extended-real epigraph sense. Its effective domain is generally not all of ℝ.
namespace ERealFunction
-- Proof sketch: split on the sign of `ξ`. For `ξ > 0`, unfold both definitions and use
-- `ξ⁻¹ • (1 : ℝ) = 1 / ξ`; for `ξ ≤ 0`, both sides reduce to `⊤`.
theorem adjoint_convexOn_univ (φ : ℝ → Set.Ioi (⊥ : EReal)) (hφ : ConvexOn φ Set.univ) :
Convex ℝ (epigraph (fun ξ : ℝ ↦ (adjoint φ ξ : EReal)))Example 8.34
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.34: the function ξ ↦ 1 / ξ for ξ > 0 and ξ ↦ +∞ for ξ ≤ 0 satisfies Jensen's inequality for every ξ₁, ξ₂, and every α ∈ [0,1].
namespace ERealFunction
theorem positiveReciprocal_convex (ξ₁ ξ₂ α : ℝ) (hα₀ : 0 ≤ α) (hα₁ : α ≤ 1) :
(positiveReciprocal (α * ξ₁ + (1 - α) * ξ₂) : EReal) ≤
(α : EReal) * (positiveReciprocal ξ₁ : EReal) +
(1 - α : EReal) * (positiveReciprocal ξ₂ : EReal)Proposition 8.35
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.35: the marginal function obtained by infimizing a convex ]-∞,+∞]-valued function over the second variable is convex.
open Set
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [AddCommGroup H] [Module ℝ H]
variable [AddCommGroup K] [Module ℝ K]
theorem marginalFunction_convex
(F : H × K → Set.Ioi (⊥ : EReal)) (hF : ConvexOn F Set.univ)
{x₁ x₂ : H} {α : ℝ} (hα0 : 0 ≤ α) (hα1 : α ≤ 1) :
marginalFunction F (α • x₁ + (1 - α) • x₂) ≤
(α : EReal) * marginalFunction F x₁ +
(((1 - α : ℝ)) : EReal) * marginalFunction F x₂Example 8.36
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.36 (1): if C is convex, then the Minkowski gauge m[C] has convex epigraph, hence is a convex extended-real-valued function.
open Set
open ERealFunction
open scoped Pointwise
universe u
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
local notation "m[" C "]" =>
extendedMinkowskiGauge C
theorem convex_epigraph_minkowskiGauge (C : Set H) (hC : Convex ℝ C) :
Convex ℝ (epigraph (m[C]))Proposition 8.37
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.37 (1): if a convex ]-∞,+∞]-valued function has finite supremum on Metric.ball x₀ ρ, then on the smaller ball Metric.ball x₀ (α * ρ) its finite real values differ from the value at x₀ by at most α times the gap between that supremum and f x₀.
open Set
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
theorem oscillation_bound_on_smaller_ball
(f : H → Set.Ioi (⊥ : EReal))
(hconv : ConvexOn f (effectiveDomain f))
{x₀ : H} {ρ : ℝ} (hρ : 0 < ρ)
(hx₀ : x₀ ∈ effectiveDomain f)
(hsup : sSup ((fun y ↦ (f y : EReal)) '' Metric.ball x₀ ρ) < ⊤)
{α : ℝ} (hα0 : 0 < α) (hα1 : α < 1)
{x : H} (hx : x ∈ Metric.ball x₀ (α * ρ)) (hx_dom : x ∈ effectiveDomain f) :Theorem 8.38
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Theorem 8.38 (1): for a convex ]-∞,+∞]-valued function at a point x₀ of its effective domain, the following are equivalent: local Lipschitz continuity of the real-valued representative near x₀, continuity at x₀, boundedness on some open ball around x₀, and finiteness of the supremum on some open ball around x₀.
open Set
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
theorem convex_tfae_locallyLipschitzNear_continuousAt_boundedBall_finiteSupBall
(f : H → Set.Ioi (⊥ : EReal))
(hconv : ConvexOn f (effectiveDomain f))
{x₀ : H} (hx₀ : x₀ ∈ effectiveDomain f) :
List.TFAE
[∃ β : NNReal, ∃ ρ > 0,
Metric.ball x₀ ρ ⊆ effectiveDomain f ∧
LipschitzOnWith β (fun x ↦ (f x : EReal).toReal) (Metric.ball x₀ ρ),
∃ ρ > 0,
Metric.ball x₀ ρ ⊆ effectiveDomain f ∧
ContinuousAt (fun x ↦ (f x : EReal).toReal) x₀,
∃ ρ > 0, Metric.ball x₀ ρ ⊆ effectiveDomain f ∧
Bornology.IsBounded (((fun x ↦ (f x : EReal).toReal) '' Metric.ball x₀ ρ) : Set ℝ),
∃ ρ > 0, sSup ((fun x ↦ (f x : EReal)) '' Metric.ball x₀ ρ) < ⊤]Corollary 8.39
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 8.39: for a proper convex ]-∞,+∞]-valued function on a real Hilbert space, if it is bounded above on some open ball, or is lower semicontinuous, or the ambient space is finite-dimensional, then the points where the finite real representative is continuous on a neighborhood contained in the effective domain are exactly the interior of the effective domain.
open Set
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
theorem continuous_points_eq_interior_effectiveDomain_of_convexOn_of_finiteSupBall_or_lowerSemicontinuous_or_finiteDimensional
(f : H → Set.Ioi (⊥ : EReal))
(hconv : ConvexOn f (effectiveDomain f))
(h :
(∃ x : H, ∃ ρ : ℝ, 0 < ρ ∧
sSup ((fun y : H ↦ (f y : EReal)) '' Metric.ball x ρ) < ⊤) ∨
LowerSemicontinuous (fun x : H ↦ (f x : EReal)) ∨
FiniteDimensional ℝ H) :
{x : H | ∃ ρ : ℝ, 0 < ρ ∧ Metric.ball x ρ ⊆ effectiveDomain f ∧
ContinuousAt (fun y : H ↦ (f y : EReal).toReal) x} = interior (effectiveDomain f)Corollary 8.40
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 8.40: every convex real-valued function on a finite-dimensional real Hilbert space is continuous.
universe u
-- Proof sketch: apply the finite-dimensional continuity theorem for convex functions on `Set.univ`,
-- for instance by first obtaining local Lipschitz continuity from `ConvexOn.locallyLipschitz` and
-- then deducing continuity from `LocallyLipschitz.continuous`.
theorem continuous_of_convexOn_univ
{H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [FiniteDimensional ℝ H]
(f : H → ℝ) (hconv : ConvexOn ℝ Set.univ f) :
Continuous fCorollary 8.41
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 8.41: if C is a closed bounded subset of the relative interior of the effective domain of a proper convex ]-∞,+∞]-valued function on a finite-dimensional real normed space, then the real-valued representative of f is Lipschitz on C with some positive constant.
open Set
open scoped Pointwise
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] [FiniteDimensional ℝ H]
theorem exists_pos_lipschitzOnWith_on_closed_bounded_subset_relativeInterior_effectiveDomain
(f : H → Set.Ioi (⊥ : EReal))
(hconv : ConvexOn f (effectiveDomain f))
{C : Set H} (hC_subset : C ⊆ ri (effectiveDomain f))
(hC_closed : IsClosed C) (hC_bounded : Bornology.IsBounded C) :
∃ β : NNReal, 0 < β ∧ LipschitzOnWith β (fun x ↦ (f x : EReal).toReal) CExample 8.42
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.42 (1): textbook clause (i), first part. A real linear functional and its negative are convex on the whole space.
open Set
open scoped Topology Pointwise
universe u
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
-- Proof sketch: apply the general fact `LinearMap.convexOn` to `f` and to `-f`, both on the
-- convex set `Set.univ`.
theorem convexOn_univ_linearFunctional_and_neg (f : H →ₗ[ℝ] ℝ) :
ConvexOn ℝ (Set.univ : Set H) f ∧
ConvexOn ℝ (Set.univ : Set H) (-f)Example 8.43
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.43: if C is convex and contains 0 in its interior, then the Minkowski gauge is finite everywhere and continuous on the whole space.
open Set
open ERealFunction
open scoped Pointwise
universe u
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
theorem minkowskiGauge_dom_eq_univ_and_continuous
(C : Set H) (hC : Convex ℝ C) (h0C : (0 : H) ∈ interior C) :
dom (m[C]) = univ ∧ Continuous (m[C])Example 8.44
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 8.44: for every threshold ρ ∈ ℝ_{++}, the Huber function is convex on ℝ and continuous.
open Filter Set
open scoped Topology
-- Proof sketch: let `f` be the displayed piecewise Huber function. Use Proposition 8.14 on the
-- monotone derivative of `f` to obtain convexity on `Set.univ`, then apply Corollary 8.40 to that
-- convexity statement to deduce continuity.
theorem huberFunction_convexOn_univ_and_continuous (ρ : Set.Ioi (0 : ℝ)) :
let f : ℝ → ℝ :=
{x : ℝ | (ρ : ℝ) < |x|}.piecewise
(fun x ↦ (ρ : ℝ) * |x| - (ρ : ℝ) ^ 2 / 2)
(fun x ↦ |x| ^ 2 / 2)
ConvexOn ℝ Set.univ f ∧ Continuous fProposition 8.45
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.45: if a convex ]-∞,+∞]-valued function is bounded above on some open ball, then its real-height epigraph has nonempty interior.
open Set
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H]
theorem interior_epigraph_nonempty_of_convexOn_of_boundedAbove_ball
[NormedSpace ℝ H]
{f : H → Set.Ioi (⊥ : EReal)} {x : H} {δ M : ℝ}
(hconv : ConvexOn f (effectiveDomain f)) (hδ : 0 < δ)
(hM : ∀ y ∈ Metric.ball x δ, (f y : EReal) ≤ (M : EReal)) :
(interior (epigraph (fun y : H ↦ (f y : EReal)))).NonemptyProposition 8.46
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 8.46 (1): if f is upper semicontinuous at x₀ and f x₀ < 0, then x₀ belongs to the interior of the lower level set lev≤₀ f.
open Set
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H]
-- Proof sketch: if `x₀` were not in the interior of the `0`-sublevel set, every neighborhood of
-- `x₀` would contain a point where the value is positive; a sequence or net of such points
-- converging to `x₀` would then contradict upper semicontinuity at `x₀` together with `f x₀ < 0`.
theorem mem_interior_lowerLevelSet_zero_of_upperSemicontinuousAt
{f : H → Set.Ioi (⊥ : EReal)} {x₀ : H}
(husc : UpperSemicontinuousAt (fun x : H ↦ (f x : EReal)) x₀)
(hx₀ : (f x₀ : EReal) < 0) :
x₀ ∈ interior (lowerLevelSet (fun x : H ↦ (f x : EReal)) 0)Corollary 8.47
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 8.47: if a convex ]-∞,+∞]-valued function has nonempty strict negative level set and either is ambiently upper semicontinuous at every point of that set, or is lower semicontinuous with open effective domain, or is defined on a finite-dimensional space with open effective domain, then the strict negative level set is open; equivalently, it equals its interior.
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
theorem
isOpen_strictLowerLevelSet_zero_of_convexOn_of_upperSemicontinuousOn_or_lowerSemicontinuous_openDomain_or_finiteDimensional_openDomain
(f : H → Set.Ioi (⊥ : EReal))
(hconv : ConvexOn f (effectiveDomain f))
(hneg : (strictLowerLevelSet (fun x : H ↦ (f x : EReal)) 0).Nonempty)
(h :
(∀ x ∈ strictLowerLevelSet (fun x : H ↦ (f x : EReal)) 0,
UpperSemicontinuousAt (fun x : H ↦ (f x : EReal)) x) ∨
(IsOpen (effectiveDomain f) ∧
(LowerSemicontinuous (fun x : H ↦ (f x : EReal)) ∨ FiniteDimensional ℝ H))) :
IsOpen (strictLowerLevelSet (fun x : H ↦ (f x : EReal)) 0)