Chapter 05 — Smoothness and Strong Convexity
Proofs omitted. Hover over highlighted terms to see their Lean types.
Definition 5.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 5.1: a real-valued function is L-smooth on D when it is differentiable at every point of D and its Fréchet derivative is L-Lipschitz on D.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
def is_l_smooth_on (f : E → ℝ) (D : Set E) (L : NNReal) : Prop :=
(∀ x ∈ D, DifferentiableAt ℝ f x) ∧ LipschitzOnWith L (fderiv ℝ f) D
-- Proof sketch: unfold `is_l_smooth_on`, then rewrite `LipschitzOnWith` using
-- `lipschitzOnWith_iff_norm_sub_le`; the metric on continuous linear maps is induced by the
-- operator norm, so the Lipschitz condition becomes the displayed derivative estimate.Proposition 5.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.1: for the quadratic function x ↦ (1 / 2) xᵀ A x + bᵀ x + c on ℝ^n, viewed with the ℓ_p norm on a finite real product ι → ℝ, and hence on ℝ^n when ι = Fin n, the smallest global smoothness parameter is Real.toNNReal ‖A‖[p,q], the textbook induced matrix norm ‖A‖_{p,q} for a Hölder-conjugate pair p, q.
open Matrix
open WithLp (ofLp toLp)
open scoped RealInnerProductSpace
open scoped Matrix
universe u
variable {ι : Type u} [Fintype ι]
local notation "E" => ι → ℝ
theorem quadratic_affine_function_on_lp_opNorm_isLeast_smoothness_parameter
(p q : ENNReal) [DecidableEq ι] [Fact (1 ≤ p)] [Fact (1 ≤ q)]
[ENNReal.HolderConjugate p q]
(A : Matrix ι ι ℝ) (hA : A.IsSymm) (b : E) (c : ℝ) :
IsLeast
{L : NNReal | is_l_smooth_on (quadratic_affine_function_on_lp p A b c) Set.univ L}
(Real.toNNReal ‖A‖[p,q])Definition 5.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
The notation C^{1,1} is represented by the existence of some global smoothness parameter L ≥ 0.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
def is_c11 (f : E → ℝ) : Prop :=
∃ L : NNReal, is_l_smooth_on f Set.univ LProposition 5.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.2: every affine functional x ↦ b x + c on a real normed space is globally 0-smooth.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem is_l_smooth_affine_functional (b : E →L[ℝ] ℝ) (c : ℝ) :
is_l_smooth_on (fun x ↦ b x + c) Set.univ 0Proposition 5.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.3 is source-facing: its mathematical content is the differentiability of x ↦ (infDist x C)^2 / 2 for a nonempty closed convex set together with the explicit gradient formula x - P_C(x). Domain sampling identifies Proposition 3.12's hasGradientAt_half_sq_infDist as the owner abstraction for that content, Theorem 5.4's firm nonexpansiveness of metricProjection as the key Lipschitz input, and Definition 5.1's is_l_smooth_on as a derived Chapter 5 bridge. The primitive data are only the set C and its nonempty/closed/convex hypotheses; the gradient field is derived from the owner theorem rather than stored through a parallel local wrapper.
universe u
open Metric
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
recall hasGradientAt_half_sq_infDistProposition 5.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.4 (1): for a nonempty closed convex set C in a Euclidean space, the gradient of euclidean_distance_potential C is the metric projection P_C(x).
universe u
open Metric
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [FiniteDimensional ℝ E]
variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
local notation "P" => projectionPoint C hC_nonempty hC_closed hC_convex
theorem gradient_euclidean_distance_potential_eq_metricProjection (x : E) :
∇ (euclidean_distance_potential C) x = P xTheorem 5.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.4 (1): the point projection onto a nonempty closed convex set in a complete real inner product space, hence in particular in a Euclidean space, is firmly nonexpansive.
universe u
open Metric
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
local notation "P" => projectionPoint C hC_nonempty hC_closed hC_convex
-- Proof sketch: apply the projection variational inequality to `v` with test point `P_C(w)` and to
-- `w` with test point `P_C(v)`, then add the resulting inequalities and rearrange the inner-product
-- terms to obtain the standard firm nonexpansiveness estimate.
theorem metricProjection_firmly_nonexpansive (v w : E) :
inner ℝ (P v - P w) (v - w) ≥ ‖P v - P w‖ ^ 2Proposition 5.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.5: for p ≥ 2, the half-squared ℓ_p norm on ℝ^n, viewed on the canonical WithLp model, is globally (p - 1)-smooth with respect to the ℓ_p norm. This is the owner-level Chapter 5 formulation of the textbook statement.
open Asymptotics Topology
open scoped Gradient
open WithLp (ofLp toLp)
variable {n : ℕ} {p : ℝ}
local notation "E" => WithLp (ENNReal.ofReal p) (Fin n → ℝ)
theorem half_squared_lp_norm_is_l_smooth (hp : 2 ≤ p) :
HalfSquaredLpNorm.IsLSmooth n p hpLemma 5.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 5.7: if D is convex and f is L-smooth on D, then f y ≤ f x + ⟪∇ f x, y - x⟫ + (L / 2) * ‖x - y‖² for all x, y ∈ D.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Proof sketch: parametrize the chord from `x` to `y` by `AffineMap.lineMap x y`, compare the
-- restriction of `f` with the quadratic barrier determined by `fderiv ℝ f x`, and use the
-- derivative-Lipschitz clause of `is_l_smooth_on` along the segment inside the convex set `D`.
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem is_l_smooth_on_descent_lemma {L : NNReal} {D : Set E} {f : E → ℝ}
(hD : Convex ℝ D) (hf : is_l_smooth_on f D L)
{x y : E} (hx : x ∈ D) (hy : y ∈ D) :
f y ≤
f x + inner ℝ (∇ f x) (y - x) + ((L : ℝ) / 2) * ‖x - y‖ ^ (2 : ℕ)Proposition 5.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.7: on any real inner-product space, the radial function x ↦ √(1 + ‖x‖²) is globally 1-smooth. This is the reusable owner-level estimate behind the Euclidean textbook statement.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem sqrt_one_add_sq_norm_is_l_smooth_innerProductSpace :
is_l_smooth_on
(fun x : E ↦ Real.sqrt (1 + ‖x‖ ^ (2 : ℕ)))
Set.univ
1Proposition 5.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.8 is source-facing: it records the Chapter 5 smoothness statement for the concrete log-sum-exp function on Euclidean ℝ^n. The smoothness owner is already is_l_smooth_on from Definition 5.1, while the function owner is already Chapter 4's log_sum_exp_function : (Fin n → ℝ) → EReal. This file therefore keeps only the Euclidean smoothness statement as a bridge/view to that earlier owner.
open scoped BigOperators Gradient
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
recall log_sum_exp_functionTheorem 5.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.8: for a convex differentiable real-valued function and a positive smoothness parameter L, the following are equivalent: (i) f is globally L-smooth, (ii) f satisfies the quadratic upper model, (iii) f satisfies the quadratic lower bound in terms of gradient differences, (iv) the gradient is 1 / L-cocoercive, and (v) the convex-combination inequality is relaxed by the quadratic error term L / 2 * λ * (1 - λ) * ‖x - y‖². The ambient differentiability hypothesis ensures that ∇ f agrees everywhere with the actual derivative, rather than with mathlib's default zero value at nondifferentiable points.
universe u
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [CompleteSpace E]
theorem convex_l_smooth_tfae_descent_gradient_lower_bound_cocoercive_convex_combo
[FiniteDimensional ℝ E]
(f : E → ℝ) (hf_convex : ConvexOn ℝ Set.univ f) (hf_diff : Differentiable ℝ f)
(L : NNReal) (hL : 0 < L) :
List.TFAE
[is_l_smooth_on f Set.univ L,
quadratic_upper_model f L,
gradient_quadratic_lower_bound f L,
gradient_cocoercive f L,
convex_combination_quadratic_lower_bound f L]Proposition 5.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.9 is source-facing: the textbook object is the concrete log-sum-exp function on ℝ^n, now viewed on the canonical l_∞ normed model WithLp ⊤ (Fin n → ℝ). Domain sampling: the Chapter 5 owner predicate is is_l_smooth_on, while the existing Chapter 4 owner declaration for the function itself is log_sum_exp_function. This file therefore keeps the source-facing smoothness statement as a bridge/view, reusing that earlier owner through the canonical coordinate-forgetting map WithLp.ofLp and EReal.toReal instead of introducing a parallel local copy of log-sum-exp.
open scoped BigOperators
variable {n : ℕ}
local notation "E" => WithLp (⊤ : ENNReal) (Fin n → ℝ)
recall log_sum_exp_function
-- Proof sketch: compute the Hessian of `fun x : E ↦ (log_sum_exp_function x.ofLp).toReal` as
-- `diag(w) - w wᵀ`, where `w_i = exp (x_i) / ∑ j, exp (x_j)`. For every direction `d`, the
-- associated quadratic form is bounded above by `‖d‖_∞^2`. Then apply the second-order
-- characterization of smoothness to deduce that the Fréchet derivative is globally
-- `1`-Lipschitz.Remark 5.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Remark 5.9 (1): on nontrivial Euclidean spaces ℝ^n, the quadratic x ↦ -(1 / 2) * ‖x‖² has least global smoothness parameter 1; equivalently, it is 1-smooth and it is not L-smooth for any L < 1.
open scoped Gradient
variable (n : ℕ)
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem negative_half_squared_norm_isLeast_smoothness_parameter (hn : 0 < n) :
IsLeast {L : NNReal | is_l_smooth_on (negative_half_squared_norm n) Set.univ L} 1Proposition 5.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.10: if an extended-real-valued function is σ₁-strongly convex, then it is also σ₂-strongly convex for every smaller positive modulus σ₂ < σ₁.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem is_strongly_convex_function.mono
{f : E → EReal} {σ₁ σ₂ : ℝ} (hf : is_strongly_convex_function f σ₁)
(hσ₂ : 0 < σ₂) (hσ₂σ₁ : σ₂ < σ₁) :
is_strongly_convex_function f σ₂Theorem 5.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.10: if a real-valued function is C² on an open set containing the segment segment ℝ x y, then it admits the second-order Taylor expansion with Lagrange remainder along that segment.
open scoped RealInnerProductSpace Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem linear_approximation_on_segment_with_lagrange_remainder
{U : Set E} {f : E → ℝ} {x y : E}
(hU_open : IsOpen U) (hf : ContDiffOn ℝ 2 f U) (hsegment : segment ℝ x y ⊆ U) :
∃ ξ ∈ segment ℝ x y,
f y = f x + inner ℝ (∇ f x) (y - x)
+ (1 / 2 : ℝ) * bilinearIteratedFDerivTwo ℝ f ξ (y - x) (y - x)Proposition 5.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.11 is source-facing: it specializes the Chapter 4 quadratic owner quadratic_affine_function_on_lp p A b c to the canonical ℓ₂ model of ℝ^n by taking p = 2, and studies strong convexity for a symmetric quadratic form. The canonical matrix-side owner abstractions are Matrix.PosSemidef, Matrix.PosDef, and the ordered Hermitian spectrum.
open Matrix
open WithLp (ofLp toLp)
open scoped MatrixOrder RealInnerProductSpace
variable {n : ℕ}
local notation "X" => Fin n → ℝ
recall quadratic_affine_function_on_lp
-- Semantic recall: local precedent `hessian_max_eigenvalue` and mathlib's
-- `Matrix.IsHermitian.eigenvalues₀_antitone` use the canonical descending Hermitian spectrum, so
-- index `0` is `λ_max` and, when `n > 0`, index `⊤` is `λ_min`.Theorem 5.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.12: on the canonical WithLp p (Fin n → ℝ) model of ℝ^n, a twice continuously differentiable function is globally L-smooth for the l_p norm if and only if its Fréchet Hessian, viewed as the derivative of fderiv ℝ f, has nonnegative operator norm at most L at every point. This is the canonical operator-norm rendering of the textbook bound ‖∇² f(x)‖_{p,q} ≤ L.
variable {n : ℕ} {p : ENNReal} [Fact (1 ≤ p)]
local notation "E" => WithLp p (Fin n → ℝ)
theorem is_l_smooth_iff_hessian_operator_norm_le
{f : E → ℝ} {L : NNReal} (hf : ContDiff ℝ 2 f) :
is_l_smooth_on f Set.univ L ↔
∀ x : E, ‖fderiv ℝ (fderiv ℝ f) x‖ ≤ (L : ℝ)Corollary 5.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 5.13: a twice continuously differentiable convex function on ℝ^n is globally L-smooth with respect to the Euclidean norm if and only if, at every point, the largest eigenvalue of its Hessian matrix is at most L.
open scoped Matrix.Norms.L2Operator MatrixOrder
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem convex_is_l_smooth_iff_hessian_max_eigenvalue_le
{f : E → ℝ} {L : NNReal} (hn : 0 < n) (hconvex : ConvexOn ℝ Set.univ f)
(hf : ContDiff ℝ 2 f) :
is_l_smooth_on f Set.univ L ↔
∀ x : E, (hessian_matrix_isHermitian f hf x).eigenvalues₀ ⟨0, by simpa using hn⟩ ≤
(L : ℝ)Proposition 5.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.13: on a convex set C in a real inner product space, the extended-real-valued function x ↦ ((‖x‖ ^ (2 : ℕ) / 2 : ℝ) : EReal) + (δ_ C) x is 1-strongly convex.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem half_squared_norm_add_indicator_is_one_strongly_convex_function
(C : Set E) (hC : Convex ℝ C) :
is_strongly_convex_function
(fun x : E ↦ ((‖x‖ ^ (2 : ℕ) / 2 : ℝ) : EReal) + (δ_ C) x)
1Proposition 5.14
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.14 (1): the negative entropy on the unit simplex is 1-strongly convex with respect to the l_1 norm, stated in the canonical real-valued form on the simplex itself.
open scoped BigOperators
open WithLp (ofLp)
variable {n : ℕ}
local notation "Δ" => stdSimplex ℝ (Fin n)
local notation "E₁" => WithLp 1 (Fin n → ℝ)
local notation "E₂" => EuclideanSpace ℝ (Fin n)
local notation "Δ₁" => Set.preimage (ofLp : E₁ → Fin n → ℝ) Δ
local notation "Δ₂" => Set.preimage (ofLp : E₂ → Fin n → ℝ) Δ
theorem negative_entropy_on_stdSimplex_is_one_strongly_convex_l1 :
StrongConvexOn
Δ₁
1
(fun x : E₁ ↦
(negative_entropy_on_stdSimplex n ((ofLp : E₁ → Fin n → ℝ) x)).toReal)Proposition 5.15
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.15: for 1 < p ≤ 2, the half-squared ℓ_p norm on the canonical WithLp model of ℝ^n is globally (p - 1)-strongly convex.
variable {n : ℕ} {p : ℝ}
local notation "E" => WithLp (ENNReal.ofReal p) (Fin n → ℝ)
theorem half_squared_lp_norm_is_strongly_convex
(hp : 1 < p) (hp₂ : p ≤ 2) :
HalfSquaredLpNorm.IsStronglyConvex n p hpDefinition 5.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 5.16: the source strong-convexity predicate is equivalent to strong convexity of the real-valued restriction x ↦ (f x).toReal on the effective domain, together with the ambient no--∞ condition.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem is_strongly_convex_function_iff_strongConvexOn_toReal
{f : E → EReal} {σ : ℝ} :
is_strongly_convex_function f σ ↔
0 < σ ∧
(∀ x, f x ≠ ⊥) ∧
StrongConvexOn (effective_domain f) σ (fun x ↦ (f x).toReal)Proposition 5.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.16: the ball-pen function from Example 5.29, represented by negative_sqrt_one_sub_norm_sq_extension, is 1-strongly convex with respect to the Euclidean norm in the chapter's source-facing extended-real-valued sense.
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem negative_sqrt_one_sub_norm_sq_extension_is_strongly_convex_function :
is_strongly_convex_function (negative_sqrt_one_sub_norm_sq_extension : E → EReal) 1Proposition 5.17
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 5.17: if f and ω are proper closed convex extended-real-valued functions and the continuous-dual Fenchel conjugate ω^* is (1 / L)-strongly convex, then the real-valued infimal convolution x ↦ ((f □ ω) x).toReal is globally L-smooth, provided f □ ω is everywhere finite. This is the canonical continuous-dual formulation of the textbook clause that ω^* being (1 / L)-strongly convex, equivalently ω being L-smooth, implies f □ ω is L-smooth; the explicit finiteness assumption keeps the global toReal surface faithful to the chapter's owner theorem.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
theorem infimal_convolution_toReal_is_l_smooth_of_conjugate_strongConvex
(f ω : E → EReal) (L : NNReal) (hL_pos : 0 < L) (hf_proper : IsProperExtendedRealFunction f)
(hω_proper : IsProperExtendedRealFunction ω) (hf_closed : LowerSemicontinuous f)
(hω_closed : LowerSemicontinuous ω) (hf_convex : is_convex_function f)
(hω_convex : is_convex_function ω)
(h_infimal_real : ∀ x, ∃ r : ℝ, (f □ ω) x = (r : EReal))
(hω_star_strong :
StrongConvexOn
(effective_domain (conjugate_function_strongDual ω))
(1 / (L : ℝ))
(fun y ↦ (conjugate_function_strongDual ω y).toReal)) :
is_l_smooth_on (fun x ↦ ((f □ ω) x).toReal) Set.univ LTheorem 5.17
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.17: on a Euclidean space, for σ > 0 and f : E → (-∞, ∞], an extended-real-valued function is σ-strongly convex if and only if subtracting (σ / 2) ‖x‖² yields a convex extended-real-valued function.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem is_strongly_convex_function_iff_sub_half_sigma_norm_sq_is_convex
(f : E → EReal) (σ : ℝ) (hσ : 0 < σ) (h_ne_bot : ∀ x, f x ≠ ⊥) :
is_strongly_convex_function f σ ↔
is_convex_function
(fun x ↦ f x - ((((σ / 2) * ‖x‖ ^ (2 : ℕ)) : ℝ) : EReal))Remark 5.18
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Remark 5.18: the entropy shift cannot realize the same positive parameter simultaneously as shift size and strong-convexity modulus for every α > 0 once the simplex has at least two distinct points.
open WithLp (ofLp)
variable {n : ℕ}
local notation "Δ" => stdSimplex ℝ (Fin n)
local notation "E₁" => WithLp 1 (Fin n → ℝ)
local notation "Δ₁" => Set.preimage (ofLp : E₁ → Fin n → ℝ) Δ
theorem not_forall_pos_strongConvexOn_negative_entropy_sub_alpha_l1Square
(hn : 1 < n) :
¬ ∀ α > 0,
StrongConvexOn Δ₁ α
(fun x : E₁ ↦
(negative_entropy_on_stdSimplex n (ofLp x)).toReal - α * ‖x‖ ^ (2 : ℕ))Lemma 5.20
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 5.20: if f is σ-strongly convex and the finite-valued restriction x ↦ (g x).toReal is convex on effective_domain g, with g never equal to ⊥, then f + g is σ-strongly convex.
universe u
variable {E : Type u}
variable [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem is_strongly_convex_function_add_of_convexOn_toReal
{f g : E → EReal} {σ : ℝ} (hf : is_strongly_convex_function f σ)
(hg_ne_bot : ∀ x, g x ≠ ⊥)
(hg : ConvexOn ℝ (effective_domain g) (fun x ↦ (g x).toReal)) :
is_strongly_convex_function (fun x ↦ f x + g x) σLemma 5.22
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 5.22: if a closed convex function f : ℝ → (-∞, ∞] never takes the value -∞ and is finite on [a, b] with a < b, then there exists a real-valued function h such that h is a subgradient selection on [a, b] and its interval integral equals the endpoint difference (f b).toReal - (f a).toReal.
open scoped Interval
open scoped Gradient
theorem exists_subgradient_selection_eq_intervalIntegral
(f : ℝ → EReal) (hne_bot : ∀ x, f x ≠ ⊥) (h_closed : LowerSemicontinuous f)
(h_convex : is_convex_function f) {a b : ℝ} (hab : a < b)
(hdom : Set.Icc a b ⊆ effective_domain f) :
∃ h : ℝ → ℝ,
IsSubgradientSelectionOnInterval f a b h ∧
(f b).toReal - (f a).toReal = ∫ t in a..b, h tLemma 5.23
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 5.23: line segment principle for relative interior. If C is convex, x lies in the relative interior of C, y lies in the closure of C, and 0 < t ≤ 1, then t • x + (1 - t) • y also lies in the relative interior of C.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
-- Proof sketch: pass to the affine span of `C`, where `intrinsicInterior ℝ C` becomes the ordinary
-- interior and, in finite dimension, `closure C` agrees with the intrinsic closure. Then apply the
-- ambient convex-topology theorem `Convex.combo_interior_closure_mem_interior` in that affine-span
-- model and transport the result back to `E`.
theorem Convex.combo_intrinsicInterior_closure_mem_intrinsicInterior {C : Set E} (hC : Convex ℝ C)
{x y : E} (hx : x ∈ intrinsicInterior ℝ C) (hy : y ∈ closure C) {t : ℝ}
(ht_pos : 0 < t) (ht_le_one : t ≤ 1) :
t • x + (1 - t) • y ∈ intrinsicInterior ℝ CTheorem 5.24
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.24: on a finite-dimensional real inner-product space, for a proper closed convex extended-real-valued function and a fixed modulus σ > 0, the following are equivalent: (i) f is σ-strongly convex in the source-facing Chapter 5 sense, (ii) every Euclidean subgradient gives the quadratic lower support model, and (iii) the Euclidean subdifferential is σ-strongly monotone. This is the source-facing rendering of the textbook first-order characterization of strong convexity.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
-- Semantic recall: Chapter 5 already provides the source-facing owner
-- `is_strongly_convex_function`, and Chapter 3 already provides the vector-side owner
-- `euclideanSubdifferential`; the dual-pairing predicates above remain companion bridge forms.
theorem strongConvexOn_tfae_subgradient_quadratic_lower_bound_strong_monotonicity
[FiniteDimensional ℝ E] (f : E → EReal) (σ : ℝ) (hσ : 0 < σ)
(hf_proper : IsProperExtendedRealFunction f)
(hf_closed : LowerSemicontinuous f) (hf_convex : is_convex_function f) :
List.TFAE
[is_strongly_convex_function f σ,
euclidean_subgradient_quadratic_lower_bound f σ,
euclidean_subdifferential_strong_monotonicity f σ]Theorem 5.25
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.25 (1): a closed σ-strongly convex extended-real-valued function with nonempty effective domain has a unique global minimizer. The no--∞ and positivity clauses are carried by the source-facing owner is_strongly_convex_function f σ, while domain nonemptiness remains an explicit hypothesis because it is not part of that owner.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
-- Semantic recall: this file is `source-facing`. The Chapter 5 owner
-- `is_strongly_convex_function f σ` packages the textbook strong-convexity assumptions, while
-- `IsMinOn` is the canonical minimizer predicate. Theorem 5.25 records the existence, uniqueness,
-- and quadratic-growth consequences of that source-facing owner.
-- Proof sketch: choose `x₀ ∈ effective_domain f` from `hdom`. The Chapter 5 owner hypothesis `hf`
-- exposes the canonical bridge `StrongConvexOn (effective_domain f) σ (fun x ↦ (f x).toReal)`,
-- so uniqueness comes from strict convexity of the real-valued restriction. Existence follows from
-- the coercive quadratic lower bound implied by strong convexity, together with lower
-- semicontinuity and finite-dimensional compactness of a suitable sublevel set.
theorem existsUnique_isMinOn_univ_of_closed_strongly_convex
{f : E → EReal} {σ : ℝ} (hf : is_strongly_convex_function f σ)
(hdom : (effective_domain f).Nonempty) (hclosed : LowerSemicontinuous f) :
∃! xStar : E, IsMinOn f Set.univ xStarTheorem 5.26
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.26 direct proof repair (1): if f : E → ℝ is convex and (1 / σ)-smooth on Set.univ, then its Fenchel conjugate on StrongDual ℝ E is σ-strongly convex on its effective domain.
universe u
open scoped Topology
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
theorem strongConvexOn_toReal_conjugate_function_of_convex_is_l_smooth
(σ : ℝ) (hσ : 0 < σ) (f : E → ℝ) (hf_convex : ConvexOn ℝ Set.univ f)
(hf_smooth : is_l_smooth_on f Set.univ (Real.toNNReal (1 / σ))) :
StrongConvexOn
(effective_domain (conjugate_function_strongDual f.toEReal))
σ
(fun y : StrongDual ℝ E ↦ (conjugate_function_strongDual f.toEReal y).toReal)Theorem 5.30
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 5.30 (1): if f is proper closed convex, ω is a convex L-smooth real-valued function, and the infimal convolution f □ ω.toEReal is everywhere finite, then the real-valued map x ↦ ((f □ ω.toEReal) x).toReal is L-smooth.
universe u
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable (f : E → EReal) (ω : E → ℝ) (L : NNReal)
variable (hf_proper : IsProperExtendedRealFunction f) (hf_closed : LowerSemicontinuous f)
variable (hf_convex : is_convex_function f)
variable (hω_convex : ConvexOn ℝ Set.univ ω) (hω_smooth : is_l_smooth_on ω Set.univ L)
variable (hreal : ∀ x, ∃ r : ℝ, (f □ ω.toEReal) x = (r : EReal))
include hf_proper hf_closed hf_convex hω_convex hω_smooth hreal
theorem infimal_convolution_toReal_is_l_smooth
: is_l_smooth_on (fun x ↦ ((f □ ω.toEReal) x).toReal) Set.univ LSupporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
ConjugateFunctionStrongDual.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.