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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 epigraph

Proposition 8.2

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 y

Example 8.9

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 f

Corollary 8.41

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

Source header · Attribution source

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) C

Example 8.42

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 f

Proposition 8.45

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

Source header · Attribution source

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)))).Nonempty

Proposition 8.46

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

Source header · Attribution source

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.

Source header · Attribution source

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)