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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 L

Proposition 5.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 0

Proposition 5.3

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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_infDist

Proposition 5.4

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 x

Theorem 5.4

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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‖ ^ 2

Proposition 5.5

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 hp

Lemma 5.7

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 1

Proposition 5.8

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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_function

Theorem 5.8

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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} 1

Proposition 5.10

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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

Proposition 5.14

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 hp

Definition 5.16

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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

Proposition 5.17

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 L

Theorem 5.17

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 t

Lemma 5.23

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Theorem 5.24

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 xStar

Theorem 5.26

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 L

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source