Chapter 02 — Extended Real-Valued Functions
Proofs omitted. Hover over highlighted terms to see their Lean types.
Corollary 2.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 2.1: a continuous real-valued function is closed, i.e. lower semicontinuous after viewing it as an EReal-valued function.
universe u
variable {E : Type u} [TopologicalSpace E]
-- Proof sketch: compose `hf` with the continuous coercion `ℝ → EReal`, then apply
-- `Continuous.lowerSemicontinuous` to the resulting `EReal`-valued function.
theorem continuous_real_isClosed {f : E → ℝ} (hf : Continuous f) :
LowerSemicontinuous (fun x ↦ (f x : EReal))Definition 2.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.1: The effective domain of an extended real-valued function f : E → EReal is the set of points where f takes a finite value, equivalently where f x < ∞.
universe u
variable {E : Type u}
def effective_domain (f : E → EReal) : Set E := {x | f x < ⊤}
-- Proof sketch: Unfold `effective_domain`; membership in the defining set is exactly the
-- inequality `f x < ⊤`.Lemma 2.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 2.1: the primal-space support function σ[C] of a subset of a real inner product space is closed, i.e. lower semicontinuous, and convex in the chapter-owner sense. The textbook states this for nonempty C, but the same conclusion holds without that extra assumption.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
notation "σ[" C "]" => support_function_primal C
-- Proof sketch: unfold `support_function_primal`; this is exactly the specialization of
-- `support_function` along `InnerProductSpace.toDualMap`.
theorem support_function_closed_and_convex (C : Set E) :
LowerSemicontinuous (σ[C]) ∧ is_convex_function (σ[C])proposition 2.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 2.1: the indicator function δ_C has closed real epigraph if and only if its underlying set C is closed.
open Set
universe u
variable {α : Type u} [TopologicalSpace α]
-- Bridge/view layer: transport the canonical lower-semicontinuity criterion for `δ_C`
-- through the chapter equivalence between lower semicontinuity and closed real epigraph.
theorem extendedIndicator_isClosed_real_epigraph_iff_isClosed (C : Set α) :
IsClosed (realEpigraph (δ_ C)) ↔ IsClosed CTheorem 2.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
The source-facing real epigraph of an extended-real-valued function.
open Set
universe u
variable {X : Type u}
def realEpigraph (f : X → EReal) : Set (X × ℝ) :=
{p | f p.1 ≤ (p.2 : EReal)}Definition 2.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.2: the textbook notion of a closed extended-real-valued function is the canonical predicate LowerSemicontinuous; for EReal-valued functions, mathlib identifies this with closedness of the epigraph.
universe u
variable {α : Type u}
variable [TopologicalSpace α]
#check (LowerSemicontinuous : (α → EReal) → Prop)Lemma 2.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 2.2: the Minkowski sum is the canonical pointwise addition of sets in scope Pointwise; the owner declaration Set.image2_add identifies it with the binary image Set.image2 (· + ·).
open scoped Pointwise
recall Set.image2_addProposition 2.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 2.2: Jensen's inequality for a convex extended-real-valued function in the source convention excluding -∞. If λ : stdSimplex ℝ (Fin k) is the textbook simplex vector Δ_k, then f (∑ i, λ i • x i) ≤ ∑ i, λ i * f (x i).
open scoped BigOperators
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E] {f : E → EReal}
theorem convex_function_jensen_inequality {k : ℕ} (hf : is_convex_function f)
(h_ne_bot : ∀ z, f z ≠ ⊥) (x : Fin k → E) (w : stdSimplex ℝ (Fin k)) :
f (∑ i, w i • x i) ≤ ∑ i, w i * f (x i)Theorem 2.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.2: for an extended real-valued function, lower semicontinuity, closedness of the real epigraph, and closedness of all real sublevel sets are equivalent.
open Set
universe u
variable {X : Type u} [TopologicalSpace X]
theorem ereal_lowerSemicontinuous_tfae (f : X → EReal) :
List.TFAE
[LowerSemicontinuous f,
IsClosed (realEpigraph f),
∀ a : ℝ, IsClosed (f ⁻¹' Iic (a : EReal))]Definition 2.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.3: the project records the textbook notion of lower semicontinuity at a point via the canonical mathlib owner declaration LowerSemicontinuousAt.
universe u
variable {α : Type u}
recall LowerSemicontinuousAtExample 2.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.3: the function truncated_identity_with_origin_value α is closed, equivalently lower semicontinuous, if and only if α ≤ 0.
theorem truncated_identity_with_origin_value_lowerSemicontinuous_iff (α : ℝ) :
LowerSemicontinuous (truncated_identity_with_origin_value α) ↔ α ≤ 0Lemma 2.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 2.3 is the canonical pointwise-set identity Set.image_smul: for a scalar α ∈ ℝ and a set A ⊆ E, the pointwise scalar multiple α • A is the image of A under the map a ↦ α • a, equivalently the set {α • a | a ∈ A}.
recall Set.image_smulProposition 2.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 2.3: if K is closed under nonnegative scalar multiplication and contains 0, then the support function σ_K is the indicator function of the polar cone Kᵒ = {y | ∀ x ∈ K, y x ≤ 0}.
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
theorem support_function_eq_indicatorFunction_polarCone
(K : Set E) (hK : IsCone K) (h0 : (0 : E) ∈ K) :
σ_ K = δ_(polar_cone K)Theorem 2.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.3: if an extended-real-valued function is continuous on its effective domain and that domain is closed, then the function is closed, equivalently lower semicontinuous.
universe u
variable {E : Type u} [TopologicalSpace E]
theorem lowerSemicontinuous_of_continuousOn_effective_domain (f : E → EReal)
(h_cont : ContinuousOn f (effective_domain f))
(h_closed : IsClosed (effective_domain f)) :
LowerSemicontinuous fDefinition 2.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.4: an extended-real-valued function is continuous over its domain exactly when it is continuous on its effective domain in the canonical mathlib sense `ContinuousOn g (effective_domain g)`.
open Filter
open scoped Topology
universe u
variable {E : Type u}
variable [TopologicalSpace E] (g : E → EReal)
#check (ContinuousOn g (effective_domain g))Example 2.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.4: the ℓ₀ function on a finite real coordinate space is closed, equivalently lower semicontinuous, because it is the finite sum of the coordinatewise nonzero indicator.
open scoped BigOperators
universe u
variable {ι : Type u} [Fintype ι]
-- Proof sketch: `hammingNorm x` is the canonical owner object for the number of nonzero
-- coordinates of `x`, while each term `l0Indicator (x i)` contributes `1` exactly when `x i ≠ 0`
-- and `0` otherwise; compare the resulting finite sum with `(hammingNorm x : ℝ)`.
theorem hammingNorm_lowerSemicontinuous :
LowerSemicontinuous (fun x : ι → ℝ ↦ (hammingNorm x : ℝ))Lemma 2.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 2.4 (1): (a) the support function is positively homogeneous in the dual variable: for a nonempty set C and α ≥ 0, one has σ_C (α y) = α σ_C (y).
open scoped Pointwise
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
theorem support_function_nonneg_smul_dual
(C : Set E) (hC : C.Nonempty) (y : Module.Dual ℝ E) {α : ℝ} (hα : 0 ≤ α) :
(σ_ C) (α • y) = (α : EReal) * (σ_ C) yProposition 2.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 2.4: in ℝ^n, under the Euclidean identification of the dual with ℝ^n, the support function of the nonnegative orthant is the indicator function of the nonpositive orthant.
theorem support_function_nonnegative_orthant_eq_indicator_nonpositive_dual_orthant
(n : ℕ) :
support_function (Set.Ici (0 : Fin n → ℝ)) =
δ_(dotProductEquiv ℝ (Fin n) '' Set.Iic (0 : Fin n → ℝ))Theorem 2.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.4 (2): if f is lower semicontinuous on a compact set C and C meets the effective domain of f, then f attains its minimum on C, and the minimizer can be chosen in the effective domain.
universe u
variable {E : Type u} [TopologicalSpace E]
-- Proof sketch: apply `LowerSemicontinuousOn.exists_isMinOn` on the compact set `C`; then compare
-- the minimizer with a point of `C ∩ effective_domain f` to show
-- that the minimizing point also lies in `effective_domain f`.
theorem exists_isMinOn_on_compact (f : E → EReal) (C : Set E)
(h_lsc : LowerSemicontinuousOn f C)
(hC : IsCompact C)
(hCdom : (C ∩ effective_domain f).Nonempty) :
∃ x ∈ C ∩ effective_domain f, IsMinOn f C xDefinition 2.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.5: a proper extended-real-valued function is coercive when its values tend to ∞ along the filter ‖x‖ → ∞.
universe u
open Filter Metric
open scoped Topology
variable {E : Type u}
variable [NormedAddCommGroup E]
class IsCoerciveExtendedRealFunction (f : E → EReal) : Prop
extends IsProperExtendedRealFunction f where
tendsto_top : Tendsto f (comap norm atTop) (𝓝 (⊤ : EReal))Example 2.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.5: for a subset C of a real inner product space, the function x ↦ (‖x‖² - d_C(x)²) / 2 is convex.
universe u
open Metric
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem euclidean_distance_potential_convex (C : Set E) :
ConvexOn ℝ Set.univ (euclidean_distance_potential C)Lemma 2.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 2.5: Farkas's lemma in the implication form. For a real matrix A and vector c, the implication A x ≤ 0 → cᵀ x ≤ 0 for every x is equivalent to the existence of a nonnegative vector y with Aᵀ y = c; here ℝ^m_+ is rendered as Set.Ici (0 : Fin m → ℝ).
open Matrix
variable {m n : ℕ}
theorem farkas_lemma_second_formulation
(c : Fin n → ℝ) (A : Matrix (Fin m) (Fin n) ℝ) :
(∀ x : Fin n → ℝ, A *ᵥ x ≤ (0 : Fin m → ℝ) → dotProduct c x ≤ 0) ↔
∃ y ∈ Set.Ici (0 : Fin m → ℝ), Aᵀ *ᵥ y = cProposition 2.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 2.5: for C = {(x₁, x₂) | x₁ + x₂^2 / 2 ≤ 0} in ℝ², the primal support function σ[C] equals y₂^2 / (2 y₁) when y₁ > 0, equals 0 at the origin, and equals ⊤ otherwise.
open WithLp (toLp)
local notation "E2" => EuclideanSpace ℝ (Fin 2)
theorem support_function_parabolic_region (y : E2) :
σ[parabolicRegion] y =
if 0 < y 0 then ((((y 1) ^ 2) / (2 * y 0) : ℝ) : EReal)
else if y = 0 then (0 : EReal)
else ⊤Theorem 2.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.5: a proper closed coercive extended-real-valued function, equivalently here a lower semicontinuous coercive function, attains its minimum on every closed set S meeting its effective domain.
universe u
open Set Filter
variable {E : Type u} [NormedAddCommGroup E] [ProperSpace E]
theorem attains_min_on_closed_set_of_coercive (f : E → EReal) {S : Set E}
(hf : LowerSemicontinuous f) (hcoercive : IsCoerciveExtendedRealFunction f)
(hS_closed : IsClosed S) (hS_dom : (S ∩ effective_domain f).Nonempty) :
∃ x ∈ S, IsMinOn f S xDefinition 2.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.6: an extended-real-valued function is convex when its real epigraph is a convex subset of E × ℝ.
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
def is_convex_function (f : E → EReal) : Prop :=
Convex ℝ {p : E × ℝ | f p.1 ≤ (p.2 : EReal)}Example 2.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.6: if C is convex, then its distance function x ↦ infDist x C is convex on the whole space.
universe u
open Metric
variable {E : Type u} [SeminormedAddCommGroup E] [NormedSpace ℝ E]
theorem convexOn_infDist (C : Set E) (hC : Convex ℝ C) :
ConvexOn ℝ Set.univ (fun x : E ↦ Metric.infDist x C)Lemma 2.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 2.6: two closed convex sets in a real inner product space are equal if and only if their primal-space support functions σ[A] and σ[B] agree. This uses the chapter owner support_function_primal, the source-facing specialization of support_function along InnerProductSpace.toDualMap; the finite-dimensional Euclidean hypothesis supplies the Fréchet-Riesz identification with the continuous dual used in the converse direction.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
theorem eq_iff_support_function_eq_of_closed_convex
(A B : Set E) (hA_closed : IsClosed A) (hA_convex : Convex ℝ A)
(hB_closed : IsClosed B) (hB_convex : Convex ℝ B) :
A = B ↔ σ[A] = σ[B]Theorem 2.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.6 (2): a finite nonnegative weighted sum of convex extended-real-valued functions is convex, provided each summand never takes the value ⊥.
open scoped BigOperators
universe u v
variable {E : Type u}
variable [AddCommMonoid E] [Module ℝ E]
-- Proof sketch: combine the epigraph inequalities for each `f i` using the nonnegativity of the
-- coefficients; equivalently, build the result by iterating the two basic closure operations of
-- nonnegative scalar multiplication and addition.
theorem is_convex_function_finset_nonneg_weighted_sum {ι : Type v} (s : Finset ι)
{f : ι → E → EReal} (hf : ∀ i ∈ s, is_convex_function (f i))
(h_ne_bot : ∀ i ∈ s, ∀ x, f i x ≠ ⊥) (α : ι → NNReal) :
is_convex_function (fun x ↦ ∑ i ∈ s, (((α i : ℝ) : EReal) * f i x))Definition 2.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.7: for a proper extended-real-valued function, convexity is equivalent to the two-point Jensen inequality along every segment between points of effective_domain f with weight in [0, 1].
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E] {f : E → EReal}
theorem is_convex_function_iff_segment_ineq [IsProperExtendedRealFunction f] :
is_convex_function f ↔
∀ x ∈ effective_domain f, ∀ y ∈ effective_domain f, ∀ {t : ℝ},
t ∈ Set.Icc (0 : ℝ) 1 →
f (t • x + (1 - t) • y) ≤ (t : EReal) * f x + (1 - t : EReal) * f yExample 2.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.7: for S = {x : ℝ^n | A *ᵥ x ≤ 0}, the support function σ_S is the indicator function of the Euclidean-dual image {(Aᵀ *ᵥ λ) | λ ∈ ℝ^m_+}.
universe u
open Matrix
open PointedCone
variable {m n : ℕ}
theorem support_function_matrix_nonpositive_cone_eq_indicator_transpose_nonnegative_dual_cone
(A : Matrix (Fin m) (Fin n) ℝ) :
σ_ (matrix_nonpositive_cone A) = δ_(transpose_nonnegative_dual_cone A)Lemma 2.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 2.7 (1): replacing a set by its topological closure does not change its primal-space support function σ[A].
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
local notation "σ[" C "]" => support_function_primal_lemma_2_7 C
-- Rewrite the local primal owner back to the chapter owner specialized along `toDualMap`.
lemma support_function_eq_support_function_closure (A : Set E) :
σ[A] = σ[closure A]Theorem 2.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.7: convexity is preserved under partial minimization. In Lean, the source value function x ↦ inf_y f (x, y) is realized as x ↦ sInf (Set.range (fun y : V ↦ f (x, y))).
universe u v
variable {E : Type u} {V : Type v}
variable [AddCommMonoid E] [Module ℝ E]
variable [AddCommMonoid V] [Module ℝ V]
theorem partial_infimum_is_convex_function
{f : E × V → EReal} (hf : is_convex_function f) :
is_convex_function (fun x ↦ sInf (Set.range (fun y : V ↦ f (x, y))))Definition 2.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.8: the infimal convolution of two extended-real-valued functions is the pointwise infimum of the translates u ↦ h1 u + h2 (x - u).
universe u
variable {E : Type u} [AddCommGroup E]
noncomputable def infimal_convolution (h1 h2 : E → EReal) : E → EReal :=
fun x ↦ ⨅ u : E, h1 u + h2 (x - u)
-- Textbook notation for infimal convolution.Example 2.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.8: if x₀ satisfies B x₀ = b, then the support function of C = {x | B x = b} is the affine functional y ↦ y x₀ plus the indicator of the dual-space realization of Range(Bᵀ).
open Matrix
open scoped Pointwise
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
theorem support_function_affine_linear_constraint_set_eq_eval_add_indicator_transpose_range_dual
(B : Matrix ι κ ℝ) (b : ι → ℝ) (x₀ : κ → ℝ)
(hx₀ : x₀ ∈ affine_linear_constraint_set B b) :
support_function (affine_linear_constraint_set B b) =
fun y ↦ (y x₀ : EReal) + (δ_ (transpose_range_dual B)) yTheorem 2.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.8: if h₁ is a proper convex extended-real-valued function and h₂ is a real-valued convex function, then the infimal convolution h₁ □ h₂.toEReal of h₁ with the canonical extended-real lift of h₂ is convex.
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
theorem infimal_convolution_is_convex_of_proper (h₁ : E → EReal) (h₂ : E → ℝ)
(hh₁_proper : IsProperExtendedRealFunction h₁)
(hh₁_convex : is_convex_function h₁) (hh₂ : ConvexOn ℝ Set.univ h₂) :
is_convex_function (h₁ □ (Real.toEReal ∘ h₂))Definition 2.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.9: the support function of a set C ⊆ E is the extended-real-valued function on the dual space E* = Module.Dual ℝ E sending y to the supremum of the pairings y x for x ∈ C. For nonempty C, this realizes the textbook codomain (-∞, ∞].
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
noncomputable def support_function (C : Set E) : Module.Dual ℝ E → EReal :=
fun y ↦ sSup ((fun x : E ↦ (y x : EReal)) '' C)Example 2.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.9 (1): the support function of the closed unit ball of a normed space is the dual norm.
open Metric
open Matrix
open WithLp (toLp)
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
-- Proof sketch: maximize the continuous linear functional `y` on the compact closed unit ball.
-- The dual-pairing inequality gives the upper bound `support_function ≤ dualNorm`, while the
-- maximizing point gives the reverse inequality.
theorem support_function_unit_ball_eq_dualNorm (y : Module.Dual ℝ E) :
support_function (closedBall (0 : E) 1) y = (dualNorm y : EReal)Theorem 2.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.9: a convex extended-real-valued function is locally Lipschitz at every point of the interior of its effective domain, in the sense that some closed ball around the point is contained in the domain and satisfies the estimate |(f x).toReal - (f x0).toReal| ≤ L * ‖x - x0‖.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
theorem convex_function_exists_closedBall_lipschitz_bound_at_interior_point
(f : E → EReal) (hf : is_convex_function f)
(h_ne_bot : ∀ x ∈ effective_domain f, f x ≠ ⊥) (x0 : E)
(hx0 : x0 ∈ interior (effective_domain f)) :
∃ ε > 0, ∃ L > 0,
Metric.closedBall x0 ε ⊆ effective_domain f ∧
∀ x ∈ Metric.closedBall x0 ε,Definition 2.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.10: if C is represented by a nonempty finite set s, then the support function of C at y is the maximum of the finitely many values y b for b ∈ s.
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
-- Proof sketch: unfold `support_function` and identify the `sSup` of the
-- finite image set `(fun b ↦ (y b : EReal)) '' (s : Set E)` with the nonempty finset supremum
-- `s.sup' hs (fun b ↦ (y b : EReal))` via `Finset.sup'_eq_csSup_image`.
theorem support_function_finset_eq_sup' (s : Finset E) (hs : s.Nonempty) (y : Module.Dual ℝ E) :
support_function (s : Set E) y = s.sup' hs (fun b ↦ (y b : EReal))Example 2.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 2.10 is bridge-only: the intrinsic statement is the chapter owner theorem support_function_unit_simplex_eq_coordinate_max, which already identifies the support function of the unit simplex with the coordinate supremum ⨆ i, (y i : EReal).
open Matrix
recall support_function_unit_simplex_eq_coordinate_maxTheorem 2.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.10: a proper closed convex extended-real-valued function on ℝ is continuous on its effective domain. Here properness is expressed by IsProperExtendedRealFunction, closedness by LowerSemicontinuous, and convexity by the chapter owner predicate is_convex_function.
open scoped Topology
-- Semantic recall note: the source-facing statement is continuity of `f` on `effective_domain f`,
-- and the chapter owner `IsProperExtendedRealFunction` packages the source properness assumptions:
-- global exclusion of `⊥` together with nonempty `effective_domain f`. The finite-valued `toReal`
-- bridge only needs the local no-`⊥` hypothesis on `effective_domain f`.
-- Proof sketch: the convexity hypothesis makes the effective domain an interval in `ℝ`, hence its
-- interior is again an interval where the finite-valued restriction of `f` is a real-valued convex
-- function and therefore continuous. At an endpoint of the effective domain, use the one-sided
-- monotonicity of secant slopes for convex functions to show that the one-sided limit exists, then
-- combine this with lower semicontinuity to identify that limit with the endpoint value.
theorem continuousOn_effective_domain_of_lowerSemicontinuous_convex_univariate
{f : ℝ → EReal} (hproper : IsProperExtendedRealFunction f) (h_closed : LowerSemicontinuous f)
(h_convex : is_convex_function f) :
ContinuousOn f (effective_domain f)Definition 2.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.11: A subset is a cone if it is closed under multiplication by nonnegative real scalars.
universe u
variable {E : Type u} [SMul ℝ E] {S : Set E}
def IsCone (S : Set E) : Prop :=
∀ ⦃a : NNReal⦄ ⦃x : E⦄, x ∈ S → a • x ∈ STheorem 2.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 2.11: strict separation theorem. A nonempty closed convex set in a real inner product space and a point outside it can be strictly separated by a nonzero continuous linear functional.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
-- Proof sketch: apply `geometric_hahn_banach_closed_point` to the closed convex set `C` and the
-- point `y ∉ C`, obtaining a continuous linear functional `p` and a real number `α` with
-- `p x < α < p y` for all `x ∈ C`. Choose `x₀ ∈ C`; if `p = 0`, then `0 < α < 0`, impossible, so
-- `p ≠ 0`. Finally weaken the strict inequality on `C` to `p x ≤ α`.
theorem strict_separation_closed_convex_point {C : Set E} {y : E} (hC_nonempty : C.Nonempty)
(hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (hy : y ∉ C) :
∃ p : StrongDual ℝ E, p ≠ 0 ∧ ∃ α : ℝ, p y > α ∧ ∀ x ∈ C, p x ≤ αDefinition 2.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 2.12: the polar cone of a set K ⊆ E is the pointed cone of dual vectors y whose pairing with every x ∈ K is nonpositive.
universe u
open scoped Pointwise
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
def polar_cone (K : Set E) : PointedCone ℝ (Module.Dual ℝ E) :=
-PointedCone.dual (Module.Dual.eval ℝ E) KProposition 2.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 2.13: for the unit simplex Δ_n = stdSimplex ℝ (Fin n) in ℝ^n, the support function at the Euclidean-dual vector corresponding to y is the supremum, equivalently the maximum, of the coordinates of y.
universe u
open Matrix
theorem support_function_unit_simplex_eq_coordinate_max {n : ℕ} (y : Fin n → ℝ) :
support_function (stdSimplex ℝ (Fin n)) (dotProductEquiv ℝ (Fin n) y) =
⨆ i : Fin n, (y i : EReal)Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Example2_1.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
Example2_2.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
FunctionToEReal.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.