Chapter 02 — Smooth Convex Optimization

Proofs omitted. Hover over highlighted terms to see their Lean types.

Algorithm 2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.1 is a recall-only item in the domain of recursive first-order optimization trajectories. Sampled owner-style declarations: - gradientMethod - gradientMethod_zero - gradientMethod_succ - gradientMethod_const_eq_iterate Source/core/bridge triage: - source-facing/core: the recursive trajectory owner gradientMethod stepSize f x0 - bridge/view: the constant-step iterate description gradientMethod_const_eq_iterate Primitive data: - the step-size schedule stepSize - the objective f - the initial point x0 Derived API: - the base-point identity gradientMethod_zero - the one-step recursion gradientMethod_succ - the constant-step iterate bridge gradientMethod_const_eq_iterate Chapter 2 therefore reuses the Chapter 1 owner directly and keeps only canonical recalls of that API, rather than repeating its full binder telescope or introducing a Euclidean-model wrapper.

recall gradientMethod

Definition 2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.1: for an objective f : ℝⁿ → ℝ, the unconstrained minimization problem min_{x ∈ ℝⁿ} f(x) is the whole-space minimization problem, and a global minimizer is canonically expressed by IsMinOn f Set.univ xStar. The owner itself does not depend on the ambient ℝⁿ presentation, so this file records the generic canonical recall and its textbook Set.univ specialization.

universe u variable {α : Type u} variable (f : α → ℝ) (xStar : α) recall IsMinOn

Lemma 2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.1 lies in the first-order convex-analysis function-class domain for the source-facing class 𝓕¹(Q). Sampled owner-style declarations: - mathlib ContDiffOn.const_smul - mathlib ConvexOn.smul - mathlib ConvexOn.add - Chapter 2 ConvexC1On in Definition_2_4 Best owner abstraction: - ConvexC1On, the chapter owner for the source class 𝓕¹(Q). Primitive data: - the feasible set Q - the objective functions f₁, f₂ - the owner hypotheses ConvexC1On Q f₁ and ConvexC1On Q f₂ Derived API: - owner closure under nonnegative scalar multiplication and addition - the weighted-sum closure theorem ConvexC1On.nonneg_combo Source/core/bridge triage: - source-facing: the textbook closure of 𝓕¹(Q) under nonnegative linear combinations - core/canonical: ConvexC1On.nonneg_combo - bridge/view: the notation 𝓕¹(Q) as the set-level source presentation of the owner predicate This numbered item is therefore a direct owner recall rather than a second declaration site.

recall ConvexC1On.nonneg_combo

Proposition 2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.1 is the direct owner recall of the dual-pairing estimate attached to Seminorm.dualNorm.

#check Seminorm.inner_le_dualNorm_mul

Text 2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.1: if α_k ≤ 1, the transport coefficient is nonnegative, μ ≥ 0, φ_k^* ≥ f(x_k), and the μ-free lower bound (2.2.57) holds at stage k, then the owner Proposition 2.22 update yields the displayed μ-free lower bound finalRhs for simpleSetEstimatingValue ... (k + 1).

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (x0 : E) (μ : ℝ) (L : NNRealˣ) (gamma0 : ℝ) (y : ℕ → E) (α : ℕ → ℝ) {k : ℕ} {xk : E} local notation "gammaK" => estimatingSequenceCurvature μ gamma0 α k local notation "gammaKp1" => estimatingSequenceCurvature μ gamma0 α (k + 1) local notation "phi" => simpleSetEstimatingValue Q hQ_nonempty hQ_closed hQ_convex f x0 μ L gamma0 y α local notation "v" => simpleSetEstimatingCenter Q hQ_nonempty hQ_closed hQ_convex f x0 μ L gamma0 y α k local notation "yK" => y k local notation "xQ" => x_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; L](yK) local notation "gQ" => g_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; L](yK) local notation "gQNormSq" => ‖gQ‖ ^ (2 : ℕ) local notation "curvatureCoeff" => α k / (2 * L) - α k ^ (2 : ℕ) / (2 * gammaKp1) local notation "transportCoeff" => α k * (1 - α k) * gammaK / gammaKp1 local notation "transportStrongConvexityTerm" => transportCoeff * (μ / 2) * ‖yK - v‖ ^ (2 : ℕ) local notation "objectiveStrongConvexityTerm" => (μ / 2) * ‖xk - yK‖ ^ (2 : ℕ) local notation "intermediateRhs" => (1 - α k) * f xk + α k * f xQ + curvatureCoeff * gQNormSq + transportCoeff * inner ℝ gQ (v - yK) local notation "intermediateStrongRhs" => intermediateRhs + transportStrongConvexityTerm local notation "objectiveLowerRhs" => f xQ + inner ℝ gQ (xk - yK) + (1 / (2 * L)) * gQNormSq local notation "objectiveLowerStrongRhs" => objectiveLowerRhs + objectiveStrongConvexityTerm local notation "combinedShift" => ((α k * gammaK) / gammaKp1) • (v - yK) + (xk - yK) local notation "finalRhs" => f xQ + (1 / (2 * L) - α k ^ (2 : ℕ) / (2 * gammaKp1)) * gQNormSq + (1 - α k) * inner ℝ gQ combinedShift local notation "finalStrongRhs" => finalRhs + (1 - α k) * objectiveStrongConvexityTerm + transportStrongConvexityTerm theorem simple_set_phi_star_lower_bound_of_objective_lower_bound (halpha_k : α k ≤ 1) (htransportCoeff : 0 ≤ transportCoeff) (hμ : 0 ≤ μ) (hphi_k : f xk ≤ phi k) (hobjective_lower : f xk ≥ objectiveLowerRhs) : phi (k + 1) ≥ finalRhs

Theorem 2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.1: a critical point of a convex differentiable function is a global minimizer.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem stationaryPoint_isMinOn_of_convexOn {f : E → ℝ} {xStar : E} (hf_conv : ConvexOn ℝ Set.univ f) (hf_diff : DifferentiableAt ℝ f xStar) (hgrad : ∇ f xStar = 0) : IsMinOn f Set.univ xStar

Algorithm 2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.2: a general optimal-method scheme for f : E → ℝ with inputs L > 0, mu ≥ 0, initial point x0, and initial curvature parameter gamma0 > 0 is an OptimalMethodRecurrence whose next iterate also satisfies the step-(c) descent inequality f(x_{k+1}) ≤ f(y_k) - (1 / (2 * L)) * ‖∇ f(y_k)‖^2. The source text is written on ℝⁿ, but the owner abstraction only uses real-Hilbert-space structure.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] structure GeneralOptimalMethodScheme (f : E → ℝ) (L mu : ℝ) (x0 : E) (gamma0 : ℝ) extends OptimalMethodRecurrence f L mu x0 gamma0 where /-- The next iterate satisfies the descent inequality from step `(c)`. -/ x_succ_le : ∀ k : ℕ, f (x (k + 1)) ≤ f (y k) - (1 / (2 * L)) * ‖∇ f (y k)‖ ^ (2 : ℕ)

Definition 2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.2: on a convex set Q, a C¹ function is convex exactly when it lies above each tangent plane determined by its within-set gradient.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem convexOn_iff_lower_tangent_plane_of_contDiffOn {Q : Set E} {f : E → ℝ} (hQ : Convex ℝ Q) (hf_C1 : ContDiffOn ℝ 1 f Q) : ConvexOn ℝ Q f ↔ ∀ ⦃x⦄, x ∈ Q → ∀ ⦃y⦄, y ∈ Q → f y ≥ f x + inner ℝ (gradientWithin f Q x) (y - x)

Lemma 2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.2 lies in Euclidean first-order convex analysis under affine pullback. Sampled owner-style declarations: - mathlib ContDiffOn.comp - mathlib ConvexOn.comp_affineMap - Chapter 2 ConvexC1On.comp_continuousAffineMap - Chapter 2 ConvexC1On.comp_affineMap Best owner abstraction: - ConvexC1On.comp_continuousAffineMap, the canonical owner-level precomposition theorem for the ConvexC1On owner predicate. Primitive data: - the source set Q - the objective f - the owner hypothesis hf : ConvexC1On Q f - the affine map g Derived API: - the Euclidean specialization ConvexC1On.comp_affineMap, obtained from finite-dimensional continuity of affine maps. Source/core/bridge triage: - source-facing: Lemma 2.2's Euclidean affine pullback statement - core/canonical: ConvexC1On.comp_continuousAffineMap - bridge/view: the finite-dimensional specialization ConvexC1On.comp_affineMap This item no longer keeps a parallel local theorem shell. The source-facing Euclidean statement now lives with the ConvexC1On owner in Definition_2_4, and this file is a direct recall of that canonical bridge.

recall ConvexC1On.comp_affineMap

Proposition 2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.2 in owner form: the explicit chain Hessian formula places f in the chapter's smooth-convex owner class 𝓕[L, p]¹¹.

open scoped BigOperators Gradient SmoothConvex variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "p" => normSeminorm ℝ E variable (L : NNReal) (k : Fin n) (f : EuclideanSpace ℝ (Fin n) → ℝ) theorem chain_hessian_formula_mem_smooth_convex_objective (hf_C2 : ContDiff ℝ 2 f) (hH : ∀ x h : E, inner ℝ (hessian f x h) h = ((L : ℝ) / 4) * nesterovChainQuadraticForm k h) : ConvexC1SeminormSmooth (normSeminorm ℝ (EuclideanSpace ℝ (Fin n))) L f

Text 2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.2: for a nonempty closed convex set Q and γ > 0, the quadratically regularized max of the affine component linearizations at xBar has components in 𝓛^1[γ] and a unique feasible minimizer. Equivalently, the owner set X_f(xBar; γ) from Definition 2.41 is a singleton, so the associated gradient mapping is well defined.

open scoped Gradient StrongConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {ι : Type*} [Fintype ι] [Nonempty ι] theorem regularizedAffineMax_gradientMapping_wellDefined (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (fi : ι → E → ℝ) (xBar : E) (γ : ℝ) (hγ : 0 < γ) : (∀ i : ι, quadraticallyRegularizedObjective (firstOrderTaylorModelAt (fi i) xBar) γ xBar ∈ 𝓛^1[γ]) ∧ ∃! xPlus : E, xPlus ∈ gradientMappingSet Q (regularizedAffineMaxModel fi γ) xBar

Theorem 2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.2: on a convex set Q, convexity of f is exactly the usual two-point Jensen inequality along every segment in Q. Specializing 𝕜 to ℝ recovers the textbook setting.

variable {𝕜 E : Type*} [Ring 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] [AddCommMonoid E] [Module 𝕜 E] variable {Q : Set E} {f : E → 𝕜} theorem convexOn_iff_segment_inequality (hQ : Convex 𝕜 Q) : ConvexOn 𝕜 Q f ↔ ∀ ⦃x⦄, x ∈ Q → ∀ ⦃y⦄, y ∈ Q → ∀ ⦃α : 𝕜⦄, α ∈ Set.Icc (0 : 𝕜) 1 → f (α • x + (1 - α) • y) ≤ α * f x + (1 - α) * f y

Algorithm 2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.3: the recursive type-I optimal-method trajectory. The primitive recursive state is (x_k, v_k, γ_k); the source-named quantities α_k and y_k are the canonical derived projections determined by step (a) and step (b).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] local notation "State" => E × E × ℝ noncomputable def constantStepSchemeI (f : E → ℝ) (L mu : ℝ) (x0 : E) (gamma0 : ℝ) : ℕ → State

Definition 2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.3: a set Q ⊆ ℝⁿ is convex exactly when it contains every two-point convex combination α • x + (1 - α) • y with α ∈ [0, 1].

universe u v variable {𝕜 : Type u} {E : Type v} variable [Semiring 𝕜] [PartialOrder 𝕜] [AddCommMonoid E] [SMul 𝕜 E] theorem convex_iff_unit_interval_smul_add_mem {n : ℕ} {Q : Set (EuclideanSpace ℝ (Fin n))} : Convex ℝ Q ↔ ∀ ⦃x : EuclideanSpace ℝ (Fin n)⦄, x ∈ Q → ∀ ⦃y : EuclideanSpace ℝ (Fin n)⦄, y ∈ Q → ∀ ⦃α : ℝ⦄, 0 ≤ α → α ≤ 1 → α • x + (1 - α) • y ∈ Q

Lemma 2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.3 in owner form: on a finite-dimensional real inner-product space, the dual norm induced by the ambient norm is the ambient norm.

open scoped SeminormDualNorm namespace Seminorm variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem dualNorm_normSeminorm_eq_norm [FiniteDimensional ℝ E] (s : E) : ‖s‖[normSeminorm ℝ E,*] = ‖s‖

Proposition 2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.3: on a convex subset Q of a real normed space, adding a convex function to a μ-strongly convex function yields another μ-strongly convex function with respect to the ambient norm.

variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] namespace StrongConvexOn variable {Q : Set E} {f g : E → ℝ} {μ : ℝ} theorem add_convexOn (hg : StrongConvexOn Q μ g) (hf : ConvexOn ℝ Q f) : StrongConvexOn Q μ (f + g)

Text 2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.3: assuming the whole-space estimate-sequence setting and φ_k^* ≥ f(x_k), the lower bound at x = x_k, xBar = y_k implies the regrouped lower bound for φ_{k+1}^*.

open scoped Gradient ProjectedGradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) (x0 : E) (μ : ℝ) (L : NNRealˣ) (gamma0 : ℝ) (y : ℕ → E) (α : ℕ → ℝ) (hγ : ∀ k, estimatingSequenceCurvature μ gamma0 α (k + 1) ≠ 0) (k : ℕ) (xk : E) local notation "gammaK" => estimatingSequenceCurvature μ gamma0 α k local notation "gammaKp1" => estimatingSequenceCurvature μ gamma0 α (k + 1) local notation "phiK" => simpleSetEstimatingValue (Set.univ : Set E) Set.univ_nonempty isClosed_univ convex_univ f x0 μ L gamma0 y α k local notation "phiKp1" => simpleSetEstimatingValue (Set.univ : Set E) Set.univ_nonempty isClosed_univ convex_univ f x0 μ L gamma0 y α (k + 1) local notation "vK" => simpleSetEstimatingCenter (Set.univ : Set E) Set.univ_nonempty isClosed_univ convex_univ f x0 μ L gamma0 y α k local notation "yK" => y k local notation "transportCoeff" => α k * (1 - α k) * gammaK / gammaKp1 local notation "strongObjectiveLowerRhs" => f (gradientStep f yK L) + inner ℝ (∇ f yK) (xk - yK) + (1 / (2 * (L : ℝ))) * ‖∇ f yK‖ ^ (2 : ℕ) + (μ / 2) * ‖xk - yK‖ ^ (2 : ℕ) local notation "intermediateRhs" => (1 - α k) * f xk + α k * f (gradientStep f yK L) + (α k / (2 * (L : ℝ)) - α k ^ (2 : ℕ) / (2 * gammaKp1)) * ‖∇ f yK‖ ^ (2 : ℕ) + transportCoeff * inner ℝ (∇ f yK) (vK - yK) local notation "finalRhs" => f (gradientStep f yK L) + (1 / (2 * (L : ℝ)) - α k ^ (2 : ℕ) / (2 * gammaKp1)) * ‖∇ f yK‖ ^ (2 : ℕ) + (1 - α k) * inner ℝ (∇ f yK) (((α k * gammaK) / gammaKp1) • (vK - yK) + (xk - yK)) theorem whole_space_phi_star_lower_bound_of_phi_star_ge_objective (hf : f ∈ 𝓢[μ, (L : ℝ)]¹¹) (halpha_k : α k ≤ 1) (htransportCoeff : 0 ≤ transportCoeff) (hphi_k : f xk ≤ phiK) : phiKp1 ≥ finalRhs

Theorem 2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.3, stated on the canonical real Hilbert-space owner layer: for a convex set Q and a function f : E → ℝ that is differentiable on Q, convexity of f on Q is equivalent to monotonicity of its within-set gradient on Q; the main theorem is stated with the owner hypothesis DifferentiableOn ℝ f Q, and the textbook C¹ version appears below as a companion bridge through ConvexC1On. The textbook Euclidean theorem is the finite-dimensional specialization.

universe u open AffineMap open InnerProductSpace open scoped ConvexC1 variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {Q : Set E} {f : E → ℝ} local notation "gradQ" => gradientWithin f Q theorem convexOn_iff_gradient_monotone (hQ : Convex ℝ Q) (hf_diff : DifferentiableOn ℝ f Q) : ConvexOn ℝ Q f ↔ GradientMonotoneOn Q f

Algorithm 2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.4: for f : E → ℝ, parameters μ, L, initial point x0, and admissible source parameter α₀ ∈ (√q[μ, L], constantStepSchemeIIAlphaUpper q[μ, L]], the recursive type-II trajectory (x_k, y_k, α_k) starts from (x₀, y₀, α₀) = (x0, x0, α₀) and applies the exact gradient step x_{k+1} = y_k - (1 / L) ∇ f(y_k), the quadratic scalar update for α_{k+1}, and the textbook momentum formula for y_{k+1}.

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (μ L : ℝ) local notation "qf" => q[μ, L] local notation "αRange" => Set.Ioc (Real.sqrt qf) (constantStepSchemeIIAlphaUpper qf) noncomputable def constantStepSchemeII (f : E → ℝ) (x0 : E) (alpha0 : αRange) : ℕ → E × E × ℝ := constantStepSchemeIICore f L qf x0 ⟨(alpha0 : ℝ), constantStepSchemeII_alpha0_mem_Ioo alpha0.2⟩

Definition 2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.4: a function on a convex set Q belongs to 𝓕¹(Q) when it is continuously differentiable on Q and is convex there in the canonical owner sense ConvexOn ℝ Q f. Supporting-nesterovHyperplane arguments should use the owner theorem ConvexOn.lower_tangent_plane through convexC1On_convexOn hf, so no duplicate wrapper theorem is kept here.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] abbrev ConvexC1On (Q : Set E) (f : E → ℝ) : Prop := ContDiffOn ℝ 1 f Q ∧ ConvexOn ℝ Q f

Lemma 2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.4: for α ∈ [0, 1], the weighted squared distance is bounded by the intermediate weighted square of ‖x‖ + ‖y‖, which is bounded by the convex combination of ‖x‖² and ‖y‖².

variable {E : Type*} [SeminormedAddGroup E] theorem convex_combination_norm_sq_bounds (x y : E) (α : ℝ) (hα : α ∈ Set.Icc (0 : ℝ) 1) : α * (1 - α) * ‖x - y‖ ^ 2 ≤ α * (1 - α) * (‖x‖ + ‖y‖) ^ 2 ∧ α * (1 - α) * (‖x‖ + ‖y‖) ^ 2 ≤ α * ‖x‖ ^ 2 + (1 - α) * ‖y‖ ^ 2

Proposition 2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.4: if A satisfies μ I ≤ A ≤ L I with 0 < μ, then the canonical quadratic objective quadraticObjective α a A belongs to the source-facing class 𝓢[μ, L]¹¹.

open scoped Gradient MatrixOrder StrongConvexSmooth open Matrix variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ theorem quadraticObjective_mem_S11 (μ L α : ℝ) (a : E) (A : Mat) (hμ : 0 < μ) (hμA : μ • (1 : Mat) ≤ A) (hAL : A ≤ L • (1 : Mat)) : quadraticObjective α a A ∈ 𝓢[μ, L]¹¹

Text 2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.4 (2): the μ-regularized affine model at xBar is a global lower quadratic model for the minimax objective.

universe u v
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {ι : Type v} [Fintype ι] [Nonempty ι]
variable {m : ℕ} {μ L : ℝ}
namespace SmoothMinimaxProblem
variable (problem : SmoothMinimaxProblem E ι μ L) (xBar : E)
local notation "modelValue" =>
  fun γ ↦
    sInf
      ((quadraticallyRegularizedObjective (problem.affineApproximation xBar) γ xBar) ''
        problem.feasibleSet)
local notation "valueFunction" =>
  sInf (problem '' problem.feasibleSet)
theorem lowerRegularizedModel_le_objective
    (x : E) :
    quadraticallyRegularizedObjective (problem.affineApproximation xBar) μ xBar x ≤
      problem x

Theorem 2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.4, stated on the canonical real Hilbert-space owner layer: on an open convex set Q, a C² function is convex on Q if and only if its Hessian is positive at every point of Q; the textbook Euclidean theorem is the finite-dimensional specialization.

open InnerProductSpace open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {Q : Set E} {f : E → ℝ} theorem convexOn_iff_hessian_isPositive (hQ_open : IsOpen Q) (hQ_conv : Convex ℝ Q) (hf_C2 : ContDiffOn ℝ 2 f Q) : ConvexOn ℝ Q f ↔ ∀ x ∈ Q, (hessian f x).IsPositive

Algorithm 2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.5: the recursive scheme-III state trajectory (x_k, y_k) started from (x₀, y₀) = (x0, x0) and updated by the exact gradient step x_{k+1} = y_k - (1 / L) ∇ f(y_k) together with the fixed-momentum extrapolation y_{k+1} = x_{k+1} + β (x_{k+1} - x_k), where β = β[q_f].

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] noncomputable def constantStepSchemeIII (f : E → ℝ) (L qf : ℝ) (x0 : E) : ℕ → E × E

Definition 2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.5 in owner form: on a real inner-product space, p.dualNorm is the support function of the closed p-unit ball for a separated seminorm p, i.e. the textbook dual norm. The finite-dimensional hypothesis is the canonical owner layer guaranteeing this support value is an honest real supremum.

universe u open scoped BigOperators namespace Seminorm variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] def dualNorm (p : Seminorm ℝ E) [FiniteDimensional ℝ E] [p.IsNorm] (g : E) : ℝ := sSup ((fun x : E ↦ inner ℝ g x) '' p.closedBall 0 1)

Lemma 2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.5: if each of the first k terms of a sequence g lies in its natural owner coordinate subspace ℝ^{j.1+1,n}, then the span of that prefix lies in ℝ^{k,n}. Applying this with g j = ∇ f (x j) recovers the gradient-prefix span statement used later in the chapter.

open scoped CoordinateSubspace
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem prefix_span_le_coordinateSubspace {k : ℕ}
    (g : ℕ → E)
    (hg : ∀ j : Fin k, g j ∈ ℝ^{j.1 + 1,n}) :
    Submodule.span ℝ (Set.range fun j : Fin k ↦ g j) ≤ ℝ^{k,n}

Proposition 2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.5: the entropy function x ↦ ∑ᵢ xᵢ log xᵢ is 1-strongly convex on the standard simplex Δ_n = stdSimplex ℝ (Fin n) with respect to the canonical ℓ₁ norm on the function-space owner Fin n → ℝ.

open scoped BigOperators variable (n : ℕ) local notation "F" => Fin n → ℝ local notation "E" => EuclideanSpace ℝ (Fin n) theorem entropyFunction_strongConvexOnWith_l1_stdSimplex : StrongConvexOnWith (simplexL1Seminorm n) 1 (stdSimplex ℝ (Fin n)) (entropyFunction n)

Theorem 2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.5: for a positive smoothness constant L, membership in 𝓕[L, p]¹¹ is equivalent to each of the six standard smooth convex inequalities (2.1.9) through (2.1.14). In Lean, every clause that mentions ∇ f is bundled with the witness that ∇ f x is the genuine ambient gradient of f at x, avoiding the totalized fallback behavior of gradient. The textbook Euclidean theorem is the finite-dimensional specialization.

universe u open AffineMap open scoped ConvexC1 Gradient SeminormDualNorm variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable [FiniteDimensional ℝ E] variable {p : Seminorm ℝ E} [Seminorm.IsNorm p] {L : NNReal} variable {Q : Set E} {f : E → ℝ} open scoped SmoothConvex theorem convexC1SeminormSmooth_tfae (p : Seminorm ℝ E) [Seminorm.IsNorm p] {L : NNReal} (hL : 0 < L) (f : E → ℝ) : List.TFAE [ f ∈ 𝓕[L, p]¹¹ , cond2_1_9 p L f , cond2_1_10 p L f , cond2_1_11 p L f , smoothConvexMonotoneGradientBoundsWithGradientOn p L Set.univ f , cond2_1_13 p L f , smoothConvexConvexCombinationQuadraticBoundOn p L Set.univ f ]

Algorithm 2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.6: the simple-set gradient method produces the iterate sequence (x_k)_{k ≥ 0} starting from x₀ = x0 and recursively updating by xₖ₊₁ = x_Q[Q; ⟨x0, hx0⟩; hQ_closed; hQ_convex | f; γ](xₖ). Equivalently, each step satisfies xₖ₊₁ = xₖ - γ⁻¹ • g_Q[Q; ⟨x0, hx0⟩; hQ_closed; hQ_convex | f; γ](xₖ). The output-feasibility statement (x_k) ⊆ Q is recorded in companion theorems.

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (Q : Set E) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (x0 : E) (hx0 : x0 ∈ Q) (γ : NNRealˣ) noncomputable def simpleSetGradientMethod (Q : Set E) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (x0 : E) (hx0 : x0 ∈ Q) (γ : NNRealˣ) : ℕ → E := Nat.rec x0 fun _ xk ↦ x_Q[Q; ⟨x0, hx0⟩; hQ_closed; hQ_convex | f; γ](xk)

Definition 2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.6: a function on Q belongs to the smooth-convex class exactly when f ∈ 𝓕[L, p]¹¹(Q), whose defining gradient clause is ‖∇ f x - ∇ f y‖[p,*] ≤ (L : ℝ) * p (x - y) together with the ambient gradient witness HasGradientAt f (∇ f x) x on Q.

open scoped Gradient SmoothConvex SeminormDualNorm universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable [FiniteDimensional ℝ E] variable {p : Seminorm ℝ E} [Seminorm.IsNorm p] {L : NNReal} variable {Q : Set E} {f : E → ℝ} variable (p) (L) (Q) (f) #check f ∈ 𝓕[L, p]¹¹(Q)

Lemma 2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.6 is the direct owner recall of nonnegative weighted-sum closure for StrongConvexOnWith.

recall StrongConvexOnWith.nonneg_combo_inter

Proposition 2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.6: if μ > 0, 1 ≤ Q_f, and 0 ≤ A ≤ 4 I in the Loewner order, then the quadratic objective f_{μ,Q_f} belongs to the source class 𝓢[μ, μ * Q_f]¹¹; in particular its condition number parameter is Q_f.

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] local notation "I" => ContinuousLinearMap.id ℝ E variable {μ Q_f : ℝ} {A : E →L[ℝ] E} variable [CompleteSpace E] theorem nesterovQuadraticObjective_mem_S11 (hμ : 0 < μ) (hQf : 1 ≤ Q_f) (hA_nonneg : 0 ≤ A) (hA_le : A ≤ (4 : ℝ) • I) : nesterovQuadraticObjective μ Q_f A ∈ 𝓢[μ, μ * Q_f]¹¹

Theorem 2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.6: for a twice continuously differentiable function on a finite-dimensional real inner-product space, belonging to 𝓕[L, p]¹¹ is equivalent to the Hessian quadratic form being nonnegative and bounded above by L * p(h)^2 in every direction. The textbook ℝⁿ statement is the finite-dimensional specialization.

open scoped Gradient SmoothConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] [FiniteDimensional ℝ E] variable {p : Seminorm ℝ E} [Seminorm.IsNorm p] {L : NNReal} {f : E → ℝ} open scoped SeminormDualNorm open InnerProductSpace theorem convexC1SeminormSmooth_iff_hessian_quadratic_form_bounded (hf_C2 : ContDiff ℝ 2 f) : f ∈ 𝓕[L, p]¹¹ ↔ ∀ x h : E, 0 ≤ inner ℝ (hessian f x h) h ∧ inner ℝ (hessian f x h) h ≤ (L : ℝ) * (p h) ^ 2

Algorithm 2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.7: for a simple closed convex set Q, objective f, step parameter L, reciprocal condition number q_f, initial feasible point x₀ ∈ Q, and admissible initial scalar α₀ ∈ (√q_f, 2 (3 + q_f) / (3 + √(21 + 4 q_f))], the recursive state (x_k, y_k, α_k) starts from (x₀, x₀, α₀) and applies the projected step x_{k+1} = x_Q(y_k; L), the scalar update α_{k+1} = constantStepSchemeIIAlphaNext q_f α_k, and the textbook type-II momentum formula for y_{k+1}. The step parameter is stored at the owner level as the positive inverse-stepsize datum L : NNRealˣ, matching the projected-gradient owner API. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (QSet : Set E) variable (hQ_closed : IsClosed QSet) (hQ_convex : Convex ℝ QSet) variable (f : E → ℝ) (L : NNRealˣ) (qf : ℝ) variable (x0 : QSet) variable (alpha0 : Set.Ioc (Real.sqrt qf) (constantStepSchemeIIAlphaUpper qf)) noncomputable def constantStepSchemeIISimpleSet : ℕ → QSet × E × ℝ := Nat.rec (x0, (x0 : E), (alpha0 : ℝ)) (fun _ state ↦ constantStepSchemeIISimpleSetStep QSet hQ_closed hQ_convex f L qf state)

Definition 2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.7: a function belongs to the source-facing class 𝓕_L^{2,1} when it already lies in the chapter smooth-convex class 𝓕[L, p]¹¹ and is twice continuously differentiable. The textbook Euclidean class 𝓕_L^{2,1}(ℝⁿ) is the specialization p = normSeminorm ℝ E.

open scoped SmoothConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] [FiniteDimensional ℝ E] variable {p : Seminorm ℝ E} [Seminorm.IsNorm p] {L : NNReal} {f : E → ℝ} abbrev ConvexC2SeminormSmooth (p : Seminorm ℝ E) [Seminorm.IsNorm p] (L : NNReal) (f : E → ℝ) : Prop := f ∈ 𝓕[L, p]¹¹ ∧ ContDiff ℝ 2 f

Lemma 2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.7: if each iterate value is bounded above by the minimum of phi k, and the estimating functions phi k are bounded above by the canonical affine model lineMap f (phi 0) (lam k), then the optimality gap at stage k lies in the interval [0, lambda_k * (phi0 x* - f x*)]. The source chapter applies this to functions on ℝⁿ, but the proof is purely pointwise and therefore lives on an arbitrary domain X.

open AffineMap variable {X : Type*} {f : X → ℝ} {phi : ℕ → X → ℝ} {lam : ℕ → ℝ} variable (xStar : X) (phiStar : ℕ → ℝ) (x : ℕ → X) lemma estimatingSequence_gap_mem_Icc (hmin : IsMinOn f Set.univ xStar) (hphiUpper : ∀ k, phi k ≤ lineMap f (phi 0) (lam k)) (hphiStar : ∀ k, IsLeast (Set.range (phi k)) (phiStar k)) (hx : ∀ k, f (x k) ≤ phiStar k) (k : ℕ) : f (x k) - f xStar ∈ Set.Icc 0 (lam k * (phi 0 xStar - f xStar))

Proposition 2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.7: for μ > 0 and 1 ≤ Q_f, a point x* minimizes the quadratic lower-bound objective on ℓ₂ exactly when its gradient vanishes.

open scoped Gradient lp StrongConvexSmooth
local notation "ℝ∞" => ℓ²(ℕ, ℝ)
local notation "I∞" => ContinuousLinearMap.id ℝ ℝ∞
local notation "e1" => (lp.single 2 0 (1 : ℝ) : ℝ∞)
theorem nesterovLowerBoundOperatorObjective_isMinOn_iff_gradient_eq_zero
    (μ Q_f : ℝ) (hμ : 0 < μ) (hQf : 1 ≤ Q_f) (xStar : ℝ∞) :
    IsMinOn (nesterovLowerBoundOperatorObjective μ Q_f) Set.univ xStar ↔
      ∇ (nesterovLowerBoundOperatorObjective μ Q_f) xStar = 0

Theorem 2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.7: if the k-th iterate lies in the stage set 𝓛_k, the terminal objective f_p agrees on 𝓛_k with the stage objective f_k, and f_k^* is the minimum value of f_k on 𝓛_k, then f_p (x_k) ≥ f_k^*.

universe u v variable {E : Type u} {β : Type v} variable [Preorder β] variable (p : ℕ) (𝓛 : ℕ → Set E) (f : ℕ → E → β) (x : ℕ → E) (fStar : ℕ → β) variable (hx_mem : ∀ ⦃k : ℕ⦄, k ≤ p → x k ∈ 𝓛 k) variable (hagree : ∀ ⦃k : ℕ⦄, k ≤ p → (𝓛 k).EqOn (f p) (f k)) theorem agreeing_family_value_ge_level_minimum (hx_mem : ∀ ⦃k : ℕ⦄, k ≤ p → x k ∈ 𝓛 k) (hagree : ∀ ⦃k : ℕ⦄, k ≤ p → (𝓛 k).EqOn (f p) (f k)) (hmin : ∀ ⦃k : ℕ⦄, k ≤ p → IsLeast (f k '' 𝓛 k) (fStar k)) {k : ℕ} (hk : k ≤ p) : f p (x k) ≥ fStar k

Algorithm 2.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.8: the constant-step minimax gradient method started from the feasible point x₀ and recursively updated by the feasible step xₖ₊₁ = xₖ - h • g_f(xₖ; L) = xₖ + hL • (x_f(xₖ; L) - xₖ), under the admissible bound h ≤ 1 / L. The sequence lives directly in the feasible-set subtype Q.

open scoped MaxTypeStep
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι]
variable
    (Q : Set E)
    (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q)
    (fi : ι → E → ℝ)
noncomputable def constantStepMinimaxGradientMethod
    (L : NNRealˣ)
    (x0 : Q)
    (h : NNRealˣ)
    (hh : (h : ℝ) ≤ 1 / (L : ℝ)) :
    ℕ → Q

Definition 2.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.8: the smooth convex first-order black-box class on a real finite-dimensional inner-product space E at smoothness constant L and accuracy ε. Its model is the subtype of smooth convex objectives f ∈ 𝓕[L, p]¹¹, its oracle returns the value-gradient reply (f x, ∇ f x), and its stopping criterion accepts exactly those pairs (f, x̄) for which x̄ is an ε-approximate minimizer of the canonical unconstrained Chapter 1 problem attached to f. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient SmoothConvex universe u variable (E : Type u) [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable [FiniteDimensional ℝ E] local notation "p" => normSeminorm ℝ E local notation "SmoothObjective[" L "]" => { f : E → ℝ // f ∈ 𝓕[L, p]¹¹ } variable (L : NNReal) (ε : ℝ) def smoothConvexProblemClass : BlackBoxOptimizationProblemClass E (ℝ × E) (SmoothObjective[L] × E)

Lemma 2.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.8: if f is differentiable at the sampled points y_k, is μ-strongly convex on the ambient real inner-product space E, the coefficients satisfy 0 ≤ α_k ≤ 1, and the canonical weight sequence Real.toNNReal ∘ estimatingWeight α tends to 0, then the recursively defined pair (φ_k, λ_k) is an estimating sequence for f. The smooth convex case is the specialization μ = 0; the textbook assumptions 0 < α_k < 1 and divergence of the partial sums are one sufficient way to obtain the stated weight-limit hypothesis.

open AffineMap open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem strongConvexEstimatingFunction_isEstimatingSequence {μ : ℝ} {f : E → ℝ} (hf_strong : StrongConvexOn Set.univ μ f) (φ₀ : E → ℝ) (y : ℕ → E) (α : ℕ → ℝ) (hf_grad : ∀ k, HasGradientAt f (∇ f (y k)) (y k)) (hα : ∀ k, α k ∈ Set.Icc (0 : ℝ) 1) (hweight_tendsto_zero : Filter.Tendsto (Real.toNNReal ∘ estimatingWeight α) Filter.atTop (nhds 0)) : IsEstimatingSequence f (strongConvexEstimatingFunction μ f φ₀ y α) (Real.toNNReal ∘ estimatingWeight α)

Proposition 2.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.8: on the monotonicity range 0 ≤ α ≤ 2 / L, the objective values along the constant-step gradient-method trajectory form an antitone sequence. The source range 0 < α ≤ 2 / L is a special case, and the textbook ℝⁿ statement is recovered by specializing E to EuclideanSpace ℝ (Fin n).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) {L : NNReal} {α : ℝ} (x0 : E) variable (hf_C1 : ContDiff ℝ 1 f) (hgrad : LipschitzWith L (∇ f)) (hα_nonneg : 0 ≤ α) (hα_le : α ≤ 2 / (L : ℝ)) local notation "traj" => gradientMethod (fun _ ↦ α) f x0 include hf_C1 hgrad hα_nonneg hα_le theorem gradientMethod_value_antitone_of_constant_stepsize : Antitone (fun k ↦ f (traj k))

Theorem 2.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.8: for every iteration index k with 1 ≤ k ≤ (n - 1) / 2 and every initial point x₀ ∈ ℝⁿ, there exists an objective f ∈ 𝓕_L^{1,1}(ℝⁿ) together with a global minimizer x*, such that every first-order iterative method satisfying the span condition has its k-th iterate satisfy the lower bounds on objective error and squared distance to x*.

open Finset open scoped Gradient SmoothConvex variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "p" => normSeminorm ℝ E open scoped CoordinateSubspace theorem exists_smoothConvexObjective_with_firstOrder_lower_bound (L : NNReal) {k : ℕ} (hk₁ : 1 ≤ k) (hk₂ : k ≤ (n - 1) / 2) (x0 : E) : ∃ f : E → ℝ, ∃ xStar : E, f ∈ (𝓕[L, p]¹¹ : Set (E → ℝ)) ∧ IsMinOn f Set.univ xStar ∧ ∀ method : (E → ℝ) → E → ℕ → E, SatisfiesSpanCondition method → let xk := method f x0 k f xk - f xStar ≥ (3 * (L : ℝ) * ‖x0 - xStar‖ ^ 2) / (32 * ((k + 1 : ℝ) ^ 2)) ∧ ‖xk - xStar‖ ^ 2 ≥ (1 / 8 : ℝ) * ‖x0 - xStar‖ ^ 2

Algorithm 2.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.9: for a smooth minimax problem, a positive step parameter L, an initial feasible point x0, and an admissible source parameter α₀ ∈ (√q[μ, L], constantStepSchemeIIAlphaUpper q[μ, L]], the recursive minimax trajectory (x_k, y_k, α_k) starts from (x₀, y₀, α₀) = (x0, x0, α₀) and applies the canonical exact max-type step x_{k+1} = x_f(y_k; L), the scheme-II quadratic scalar update for α_{k+1}, and the textbook momentum formula for y_{k+1}.

open scoped MaxTypeStep StrongConvexSmooth
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι] {μ L : ℝ}

-- Route correction: `Definition_2_38.olean` is currently unavailable, but Algorithm 2.9 only
-- uses the minimax owner data and its affine-approximation bridge. Reconstruct that minimal API
-- here from earlier chapter dependencies so the target file remains dependency-closed.
variable (problem : SmoothMinimaxProblem E ι μ L) (hL : 0 < L)
local notation "qf" => q[μ, L]
local notation "αRange" => Set.Ioc (Real.sqrt qf) (constantStepSchemeIIAlphaUpper qf)
local notation "Q" => problem.feasibleSet
local notation "γL" => (Units.mk0 (Real.toNNReal L) (by positivity) : NNRealˣ)
noncomputable def constantStepSchemeIIMinimax
    (problem : SmoothMinimaxProblem E ι μ L) (hL : 0 < L)
    (x0 : problem.feasibleSet) (alpha0 : αRange) :
    ℕ → problem.feasibleSet × E × ℝ

Definition 2.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.9: a first-order iterate family method satisfies the span condition when, for every C¹ objective f, it starts from the prescribed initial point and every iterate x_k with k ≥ 1 lies in the affine translate by x₀ of the linear span of the earlier gradients ∇ f(x₀), …, ∇ f(x_{k-1}).

open scoped Gradient variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def SatisfiesSpanCondition (method : (E → ℝ) → E → ℕ → E) : Prop := ∀ (f : E → ℝ) (_ : ContDiff ℝ 1 f) (x0 : E) (k : ℕ), method f x0 k ∈ gradientSpanSearchSpace method f x0 k

Lemma 2.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.9: if each successor curvature γ_{k+1} is nonzero, then the strong-convex estimating sequence from Lemma_2_8 stays in centered quadratic form. Starting from the centered quadratic model quadraticallyRegularizedObjective (fun _ ↦ φ0Star) γ0 v0, every stage of strongConvexEstimatingFunction μ f ... y α is exactly the owner quadratic quadraticallyRegularizedObjective (fun _ ↦ φ_k^*) γ_k v_k, where φ_k^*, γ_k, and v_k are estimatingSequenceValue, estimatingSequenceCurvature, and estimatingSequenceCenter.

open AffineMap open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem estimatingSequence_eq_canonicalQuadratic (f : E → ℝ) (α : ℕ → ℝ) (y : ℕ → E) (μ φ0Star γ0 : ℝ) (v0 : E) (hγ : ∀ k, estimatingSequenceCurvature μ γ0 α (k + 1) ≠ 0) (k : ℕ) : strongConvexEstimatingFunction μ f (quadraticallyRegularizedObjective (fun _ ↦ φ0Star) γ0 v0) y α k = quadraticallyRegularizedObjective (fun _ ↦ estimatingSequenceValue f α y μ φ0Star γ0 v0 k) (estimatingSequenceCurvature μ γ0 α k) (estimatingSequenceCenter f α y μ γ0 v0 k)

Proposition 2.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.9 is a recall-only item in the Euclidean optimal-method recurrence domain. Primary domain: * the scalar coefficient law L * α_k^2 = (1 - α_k) γ_k + α_k μ Sampled owner-style declarations: * OptimalMethodRecurrence in Algorithm_2_2, which owns the recurrence data (x_k, y_k, v_k, α_k, γ_k); * OptimalMethodRecurrence.alpha_equation in Algorithm_2_2, the primitive owner field for the scalar law recalled here; * constantStepSchemeIAlpha_equation in Algorithm_2_3, the same scalar law on the source-facing recursive Algorithm 2.3 quantities; * constantStepSchemeIToOptimalMethodRecurrence in Algorithm_2_3, the bridge packaging those recursive quantities into the owner recurrence abstraction. Best owner abstraction: * OptimalMethodRecurrence.alpha_equation Primitive data: * the parameters L, μ, x0, and gamma0 * the recurrence sequences x, y, v, alpha, and gamma Derived API: * the textbook ω-notation specialization obtained by substituting L = 1 / ω Source/core/bridge triage: * source-facing: Proposition 2.9's displayed scalar identity in textbook notation * core/canonical: OptimalMethodRecurrence.alpha_equation * bridge/view: the recursive Algorithm 2.3 realization and its conversion to OptimalMethodRecurrence This file therefore keeps the main entry as a direct recall of the owner coefficient law and introduces no local shell theorem.

recall OptimalMethodRecurrence.alpha_equation

Theorem 2.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.9 is the direct source-facing recall of the stationary-point quadratic-growth theorem for the strong-convexity class 𝓛^1[μ].

recall quadratic_growth_of_gradient_eq_zero

Algorithm 2.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.10: the recursive minimax trajectory started from (x₀, y₀) = (x0, x0) and updated by the canonical exact max-type step x_{k+1} = x_f(y_k; L) together with the fixed-momentum extrapolation y_{k+1} = x_{k+1} + β (x_{k+1} - x_k), where β = β[qf] = β[q[μ, L]].

open scoped MaxTypeStep StrongConvexSmooth
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι] {μ L : ℝ}
local notation "qf" => q[μ, L]
variable (problem : SmoothMinimaxProblem E ι μ L) (x0 : problem.feasibleSet) (hL : 0 < L)
local notation "Q" => problem.feasibleSet
local notation "γL" => (Units.mk0 (Real.toNNReal L) (by positivity) : NNRealˣ)
noncomputable def optimalMinimaxMethod
    (problem : SmoothMinimaxProblem E ι μ L) (x0 : problem.feasibleSet) (hL : 0 < L) :
    ℕ → problem.feasibleSet × E

Definition 2.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.10: for fixed L and k : Fin n, the textbook hard instance with one-based index k.1 + 1 ∈ {1, ..., n} is the quadratic objective on ℝⁿ obtained by applying smoothLowerBoundFunction L (Nat.succPNat k.1) to the first k.1 + 1 zero-based coordinates.

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) def quadraticHardInstanceFamily (L : ℝ) (k : Fin n) : E → ℝ := fun x ↦ smoothLowerBoundFunction L (Nat.succPNat k.1) (hardInstancePrefix k x)

Lemma 2.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.10: if an optimal-method recurrence has μ > 0 and initial curvature γ₀ ∈ (μ, 3L + μ], then its canonical estimating-sequence weight λₖ = method.weight k is bounded above by the stated hyperbolic expression, and that hyperbolic bound is itself bounded above by 4L / ((γ₀ - μ) (k + 1)^2).

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] namespace OptimalMethodRecurrence variable {f : E → ℝ} {L μ gamma0 : ℝ} {x0 : E} open Real open scoped StrongConvexSmooth local notation "qf" => q[μ, L] theorem weight_bounds (method : OptimalMethodRecurrence f L μ x0 gamma0) (hμ : 0 < μ) (hgamma0 : gamma0 ∈ Set.Ioc μ (3 * L + μ)) (k : ℕ) : let t := ((k + 1 : ℝ) * Real.sqrt q[μ, L]) / 2 let hyperbolicBound := 4 * μ / ((gamma0 - μ) * (Real.exp t - Real.exp (-t)) ^ (2 : ℕ)) method.weight k ≤ hyperbolicBound ∧ hyperbolicBound ≤ 4 * L / ((gamma0 - μ) * (k + 1 : ℝ) ^ (2 : ℕ))

Proposition 2.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.10: for a smooth convex objective, every type-II recurrence specialized to q_f = 0, α₀ = 1, and the exact gradient step x_{k+1} = y_k - (1 / L) ∇ f(y_k) satisfies the textbook quadratic function-value bound. This is the owner-abstraction form of the proposition: the textbook sequence t_k is the derived reciprocal t_k = 1 / α_k, and the iterate sequence is the owner field scheme.x, equivalently the coercion scheme : ℕ → E.

open scoped Gradient SmoothConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] local notation "p" => normSeminorm ℝ E namespace ConstantStepSchemeIIRecurrence variable {L : NNReal} variable {f : E → ℝ} variable {x0 xStar : E} variable (scheme : _root_.ConstantStepSchemeIIRecurrence E E f (L : ℝ) 0 x0 1) local notation "t" => fun k : ℕ ↦ 1 / scheme.alpha k theorem objective_gap_le_quadratic_rate (hconvex : ConvexOn ℝ Set.univ f) (hcontDiff : ContDiff ℝ 1 f) (hgrad_lipschitz : LipschitzWith L (∇ f)) (hxStar : IsMinOn f Set.univ xStar) (k : ℕ) : f (scheme.x k) - f xStar ≤ (8 * (L : ℝ) * ‖scheme.x 0 - xStar‖ ^ (2 : ℕ)) / (3 * (k + 1 : ℝ) ^ (2 : ℕ))

Theorem 2.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.10 on the canonical Hilbert-space owner layer: on a convex set Q, a differentiable function f is μ-strongly convex exactly when either of the two standard source-facing bridges holds, namely the strong gradient-monotonicity inequality or the quadratic Jensen inequality. The textbook Euclidean C¹ theorem is a direct specialization.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ : ℝ} {Q : Set E} {f : E → ℝ} local notation "gradQ" => gradientWithin f Q theorem strongConvexOn_tfae (hQ : Convex ℝ Q) (hf_diff : DifferentiableOn ℝ f Q) : List.TFAE [ StrongConvexOn Q μ f , ∀ ⦃x y : E⦄ (_ : x ∈ Q) (_ : y ∈ Q), μ * ‖x - y‖ ^ (2 : ℕ) ≤ inner ℝ (gradQ x - gradQ y) (x - y) , ∀ ⦃x y : E⦄ (_ : x ∈ Q) (_ : y ∈ Q) ⦃α : ℝ⦄ (_ : α ∈ Set.Icc (0 : ℝ) 1), f (α • x + (1 - α) • y) + α * (1 - α) * (μ / 2) * ‖x - y‖ ^ (2 : ℕ) ≤ α * f x + (1 - α) * f y ]

Algorithm 2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 2.11: the Chapter 2 constrained minimization method with the textbook outer recursion x_{k+1} = x_f(t_k; x_{k,j*(k)}; L) and t_{k+1} = t^*(x_{k,j(k)}, t_k). The source-facing owner is the recursive outer trajectory itself, while Step 1(a) existence is an explicit hypothesis rather than packaged data.

open scoped SmoothFunctionalConstraintsMinimizationProblem.ConstrainedStep
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [FiniteDimensional ℝ E]
variable {m : ℕ} {μ L : ℝ}
variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L)
local notation "parametricProblem" => problem.toParametricSmoothMinimaxProblem
local notation "modelValue" => problem.regularizedModelValue
noncomputable def ConstrainedMinimizationMethod
    (κ t0 : ℝ) (x0 : problem.ambientSet) (hL : 0 < L)
    (hStep1a :
      ∀ xBar : problem.ambientSet, ∀ t : ℝ, ∃ j, step1aAt problem κ xBar t hL j) :
    ℕ → problem.ambientSet × ℝ

Definition 2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.11: for the textbook lower-bound quadratic f_k, the Chapter 1 Hessian matrix is the constant tridiagonal matrix (L / 4) A_k.

open Matrix open scoped Gradient theorem smoothLowerBoundFunction_hessian_eq_tridiagonal (L : ℝ) (k : ℕ+) (x : EuclideanSpace ℝ (Fin k)) : ∇² (smoothLowerBoundFunction L k) x = (L / 4) • pathTridiagonalMatrix k

Lemma 2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.11 is a recall-only source-facing item in the convex-sublevel-set domain. Sampled owner-style declarations: * ConvexOn.convex_le, the owner theorem for convex sublevel sets on an ambient set; * ConvexOn.convex_lt, the open-sublevel analogue in the same owner API; * Convex.quasiconvexOn_of_convex_le, showing that convex sublevel sets are the canonical route to quasiconvexity; * convex_euclidean_posSemidef_quadratic_sublevelSet in Chap02/Exmaple_2_18_1.lean, a downstream chapter use that already calls ConvexOn.convex_le directly. Best owner abstraction: * ConvexOn ℝ Set.univ f. Primitive data: * a function f : ℝⁿ → ℝ; * the owner hypothesis ConvexOn ℝ Set.univ f. Derived API: * convexity of the sublevel set {x | f x ≤ β}. Source/core/bridge triage: * source-facing: the textbook whole-space sublevel-set convexity lemma; * core/canonical: the owner predicate ConvexOn ℝ Set.univ f; * bridge/view: ConvexOn.convex_le, which produces the sublevel-set convexity statement from the owner predicate. So this file stays as direct canonical recall/use. It intentionally adds no parallel wrapper theorem, and downstream files should use ConvexOn.convex_le directly.

recall ConvexOn.convex_le

Proposition 2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.11 is recall-only. Primary domain: - type-II accelerated Euclidean momentum recurrences. Sampled owner-style declarations: - OptimalMethodRecurrence.y_eq in Algorithm_2_2, the heavier interpolation formula from which the type-II momentum update is derived; - OptimalMethodRecurrence.gamma_succ_eq_L_mul_sq in Algorithm_2_2, the heavier curvature identity used in the same elimination; - constantStepSchemeIIAlpha_succ_equation in Algorithm_2_4, the source-facing scalar recurrence for Algorithm 2.4; - constantStepSchemeIIY_succ in Algorithm_2_4, the source-facing momentum update y_{k+1} = x_{k+1} + β_k (x_{k+1} - x_k). Best owner abstraction: - the recursive source-facing trajectory constantStepSchemeII for Proposition 2.11 itself; - OptimalMethodRecurrence only as upstream bridge/provenance for the eliminated auxiliary parameters. Primitive data: - the recursive trajectory constantStepSchemeII together with constantStepSchemeIIAlpha_succ_equation and constantStepSchemeIIY_succ. Derived API: - the textbook coefficient β_k; - the derivation from the heavier optimal-method owner via y_eq and gamma_succ_eq_L_mul_sq. Source/core/bridge triage: - source-facing: Proposition 2.11's displayed type-II scalar and momentum formulas; - core/canonical: ConstantStepSchemeIIMomentumRecurrence; - bridge/view: constantStepSchemeIIToMomentumRecurrence, together with elimination of the heavier optimal-method fields v, γ via y_eq and gamma_succ_eq_L_mul_sq. This file therefore recalls the source-facing Algorithm 2.4 theorems directly. The generic momentum owner remains background provenance available through constantStepSchemeIIToMomentumRecurrence, but the main labeled entry stays on the textbook recursive trajectory. This file intentionally adds no local estimatingSequenceMomentumCoefficient wrapper and no parallel proposition-specific momentum theorem.

recall constantStepSchemeIIAlpha_succ_equation

Text 2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.11: for every k : Fin n, representing the textbook index k.1 + 1 ∈ {1, ..., n}, the Hessian matrix of the hard instance f_k satisfies 0 ≤ ∇² f_k(x) ≤ L I_n for every x ∈ ℝⁿ.

open scoped Gradient MatrixOrder SmoothConvex variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ local notation "p" => normSeminorm ℝ E theorem quadraticHardInstanceFamily_hessian_loewner_bounds (L : NNReal) (k : Fin n) (x : E) : 0 ≤ ∇² (quadraticHardInstanceFamily (L : ℝ) k) x ∧ ∇² (quadraticHardInstanceFamily (L : ℝ) k) x ≤ (L : ℝ) • (1 : Mat)

Theorem 2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.11 (1): if a μ-strongly convex function has gradients at x and y, then its value at y is bounded above by the tangent model at x plus a quadratic term in the dual norm of the gradient difference. Here strong convexity is the whole-space specialization StrongConvexOnWith p μ Set.univ f.

open scoped Gradient SeminormDualNorm universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] namespace StrongConvexOnWith variable [FiniteDimensional ℝ E] variable {p : Seminorm ℝ E} [Seminorm.IsNorm p] {μ : ℝ} {f : E → ℝ} theorem tangent_upper_bound_by_dualNorm (hf_strong : StrongConvexOnWith p μ Set.univ f) (x y : E) (_hx : DifferentiableAt ℝ f x) (hy : DifferentiableAt ℝ f y) : f y ≤ f x + inner ℝ (∇ f x) (y - x) + (1 / (2 * μ)) * ‖∇ f x - ∇ f y‖[p,*] ^ 2

Definition 2.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.12 is a source-facing recall in the finite-dimensional linear-algebra domain of coordinate subspaces of ℝⁿ. Primary domain: - linear-algebraic coordinate subspaces in Euclidean space. Sampled owner-style declarations: - coordinateSubspace k n, the chapter's canonical Submodule owner for ℝ^{k,n}; - mem_coordinateSubspace_iff, the coordinatewise derived membership criterion; - the scoped notation ℝ^{k,n}, the source-facing surface for that owner; - Submodule.comap, the canonical way to realize a subspace by pulling back a product-side submodule along a linear equivalence; - Submodule.pi, the canonical product-side owner used to encode coordinatewise vanishing. Best owner abstraction: - coordinateSubspace k n : Submodule ℝ (EuclideanSpace ℝ (Fin n)) Primitive data: - the cut index k; - the ambient dimension n. Derived API: - mem_coordinateSubspace_iff, which rewrites membership in the owner submodule into the textbook coordinate-vanishing condition. - the notation ℝ^{k,n}, which exposes the source-facing surface while keeping coordinateSubspace k n as the raw owner. Source/core/bridge triage: - source-facing: the textbook coordinate subspace ℝ^{k,n} ⊆ ℝⁿ; - core/canonical: the owner submodule coordinateSubspace k n; - bridge/view: the coordinatewise criterion mem_coordinateSubspace_iff. This recall file therefore uses the upstream owner declaration directly and introduces no parallel wrapper or duplicate local definition. It also reuses the upstream notation ℝ^{k,n} rather than adding a second alias layer.

open scoped CoordinateSubspace
recall coordinateSubspace (k n : ℕ) : Submodule ℝ (EuclideanSpace ℝ (Fin n))

Lemma 2.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.12 is a recall-only item in the epigraph convexity domain for real-valued convex functions. Primary domain: - convexity of epigraphs of convex functions. Sampled owner-style declarations: - ConvexOn - ConvexOn.convex_epigraph - convexOn_iff_convex_epigraph - the later Euclidean specialization in Chap03/Theorem_3_1_2 Best owner abstraction: - ConvexOn.convex_epigraph Primitive data: - a function f - the owner hypothesis hf : ConvexOn 𝕜 s f Derived API: - convexity of the epigraph {p | p.1 ∈ s ∧ f p.1 ≤ p.2} - in the textbook whole-space specialization, simplification of p.1 ∈ Set.univ Source/core/bridge triage: - source-facing: Lemma 2.12 as the whole-space epigraph convexity consequence - core/canonical: ConvexOn.convex_epigraph - bridge/view: specialization to s = Set.univ This file therefore keeps no parallel whole-space wrapper theorem and recalls the canonical owner declaration directly.

recall ConvexOn.convex_epigraph

Proposition 2.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.12: if f : E → ℝ belongs to the strongly convex smooth class with parameters μ and L, xStar is a minimizer of f, and x_k is generated by constant step scheme III with reciprocal condition number q_f = q[μ, L] and momentum coefficient β[q[μ, L]] = (1 - √q[μ, L]) / (1 + √q[μ, L]), then f(x_k) - f(xStar) ≤ ((L + μ) / 2) ‖x₀ - xStar‖² exp(-k √q[μ, L]) for every k ≥ 0.

open AffineMap open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L : ℝ} {f : E → ℝ} (hf : IsStrongConvexSmoothObjective μ L f) variable {xStar x0 : E} (hxStar : IsMinOn f Set.univ xStar) variable (scheme : ConstantStepSchemeIII f L (q[μ, L]) x0) local notation "qf" => q[μ, L] local notation "a" => Real.sqrt qf local notation "alpha" => fun _ : ℕ ↦ a local notation "phi" => strongConvexEstimatingFunction μ f (quadraticallyRegularizedObjective (fun _ : E ↦ f x0) μ x0) scheme.y alpha local notation "phiStar" => estimatingSequenceValue f alpha scheme.y μ (f x0) μ x0 local notation "center" => estimatingSequenceCenter f alpha scheme.y μ μ x0 include hf include hf include hf hxStar omit hf hxStar include hf hxStar theorem constantStepSchemeIII_objective_gap_le_exponential_rate (k : ℕ) : f (scheme k) - f xStar ≤ ((L + μ) / 2) * ‖x0 - xStar‖ ^ (2 : ℕ) * Real.exp (-(k : ℝ) * Real.sqrt (q[μ, L]))

Theorem 2.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.12 on the canonical owner layer: for a convex set in a real Hilbert space, a function that is continuous on Q and C² on interior Q satisfies the strong-convexity tangent inequality with parameter μ if and only if its Hessian quadratic form is bounded below by μ ‖h‖²_p at every interior point. The theorem stays at the arbitrary-seminorm owner layer of Definition_2_14; the textbook ℝⁿ statement is the finite-dimensional specialization.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (p : Seminorm ℝ E) variable {μ : ℝ} {U Q : Set E} {f : E → ℝ} theorem interior_lower_tangent_quadratic_iff_hessian_quadratic_form_lower_bound (μ : ℝ) (hQ_conv : Convex ℝ Q) (hf_cont : ContinuousOn f Q) (hf_C2 : ContDiffOn ℝ 2 f (interior Q)) : (∀ x : E, x ∈ interior Q → ∀ y : E, y ∈ Q → f y ≥ f x + inner ℝ (∇ f x) (y - x) + (μ / 2) * (p (y - x)) ^ 2) ↔ ∀ x ∈ interior Q, ∀ h : E, μ * (p h) ^ 2 ≤ inner ℝ (hessian f x h) h

Definition 2.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.13: the textbook whole-space strong-convexity condition with respect to p is the chapter owner predicate StrongConvexOnWith p μ Set.univ f.

open scoped Gradient StrongConvex universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] variable {p : Seminorm ℝ E} {μ : ℝ} {f : E → ℝ} #check (StrongConvexOnWith p μ Set.univ f : Prop)

Lemma 2.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.13: if p is a projection point of x₀ onto a convex set Q in a real inner product space, then the displacement p - x₀ has nonnegative inner product with every feasible direction x - p based at p.

open Metric universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] namespace IsProjectionPointOn theorem inner_sub_nonneg {Q : Set E} (hQ_convex : Convex ℝ Q) {x₀ p x : E} (hp : IsProjectionPointOn Q x₀ p) (hx : x ∈ Q) : 0 ≤ inner ℝ (p - x₀) (x - p)

Proposition 2.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.13: at a minimizer of the quadratically regularized objective x ↦ f x + (δ / 2) ‖x - x₀‖², if f is differentiable at the minimizer then the gradient of f balances the centered quadratic penalty: ∇ f xδStar + δ • (xδStar - x0) = 0. The source proposition is stated for f : ℝⁿ → ℝ, but the proof uses only the canonical real inner-product-space gradient calculus. Convexity of f and positivity of δ belong to the ambient optimization setting, while the displayed first-order identity itself uses only differentiability at the minimizer and the minimizing hypothesis.

open scoped Gradient variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem gradient_add_quadratic_regularization_eq_zero_of_isMinOn (f : E → ℝ) (δ : ℝ) (x0 xδStar : E) (hf_diff : DifferentiableAt ℝ f xδStar) (hxδStar : IsMinOn (quadraticallyRegularizedObjective f δ x0) Set.univ xδStar) : ∇ f xδStar + δ • (xδStar - x0) = 0

Text 2.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.13: on the leading-coordinate subspace ℝ^{k.1 + 1,n}, a point is stationary for quadraticHardInstanceFamily L k if and only if it is the canonical affine-profile point whose coordinates are given by quadraticHardInstanceStationaryPoint_apply; equivalently, the equation ∇ f_k(x) = A_k x - e₁ = 0 has the unique solution described in the text.

variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
open scoped Gradient
open scoped CoordinateSubspace
theorem hasGradientAt_zero_iff_eq_quadraticHardInstanceStationaryPoint_of_mem_coordinateSubspace
    {L : ℝ} (hL : L ≠ 0) (k : Fin n) {x : E} (hx_mem : x ∈ ℝ^{k.1 + 1,n}) :
    HasGradientAt (quadraticHardInstanceFamily L k) 0 x ↔
      x = quadraticHardInstanceStationaryPoint k

Theorem 2.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.13: a function in 𝓢^{1,1}_{μ,L} satisfies the strengthened secant inequality ⟪∇ f x - ∇ f y, x - y⟫ ≥ (μ L / (μ + L)) ‖x - y‖² + (1 / (μ + L)) ‖∇ f x - ∇ f y‖² for all x, y.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] namespace IsStrongConvexSmoothObjective variable {μ L : ℝ} {f : E → ℝ} theorem pairing_lower_bound (hf : IsStrongConvexSmoothObjective μ L f) (x y : E) : inner ℝ (∇ f x - ∇ f y) (x - y) ≥ (μ * L / (μ + L)) * ‖x - y‖ ^ 2 + (1 / (μ + L)) * ‖∇ f x - ∇ f y‖ ^ 2

Definition 2.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.14 in owner form: a function on a convex set Q is μ-strongly convex with respect to a seminorm p when μ > 0 and it satisfies the intrinsic strong-convexity inequality f (a • x + b • y) ≤ a • f x + b • f y - a * b * (μ / 2) * p (x - y)^2 for all x, y ∈ Q and all nonnegative a, b with a + b = 1. The tangent-plane inequality is kept as a companion theorem under an explicit ambient differentiability hypothesis. The stronger assumption [Seminorm.IsNorm p] is imposed only on the later norm-comparison bridge theorems.

open scoped Gradient universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] def StrongConvexOnWith (p : Seminorm ℝ E) (μ : ℝ) (Q : Set E) (f : E → ℝ) : Prop := Convex ℝ Q ∧ 0 < μ ∧ ∀ ⦃x⦄, x ∈ Q → ∀ ⦃y⦄, y ∈ Q → ∀ ⦃a b : ℝ⦄, 0 ≤ a → 0 ≤ b → a + b = 1 → f (a • x + b • y) ≤ a • f x + b • f y - a * b * ((μ / 2) * (p (x - y)) ^ (2 : ℕ))

Lemma 2.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.14: every feasible point of a convex set in a real inner product space lies no closer to an ambient point y than a projection point p does, with the usual Pythagorean squared-distance decomposition.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] namespace IsProjectionPointOn theorem pythagorean_ineq {Q : Set E} (hQ_convex : Convex ℝ Q) {y p x : E} (hp : IsProjectionPointOn Q y p) (hx : x ∈ Q) : ‖x - p‖ ^ 2 + ‖p - y‖ ^ 2 ≤ ‖x - y‖ ^ 2

Proposition 2.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.14: if xStar minimizes a convex function f on a real inner-product space and xDeltaStar minimizes the quadratically regularized objective x ↦ f x + (δ / 2) ‖x - x₀‖² with δ > 0, then the regularized minimizer satisfies the squared distance contraction ‖xDeltaStar - x₀‖² + ‖xDeltaStar - xStar‖² ≤ ‖x₀ - xStar‖². The textbook ℝⁿ statement is the Euclidean specialization.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem regularized_minimizer_sqdist_add_sqdist_le_sqdist (f : E → ℝ) (hf_conv : ConvexOn ℝ Set.univ f) (xStar : E) (hxStar : IsMinOn f Set.univ xStar) (x0 xDeltaStar : E) {δ : ℝ} (hδ : 0 < δ) (hxDeltaStar : IsMinOn (quadraticallyRegularizedObjective f δ x0) Set.univ xDeltaStar) : ‖xDeltaStar - x0‖ ^ 2 + ‖xDeltaStar - xStar‖ ^ 2 ≤ ‖x0 - xStar‖ ^ 2

Text 2.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.14: for the canonical smoothness parameter L : NNReal, the optimal value of the quadratic hard-instance objective f_k is ((L : ℝ) / 8) * (-1 + 1 / (k + 1)); in the file's zero-based Fin indexing, k : Fin n represents the textbook index k + 1, so the denominator becomes k.1 + 2.

open scoped SmoothConvex
variable {n : ℕ}
theorem quadraticHardInstanceFamily_optimal_value
    (L : NNReal) (k : Fin n) :
    (SetConstrainedMinimizationProblem.mk Set.univ
      (quadraticHardInstanceFamily (L : ℝ) k)).optimalValue =
      ((((L : ℝ) / 8) * (-1 + 1 / (((k.1 + 2 : ℕ) : ℝ))) : ℝ) : EReal)

Theorem 2.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.14: for every initial point x₀ ∈ ℝ∞, every μ > 0, and every condition number Q_f > 1, setting L := μ Q_f and q := (√Q_f - 1) / (√Q_f + 1), there exists a function f ∈ 𝓢^{∞,1}_{μ,L}(ℝ∞) together with a minimizing point x*; uniqueness of the minimizer is a derived consequence of strong convexity, so the statement is expressed with IsMinOn rather than a separate uniqueness wrapper. Every first-order method satisfying Assumption 2.1.4 obeys the geometric lower bounds ‖x_k - x*‖² ≥ q^(2k) ‖x₀ - x*‖² and f(x_k) - f(x*) ≥ (μ / 2) q^(2k) ‖x₀ - x*‖² for all k ≥ 0.

open scoped Gradient lp StrongConvexSmooth
local notation "ℝ∞" => ℓ²(ℕ, ℝ)
local notation "I∞" => ContinuousLinearMap.id ℝ ℝ∞
local notation "e1" => (lp.single 2 0 (1 : ℝ) : ℝ∞)
theorem exists_rinfty_hard_instance_with_firstOrder_lower_bound
    (x0 : ℝ∞) (μ Qf : ℝ) (hμ : 0 < μ) (hQf : 1 < Qf) :
    let L := μ * Qf
    let q := (Real.sqrt Qf - 1) / (Real.sqrt Qf + 1)
    ∃ f : ℝ∞ → ℝ,
      ∃ xStar : ℝ∞,
          f ∈ 𝓢[μ, L]¹¹ ∧
          IsMinOn f Set.univ xStar ∧
          ∀ method : (ℝ∞ → ℝ) → ℝ∞ → ℕ → ℝ∞,
            SatisfiesSpanCondition method →
              ∀ k : ℕ,
                let xk := method f x0 k
                q ^ (2 * k) * ‖x0 - xStar‖ ^ (2 : ℕ) ≤ ‖xk - xStar‖ ^ (2 : ℕ) ∧
                  (μ / 2) * q ^ (2 * k) * ‖x0 - xStar‖ ^ (2 : ℕ) ≤
                    f xk - f xStar

Definition 2.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.15: on a convex set with nonempty interior in a complete real inner-product space, the intrinsic Hessian lower bound μ • id ≤ ∇² f(x) on interior Q is exactly mathlib's canonical strong-convexity predicate, under the standard μ > 0, continuity, and C² hypotheses.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ : ℝ} {Q : Set E} {f : E → ℝ} variable (hμ : 0 < μ) (hQ_conv : Convex ℝ Q) (hQ_int : (interior Q).Nonempty) variable (hf_cont : ContinuousOn f Q) (hf_C2 : ContDiffOn ℝ 2 f (interior Q)) -- Proof sketch: rewrite `μ • id ≤ H` as nonnegativity of `H - μ • id` using the Loewner order -- from `ContinuousLinearMap.le_def`, then use `ContinuousLinearMap.nonneg_iff_isPositive` and the -- self-adjointness of the Hessian of a `C²` real function to identify positivity of -- `H - μ • id` with nonnegativity of its quadratic form. Combine this intrinsic operator -- reformulation with `interior_lower_tangent_quadratic_iff_hessian_quadratic_form_lower_bound` -- and the ambient-norm bridge `strongConvexOnWith_normSeminorm_iff`. theorem strongConvexOn_iff_hessian_lower_bound (hμ : 0 < μ) (hQ_conv : Convex ℝ Q) (hQ_int : (interior Q).Nonempty) (hf_cont : ContinuousOn f Q) (hf_C2 : ContDiffOn ℝ 2 f (interior Q)) : StrongConvexOn Q μ f ↔ ∀ x ∈ interior Q, μ • (1 : E →L[ℝ] E) ≤ hessian f x

Lemma 2.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.15 on the canonical real Hilbert-space owner layer: the half squared distance to a convex set is a convex C¹ objective whose gradient is 1-Lipschitz in the ambient norm. The textbook Euclidean statement is the specialization to ℝⁿ.

open scoped Gradient SmoothConvex
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [FiniteDimensional ℝ E]
theorem halfSquaredDistance_mem_F11
    (Q : Set E) (hQ_convex : Convex ℝ Q) :
    Q.halfSquaredDistance ∈ 𝓕[1, normSeminorm ℝ E]¹¹

Proposition 2.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.15 (1): subtracting the nonnegative first-coordinate ray from Q gives exactly the open upper half-plane {x ∈ ℝ² | x₂ > 0}.

open Set open scoped Pointwise theorem reciprocalEpigraphOnPositiveRay_sub_nonnegativeFirstCoordinateRay : reciprocalEpigraphOnPositiveRay - nonnegativeFirstCoordinateRay = {x : ℝ × ℝ | 0 < x.2}

Text 2.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.15: the hard-instance stationary point \bar x_k, encoded by quadraticHardInstanceStationaryPoint k, satisfies ‖\bar x_k‖^2 ≤ (1 / 3) * (k + 1). In the file's zero-based Fin indexing, k : Fin n encodes the textbook index k + 1, so the right side becomes (1 / 3) * (k.1 + 2).

open Finset
variable {n : ℕ}
theorem quadraticHardInstanceStationaryPoint_sqNorm_le (k : Fin n) :
    ‖quadraticHardInstanceStationaryPoint k‖ ^ 2 ≤ (1 / 3 : ℝ) * (k.1 + 2)

Theorem 2.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.15 on the intrinsic real-Hilbert-space owner layer: if f is convex on the whole space, C¹, has L-Lipschitz gradient, xStar is a global minimizer of f, and 0 ≤ h ≤ 2 / L, then the gradient method with step size h satisfies the explicit sublinear objective-gap bound at every iterate. The textbook ℝⁿ formulation is recovered by the finite-dimensional Chapter 2 specialization theorem below. The source strict range 0 < h < 2 / L is a special case, and at the endpoints the correction factor h * (2 - L * h) vanishes.

open scoped Gradient SmoothConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] namespace ConvexC1SeminormSmooth variable {L : NNReal} {f : E → ℝ} variable [CompleteSpace E] theorem gradientMethod_objective_gap_le_explicit_rate (hconv : ConvexOn ℝ Set.univ f) (hf_C1 : ContDiff ℝ 1 f) (hgrad : LipschitzWith L (∇ f)) (xStar : E) (hxStar : IsMinOn f Set.univ xStar) (h : ℝ) (hh_nonneg : 0 ≤ h) (hh_le : h ≤ 2 / (L : ℝ)) (x0 : E) (k : ℕ) : f (gradientMethod (fun _ ↦ h) f x0 k) - f xStar ≤ (2 * (f x0 - f xStar) * ‖x0 - xStar‖ ^ (2 : ℕ)) / (2 * ‖x0 - xStar‖ ^ (2 : ℕ) + h * (2 - (L : ℝ) * h) * (k : ℝ) * (f x0 - f xStar))

Definition 2.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.16: the Euclidean source-facing class 𝓢[μ, L]¹¹ is equivalently the textbook combination of C¹ regularity, positive strong convexity modulus, and the whole-space strong gradient-monotonicity and gradient-Lipschitz estimates.

open scoped Gradient MatrixOrder StrongConvexSmooth variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ theorem mem_S11_iff_contDiff_and_gradient_strong_mono {μ L : ℝ} {f : E → ℝ} : f ∈ 𝓢[μ, L]¹¹ ↔ 0 < μ ∧ ContDiff ℝ 1 f ∧ (∀ x y : E, μ * ‖x - y‖ ^ (2 : ℕ) ≤ inner ℝ (∇ f x - ∇ f y) (x - y)) ∧ ∀ x y : E, ‖∇ f x - ∇ f y‖ ≤ L * ‖x - y‖

Lemma 2.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.16 on the real inner-product-space owner layer: for a differentiable function with L-Lipschitz gradient, the gradient step of size 1 / L decreases the objective by at least (1 / (2 * L)) * ‖∇ f x‖² at every point. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem gradient_step_value_descent_of_lipschitzGradient (f : E → ℝ) {L : ℝ} (hL : 0 < L) (hf : Differentiable ℝ f) (hgrad : LipschitzWith ⟨L, le_of_lt hL⟩ (∇ f)) (x : E) : f (x - (1 / L) • ∇ f x) ≤ f x - (1 / (2 * L)) * ‖∇ f x‖ ^ (2 : ℕ)

Proposition 2.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.16: the cone generated by the closed unit disk centered at (1, 0) is exactly the set of points in ℝ² with strictly positive first coordinate together with the origin.

open PointedCone (hull) open scoped Pointwise local notation "E" => EuclideanSpace ℝ (Fin 2) local notation "e₁" => EuclideanSpace.single (0 : Fin 2) (1 : ℝ) theorem cone_generated_by_Q1_eq_positive_first_coordinate_or_origin : (hull ℝ Q₁ : Set E) = {x : E | 0 < x 0} ∪ ({0} : Set E)

Text 2.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 2.16: The sum of the squares from 1 to k is bounded above by (k + 1)^3 / 3.

open Finset theorem sum_Icc_sq_le_cubic_third (k : ℕ) : (∑ i ∈ Icc 1 k, (i : ℚ) ^ 2) ≤ ((k + 1 : ℚ) ^ 3) / 3

Theorem 2.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.16: if f is convex on E, admits the ambient gradient ∇ f everywhere, that gradient is L-Lipschitz in the ambient norm, xStar is a global minimizer of f, L > 0, and x_k is the recursive textbook accelerated-gradient trajectory with x₀ = y₀ = x0, x_{k+1} = y_k - (1 / L) ∇ f(y_k), y_{k+1} = x_{k+1} + (k / (k + 3)) • (x_{k+1} - x_k), then the objective gap satisfies the quadratic rate f(x_k) - f(x*) ≤ 8 L ‖x₀ - x*‖² / (3 (k + 1)²). This keeps the textbook accelerated scheme as a recursive source-facing owner on the intrinsic real-Hilbert-space layer, rather than quantifying over arbitrary sequence data. The chapter notation f ∈ 𝓕[L, normSeminorm ℝ E]¹¹ is a finite-dimensional bridge to this intrinsic statement, not the main owner surface.

open scoped Gradient SmoothConvex
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
local notation "p" => normSeminorm ℝ E
variable {L : NNReal} {f : E → ℝ}
theorem nesterovAcceleratedGradient_objective_gap_le_quadratic_rate
    (hconvex : ConvexOn ℝ Set.univ f)
    (hgrad : ∀ x : E, HasGradientAt f (∇ f x) x)
    (hgrad_lipschitz : LipschitzWith L (∇ f))
    (xStar : E) (hxStar : IsMinOn f Set.univ xStar)
    (hL : 0 < L)
    (x0 : E)
    (k : ℕ) :
    f (nesterovAcceleratedGradientX f L x0 k) - f xStar ≤
      (8 * (L : ℝ) * ‖x0 - xStar‖ ^ (2 : ℕ)) /
        (3 * (k + 1 : ℝ) ^ (2 : ℕ))

Definition 2.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.17: relative to a chosen minimizer x* of an objective in 𝓢^{1,1}_{μ,L}, a point x̄ is an approximate solution with accuracy ε when both the objective gap f(x̄) - f(x*) and the squared distance ‖x̄ - x*‖² are at most ε. The textbook ℝⁿ version is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open scoped StrongConvexSmooth variable {μ L : ℝ} variable (f : E → ℝ) (xStar : E) variable (sameDataNear : (E → ℝ) → (E → ℝ) → E → Prop) def IsStrongConvexSmoothApproximateSolution (f : E → ℝ) (xStar : E) (ε : ℝ) (xBar : E) : Prop := f xBar - f xStar ≤ ε ∧ ‖xBar - xStar‖ ^ (2 : ℕ) ≤ ε

Lemma 2.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.17 on the intrinsic real-Hilbert-space smooth-convex owner layer: if f is convex on the whole space, admits the ambient gradient ∇ f everywhere, has L-Lipschitz gradient, and xStar is a global minimizer, then every point x satisfies (1 / L) ‖∇ f x‖² ≤ ⟪∇ f x, x - xStar⟫. The textbook ℝⁿ statement is recovered by the finite-dimensional specialization theorem below.

open scoped Gradient SmoothConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] namespace ConvexC1SeminormSmooth variable [CompleteSpace E] variable {L : NNReal} {f : E → ℝ} theorem gradient_pairing_with_minimizer_gap_ge_norm_sq_div (hconv : ConvexOn ℝ Set.univ f) (hgrad : ∀ x : E, HasGradientAt f (∇ f x) x) (hgrad_lipschitz : LipschitzWith L (∇ f)) {xStar : E} (hxStar : IsMinOn f Set.univ xStar) (x : E) : (1 / (L : ℝ)) * ‖∇ f x‖ ^ (2 : ℕ) ≤ inner ℝ (∇ f x) (x - xStar)

Proposition 2.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.17: the convex hull of {(0, 0)} ∪ Q equals the canonical cone hull of Q, where Q = reciprocalEpigraphOnPositiveRay.

open Set open PointedCone open scoped Pointwise local notation "Q" => reciprocalEpigraphOnPositiveRay theorem convexHull_zero_union_reciprocalEpigraphOnPositiveRay_eq_conicHull : convexHull ℝ (insert (0 : ℝ × ℝ) reciprocalEpigraphOnPositiveRay) = (hull ℝ reciprocalEpigraphOnPositiveRay : Set (ℝ × ℝ))

Theorem 2.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.17: if f : E → ℝ lies in the strongly convex smooth class 𝓢^{1,1}_{μ,L}, xStar is a minimizer of f, and 0 < h ≤ 2 / (μ + L), then the gradient-method iterates satisfy the geometric squared-distance contraction ‖x_k - xStar‖² ≤ (1 - 2 h μ L / (μ + L))^k ‖x₀ - xStar‖².

open scoped Gradient StrongConvexSmooth open HasGeometricRateOfConvergence universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L : ℝ} {f : E → ℝ} theorem gradientMethod_sqdist_le_geometric_rate (hf : f ∈ 𝓢[μ, L]¹¹) {xStar : E} (hxStar : IsMinOn f Set.univ xStar) (h : ℝ) (hh0 : 0 < h) (hh : h ≤ 2 / (μ + L)) (x0 : E) (k : ℕ) : ‖gradientMethod (fun _ ↦ h) f x0 k - xStar‖ ^ (2 : ℕ) ≤ (1 - (2 * h * μ * L) / (μ + L)) ^ k * ‖x0 - xStar‖ ^ (2 : ℕ)

Definition 2.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.18: the infinite tridiagonal operator A on ℓ₂(ℕ, ℝ) used in Nesterov's lower-bound construction.

open scoped BigOperators lp
local notation "ℝ∞" => ℓ²(ℕ, ℝ)
local notation "e1" => (lp.single 2 0 (1 : ℝ) : ℝ∞)
def nesterovLowerBoundTridiagonalOperator : ℝ∞ →L[ℝ] ℝ∞ :=
  ({ toFun := tridiagonalApply
     map_add' := tridiagonalApply_add
     map_smul' := tridiagonalApply_smul } : ℝ∞ →ₗ[ℝ] ℝ∞).mkContinuous 4
    tridiagonalApply_bound

Lemma 2.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.18 in the chapter notation surface: if each component of a finite max-type objective lies in 𝓢[μ, L]¹¹, then the max-type function satisfies the corresponding lower and upper quadratic bounds relative to its canonical affine approximation maxTypeAffineApproximation fi xBar.

open scoped Gradient StrongConvexSmooth universe u variable {ι : Type*} [Fintype ι] [Nonempty ι] variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem maxTypeObjective_quadratic_bounds_of_components_mem (fi : ι → E → ℝ) (μ L : ℝ) (hfi : ∀ i : ι, fi i ∈ 𝓢[μ, L]¹¹) (x xBar : E) : maxTypeObjective fi x ≥ maxTypeAffineApproximation fi xBar x + (μ / 2) * ‖x - xBar‖ ^ (2 : ℕ) ∧ maxTypeObjective fi x ≤ maxTypeAffineApproximation fi xBar x + (L / 2) * ‖x - xBar‖ ^ (2 : ℕ)

Proposition 2.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.18: the second-coordinate projection of reciprocalEpigraphOnPositiveRay is exactly the positive real half-line. The textbook region {(τ, x) | 0 < τ ∧ x ≥ 1 / τ} is already represented by this owner set.

open Set local notation "Q" => reciprocalEpigraphOnPositiveRay theorem snd_image_reciprocalEpigraphOnPositiveRay_eq_Ioi : Prod.snd '' Q = Ioi (0 : ℝ)

Theorem 2.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.18 on the intrinsic real-Hilbert-space owner layer: if f : E → ℝ lies in the strongly convex smooth class 𝓢^{1,1}_{μ,L} and xStar is a minimizer of f, then gradient descent with step size 2 / (μ + L) contracts the squared distance to xStar by the factor ((L - μ) / (L + μ))^(2k) after k iterations. The textbook ℝⁿ statement is recovered by specializing E = EuclideanSpace ℝ (Fin n).

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L : ℝ} {f : E → ℝ} theorem gradientMethod_sqdist_le_optimal_linear_rate (hf : f ∈ 𝓢[μ, L]¹¹) {xStar : E} (hxStar : IsMinOn f Set.univ xStar) (x0 : E) (k : ℕ) : ‖gradientMethod (fun _ ↦ 2 / (μ + L)) f x0 k - xStar‖ ^ (2 : ℕ) ≤ (((L - μ) / (L + μ)) ^ (2 * k)) * ‖(x0 - xStar)‖ ^ (2 : ℕ)

Exmaple 2.18.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Exmaple 2.18.1 (1): a half-space cut out by one affine linear inequality is convex on any real inner-product space. The textbook ℝ^n statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped RealInnerProductSpace universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem convex_halfspace_inner_le (a : E) (β : ℝ) : Convex ℝ {x : E | inner ℝ a x ≤ β}

Exmaple 2.18.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Exmaple 2.18.2: for the constrained problem \min_{x \ge 0} x, the boundary point 0 belongs to the constrained minimizer set even though the derivative there is strictly positive.

open scoped ConstrainedArgmin theorem nonnegativeLinearProblem_zero_mem_argmin_and_deriv_pos : 0 ∈ argmin[Set.Ici 0] (id : ℝ → ℝ) ∧ 0 < deriv (id : ℝ → ℝ) 0

Definition 2.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.19: given a smooth convex objective f ∈ 𝓕[L, p]¹¹, the unconstrained minimization problem min_{x ∈ E} f(x) is the Chapter 1 whole-space owner SetConstrainedMinimizationProblem.unconstrained f.

open scoped ConstrainedArgmin SmoothConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] local notation "p" => normSeminorm ℝ E variable (L : NNReal) (f : E → ℝ) variable (xStar : E) #check (SetConstrainedMinimizationProblem.unconstrained f : SetConstrainedMinimizationProblem E)

Lemma 2.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.19: if the source-facing lower quadratic model inequality holds at xBar with parameter γ₁ > 0 and reduced-gradient vector g₁, then the exact regularized model values satisfy f^*(xBar; γ₂) ≥ f^*(xBar; γ₁) + ((γ₂ - γ₁) / (2 γ₁ γ₂)) ‖g₁‖² for every γ₂ > 0. Here the textbook value f^*(xBar; γ) is recorded by the local notation modelValue γ, i.e. the real view of the Chapter 1 owner exact value of the constrained problem with feasible set Q and objective quadraticallyRegularizedObjective (f xBar) γ xBar.

universe u variable {E : Type u} [NormedAddCommGroup E] variable (Q : Set E) (f : E → E → ℝ) (xBar : E) local notation "modelOptimalValue" => fun γ : ℝ ↦ SetConstrainedMinimizationProblem.optimalValue ((SetConstrainedMinimizationProblem.mk Q (quadraticallyRegularizedObjective (f xBar) γ xBar)) : SetConstrainedMinimizationProblem E) local notation "modelValue" => fun γ : ℝ ↦ EReal.toReal (modelOptimalValue γ) variable [InnerProductSpace ℝ E] theorem exactValue_ge_of_lowerQuadraticModel (hQ : Q.Nonempty) (γ₁ γ₂ : ℝ) (g₁ : E) (hγ₁ : 0 < γ₁) (hγ₂ : 0 < γ₂) (hlower : ∀ x ∈ Q, f xBar x ≥ modelValue γ₁ + inner ℝ g₁ (x - xBar) + (1 / (2 * γ₁)) * ‖g₁‖ ^ (2 : ℕ)) : modelValue γ₂ ≥ modelValue γ₁ + ((γ₂ - γ₁) / (2 * γ₁ * γ₂)) * ‖g₁‖ ^ (2 : ℕ)

Proposition 2.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.19: for a chosen minimizer x(u) ∈ argmin_x 𝓛(x, u) of each equality- constrained Lagrangian subproblem, the selected dual profile u ↦ 𝓛(x(u), u) satisfies the affine support inequality φ(u₁) ≤ φ(u₂) + ⟪u₁ - u₂, g(u₂)⟫, where g(u) = b - A x(u).

universe u v open scoped PrimalEqualityConstrainedProblem.LagrangianMinimizerSelectionNotation namespace PrimalEqualityConstrainedProblem namespace LagrangianMinimizerSelection variable {E : Type u} {Λ : Type v} [AddCommMonoid E] [Module ℝ E] variable [NormedAddCommGroup Λ] [InnerProductSpace ℝ Λ] variable {problem : PrimalEqualityConstrainedProblem E Λ} variable (selection : LagrangianMinimizerSelection problem) local notation "φ" => φ[selection] local notation "g" => g[selection] theorem selectedDualProfile_le_affine_support (u₁ u₂ : Λ) : φ u₁ ≤ φ u₂ + inner ℝ (u₁ - u₂) (g u₂)

Theorem 2.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.19: if xₖ, φₖ, and the recursively defined weights λ₀ = 1, λₖ₊₁ = (1 - αₖ) λₖ satisfy the estimating-sequence upper-model hypotheses, φ₀ = quadraticallyRegularizedObjective (fun _ ↦ f(x₀)) γ₀ x₀, equivalently φ₀(z) = f(x₀) + (γ₀ / 2) ‖z - x₀‖², and xStar is a minimizer of f, then f(xₖ) - f(xStar) is bounded by λₖ * (f(x₀) - f(xStar) + (γ₀ / 2) ‖x₀ - xStar‖²), where λₖ = ∏_{i=0}^{k-1} (1 - αᵢ).

open AffineMap universe u variable {E : Type u} [NormedAddCommGroup E] theorem estimating_sequence_suboptimality_le (f : E → ℝ) (x : ℕ → E) (φ : ℕ → E → ℝ) (φStar : ℕ → ℝ) (α : ℕ → ℝ) (xStar : E) (hxStar : IsMinOn f Set.univ xStar) (γ0 : ℝ) (hfx : ∀ k : ℕ, f (x k) ≤ φStar k) (hφmin : ∀ k : ℕ, IsLeast (Set.range (φ k)) (φStar k)) (hφupper : ∀ k : ℕ, φ k ≤ lineMap f (φ 0) (estimatingWeight α k)) (hφ0 : φ 0 = quadraticallyRegularizedObjective (fun _ ↦ f (x 0)) γ0 (x 0)) (k : ℕ) : f (x k) - f xStar ≤ estimatingWeight α k * (f (x 0) - f xStar + (γ0 / 2) * ‖x 0 - xStar‖ ^ (2 : ℕ))

Definition 2.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.20: for a smooth convex objective f ∈ 𝓕[L, p]¹¹ or a strongly convex smooth objective f ∈ 𝓢[μ, L]¹¹, the associated unconstrained minimization problem min_{x ∈ ℝⁿ} f(x) is the canonical whole-space owner SetConstrainedMinimizationProblem.unconstrained f. If xStar satisfies IsMinOn f Set.univ xStar, then xStar is an optimal solution and the optimal value is given by the companion theorem SetConstrainedMinimizationProblem.unconstrained_optimalValue_eq_of_isMinOn.

universe u variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) variable (f : E → ℝ) theorem associated_unconstrained_problem_eq_unconstrained : ({ feasibleSet := Set.univ, objective := f } : SetConstrainedMinimizationProblem E) = SetConstrainedMinimizationProblem.unconstrained f

Lemma 2.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.20 lies in the whole-space specialization of the simple-set estimating-sequence domain on a complete real inner-product space. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n). Owner declarations sampled for this refinement: * simpleSetEstimatingModel in Proposition_2_22, the owner lower model over a closed convex feasible set; * simpleSetEstimatingFunction, simpleSetEstimatingCenter, and simpleSetEstimatingValue in Proposition_2_22, the owner recursive estimating-sequence objects in canonical quadratic form; * simpleSetEstimatingFunction_eq_canonicalQuadratic and simpleSetEstimatingFunction_eq_canonicalQuadratic_apply in Proposition_2_22, the owner centered-quadratic function identity and its pointwise companion; * gradientMapping_univ_eq_gradient_step and reducedGradient_univ_eq_gradient in Remark_2_35_1, the chapter's canonical whole-space bridge from projected-gradient stage data to the unconstrained gradientStep / ∇ f formulas. Best owner abstraction: * source-facing: the textbook whole-space formulas obtained by specializing the simple-set owners to Q = Set.univ; * core/canonical: simpleSetEstimatingModel, simpleSetEstimatingFunction, simpleSetEstimatingCenter, simpleSetEstimatingValue, and simpleSetEstimatingFunction_eq_canonicalQuadratic_apply; * bridge/view: the ordinary specialization Q = Set.univ, simplified through gradientMapping_univ_eq_gradient_step and reducedGradient_univ_eq_gradient. Primitive data: * the objective f, initial point x0, parameters (μ, L, γ₀), and stage data (y, α); * the nonvanishing hypothesis on the owner curvature sequence. Derived API: * the whole-space lower-model formula rewritten to gradientStep / ∇ f; * the whole-space recursive estimating-function and scalar-value families; * the whole-space centered-quadratic identity. The previous file duplicated these declarations with separate smoothEstimating... names. Those definitions were exact Set.univ specializations of the owner simple-set API, so this file now keeps only the specialization layer and reuses the canonical owner declarations directly.

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall simpleSetEstimatingModel

Proposition 2.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.20 in textbook form: if the canonical selected dual profile selection.selectedDualProfile is maximized at uStar and has gradient there equal to the dual residual, then the selected minimizer at uStar solves the primal problem.

open scoped Gradient open scoped PrimalEqualityConstrainedProblem.LagrangianMinimizerSelectionNotation universe u v namespace PrimalEqualityConstrainedProblem namespace LagrangianMinimizerSelection variable {E : Type u} {Λ : Type v} [AddCommMonoid E] [Module ℝ E] variable [NormedAddCommGroup Λ] [InnerProductSpace ℝ Λ] variable {problem : PrimalEqualityConstrainedProblem E Λ} variable (selection : LagrangianMinimizerSelection problem) local notation "Q₌" => problem.equalityFeasibleSet local notation "φ" => φ[selection] local notation "g" => g[selection] variable [CompleteSpace Λ] theorem isMinOn_feasibleSet_of_dualOptimal {uStar : Λ} (huStar : IsMaxOn φ Set.univ uStar) (hprofile_grad : HasGradientAt φ (g uStar) uStar) : (selection uStar : E) ∈ Q₌ ∧ IsMinOn problem Q₌ (selection uStar)

Theorem 2.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.20 (1): for a smooth strongly convex minimization problem with γ₀ = 3L + μ, the iterate sequence of the optimal method satisfies the O((k + 1)⁻²) function-value bound.

open AffineMap open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L gamma0 : ℝ} {f : E → ℝ} variable {xStar : E} variable {x0 : E} variable {x0 : E} theorem optimal_method_quadratic_suboptimality_le (method : GeneralOptimalMethodScheme f L μ x0 (3 * L + μ)) (hf : f ∈ 𝓢[μ, L]¹¹) (hxStar : IsMinOn f Set.univ xStar) (k : ℕ) : f (method k) - f xStar ≤ (2 * (4 + q[μ, L]) * L * ‖x0 - xStar‖ ^ (2 : ℕ)) / (3 * (k + 1 : ℝ) ^ (2 : ℕ))

Remark 2.20.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Remark 2.20.1: if φ_k^* ≥ f(x_k) and the whole-space lower model (2.3.8) holds at y_k, then the next estimate-sequence value satisfies the textbook whole-space lower bound (2.3.10).

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) (x0 : E) (μ : ℝ) (L : NNRealˣ) (gamma0 : ℝ) (y : ℕ → E) (α : ℕ → ℝ) (hγ : ∀ k, estimatingSequenceCurvature μ gamma0 α (k + 1) ≠ 0) (k : ℕ) (xk : E) local notation "gammaK" => estimatingSequenceCurvature μ gamma0 α k local notation "gammaKp1" => estimatingSequenceCurvature μ gamma0 α (k + 1) local notation "phiK" => simpleSetEstimatingValue (Set.univ : Set E) Set.univ_nonempty isClosed_univ convex_univ f x0 μ L gamma0 y α k local notation "phiKp1" => simpleSetEstimatingValue (Set.univ : Set E) Set.univ_nonempty isClosed_univ convex_univ f x0 μ L gamma0 y α (k + 1) local notation "vK" => simpleSetEstimatingCenter (Set.univ : Set E) Set.univ_nonempty isClosed_univ convex_univ f x0 μ L gamma0 y α k local notation "yK" => y k local notation "transportCoeff" => α k * (1 - α k) * gammaK / gammaKp1 local notation "intermediateRhs" => (1 - α k) * f xk + α k * f (gradientStep f yK L) + (α k / (2 * (L : ℝ)) - α k ^ (2 : ℕ) / (2 * gammaKp1)) * ‖∇ f yK‖ ^ (2 : ℕ) + transportCoeff * inner ℝ (∇ f yK) (vK - yK) local notation "strongObjectiveLowerRhs" => f (gradientStep f yK L) + inner ℝ (∇ f yK) (xk - yK) + (1 / (2 * (L : ℝ))) * ‖∇ f yK‖ ^ (2 : ℕ) + (μ / 2) * ‖xk - yK‖ ^ (2 : ℕ) local notation "finalRhs" => f (gradientStep f yK L) + (1 / (2 * (L : ℝ)) - α k ^ (2 : ℕ) / (2 * gammaKp1)) * ‖∇ f yK‖ ^ (2 : ℕ) + (1 - α k) * inner ℝ (∇ f yK) (((α k * gammaK) / gammaKp1) • (vK - yK) + (xk - yK)) theorem whole_space_phi_star_lower_bound_of_strong_objective_lower_bound (halpha_k : α k ≤ 1) (htransportCoeff : 0 ≤ transportCoeff) (hμ : 0 ≤ μ) (hphi_k : f xk ≤ phiK) (hobjective_lower : f xk ≥ strongObjectiveLowerRhs) : phiKp1 ≥ finalRhs

Definition 2.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.21: a pair of sequences φₖ : X → ℝ and λₖ ∈ [0, ∞) is an estimating sequence for f when λₖ → 0 and each model φₖ satisfies the upper estimate φₖ(x) ≤ (1 - λₖ) f(x) + λₖ φ₀(x) for every k and every x.

open AffineMap universe u def IsEstimatingSequence {X : Type u} (f : X → ℝ) (φ : ℕ → X → ℝ) (lam : ℕ → NNReal) : Prop := Filter.Tendsto lam Filter.atTop (nhds 0) ∧ ∀ k : ℕ, φ k ≤ lineMap f (φ 0) (lam k : ℝ)

Lemma 2.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.21 (below-threshold side): if t < tStar and the auxiliary objective attains its minimum, then the auxiliary optimal value is strictly positive. This is the source-facing threshold-sign law for the owner value problem.constrainedAuxiliaryOptimalValue t; the explicit attainment input keeps the infimum-to-minimum step faithful to the mathematics.

universe u namespace LagrangianProblem variable {Q : Type u} {m : ℕ} variable (problem : LagrangianProblem Q m) {tStar : ℝ} theorem constrainedAuxiliaryOptimalValue_pos_of_lt (htStar : IsGLB (Set.range fun x : problem.feasibleSet ↦ problem x) tStar) (t : ℝ) (ht : t < tStar) (hattained : ∃ x : Q, IsMinOn (problem.constrainedAuxiliaryObjective t) Set.univ x) : (0 : EReal) < problem.constrainedAuxiliaryOptimalValue t

Proposition 2.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.21 in owner form: if the selected dual profile φ(u) = 𝓛(x(u), u) has pointwise gradient g(u) = b - A x(u) at the optimal multiplier uStar and at the comparison point uBar, and uStar is a global maximizer of φ, then the dual norm of the infeasibility at uBar equals the dual norm of ∇ φ(uBar), and the primal suboptimality of x(uBar) relative to the optimal selected point x(uStar) is bounded by ‖uBar‖_d ‖∇ φ(uBar)‖_{d,*}.

open scoped Gradient SeminormDualNorm open scoped PrimalEqualityConstrainedProblem.LagrangianMinimizerSelectionNotation universe u v namespace PrimalEqualityConstrainedProblem namespace LagrangianMinimizerSelection variable {E : Type u} {Λ : Type v} [AddCommMonoid E] [Module ℝ E] variable [NormedAddCommGroup Λ] [InnerProductSpace ℝ Λ] variable [FiniteDimensional ℝ Λ] variable {problem : PrimalEqualityConstrainedProblem E Λ} variable (selection : LagrangianMinimizerSelection problem) local notation "Q₌" => problem.equalityFeasibleSet local notation "φ" => φ[selection] local notation "g" => g[selection] theorem dual_gradient_bounds_infeasibility_and_suboptimality (d : Seminorm ℝ Λ) [Seminorm.IsNorm d] {uStar uBar : Λ} (hprofile_grad_star : HasGradientAt φ (g uStar) uStar) (hprofile_grad_bar : HasGradientAt φ (g uBar) uBar) (huStar : IsMaxOn φ Set.univ uStar) : ‖g uBar‖[d,*] = ‖∇ φ uBar‖[d,*] ∧ problem (selection uBar) - problem (selection uStar) ≤ d uBar * ‖∇ φ uBar‖[d,*]

Theorem 2.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.21: for a smooth μ-strongly convex objective on a real Hilbert space, the optimal-method trajectory started from the parameter α₀ in the stated admissible range satisfies the displayed hyperbolic upper bound on the objective gap.

open scoped StrongConvexSmooth variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L : ℝ} local notation "qf" => q[μ, L] local notation "αRange" => Set.Ioc (Real.sqrt qf) (constantStepSchemeIIAlphaUpper qf) variable {f : E → ℝ} variable (α0 : ℝ) local notation "γ0" => optimal_method_alpha0_initial_curvature μ L α0 variable (xStar : E) variable {x0 : E} theorem optimal_method_alpha0_hyperbolic_objective_gap_le (hf : f ∈ 𝓢[μ, L]¹¹) (hα0 : α0 ∈ αRange) (hxStar : IsMinOn f Set.univ xStar) (method : GeneralOptimalMethodScheme f L μ x0 γ0) (k : ℕ) : f (method k) - f xStar ≤ (4 * μ * (f x0 - f xStar + (γ0 / 2) * ‖x0 - xStar‖ ^ (2 : ℕ))) / ((γ0 - μ) * (Real.exp (((k + 1 : ℝ) / 2) * Real.sqrt qf) - Real.exp (-(((k + 1 : ℝ) / 2) * Real.sqrt qf))) ^ (2 : ℕ))

Definition 2.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.22: for a μ-strongly convex function with L-Lipschitz continuous gradient, the textbook reciprocal condition number q_f is the chapter scalar q[μ, L], namely the reciprocal of Q_f and concretely the ratio μ / L.

open scoped StrongConvexSmooth variable (μ L : ℝ) #check (rfl : q[μ, L] = μ / L)

Lemma 2.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.22: increasing the parameter by Δ ≥ 0 lowers the owner auxiliary optimal value by at most Δ and never increases it. For the source value notation f^*(t) attached to x ↦ max {f₀(x) - t, f₁(x), …, fₘ(x)}, one has f^*(t) - Δ ≤ f^*(t + Δ) ≤ f^*(t) at the canonical problem.constrainedAuxiliaryOptimalValue level.

universe u namespace LagrangianProblem variable {Q : Type u} {m : ℕ} theorem constrainedAuxiliaryOptimalValue_shift_bounds (problem : LagrangianProblem Q m) {t Δ : ℝ} (hΔ : 0 ≤ Δ) : problem.constrainedAuxiliaryOptimalValue t - Δ ≤ problem.constrainedAuxiliaryOptimalValue (t + Δ) ∧ problem.constrainedAuxiliaryOptimalValue (t + Δ) ≤ problem.constrainedAuxiliaryOptimalValue t

Proposition 2.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.22: if each successor curvature γ_{k+1} is nonzero, the recursively defined estimating sequence over a simple set is exactly the centered quadratic quadraticallyRegularizedObjective (fun _ ↦ φ_k^*) γ_k v_k, where φ_k^* and v_k are the source-facing recursive sequences simpleSetEstimatingValue and simpleSetEstimatingCenter, while γ_k is the owner curvature sequence estimatingSequenceCurvature from Lemma_2_9.

open AffineMap open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (x0 : E) (μ : ℝ) (L : NNRealˣ) (gamma0 : ℝ) (y : ℕ → E) (α : ℕ → ℝ) local notation "xProj" => fun k : ℕ ↦ x_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; L](y k) local notation "gProj" => fun k : ℕ ↦ g_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; L](y k) local notation "gamma" => estimatingSequenceCurvature μ gamma0 α local notation "phi" => simpleSetEstimatingFunction Q hQ_nonempty hQ_closed hQ_convex f x0 μ L gamma0 y α theorem simpleSetEstimatingFunction_eq_canonicalQuadratic (hγ : ∀ k, gamma (k + 1) ≠ 0) (k : ℕ) : phi k = quadraticallyRegularizedObjective (fun _ ↦ simpleSetEstimatingValue Q hQ_nonempty hQ_closed hQ_convex f x0 μ L gamma0 y α k) (gamma k) (simpleSetEstimatingCenter Q hQ_nonempty hQ_closed hQ_convex f x0 μ L gamma0 y α k)

Theorem 2.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.22 (1): for the smooth convex optimal-method scheme, every estimating-sequence center vₖ stays within sqrt (1 + L / γ₀) ‖x* - x₀‖ of a minimizer x*, written on the owner surface as ‖xStar - method 0‖.

open scoped BigOperators Gradient variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open scoped OptimalMethodRecurrence.OptimalMethodGradientAverage namespace GeneralOptimalMethodScheme variable {L : NNReal} {f : E → ℝ} {x0 : E} {gamma0 : ℝ} -- The source-facing owner of `gₖ` remains `OptimalMethodRecurrence.gradientAverage`. The scheme -- statements below reuse that owner through the underlying recurrence view of `method`. local notation:max "g_[" method ";" k "]" => OptimalMethodRecurrence.gradientAverage (GeneralOptimalMethodScheme.toOptimalMethodRecurrence method) k variable (hconv : ConvexOn ℝ Set.univ f) variable (hgrad : ∀ x : E, HasGradientAt f (∇ f x) x) variable (hgrad_lipschitz : LipschitzWith L (∇ f)) variable (xStar : E) variable (hxStar : IsMinOn f Set.univ xStar) variable {x0 : E} {gamma0 : ℝ} variable (method : GeneralOptimalMethodScheme f (L : ℝ) 0 x0 gamma0) include hconv hgrad omit hconv include hgrad hgrad_lipschitz include xStar hxStar include hconv theorem center_norm_le (k : ℕ) : ‖method.v k - xStar‖ ≤ Real.sqrt (1 + (L : ℝ) / gamma0) * ‖xStar - method 0‖

Remark 2.22.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Remark 2.22.1 is recall-only. The primary domain here is the simple-set estimate-sequence lower bound built from the projected-gradient owner API on a nonempty closed convex feasible set. Owner declarations sampled for this refinement: * gradientMapping and reducedGradient in Definition_2_35_1; * gradientMapping_objective_lower_bound in Theorem_2_36; * simple_set_phi_star_lower_bound_intermediate and simple_set_phi_star_lower_bound_of_objective_lower_bound in Text_2_1. Best owner abstraction: * the two theorem-level lower bounds in Text_2_1, derived from the canonical projected-gradient data and the canonical objective lower bound. Primitive data: the feasible set Q, the objective f, the iterate data (y_k, x_k, v_k), and the scalar parameters (L, α_k, γ_k, γ_{k+1}, φ_k^*, φ_{k+1}^*). Derived API: the projected-gradient point x_Q(y_k; L), the reduced gradient g_Q(y_k; L), and the two algebraic lower bounds already packaged in Text_2_1. Source/core/bridge triage: * source-facing: the remark's lower bound obtained after inserting (2.2.57) into the estimate-sequence update; * core/canonical: gradientMapping, reducedGradient, and gradientMapping_objective_lower_bound; * bridge/view: the two theorem-level combination steps in Text_2_1. Accordingly, this file adds no parallel local theorem wrappers; downstream use should refer directly to the owner declarations from Text_2_1.

recall simple_set_phi_star_lower_bound_intermediate

Definition 2.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.23: for iterates xᵢ of a differentiable function f : E → ℝ on a real Hilbert space and indices k ≤ T, g[f; x; k, T | h] is the minimum of ‖∇ f (xᵢ)‖ over all i with k ≤ i ≤ T.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def minGradientNormAlongIterates (f : E → ℝ) (x : ℕ → E) (k T : ℕ) (h : k ≤ T) : ℝ := (Finset.Icc k T).inf' (Finset.nonempty_Icc.2 h) (fun i ↦ ‖∇ f (x i)‖)

Lemma 2.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.23: if the objective and all constraint functions are convex and the auxiliary minimum is attained for every parameter t, then the auxiliary optimal value function satisfies the displayed left-shifted secant lower bound. This follows the source proof directly: choose attained minimizers, prove the convex-combination inequality for the attained real values, and then rewrite the result back into the canonical extended-real optimal-value notation.

universe u namespace LagrangianProblem variable {E : Type u} {m : ℕ} variable [AddCommMonoid E] [Module ℝ E] variable (problem : LagrangianProblem E m) theorem constrainedAuxiliaryOptimalValue_secant_lower_bound (hobjective : ConvexOn ℝ Set.univ problem) (hconstraints : ∀ i, ConvexOn ℝ Set.univ (problem.constraints i)) (hattained : ∀ t : ℝ, ∃ x : E, IsMinOn (problem.constrainedAuxiliaryObjective t) Set.univ x) {t1 t2 Delta : ℝ} (ht : t1 < t2) (hDelta : 0 ≤ Delta) : problem.constrainedAuxiliaryOptimalValue (t1 - Delta) ≥ problem.constrainedAuxiliaryOptimalValue t1 + (Delta / (t2 - t1)) * (problem.constrainedAuxiliaryOptimalValue t1 - problem.constrainedAuxiliaryOptimalValue t2)

Proposition 2.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.23: if f : E → ℝ lies in the strongly convex smooth class 𝓢^{1,1}_{μ,L}, xStar is a minimizer of f, and gradient descent uses the constant step size 1 / L, then the iterates satisfy the linear squared-distance contraction ‖x_k - xStar‖² ≤ (1 - q[μ, L])^k ‖x₀ - xStar‖², equivalently ‖x_k - xStar‖² ≤ (1 - μ / L)^k ‖x₀ - xStar‖². The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L : ℝ} {f : E → ℝ} theorem gradientMethod_sqdist_le_geometric_rate_step_inv_L (hf : f ∈ 𝓢[μ, L]¹¹) {xStar : E} (hxStar : IsMinOn f Set.univ xStar) (x0 : E) (k : ℕ) : ‖gradientMethod (fun _ ↦ 1 / L) f x0 k - xStar‖ ^ (2 : ℕ) ≤ (1 - q[μ, L]) ^ k * ‖x0 - xStar‖ ^ (2 : ℕ)

Theorem 2.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.23: for every stage k and threshold M, there is a one-dimensional quadratic objective together with an actual optimal-method scheme whose weighted sampled point \hat y_k = (λ_k / (1 - λ_k)) ∑_{i < k} (α_i / λ_{i+1}) y_i, formed from the owner data λ_k = method.weight k, α_i = method.alpha i, and y_i = method.y i, has gradient norm at least M.

open scoped BigOperators Gradient open Matrix local notation "E" => EuclideanSpace ℝ (Fin 1) local notation "Mat" => Matrix (Fin 1) (Fin 1) ℝ theorem exists_estimatingSequence_counterexample_with_large_gradient_norm (k : ℕ) (M : ℝ) : ∃ (linearCoeff : E) (method : GeneralOptimalMethodScheme (quadraticObjective 0 linearCoeff (0 : Mat)) 1 0 0 1), let yHat := method.weightedAverage method.y k M ≤ ‖∇ (quadraticObjective 0 linearCoeff (0 : Mat)) yHat‖

Definition 2.24

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.24: the regularized function f_δ(x) = f(x) + (δ / 2) ‖x - x₀‖² is the canonical quadratic-regularization owner quadraticallyRegularizedObjective f δ x₀.

universe u variable {E : Type u} [NormedAddCommGroup E] variable (f : E → ℝ) (δ : ℝ) (x0 : E) recall quadraticallyRegularizedObjective

Lemma 2.24

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.24 (1): if the owner μ-model value at (tBar, xBar) dominates (1 - κ) times the owner L-model value, if the owner constrained value at tBar is positive, and if τ ↦ modelValue τ xBar μ is convex and has a root not smaller than tBar, then the selected owner least root lies strictly above the reference parameter tBar.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} {μ L : ℝ}
open scoped RegularizedModelValueRootNotation
variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L)
local notation "parametricProblem" => problem.toParametricSmoothMinimaxProblem
local notation "modelValue" =>
  problem.regularizedModelValue
local notation "parametricOptimalValue" =>
  fun t ↦ sInf ((parametricProblem t) '' problem.ambientSet)
variable {xBar : E} {tBar κ : ℝ}
theorem referenceParameter_lt_regularizedModelValueRoot
    (hκ : κ < 1)
    (hcomparison : modelValue tBar xBar μ ≥ (1 - κ) * modelValue tBar xBar L)
    (hvalue_pos : 0 < parametricOptimalValue tBar)
    (hmu_convex : ConvexOn ℝ Set.univ (fun τ ↦ modelValue τ xBar μ))
    (hmu_root : ∃ τ : ℝ, tBar ≤ τ ∧ modelValue τ xBar μ = 0) :
    tBar < t★[problem; xBar](tBar)

Proposition 2.24

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.24: for each t, the constrained max-type problem is the owner problem.toParametricSmoothMinimaxProblem t, so existence and uniqueness of its feasible minimizer are given directly by the canonical owner theorem SmoothMinimaxProblem.existsUnique_isMinOn.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} {μ L : ℝ}
variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L) (t : ℝ)
recall SmoothMinimaxProblem.existsUnique_isMinOn

Theorem 2.24

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.24: on a finite-dimensional real inner-product space, for the constant-step gradient-method trajectory with step 1 / L, some iterate among x₀, …, x_T has squared gradient norm at most 16 L² ‖x₀ - x^*‖² / ((T + 4) (T + 6)) whenever T ≥ 3. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient SmoothConvex MinGradientNormAlongIterates universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] local notation "p" => normSeminorm ℝ E variable {L : NNReal} {f : E → ℝ} namespace ConvexC1SeminormSmooth theorem gradientMethod_exists_iterate_with_small_gradient_sq (xStar : E) (x0 : E) {T : ℕ} (hf : f ∈ 𝓕[L, p]¹¹) (hxStar : IsMinOn f Set.univ xStar) (hT : 3 ≤ T) : ∃ i ≤ T, ‖∇ f ((gradientMethod (fun _ ↦ 1 / (L : ℝ)) f x0) i)‖ ^ (2 : ℕ) ≤ (16 * (L : ℝ) ^ (2 : ℕ) * ‖x0 - xStar‖ ^ (2 : ℕ)) / ((T + 4 : ℝ) * (T + 6 : ℝ))

Definition 2.25

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.25: a constrained minimization problem over a set is the canonical owner SetConstrainedMinimizationProblem E, packaging a feasible set Q ⊆ ℝⁿ together with a real-valued ambient objective whose restriction to Q is minimized.

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) variable (Q : Set E) (f : E → ℝ) recall SetConstrainedMinimizationProblem

Lemma 2.25

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.25: for the Chapter 2 two-level scheme with the canonical root update t_{k+1} = t^*(x_{k,j(k)}, t_k), assume 0 ≤ κ < 1 / 2, assume the normalized stopped residuals f^*(t_k; x_{k,j(k)}; L) / √(t_{k+1} - t_k) decay by the factor 1 / (2 * (1 - κ)), assume tStar is the primal threshold, assume the initial threshold control f^*(t₀) ≤ t^* - t₀, assume the initial μ-model value is controlled by the first parameter increment, and assume every parameter increment is at most t^* - t₀. Then the selected residual f^*(t_k; x_{k,j^*(k)}; L) satisfies the displayed geometric estimate. The attained upper-model formulation at the exact successor x_{k+1} is kept only as a bridge consequence via selected_residual_eq_upperModel_at_successor.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [FiniteDimensional ℝ E]
variable {m : ℕ} {μ L : ℝ}
open SmoothMinimaxProblem ConstrainedMinimizationMethod
variable {problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L}
local notation "parametricProblem" => problem.toParametricSmoothMinimaxProblem
local notation "modelValue" => problem.regularizedModelValue
variable
    {κ t0 tStar : ℝ} {x0 : problem.ambientSet} {hL : 0 < L}
    {hStep1a : ∀ xBar : problem.ambientSet, ∀ t : ℝ, ∃ j, step1aAt problem κ xBar t hL j}
local notation "xSeq" =>
  ConstrainedMinimizationMethod.x problem κ t0 x0 hL hStep1a
local notation "tSeq" =>
  ConstrainedMinimizationMethod.t problem κ t0 x0 hL hStep1a
local notation "stoppedSeq" =>
  ConstrainedMinimizationMethod.stoppedInternalIterate problem κ t0 x0 hL hStep1a
local notation "selectedSeq" =>
  ConstrainedMinimizationMethod.selectedInternalIterate problem κ t0 x0 hL hStep1a
local notation "stoppedResidual" =>
  fun k ↦ modelValue (tSeq k) (stoppedSeq k : E) L
local notation "selectedResidual" =>
  fun k ↦ modelValue (tSeq k) (selectedSeq k : E) L
local notation "valueFunctionAt(" t ")" =>
  sInf ((parametricProblem t) '' (SmoothMinimaxProblem.feasibleSet (parametricProblem t)))
local notation "upperModelAtSuccessor(" k ")" =>
  quadraticallyRegularizedObjective
    (SmoothMinimaxProblem.affineApproximation
      (parametricProblem (tSeq k))
      (selectedSeq k : E))
    L
    (selectedSeq k : E)
    (xSeq (k + 1) : E)
local notation "geometricBound(" k ")" =>
  ((tStar - t0) / (1 - κ)) * ((1 / (2 * (1 - κ))) ^ k)
lemma selected_residual_le_geometric_rate
    (hprimal :
      IsGLB
        (Set.range fun x : problem.toFunctionalConstraintsMinimizationProblem.feasibleSet ↦
          problem x)
        tStar)
    (hκ_nonneg : 0 ≤ κ)
    (hκ : κ < 1 / 2)
    (hdecay :
      ∀ k : ℕ,
        2 * (1 - κ) *
            (stoppedResidual (k + 1) /
              Real.sqrt (tSeq (k + 2) - tSeq (k + 1))) ≤
          stoppedResidual k / Real.sqrt (tSeq (k + 1) - tSeq k))
    (hinit_step :
      modelValue t0 (stoppedSeq 0 : E) μ ≤ tSeq 1 - t0)
    (hinitial_value : valueFunctionAt(t0) ≤ tStar - t0)
    (hinitial_model :
      stoppedResidual 0 ≤ (1 / (1 - κ)) * modelValue t0 (stoppedSeq 0 : E) μ)
    (hstep_bound : ∀ k : ℕ, tSeq (k + 1) - tSeq k ≤ tStar - t0)
    (k : ℕ) :
    selectedResidual k ≤ geometricBound(k)

Proposition 2.25

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.25: if Q is compact and φ : ℝ × Q → ℝ is continuous, then the infimum profile t ↦ inf_{x ∈ Q} φ(t, x) is continuous. Applied to a compact subset Q ⊆ ℝ^n, this is the textbook minimum-value function f^*(t) = min_{x ∈ Q} φ(t, x).

universe u theorem continuous_sInf_range_of_isCompact {X : Type u} [TopologicalSpace X] {Q : Set X} (hQ : IsCompact Q) {φ : ℝ × Q → ℝ} (hφ : Continuous φ) : Continuous (fun t ↦ sInf (Set.range fun x ↦ φ (t, x)))

Theorem 2.25

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.25 on the intrinsic real-Hilbert-space owner layer: if f is convex on the whole space, admits the ambient gradient ∇ f everywhere, has L-Lipschitz gradient, and xStar is a global minimizer, then the minimum gradient norm among the first T + 1 iterates of gradient descent with step 1 / L is bounded by 4 L ‖x₀ - x^*‖ / √((T + 4)(T + 6)) whenever T ≥ 3. The textbook ℝⁿ statement is recovered by the finite-dimensional Chapter 2 specialization theorem below.

open scoped Gradient SmoothConvex MinGradientNormAlongIterates universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] namespace ConvexC1SeminormSmooth variable {L : NNReal} {f : E → ℝ} variable [CompleteSpace E] theorem gradientMethod_min_gradient_norm_le_explicit_sublinear_rate (hconv : ConvexOn ℝ Set.univ f) (hgrad : ∀ x : E, HasGradientAt f (∇ f x) x) (hgrad_lipschitz : LipschitzWith L (∇ f)) (xStar : E) (hxStar : IsMinOn f Set.univ xStar) (x0 : E) {T : ℕ} (hT : 3 ≤ T) : g[f; gradientMethod (fun _ ↦ 1 / (L : ℝ)) f x0; 0, T | Nat.zero_le T] ≤ (4 * (L : ℝ) * ‖x0 - xStar‖) / Real.sqrt ((T + 4 : ℝ) * (T + 6 : ℝ))

Definition 2.26

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.26 is a source-facing recall in the convex-geometry domain of epigraphs in ℝ². Primary domain: - the epigraph of the reciprocal map x ↦ 1 / x on the positive ray. Sampled owner-style declarations: - reciprocalEpigraphOnPositiveRay, the Chapter 2 owner set for the textbook region Q; - mem_reciprocalEpigraphOnPositiveRay_iff, the owner membership criterion; - ConvexOn.convex_epigraph, the mathlib owner theorem expressing the general epigraph style; - convexOn_iff_convex_epigraph, the canonical bridge between convexity and epigraph convexity. Best owner abstraction: - reciprocalEpigraphOnPositiveRay : Set (ℝ × ℝ) Primitive data: - the positivity condition 0 < x.1; - the epigraph inequality x.2 ≥ 1 / x.1. Derived API: - the additional displayed condition 0 ≤ x.2, since 0 < x.1 implies 0 < 1 / x.1. Source/core/bridge triage: - source-facing: the textbook set Q = {(x₁, x₂) | 0 < x₁, x₂ ≥ 1 / x₁}; - core/canonical: reciprocalEpigraphOnPositiveRay; - bridge/view: mem_reciprocalEpigraphOnPositiveRay_iff. This recall file therefore introduces no parallel local definition such as positiveReciprocalEpigraph; downstream use should refer directly to the owner set and its companion membership theorem.

recall reciprocalEpigraphOnPositiveRay : Set (ℝ × ℝ)

Lemma 2.26

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.26: for the fixed-t parametric minimax problem attached to a smooth functional constraints problem, if the regularized μ-model value is bounded below by the regularized L model value minus (Q_f - 1) times the current relative gap, and that relative gap is at most (α / (Q_f - 1)) f^*(t; xBar; L), then the stopping comparison f^*(t; xBar; μ) ≥ (1 - α) f^*(t; xBar; L) holds.

universe u v
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {ι : Type v} [Fintype ι] [Nonempty ι]
variable {m : ℕ} {μ L : ℝ}
variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L) (t : ℝ)
local notation "parametricProblem" => problem.toParametricSmoothMinimaxProblem t
local notation "modelValue" => problem.regularizedModelValue t
local notation "valueFunction" =>
  sInf (parametricProblem '' (SmoothMinimaxProblem.feasibleSet parametricProblem))
local notation "relativeGap" => fun xBar ↦ parametricProblem xBar - valueFunction
theorem stopping_condition_of_relativeGapBound
    {α Qf : ℝ} {xBar : E}
    (hQf : 1 < Qf)
    (hModelComparison :
      modelValue xBar μ ≥
        modelValue xBar L - (Qf - 1) * relativeGap xBar)
    (hRelativeGap :
      relativeGap xBar ≤
        (α / (Qf - 1)) * modelValue xBar L) :
    (1 - α) * modelValue xBar L ≤ modelValue xBar μ

Proposition 2.26

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.26: if an extended-real convex value function is finite at the secant endpoints, then the same left-shifted secant lower bound holds for its finite real values. This is the source-facing finite-value form used for functions such as t ↦ f^*(t; x̄; γ).

open scoped ConvexAnalysis theorem secant_lower_bound_left_shift_of_finite_values {f : ℝ → EReal} (hf : ConvexOn ℝ (dom f) (extendedRealRealPart f)) {t1 t2 Delta : ℝ} (hleft : t1 - Delta ∈ dom f) (ht2 : t2 ∈ dom f) (hDelta : 0 ≤ Delta) (ht : t1 < t2) : extendedRealRealPart f (t1 - Delta) ≥ extendedRealRealPart f t1 + (Delta / (t2 - t1)) * (extendedRealRealPart f t1 - extendedRealRealPart f t2)

Theorem 2.26

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.26 on the intrinsic real-Hilbert-space owner layer: if f is convex on the whole space, admits the ambient gradient ∇ f everywhere, that gradient is L-Lipschitz in the ambient norm, and xStar is a global minimizer, then the recursive monotone type-I trajectory of method (2.2.32) satisfies the explicit O(T^{-3/2}) bound on the minimum gradient norm g_{0,T} over the first T + 1 iterates. The textbook ℝⁿ statement is the finite-dimensional specialization below.

open scoped Gradient MinGradientNormAlongIterates SmoothConvex universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] local notation "p" => normSeminorm ℝ E local notation "State" => E × E × ℝ theorem monotoneConstantStepSchemeIA_minGradientNormAlongIterates_le_explicit_bound {L : NNReal} {f : E → ℝ} (hconvex : ConvexOn ℝ Set.univ f) (hgrad : ∀ x : E, HasGradientAt f (∇ f x) x) (hgrad_lipschitz : LipschitzWith L (∇ f)) (xStar : E) (hxStar : IsMinOn f Set.univ xStar) (x0 : E) {T : ℕ} (hT : 1 ≤ T) : g[f; monotoneConstantStepSchemeIAX f L x0; 0, T | Nat.zero_le T] ≤ (4 * (L : ℝ) * ‖x0 - xStar‖) / Real.sqrt ((4 / 3 : ℝ) * (T + 2 : ℝ) ^ (3 : ℕ) - (9 / 4 : ℝ) * (T + 2 : ℝ) - (9 / 8 : ℝ))

Definition 2.27

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.27 is a recall-only item in the Euclidean convex-geometry domain of the nonnegative first-coordinate ray in ℝ². Primary domain: - convex-geometric subsets of ℝ² presented by coordinate conditions. Sampled owner-style declarations: - nonnegativeFirstCoordinateRay, the chapter's canonical owner for ℝ_+^{1,2}; - mem_nonnegativeFirstCoordinateRay_iff, the derived coordinate membership criterion; - Set.prod, the canonical product-set owner used to form coordinate-axis subsets; - Ici, the canonical half-line owner for the nonnegative first coordinate. Best owner abstraction: - nonnegativeFirstCoordinateRay : Set (ℝ × ℝ) Primitive data: - the first-coordinate half-line Ici (0 : ℝ); - the second-coordinate singleton {(0 : ℝ)}; - their product-set realization Ici (0 : ℝ) ×ˢ ({(0 : ℝ)} : Set ℝ). Derived API: - mem_nonnegativeFirstCoordinateRay_iff, which rewrites membership in the owner set as 0 ≤ x.1 ∧ x.2 = 0. Source/core/bridge triage: - source-facing: the textbook ray ℝ_+^{1,2}; - core/canonical: nonnegativeFirstCoordinateRay; - bridge/view: mem_nonnegativeFirstCoordinateRay_iff. This file therefore recalls the upstream owner declaration directly and introduces no parallel local definition such as nonnegativeFirstCoordinateAxis.

recall nonnegativeFirstCoordinateRay : Set (ℝ × ℝ)

Lemma 2.27

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.27: if Q_f > 1, κ > 0, Δ_{k+1} > 0, and Δ_{k+1} ≤ (2 (Q_f - 1) / κ) * exp (-(j(k) - 1) / √Q_f) * Δ_k for every k ≤ N, then the stopping index j(k) is bounded above by 1 + √Q_f log (2 (Q_f - 1) / κ) + √Q_f log (Δ_k / Δ_{k+1}) for every k ≤ N.

lemma stoppingIndex_le_one_add_sqrt_condition_log_ratio (Qf κ : ℝ) (N : ℕ) (j Δ : ℕ → ℝ) (hQf : 1 < Qf) (hκ : 0 < κ) (hΔ_succ_pos : ∀ ⦃k : ℕ⦄, k ≤ N → 0 < Δ (k + 1)) (hΔ_succ_bound : ∀ ⦃k : ℕ⦄, k ≤ N → Δ (k + 1) ≤ (2 * (Qf - 1) / κ) * Real.exp (-((j k - 1) / Real.sqrt Qf)) * Δ k) {k : ℕ} (hk : k ≤ N) : j k ≤ 1 + Real.sqrt Qf * Real.log (2 * (Qf - 1) / κ) + Real.sqrt Qf * Real.log (Δ k / Δ (k + 1))

Proposition 2.27

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.27: if xL minimizes the unshifted regularized objective x ↦ f x + (L / 2) ‖x - xBar‖² and gL := reducedGradientOf (L : ℝ) xBar xL, then the shifted exact regularized values satisfy f^*(t; xBar; μ) ≥ f^*(t; xBar; L) - ((L - μ) / (2 μ L)) ‖gL‖². The textbook ℝⁿ statement is recovered by specializing E := EuclideanSpace ℝ (Fin n).

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ : ℝ} {L : NNReal} {f : E → ℝ} local notation "shiftedObjective" => fun t : ℝ ↦ fun x : E ↦ f x - t local notation "shiftedFamily" => fun t : ℝ ↦ fun _ x : E ↦ f x - t local notation "modelOptimalValue" => fun t : ℝ ↦ fun xBar : E ↦ fun γ : ℝ ↦ SetConstrainedMinimizationProblem.optimalValue (SetConstrainedMinimizationProblem.unconstrained (quadraticallyRegularizedObjective (shiftedObjective t) γ xBar)) local notation "modelValue" => fun t : ℝ ↦ fun xBar : E ↦ fun γ : ℝ ↦ EReal.toReal (modelOptimalValue t xBar γ) theorem regularizedModelValue_mu_ge_L_sub_sq_norm (hf : f ∈ 𝓢[μ, (L : ℝ)]¹¹) (t : ℝ) (xBar xL : E) (hxL : IsMinOn (quadraticallyRegularizedObjective f (L : ℝ) xBar) Set.univ xL) : let gL := reducedGradientOf (L : ℝ) xBar xL modelValue t xBar μ ≥ modelValue t xBar (L : ℝ) - (((L : ℝ) - μ) / (2 * μ * (L : ℝ))) * ‖gL‖ ^ (2 : ℕ)

Theorem 2.27

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.27: let f : E → ℝ be convex and C¹ with L-Lipschitz gradient. If xStar minimizes f, if ‖x₀ - xStar‖ ≤ R₀, and if method (2.2.22) is applied from x₀ to the regularized objective f₈(x) = f(x) + (ε / (4 R₀)) ‖x - x₀‖², then any iterate count at least 3 √(1 + 2 L R₀ / ε) log (1 + 2 L R₀ / ε) yields a point whose original gradient norm is at most ε. Here δ = ε / (2 R₀), and the regularized problem has reciprocal condition number q[δ, (L : ℝ) + δ], so the source-facing method parameter is fixed by the regularization rather than chosen via an auxiliary admissible α₀; the owner scheme assumption already forces δ > 0, and with hR : ‖x₀ - xStar‖ ≤ R₀ this yields the textbook side conditions R₀ > 0 and ε > 0 internally instead of keeping them as primitive public hypotheses.

open scoped Gradient SmoothConvex StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] local notation "p" => normSeminorm ℝ E variable {L : NNReal} {R0 ε : ℝ} {f : E → ℝ} local notation "δ" => ε / (2 * R0) namespace ConvexC1SeminormSmooth theorem constantStepSchemeIII_regularizedObjective_gradient_norm_le_target (hf : f ∈ 𝓕[L, p]¹¹) (x0 xStar : E) (hxStar : IsMinOn f Set.univ xStar) (hR : ‖x0 - xStar‖ ≤ R0) (scheme : ConstantStepSchemeIII (quadraticallyRegularizedObjective f δ x0) ((L : ℝ) + δ) (q[δ, (L : ℝ) + δ]) x0) (T : ℕ) (hT : 3 * Real.sqrt (1 + 2 * (L : ℝ) * R0 / ε) * Real.log (1 + 2 * (L : ℝ) * R0 / ε) ≤ (T : ℝ)) : ‖∇ f (scheme T)‖ ≤ ε

Definition 2.28

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.28: the pointed conic hull 𝒦(Q) of Q = reciprocalEpigraphOnPositiveRay is the open positive quadrant together with the origin.

open Set open PointedCone local notation "Q" => reciprocalEpigraphOnPositiveRay theorem conicHull_reciprocalEpigraphOnPositiveRay_eq_openPositiveQuadrant_or_origin : (hull ℝ Q : Set (ℝ × ℝ)) = (Ioi (0 : ℝ) ×ˢ Ioi (0 : ℝ)) ∪ ({0} : Set (ℝ × ℝ))

Lemma 2.28

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 2.28: if Q_f > 1, κ > 0, ε > 0, and if for the predecessor index j = j^* - 1 one has ε ≤ f^*(t_{N+1}; x_{N+1}, j; L) ≤ ((Q_f - 1) / κ) * (f(t_{N+1}; x_{N+1}, j) - f^*(t_{N+1})) and ((Q_f - 1) / κ) * (f(t_{N+1}; x_{N+1}, j) - f^*(t_{N+1})) ≤ (2 * (Q_f - 1) / κ) * e^{-j / √Q_f} * Δ_{N+1}, then j^* ≤ 1 + √Q_f * log (2 (Q_f - 1) Δ_{N+1} / (κ ε)).

lemma accuracyStoppingIndex_le_one_add_sqrt_condition_log_ratio (Qf κ ε ΔNext : ℝ) (jStar jPrev : ℕ) {previousInternalValue objectiveGap : ℝ} (hQf : 1 < Qf) (hκ : 0 < κ) (hε : 0 < ε) (hjStar : jStar = jPrev + 1) (hLower : ε ≤ previousInternalValue) (hMiddle : previousInternalValue ≤ ((Qf - 1) / κ) * objectiveGap) (hUpper : ((Qf - 1) / κ) * objectiveGap ≤ (2 * (Qf - 1) / κ) * Real.exp (-((jPrev : ℝ) / Real.sqrt Qf)) * ΔNext) : (jStar : ℝ) ≤ 1 + Real.sqrt Qf * Real.log ((2 * (Qf - 1) * ΔNext) / (κ * ε))

Proposition 2.28

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.28: if the owner auxiliary optimal value at tk is at most ε, then any exact minimizer xStar of the owner auxiliary objective at tk satisfies f₀(xStar) ≤ tStar + ε and every constraint value fᵢ(xStar) is at most ε, provided tk ≤ tStar. The companion theorem constrainedAuxiliaryObjective_le_of_optimalValue_le_of_isMinOn records the attained-value bound on the auxiliary objective itself.

universe u namespace LagrangianProblem variable {Q : Type u} {m : ℕ} variable (problem : LagrangianProblem Q m) theorem objective_and_constraint_bounds_of_constrainedAuxiliaryOptimalValue_le {tk ε tStar : ℝ} {xStar : Q} (hxStar : IsMinOn (problem.constrainedAuxiliaryObjective tk) Set.univ xStar) (hopt : problem.constrainedAuxiliaryOptimalValue tk ≤ ε) (htk : tk ≤ tStar) : problem xStar ≤ tStar + ε ∧ ∀ i : Fin m, problem.constraints i xStar ≤ ε

Theorem 2.28

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.28 (1), (2), (3), and (9) are direct owner recalls.

open AffineMap open PointedCone (hull) open scoped Pointwise recall Convex.inter

Definition 2.29

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.29: Q₁ is the closed Euclidean unit disk in ℝ² centered at e₁ = (1, 0).

local notation "E" => EuclideanSpace ℝ (Fin 2) local notation "e₁" => EuclideanSpace.single (0 : Fin 2) (1 : ℝ) def Q₁ : Set E := Metric.closedBall e₁ (1 : ℝ)

Proposition 2.29

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.29: if the residual sequence satisfies t^* - t_{n + 1} ≤ (t^* - t_n) / (2 (1 - κ)) at every step and 1 < 2 * (1 - κ), then every iterate index n ≥ N(ε) satisfies t^* - t_n ≤ (1 - κ) ε, where N(ε) is the explicit logarithmic threshold from the proposition.

open HasGeometricRateOfConvergence variable {κ tStar : ℝ} {t : ℕ → ℝ} local notation "base" => 2 * (1 - κ) local notation "residual" => fun n : ℕ ↦ tStar - t n theorem constrainedMinimization_error_le_target_of_iterationThreshold_le {ε : ℝ} (hκ_contract : 1 < 2 * (1 - κ)) (hε : 0 < ε) (hstep : ∀ n : ℕ, tStar - t (n + 1) ≤ (tStar - t n) / (2 * (1 - κ))) {n : ℕ} (hn : Real.log ((tStar - t 0) / ((1 - κ) * ε)) / Real.log (2 * (1 - κ)) ≤ (n : ℝ)) : tStar - t n ≤ (1 - κ) * ε

Theorem 2.29

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.29: for a convex function f on Q that is differentiable at the feasible point xStar, constrained optimality at xStar is equivalent to the variational inequality ⟪∇ f xStar, x - xStar⟫ ≥ 0 for every x ∈ Q.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] namespace ConvexOn variable {Q : Set E} {f : E → ℝ} {xStar : E} theorem isMinOn_iff_gradient_variational_inequality (hf_conv : ConvexOn ℝ Q f) (hxStar : xStar ∈ Q) (hf_diff : DifferentiableAt ℝ f xStar) : IsMinOn f Q xStar ↔ ∀ x ∈ Q, 0 ≤ inner ℝ (∇ f xStar) (x - xStar)

Definition 2.30

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.30: a primal equality-constrained problem consists of an ambient feasible set Q, an objective f, a linear map A, and a right-hand side b, encoding f^* = min {f(x) | x ∈ Q, A x = b}. In the textbook Euclidean presentation, the linear map is represented by a matrix via Matrix.toEuclideanLin.

open scoped ConstrainedArgmin universe u v structure PrimalEqualityConstrainedProblem (E : Type u) (Λ : Type v) [AddCommMonoid E] [Module ℝ E] [AddCommMonoid Λ] [Module ℝ Λ] extends SetConstrainedMinimizationProblem E where /-- The linear equality map. -/ A : E →ₗ[ℝ] Λ /-- The right-hand side of the equality constraint. -/ b : Λ

Proposition 2.30

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.30: if optimalValue is the exact optimal value of the fixed-parameter objective f tk, then the internal suboptimality-gap sequence j ↦ f tk (x j) - optimalValue has geometric rate with contraction factor 1 - √q_f.

open HasGeometricRateOfConvergence universe u variable {α : Type u} variable (f : ℝ → α → ℝ) (tk optimalValue : ℝ) (x : ℕ → α) {qf : ℝ} (hqf : qf ∈ Set.Ioc (0 : ℝ) 1) (hoptimal : IsGLB (Set.range (f tk)) optimalValue) (hstep : ∀ j : ℕ, f tk (x (j + 1)) - optimalValue ≤ (1 - Real.sqrt qf) * (f tk (x j) - optimalValue)) local notation "σ" => Real.sqrt qf local notation "Δ" => fun j : ℕ ↦ f tk (x j) - optimalValue include hqf hoptimal hstep theorem constrainedMinimizationInternalGap_hasGeometricRateOfConvergence : HasGeometricRateOfConvergence Δ σ (2 * Δ 0)

Theorem 2.30

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.30: if f : E → ℝ is μ-strongly convex on the normed space E, xStar is a global minimizer of f, then every point x satisfies the quadratic growth bound f x ≥ f xStar + (μ / 2) ‖x - xStar‖².

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] namespace StrongConvexOn variable {μ : ℝ} {Q : Set E} {f : E → ℝ} theorem quadratic_growth_of_isMinOn (hf : StrongConvexOn Set.univ μ f) {xStar : E} (hxStar : IsMinOn f Set.univ xStar) (x : E) : f x ≥ f xStar + (μ / 2) * ‖x - xStar‖ ^ (2 : ℕ)

Definition 2.31

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.31: the equality-constrained Lagrangian dual objective is the negation of the source-facing dual function φ(u) = inf_{x ∈ Q} 𝓛(x, u) attached to problem; minimizing this function over u ∈ ℝᵐ is the textbook dual problem.

universe u v namespace PrimalEqualityConstrainedProblem variable {E : Type u} {Λ : Type v} [AddCommMonoid E] [Module ℝ E] variable [NormedAddCommGroup Λ] [InnerProductSpace ℝ Λ] def dualObjective (problem : PrimalEqualityConstrainedProblem E Λ) : Λ → EReal := -problem.dualFunction

Proposition 2.31

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.31: if the master parameters satisfy t_k ≤ tStar and the textbook comparison f(t_{k+1}; x_{k+1}) ≤ f(t_k; x_{k+1}) ≤ f^*(t_k; x_{k,j^*(k)}; L) holds at each step, then the constrained suboptimality gap f(t_k; x_k) - f^*(t_k) is bounded by the comparison quantity Δ_k. The exact values fStar k are supplied canonically by IsGLB, while the nonnegativity of these values is obtained from t_k ≤ tStar through the Chapter 2 threshold-sign owner API rather than taken as a primitive hypothesis.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} {μ L : ℝ}
open SmoothMinimaxProblem
open scoped Gradient
variable {problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L}
local notation "parametricProblem" => problem.toParametricSmoothMinimaxProblem
local notation "objective" =>
  fun t x ↦ (parametricProblem t) x
local notation "modelValue" =>
  problem.regularizedModelValue
local notation "feasibleObjectiveValues" =>
  fun t ↦ Set.range fun x : problem.ambientSet ↦ objective t (x : E)
theorem suboptimality_le_constrainedMinimizationDelta
    (x xSelected : ℕ → problem.ambientSet)
    (t : ℕ → ℝ)
    (fStar : ℕ → ℝ)
    (Δ : ℕ → ℝ)
    (tStar : ℝ)
    (hΔ_zero : Δ 0 = objective (t 0) (x 0 : E))
    (hΔ_succ : ∀ k : ℕ,
      Δ (k + 1) = modelValue (t k) (xSelected k : E) L)
    (hprimal : IsGLB (Set.range fun x : problem.feasibleSet ↦ problem x) tStar)
    (ht_le : ∀ k : ℕ, t k ≤ tStar)
    (hoptimal :
      ∀ k : ℕ, IsGLB (feasibleObjectiveValues (t k)) (fStar k))
    (hcomparison :
      ∀ k : ℕ,
        objective (t (k + 1)) (x (k + 1) : E) ≤ objective (t k) (x (k + 1) : E) ∧
          objective (t k) (x (k + 1) : E) ≤ modelValue (t k) (xSelected k : E) L) :
    ∀ k : ℕ,
      objective (t k) (x k : E) - fStar k ≤ Δ k

Theorem 2.31

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.31 / Theorem 2.3.1 is the direct owner recall of the constrained max-type optimality criterion. The textbook ℝⁿ / Fin m formulation is the Euclidean specialization of this owner theorem.

recall isMinOn_maxTypeObjective_iff_affineApproximation_ge

Definition 2.32

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.32: the p-to-d* induced operator norm of a dual-valued linear map A, computed as the supremum of the transported d*-norm over the primal closed unit ball. The owner lives on E →ₗ[ℝ] StrongDual ℝ F, with the concrete Euclidean realization E →ₗ[ℝ] F recovered by composing with toDual. Under the finite-dimensional separated source/target hypotheses of the textbook setting, this ℝ-valued supremum is the genuine induced operator norm; in the later ambient-norm specialization it agrees with the ordinary operator norm.

open InnerProductSpace open scoped Matrix.Norms.L2Operator SeminormDualNorm universe u v namespace Seminorm variable {E : Type u} {F : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] variable [NormedAddCommGroup F] [InnerProductSpace ℝ F] variable (p : Seminorm ℝ E) [IsNorm p] variable (d : Seminorm ℝ F) [FiniteDimensional ℝ F] [IsNorm d] def primalDualOperatorNorm (p : Seminorm ℝ E) [FiniteDimensional ℝ E] [p.IsNorm] (d : Seminorm ℝ F) [FiniteDimensional ℝ F] [d.IsNorm] (A : E →ₗ[ℝ] StrongDual ℝ F) : ℝ := sSup ((fun x : E ↦ ‖(toDual ℝ F).symm (A x)‖[d,*]) '' p.closedBall 0 1)

Proposition 2.32

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.32: if each internal cost j(k) satisfies the one-step logarithmic bound j(k) ≤ 1 + √Q_f log (2 (L - μ) / (κ μ)) + √Q_f log (Δ_k / Δ_{k+1}), then summing from k = 0 to N yields ∑_{k=0}^N j(k) ≤ (N + 1) * (1 + √Q_f log (2 (L - μ) / (κ μ))) + √Q_f log (Δ_0 / Δ_{N+1}).

open scoped BigOperators theorem sum_le_of_log_ratio_step_bounds (N : ℕ) (j Δ : ℕ → ℝ) (Qf L μ κ : ℝ) (hΔ_pos : ∀ k ≤ N + 1, 0 < Δ k) (hj_bound : ∀ k ≤ N, j k ≤ 1 + Real.sqrt Qf * Real.log (2 * (L - μ) / (κ * μ)) + Real.sqrt Qf * Real.log (Δ k / Δ (k + 1))) : Finset.sum (Finset.range (N + 1)) j ≤ (N + 1 : ℝ) * (1 + Real.sqrt Qf * Real.log (2 * (L - μ) / (κ * μ))) + Real.sqrt Qf * Real.log (Δ 0 / Δ (N + 1))

Theorem 2.32

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.32 is the direct owner recall of the closed-set unique-minimizer theorem for StrongConvexOnWith.

recall StrongConvexOnWith.existsUnique_isMinOn_of_isClosed

Definition 2.33

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.33: for a nonempty closed set Q, the textbook projection set π_Q(x₀) is formalized by the canonical constrained argmin set of the distance function x ↦ ‖x - x₀‖ on Q.

open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] variable (Q : Set E) (x₀ : E) #check (argmin[Q] (fun x : E ↦ ‖x - x₀‖) : Set E)

Proposition 2.33

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.33: if x ∈ (0, 2 * (Q_f - 1)) (so in particular Q_f > 1), ε > 0, the stage values Δ₀, …, Δ_{N+1} are positive, the terminal index j^* satisfies the Lemma 2.28 bound with Δ_{N+1}, and each internal cost j(k) satisfies the Proposition 2.32 hypothesis, then the total internal iteration count is bounded by (N + 2) * (1 + √Q_f * log (2 (Q_f - 1) / x)) + √Q_f * log (Δ₀ / ε).

open scoped BigOperators theorem constrainedMinimization_totalIterationCount_le_logarithmic_bound (N : ℕ) (j : ℕ → ℝ) (jStar : ℝ) (Δ : ℕ → ℝ) (Qf x ε : ℝ) (hx : x ∈ Set.Ioo (0 : ℝ) (2 * (Qf - 1))) (hε : 0 < ε) (hΔ_pos : ∀ ⦃k : ℕ⦄, k ≤ N + 1 → 0 < Δ k) (hjStar_bound : jStar ≤ 1 + Real.sqrt Qf * Real.log ((2 * (Qf - 1) * Δ (N + 1)) / (x * ε))) (hj_bound : ∀ ⦃k : ℕ⦄, k ≤ N → j k ≤ 1 + Real.sqrt Qf * Real.log (2 * (Qf - 1) / x) + Real.sqrt Qf * Real.log (Δ k / Δ (k + 1))) : jStar + Finset.sum (Finset.range (N + 1)) j ≤ (N + 2 : ℝ) * (1 + Real.sqrt Qf * Real.log (2 * (Qf - 1) / x)) + Real.sqrt Qf * Real.log (Δ 0 / ε)

Theorem 2.33

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.33, stated at the owner level: every point of a complete real inner product space has a unique projection point on a nonempty closed convex set Q. The Euclidean-space statement is the specialization to ℝⁿ.

open Metric universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [CompleteSpace E] variable (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (x₀ : E) theorem exists_unique_projection_point_of_nonempty_closed_convex (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (x₀ : E) : ∃! p : E, IsProjectionPointOn Q x₀ p

Definition 2.34

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.34: the half squared distance to a set sends x to one half of the square of its minimal distance to Q. The textbook Euclidean statement is the specialization to ℝⁿ.

open Metric universe u variable {E : Type u} [PseudoMetricSpace E] def Set.halfSquaredDistance (Q : Set E) : E → ℝ := fun x ↦ (1 / 2 : ℝ) * infDist x Q ^ 2

Proposition 2.34

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.34: if N is the source index of the last full iteration of process (2.3.22), if N satisfies the logarithmic master-iteration bound from Proposition 2.29, and if the final count j*, the full-step counts j(k) = scheme.stopIndex k, and the stage sequence Δ satisfy the specialized Proposition 2.33 hypotheses, then the total number of internal iterations is bounded by the displayed formula (2.3.27). The initial max-violation term is the owner auxiliary objective initialViolation = problem.toLagrangianProblem.constrainedAuxiliaryObjective t0 x0. The textbook ℝⁿ statement is recovered by specializing E = EuclideanSpace ℝ (Fin n).

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [FiniteDimensional ℝ E]
variable {m : ℕ} {μ L : ℝ}
variable {problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L}
variable {κ t0 tStar ε Qf : ℝ} {x0 : problem.ambientSet} {hL : 0 < L}
variable
  {hStep1a : ∀ xBar : problem.ambientSet, ∀ t : ℝ, ∃ j, step1aAt problem κ xBar t hL j}
local notation "initialViolation" =>
  problem.toLagrangianProblem.constrainedAuxiliaryObjective t0 x0
local notation "fullIterationBound" =>
  Real.log ((tStar - t0) / ((1 - κ) * ε)) / Real.log (2 * (1 - κ))
local notation "perIterationCost" =>
  1 + Real.sqrt Qf * Real.log (2 * (Qf - 1) / κ)
namespace ConstrainedMinimizationMethod
local notation "stopSeq" => stopIndex problem κ t0 x0 hL hStep1a
theorem totalInternalIterations_le_logarithmic_bound
    (N jStar : ℕ) (Δ : ℕ → ℝ)
    (hκ_domain : κ ∈ Set.Ioo (0 : ℝ) (2 * (Qf - 1)))
    (hε : 0 < ε)
    (hΔ_zero : Δ 0 = initialViolation)
    (hfullIterations : (N : ℝ) ≤ fullIterationBound)
    (hΔ_pos : ∀ ⦃k : ℕ⦄, k ≤ N + 1 → 0 < Δ k)
    (hjStar_bound :
      (jStar : ℝ) ≤
        1 + Real.sqrt Qf * Real.log ((2 * (Qf - 1) * Δ (N + 1)) / (κ * ε)))
    (hj_bound :
      ∀ ⦃k : ℕ⦄, k ≤ N →
        (stopSeq k : ℝ) ≤
          1 + Real.sqrt Qf * Real.log (2 * (Qf - 1) / κ) +
            Real.sqrt Qf * Real.log (Δ k / Δ (k + 1))) :
    (jStar : ℝ) +
        Finset.sum (Finset.range (N + 1)) (fun k ↦ (stopSeq k : ℝ)) ≤
      (fullIterationBound + 2) * perIterationCost +
        Real.sqrt Qf * Real.log (initialViolation / ε)

Theorem 2.34

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.34: the Euclidean projection onto a nonempty closed convex set in a complete real inner product space is nonexpansive, recorded in the canonical map-level form LipschitzWith 1. The textbook Euclidean-space statement is the specialization to ℝⁿ.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [CompleteSpace E] theorem euclideanProjection_nonexpansive (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) : LipschitzWith 1 (euclideanProjection Q hQ_nonempty hQ_closed hQ_convex)

Definition 2.35

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.35: the textbook gradient mapping and reduced gradient are represented by the canonical owner declarations gradientMapping and reducedGradient. The point gradientMapping Q hQ_nonempty hQ_closed hQ_convex f xBar γ is the unique minimizer of the quadratically regularized first-order Taylor model over Q, and reducedGradient Q hQ_nonempty hQ_closed hQ_convex f xBar γ is the scaled residual γ • (xBar - gradientMapping Q hQ_nonempty hQ_closed hQ_convex f xBar γ).

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall gradientMapping {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (xBar : E) (γ : NNRealˣ) : E

Proposition 2.35

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 2.35 at the owner layer: if t0 ∈ Q minimizes the quadratically regularized affine model determined by an explicit first-order witness g at tStar, and tStar ∈ Q minimizes f on the convex set Q, then t0 = tStar.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable {Q : Set E} {f : E → ℝ} {g : E} {γ : NNRealˣ} theorem eq_of_isMinOn_quadraticallyRegularizedObjective_affineModelAt_of_isMinOn (hQ_convex : Convex ℝ Q) {t0 tStar : E} (htStar_fderiv : HasFDerivAt f (InnerProductSpace.toDualMap ℝ E g) tStar) (ht0_mem : t0 ∈ Q) (htStar_mem : tStar ∈ Q) (ht0 : IsMinOn (quadraticallyRegularizedObjective (affineModelAt f (fun _ ↦ g) tStar) (γ : ℝ) tStar) Q t0) (htStar : IsMinOn f Q tStar) : t0 = tStar

Theorem 2.35

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.35: every optimal solution on a closed convex feasible set is a fixed point of the projected-gradient mapping for every positive inverse-stepsize parameter on a complete real inner-product space. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {Q : Set E} {f : E → ℝ} {xStar : E} {g : E} {γ : NNRealˣ} theorem gradientMapping_eq_of_isMinOn (Q : Set E) {f : E → ℝ} {xStar : E} {γ : NNRealˣ} (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (hxStar : xStar ∈ Q) (hopt : IsMinOn f Q xStar) (hf_diff : DifferentiableAt ℝ f xStar) : x_Q[Q; ⟨xStar, hxStar⟩; hQ_closed; hQ_convex | f; γ](xStar) = xStar

Definition 2.35.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.35.1 (1): the projected-gradient point is the Euclidean projection of the explicit gradient step gradientStep f xBar γ onto Q.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [CompleteSpace E] def gradientMapping (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (xBar : E) (γ : NNRealˣ) : E := euclideanProjection Q hQ_nonempty hQ_closed hQ_convex (gradientStep f xBar γ)

Remark 2.35.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Remark 2.35.1: the projected-gradient point is obtained from xBar by a step of size 1 / γ in the direction of the reduced gradient.

open scoped Gradient ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (xBar : E) (γ : NNRealˣ) theorem gradientMapping_eq_point_sub_inv_smul_reducedGradient : x_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; γ](xBar) = xBar - (γ : ℝ)⁻¹ • g_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; γ](xBar)

Remark 2.35.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Remark 2.35.2 is a recall-only item in the projected-gradient / Euclidean-projection domain on nonempty closed convex sets in a complete real inner-product space. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n). Primary domain: * the ambient projected-gradient point x_Q(xBar; γ), defined by projecting the explicit gradient step from an arbitrary ambient base point xBar : E. Owner declarations sampled for this refinement: * gradientMapping in Definition_2_35_1, the source-facing projected-gradient point; * gradientMapping_isProjectionPointOn in Definition_2_35_1, the chapter's source-facing projection-point bridge for that projected-gradient point; * euclideanProjection in Theorem_2_33, the lower owner used internally by gradientMapping; * gradientMapping_eq_point_sub_inv_smul_reducedGradient in Remark_2_35_1, the later source-facing step identity derived from the same owner. Best owner abstraction: * gradientMapping. Primitive data: * the feasible set Q with nonempty / closed / convex structure; * the objective f, the ambient base point xBar, and the parameter γ; * the complete real inner-product-space structure on E, which is exactly the ambient owner layer used by gradientMapping and euclideanProjection. Derived API: * gradientMapping_isProjectionPointOn, the direct source-facing projection-point bridge; * the later step identity gradientMapping_eq_point_sub_inv_smul_reducedGradient. Source/core/bridge triage: * source-facing: the remark that x_Q(xBar; γ) is well-defined for every ambient xBar : E, with no hypothesis xBar ∈ Q; * core/canonical: gradientMapping; * bridge/view: gradientMapping_isProjectionPointOn. Accordingly, this file stays at the owner level: it recalls gradientMapping directly in the general ambient space where it is defined, and recalls its chapter-local projection-point bridge instead of dropping back to the lower euclideanProjection interface or re-specializing either declaration to ℝⁿ.

open scoped Gradient ProjectedGradient universe u recall gradientMapping {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) (f : E → ℝ) (xBar : E) (γ : NNRealˣ) : E

Definition 2.36

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.36: a constrained smooth strongly convex minimization problem with parameters μ and L is a set-constrained minimization problem on a real Hilbert space whose feasible set is nonempty and closed and whose objective belongs to 𝓢^{1,1}_{μ,L}(Q) on that feasible set.

open scoped Gradient StrongConvexSmooth
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [FiniteDimensional ℝ E]
local notation "p" => normSeminorm ℝ E
namespace SetConstrainedMinimizationProblem
variable {μ L : ℝ}
structure IsConstrainedStrongConvexSmooth
    (problem : SetConstrainedMinimizationProblem E)
    (μ L : ℝ) : Prop where
  nonempty : problem.feasibleSet.Nonempty
  isClosed : IsClosed problem.feasibleSet
  objective_mem : problem.objective ∈ 𝓢[μ, L]¹¹(problem.feasibleSet)

Theorem 2.36

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.36: for a nonempty closed convex set Q in a complete real inner-product space, the canonical projected-gradient point gradientMapping ... and reduced gradient reducedGradient ... give the lower bound `f x ≥ f(x_Q(xBar; γ)) + ⟪g_Q(xBar; γ), x - xBar⟫ + (1 / (2γ)) ‖g_Q(xBar; γ)‖² + (μ / 2) ‖x - xBar‖²` for every x ∈ Q whenever f ∈ 𝓢^{1,1}_{μ,L} on the ambient space and γ ≥ L. This is the canonical-owner generalization of the textbook ℝⁿ statement. The base point xBar is ambient: no hypothesis xBar ∈ Q is required.

open scoped Gradient ProjectedGradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (Q : Set E) (hQ_nonempty : Q.Nonempty) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) {μ : ℝ} {γ : NNRealˣ} {L : NNReal} {f : E → ℝ} (xBar : E) local notation "xQ" => x_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; γ](xBar) local notation "gQ" => g_Q[Q; hQ_nonempty; hQ_closed; hQ_convex | f; γ](xBar) theorem gradientMapping_objective_lower_bound (hf : f ∈ 𝓢[μ, (L : ℝ)]¹¹) (hγ_ge_L : (L : ℝ) ≤ (γ : ℝ)) (x : E) (hx : x ∈ Q) : f x ≥ f xQ + inner ℝ gQ (x - xBar) + (1 / (2 * (γ : ℝ))) * ‖gQ‖ ^ (2 : ℕ) + (μ / 2) * ‖x - xBar‖ ^ (2 : ℕ)

Definition 2.37

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.37 is a recall-only item in the projected-gradient estimating-sequence domain for a simple feasible set in a complete real inner-product space. Primary domain: * projected-gradient estimating sequences over a closed convex feasible set Sampled owner-style declarations: * simpleSetEstimatingModel * simpleSetEstimatingModel_apply * simpleSetEstimatingFunction * simpleSetEstimatingFunction_succ Best owner abstraction: * the source-facing owners simpleSetEstimatingModel and simpleSetEstimatingFunction already defined in Proposition_2_22 Primitive data: * a feasible set Q with nonempty / closed / convex hypotheses * an objective f, initial point x0, and parameters μ, L, gamma0 * the stage points y and weights α Derived API: * the displayed lower-model formula simpleSetEstimatingModel_apply * the initial-value identity simpleSetEstimatingFunction_zero * the affine-recursion identity simpleSetEstimatingFunction_succ Source/core/bridge triage: * source-facing: the simple-set lower model and recursive estimating sequence from the text * core/canonical: the owner declarations in Proposition_2_22, together with quadraticallyRegularizedObjective and lineMap * bridge/view: the ..._apply, zero-stage, and successor-stage formulas This file therefore uses direct canonical recall for the owners and their companion formulas, without re-spelling those long interfaces as parallel local declarations.

open AffineMap open scoped ProjectedGradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall simpleSetEstimatingModel

Theorem 2.37

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.37 (1): on a nonempty closed convex feasible set whose objective lies in 𝓕_L^{1,1}(Q), the projected gradient step with parameter γ ≥ L decreases the objective by at least (2γ)⁻¹ ‖g_Q(xBar; γ)‖².

open scoped Gradient ProjectedGradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [FiniteDimensional ℝ E]
variable (problem : SetConstrainedMinimizationProblem E) {L : NNReal}
variable
    (hQ_closed : IsClosed problem.feasibleSet)
    (hSmooth :
      ConvexC1SeminormSmoothOn (normSeminorm ℝ E) L problem.feasibleSet problem)
    (xBar : E) (hxBar : xBar ∈ problem.feasibleSet) {γ : NNRealˣ}
local notation "xQ" =>
  x_Q[problem.feasibleSet; Exists.intro xBar hxBar; hQ_closed; hSmooth.convex | problem; γ](xBar)
local notation "gQ" =>
  g_Q[problem.feasibleSet; Exists.intro xBar hxBar; hQ_closed; hSmooth.convex | problem; γ](xBar)
theorem gradientMapping_value_le_sub_reducedGradient_sq
    (hγ : (L : ℝ) ≤ (γ : ℝ)) :
    problem xQ ≤
      problem xBar -
        (1 / (2 * (γ : ℝ))) * ‖gQ‖ ^ (2 : ℕ)

Definition 2.38

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.38: a smooth minimax problem with parameters μ and L consists of a nonempty closed convex feasible set Q ⊆ E on a real Hilbert space together with finitely many component functions fᵢ ∈ 𝓢^{1,1}_{μ,L}(E) indexed by a nonempty finite type ι; its objective is the max-type function x ↦ max_i fᵢ(x), so the problem is min_{x ∈ Q} max_i fᵢ(x). The textbook ℝⁿ/Fin m presentation is the specialization E = EuclideanSpace ℝ (Fin n) and ι = Fin m.

open scoped StrongConvexSmooth universe u v variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {ι : Type v} [Fintype ι] [Nonempty ι] {μ L : ℝ} structure SmoothMinimaxProblem (E : Type u) [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] (ι : Type v) [Fintype ι] [Nonempty ι] (μ L : ℝ) where /-- The closed convex feasible set `Q ⊆ E`. -/ feasibleSet : Set E /-- The feasible set is nonempty. -/ feasible_nonempty : feasibleSet.Nonempty /-- The feasible set is closed. -/ feasible_closed : IsClosed feasibleSet /-- The feasible set is convex. -/ feasible_convex : Convex ℝ feasibleSet /-- The component functions whose pointwise maximum defines the minimax objective. -/ components : ι → E → ℝ /-- Each component belongs to the smooth strongly convex class `𝓢^{1,1}_{μ,L}(E)`. -/ components_mem : ∀ i : ι, components i ∈ 𝓢[μ, L]¹¹

Theorem 2.38

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.38: if Q is closed and convex in a real Hilbert space E, f belongs to 𝓢^{1,1}_{μ,L}(E), and xStar ∈ Q minimizes f on Q, then every projected-gradient trajectory with inverse-stepsize parameter γ ≥ (L + μ) / 2 contracts linearly toward xStar, with ‖x_k - xStar‖ ≤ (1 - μ / γ)^k ‖x0 - xStar‖ for all k ≥ 0. Uniqueness of the constrained minimizer is derived from strong convexity and is not stored as a separate hypothesis; likewise, in the nontrivial real-Hilbert-space cases the owner hypothesis already forces μ ≤ L, while the subsingleton case is tautological. The textbook ℝⁿ theorem is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient ProjectedGradient StrongConvexSmooth open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem projectedGradientSequence_dist_le_geometric (Q : Set E) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) {μ L : ℝ} {γ : NNRealˣ} {f : E → ℝ} (hf : f ∈ 𝓢[μ, L]¹¹) {x0 xStar : E} (hx0_mem : x0 ∈ Q) (hxStar : xStar ∈ argmin[Q] f) (x : ℕ → E) (hx_zero : x 0 = x0) (hx_succ : ∀ k : ℕ, x (k + 1) = x_Q[Q;⟨x0, hx0_mem⟩;hQ_closed;hQ_convex|f;γ](x k)) (hγ : (L + μ) / 2 ≤ (γ : ℝ)) (k : ℕ) : ‖x k - xStar‖ ≤ (1 - μ / (γ : ℝ)) ^ k * ‖x0 - xStar‖

Remark 2.38.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Remark 2.38.1: when Algorithm 2.6 uses the optimal inverse-stepsize parameter γ = (L + μ) / 2, its canonical trajectory simpleSetGradientMethod contracts the distance to the constrained minimizer at the same sharp linear rate as the unconstrained gradient method: ‖x_k - xStar‖ ≤ ((L - μ) / (L + μ))^k ‖x₀ - xStar‖. The textbook ℝⁿ statement is the specialization E = EuclideanSpace ℝ (Fin n).

open scoped Gradient ProjectedGradient StrongConvexSmooth open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem simpleSetGradientMethod_dist_le_optimal_geometric_rate {μ L : ℝ} {Q : Set E} {f : E → ℝ} {γ : NNRealˣ} (hf : f ∈ 𝓢[μ, L]¹¹) (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q) {x0 xStar : E} (hx0_mem : x0 ∈ Q) (hxStar : xStar ∈ argmin[Q] f) (hγ : (γ : ℝ) = (L + μ) / 2) (k : ℕ) : ‖simpleSetGradientMethod Q hQ_closed hQ_convex f x0 hx0_mem γ k - xStar‖ ≤ ((L - μ) / (L + μ)) ^ k * ‖x0 - xStar‖

Definition 2.39

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.39: the affine approximation of a finite max-type objective at xBar is the pointwise maximum of the canonical first-order Taylor models of its components at xBar.

open scoped Gradient universe u variable {ι : Type*} [Fintype ι] [Nonempty ι] variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def maxTypeAffineApproximation (fi : ι → E → ℝ) (xBar : E) : E → ℝ := maxTypeObjective (fun i ↦ firstOrderTaylorModelAt (fi i) xBar)

Theorem 2.39

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.39: for a nonempty family of components f₁, …, fₘ convex on the same feasible set Q ⊆ E and differentiable at the feasible base point xStar, the point xStar minimizes the pointwise maximum objective exactly when every first-order affine max model based at xStar is bounded below by f(xStar) on Q. The textbook ℝⁿ/Fin m formulation is the specialization E = EuclideanSpace ℝ (Fin n) and ι = Fin m.

open Filter Asymptotics
open scoped Gradient Topology
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι]
theorem isMinOn_maxTypeObjective_iff_affineApproximation_ge
    (Q : Set E) (fs : ι → E → ℝ) (xStar : E)
    (hconv : ∀ i : ι, ConvexOn ℝ Q (fs i))
    (hxStar : xStar ∈ Q)
    (hdiff : ∀ i : ι, DifferentiableAt ℝ (fs i) xStar) :
    IsMinOn (maxTypeObjective fs) Q xStar ↔
      ∀ x ∈ Q,
        maxTypeAffineApproximation fs xStar x ≥ maxTypeObjective fs xStar

Definition 2.40

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.40 is a recall-only item in the finite max-type quadratic-regularization domain on a real Hilbert space. Sampled owner-style declarations: * maxTypeAffineApproximation in Definition_2_39, the owner affine max-type model at xBar; * maxTypeAffineApproximation_apply, the pointwise bridge for that affine model; * quadraticallyRegularizedObjective in Definition_1_4_17.lean, the owner quadratic regularization of an objective; * quadraticallyRegularizedObjective_apply, the pointwise bridge for the regularized objective. Best owner abstraction: * source-facing/core: quadraticallyRegularizedObjective (maxTypeAffineApproximation fi xBar) γ xBar; * bridge/view: the pointwise expansion obtained by composing the two owner ..._apply lemmas. Primitive data: * a nonempty finite component family fi : ι → E → ℝ; * a base point xBar : E; * a regularization parameter γ : ℝ. Derived API: * the affine max-type model maxTypeAffineApproximation fi xBar; * the expanded value formula for the regularized max-type model. Source/core/bridge triage: * source-facing/core: quadraticallyRegularizedObjective (maxTypeAffineApproximation fi xBar) γ xBar; * bridge/view: its pointwise expansion. This file therefore recalls the composed owner expression directly and introduces no parallel local alias such as regularizedMaxTypeModel or proximalMaxLinearization.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {ι : Type*} [Fintype ι] [Nonempty ι] recall maxTypeAffineApproximation

Theorem 2.40

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.40 is the direct owner recall of constrained quadratic growth at a feasible minimizer.

recall StrongConvexOnWith.quadratic_growth_of_isMinOn_of_mem

Definition 2.41

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.41: the textbook set X_f(xBar; γ) of gradient mappings is the constrained argmin set of the model x ↦ fγ xBar x on Q. The corresponding canonical optimal value is gradientMappingOptimalValue Q fγ xBar, and any chosen x ∈ gradientMappingSet Q fγ xBar determines the reduced gradient reducedGradientOf γ xBar x.

open scoped ConstrainedArgmin universe u variable {E : Type u} abbrev gradientMappingSet (Q : Set E) (fγ : E → E → ℝ) (xBar : E) : Set E := argmin[Q] (fγ xBar)

Theorem 2.41

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.41 is the direct owner recall of the unique feasible minimizer theorem for SmoothMinimaxProblem.

namespace SmoothMinimaxProblem recall existsUnique_isMinOn

Remark 2.41.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Remark 2.41.1: the regularized max-type affine subproblem has a unique feasible exact step. This well-definedness is obtained by combining convexity of the affine max-type model with the centered quadratic regularization.

open scoped Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {ι : Type*} [Fintype ι] [Nonempty ι]
variable [ProperSpace E]
theorem existsUnique_maxTypeGradientMapping
    (Q : Set E) (hQ_nonempty : Q.Nonempty)
    (hQ_closed : IsClosed Q) (hQ_convex : Convex ℝ Q)
    (fi : ι → E → ℝ) (xBar : E) (γ : NNRealˣ) :
    ∃! xPlus : E,
      xPlus ∈ Q ∧
        IsMinOn
          (quadraticallyRegularizedObjective (maxTypeAffineApproximation fi xBar) γ xBar)
          Q
          xPlus

Definition 2.42

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.42: the initial model is the quadratic regularization of the constant objective with value f0, centered at x0 with curvature gamma0. In the smooth minimax setting one specializes to f0 = problem x0.

open scoped MaxTypeStep
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι] {μ L : ℝ}
namespace SmoothMinimaxProblem
def initialQuadraticModel
    (f0 : ℝ) (gamma0 : ℝ) (x0 : E) :
    E → ℝ :=
  quadraticallyRegularizedObjective (fun _ : E ↦ f0) gamma0 x0

Theorem 2.42

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.42: for a smooth minimax problem on a real Hilbert space, if L ≤ γ, x ∈ Q, and xPlus minimizes the owner quadratically regularized max-type affine model quadraticallyRegularizedObjective (problem.affineApproximation xBar) γ xBar over the feasible set, then the objective is bounded below by the value at xPlus, the affine term induced by γ • (xBar - xPlus), the quadratic correction (2γ)⁻¹ ‖γ • (xBar - xPlus)‖², and the strong-convexity term (μ / 2) ‖x - xBar‖².

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι] {μ L : ℝ}
namespace SmoothMinimaxProblem
theorem objective_lower_bound_of_isMinOn_regularizedAffineApproximation
    (problem : SmoothMinimaxProblem E ι μ L) (xBar : E)
    {γ : NNRealˣ} {x xPlus : E} (hLγ : L ≤ (γ : ℝ))
    (hx : x ∈ problem.feasibleSet)
    (hxPlus_mem : xPlus ∈ problem.feasibleSet)
    (hxPlus :
      IsMinOn
        (quadraticallyRegularizedObjective
          (problem.affineApproximation xBar) γ xBar)
        problem.feasibleSet xPlus) :
    problem x ≥
        problem xPlus +
          inner ℝ ((γ : ℝ) • (xBar - xPlus)) (x - xBar) +
          (1 / (2 * (γ : ℝ))) * ‖(γ : ℝ) • (xBar - xPlus)‖ ^ (2 : ℕ) +
        (μ / 2) * ‖x - xBar‖ ^ (2 : ℕ)

Definition 2.43

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.43 is a recall-only item in the epigraph reformulation domain for constrained quadratically regularized max-type affine minimization on a real Hilbert space. Primary domain: * the auxiliary-variable epigraph presentation of the Chapter 2 regularized minimax subproblem on E × ℝ Sampled owner-style declarations: * SetConstrainedMinimizationProblem in Chap01/Definition_1_3_3, the project owner of a feasible set together with a real-valued ambient objective; * SetConstrainedMinimizationProblem.coe_apply, the canonical coercion view of that owner as its objective function; * maxTypeAffineApproximation in Definition_2_39, the owner affine max-type model at xBar; * quadraticallyRegularizedObjective in Chap01/FirstOrderTaylorModel.lean, the owner quadratic regularization of an objective on E. Best owner abstraction: * source-facing/core: SetConstrainedMinimizationProblem (E × ℝ), built from the epigraph feasible set and its auxiliary-variable objective; * bridge/view: the displayed feasible-set and objective expressions, together with the tight-slack specialization back to the Chapter 2 owner quadraticallyRegularizedObjective (maxTypeAffineApproximation fi xBar) γ xBar. Primitive data: * a feasible set Q : Set E; * a nonempty finite component family fi : ι → E → ℝ; * a base point xBar : E; * a regularization parameter γ : ℝ. Derived API: * the epigraph problem `SetConstrainedMinimizationProblem.mk {xt : E × ℝ | xt.1 ∈ Q ∧ maxTypeAffineApproximation fi xBar xt.1 ≤ xt.2} (fun xt ↦ xt.2 + (γ / 2) * ‖xt.1 - xBar‖ ^ (2 : ℕ))`; * the coercion of that problem to its objective on E × ℝ; * the constrained minimizer predicate IsMinOn problem problem.feasibleSet xtStar; * the tight-slack specialization xt.2 = maxTypeAffineApproximation fi xBar xt.1. Source/core/bridge triage: * source-facing: the epigraph minimization problem on E × ℝ; * core/canonical: SetConstrainedMinimizationProblem (E × ℝ); * bridge/view: the displayed feasible-set and objective formulas for that owner, and the projection back to the regularized max-type model on E. This recall file therefore presents the epigraph reformulation through the Chapter 1 owner object, not as a parallel collection of standalone feasible-set, objective, and minimizer displays. Downstream Chapter 2 files should package the epigraph problem with SetConstrainedMinimizationProblem.mk ... and use problem.feasibleSet, coercion to the objective, and IsMinOn problem problem.feasibleSet ... as the derived API. The textbook states the item on ℝⁿ, but the owner declarations sampled above already live on the canonical abstract real-Hilbert-space / finite-index layer, so this recall file keeps that generality instead of re-specializing it to EuclideanSpace ℝ (Fin n) and Fin m.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {ι : Type*} [Fintype ι] [Nonempty ι] recall SetConstrainedMinimizationProblem

Theorem 2.43

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.43 (1): for a whole-space strongly convex smooth objective, the exact step x_f(xBar; γ) = xBar - (1 / γ) • ∇ f xBar satisfies the standard lower bound, and in the whole-space setting g_f(xBar; γ) = ∇ f xBar.

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ : ℝ} {γ : NNRealˣ} {L : NNReal} {f : E → ℝ} theorem exactStep_objective_lower_bound (xBar x : E) (hf : f ∈ 𝓢[μ, (L : ℝ)]¹¹) (hγ_ge_L : (L : ℝ) ≤ (γ : ℝ)) : f x ≥ f (gradientStep f xBar γ) + inner ℝ (∇ f xBar) (x - xBar) + (1 / (2 * (γ : ℝ))) * ‖∇ f xBar‖ ^ (2 : ℕ) + (μ / 2) * ‖x - xBar‖ ^ (2 : ℕ)

Definition 2.44

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.44: a smooth convex constrained minimization problem with parameters μ and L consists of a nonempty simple closed convex set Q ⊆ E, an objective f₀ : E → ℝ, and constraint functions fᵢ : E → ℝ for i = 1, …, m, where every component belongs to 𝓢[μ, L]¹¹; the associated problem is to minimize f₀ over points x ∈ Q satisfying fᵢ(x) ≤ 0 for all constraints. The textbook ℝⁿ case is the specialization E = EuclideanSpace ℝ (Fin n).

universe u open scoped StrongConvexSmooth variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {m : ℕ} {μ L : ℝ} structure SmoothFunctionalConstraintsMinimizationProblem (E : Type u) [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] (m : ℕ) (μ L : ℝ) extends LagrangianProblem E m where /-- The ambient closed convex set `Q ⊆ E` on which the constrained problem is posed. -/ ambientSet : Set E /-- The ambient set `Q` is nonempty. -/ ambient_nonempty : ambientSet.Nonempty /-- The ambient set `Q` is closed. -/ ambient_closed : IsClosed ambientSet /-- The ambient set `Q` is convex. -/ ambient_convex : Convex ℝ ambientSet /-- The objective belongs to the smooth strongly convex class `𝓢[μ, L]¹¹`. -/ objective_mem : objective ∈ 𝓢[μ, L]¹¹ /-- Every constraint component belongs to the same smooth strongly convex class `𝓢[μ, L]¹¹`. -/ constraints_mem : ∀ i : Fin m, constraints i ∈ 𝓢[μ, L]¹¹

Theorem 2.44

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.44: for the recursive Algorithm 2.8 trajectory of a smooth minimax problem, the squared distance to any feasible minimizer xStar decays geometrically as ‖x_k - xStar‖² ≤ (1 - μ h)^k ‖x₀ - xStar‖² whenever h ≤ 1 / L, with the primitive positive step size owned canonically as h : NNRealˣ. Feasibility is encoded by the subtype-valued trajectory constantStepMinimaxGradientMethod ... : ℕ → problem.feasibleSet, while the target minimizer keeps the canonical constrained-minimization data xStar ∈ problem.feasibleSet and IsMinOn problem problem.feasibleSet xStar.

open scoped Gradient MaxTypeStep
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι] {μ : ℝ} {L : NNRealˣ}
namespace SmoothMinimaxProblem
variable (problem : SmoothMinimaxProblem E ι μ (L : ℝ))
local notation "Q" => problem.feasibleSet
theorem constantStepMinimaxGradientSequence_sqdist_le_geometric
    {xStar : E} (hxStar_mem : xStar ∈ Q) (hxStar : IsMinOn problem Q xStar)
    {x0 : Q} {h : NNRealˣ}
    (hh : (h : ℝ) ≤ 1 / (L : ℝ))
    (k : ℕ) :
    let x :=
      constantStepMinimaxGradientMethod
        Q
        problem.feasible_closed
        problem.feasible_convex
        problem.components
        L
        x0
        h
        hh
    ‖((x k : E) - xStar)‖ ^ (2 : ℕ) ≤
      (1 - μ * (h : ℝ)) ^ k * ‖((x0 : E) - xStar)‖ ^ (2 : ℕ)

Definition 2.45

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.45 is a recall-only item in the chapter's functional-constraint max-type value-function domain. Sampled owner-style declarations: * LagrangianProblem.constrainedAuxiliaryObjective in Lemma_2_21, the canonical auxiliary max-type objective x ↦ max {f₀(x) - t, f₁(x), …, fₘ(x)}; * LagrangianProblem.constrainedAuxiliaryOptimalValue in Lemma_2_21, the generic owner infimum of the same max-violation objective on an ambient type; * LagrangianProblem.constrainedAuxiliaryOptimalValue_eq_of_isMinOn in Lemma_2_21, the owner attained-minimum theorem reused on restricted subtype problems when needed; * maxTypeObjective_apply in Definition_2_39, the canonical finite-maximum evaluation theorem used to expose the textbook pointwise formula from the owner max-type objective. Best owner abstraction: * core/canonical: LagrangianProblem.mk (fun x : Q ↦ f0 x) (fun i x ↦ fi i x) : LagrangianProblem Q m; * source-facing: the owner objective `LagrangianProblem.constrainedAuxiliaryObjective (LagrangianProblem.mk (fun x : Q ↦ f0 x) (fun i x ↦ fi i x)) t` and the corresponding owner value on Q; * bridge/view: LagrangianProblem.constrainedAuxiliaryOptimalValue_eq_sInf, which expands the owner value to the textbook constrained infimum formula. Primitive data: * feasible set Q; * objective f0; * constraint family fi; * scalar parameter t. Derived API: * the subtype owner LagrangianProblem.mk (fun x : Q ↦ f0 x) (fun i x ↦ fi i x) : LagrangianProblem Q m; * the parametric max-type objective on Q; * its constrained owner value on Q; * the restricted-attainment bridge furnished by the generic LagrangianProblem theorem. This recall file intentionally introduces no parallel public wrappers such as functionalConstraintValueObjective, functionalConstraintValueFunction, or a specialized ..._eq_of_isMinOn theorem. Downstream files should use the owner max-type expression and the corresponding subtype owner value directly.

recall LagrangianProblem.constrainedAuxiliaryObjective

Theorem 2.45

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.45: if a finite max-type objective has μ-strongly convex L-smooth component functions, admits a global minimizer xStar, and the exact accelerated proximal-gradient scheme is started from an admissible parameter α₀, then the objective gap along the iterates satisfies the displayed hyperbolic estimate.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
variable {ι : Type*} [Fintype ι] [Nonempty ι]
open AffineMap
open scoped MaxTypeStep StrongConvexSmooth
variable {μ L : ℝ} (problem : SmoothMinimaxProblem E ι μ L)
local notation "Q" => problem.feasibleSet
variable (hfeasible_univ : problem.feasibleSet = Set.univ)
local notation "fObj" => maxTypeObjective problem.components
variable (xStar : E)
variable (hL : 0 < L)
variable (x0 : E)
local notation "γL" => (Units.mk0 (Real.toNNReal L) (by positivity) : NNRealˣ)
local notation "qf" => q[μ, L]
local notation "αRange" => Set.Ioc (Real.sqrt qf) (constantStepSchemeIIAlphaUpper qf)
variable (α0 : ℝ)
local notation "γ0" => optimal_method_alpha0_initial_curvature μ L α0
variable (hα0 : α0 ∈ αRange)
local notation "x0Q" =>
  Subtype.mk x0 (x0_mem_feasible problem hfeasible_univ x0)
local notation "xSeq" =>
  constantStepSchemeIIMinimaxX problem hL x0Q (Subtype.mk α0 hα0)
theorem acceleratedMaxTypeProximal_hyperbolic_objective_gap_le
    (hα0 : α0 ∈ αRange)
    (hxStar : IsMinOn fObj Set.univ xStar)
    (k : ℕ) :
    fObj (xSeq k) - fObj xStar ≤
      (4 * μ *
        (fObj x0 - fObj xStar +
          (γ0 / 2) * ‖x0 - xStar‖ ^ (2 : ℕ))) /
        ((γ0 - μ) *
          (Real.exp
              (((k + 1 : ℝ) / 2) * Real.sqrt qf) -
            Real.exp
              (-(((k + 1 : ℝ) / 2) * Real.sqrt qf))) ^
            (2 : ℕ))

Definition 2.46

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.46 lies in the constrained max-type affine-linearization domain on a real Hilbert space. Sampled owner-style declarations: * LagrangianProblem.constrainedAuxiliaryComponents in Lemma_2_21, the canonical finite component family encoding the shifted objective and the constraint functions; * LagrangianProblem.constrainedAuxiliaryComponents_zero and LagrangianProblem.constrainedAuxiliaryComponents_succ in Lemma_2_21, the source-facing split of index 0 versus the successor constraint indices; * maxTypeAffineApproximation in Definition_2_39, the owner affine linearization of a finite max-type family at a base point; * maxTypeAffineApproximation_apply in Definition_2_39, the pointwise bridge for that owner affine model; * firstOrderTaylorModelAt in Chap01/Definition_1_4_17, the canonical affine owner of each single component. Best owner abstraction: * maxTypeAffineApproximation (problem.constrainedAuxiliaryComponents t) xBar. Primitive data: * the owner constrained problem problem : LagrangianProblem E m; * the parameter t and base point xBar. Derived API: * the pointwise evaluation formula from maxTypeAffineApproximation_apply; * the source-facing 0/i.succ split of problem.constrainedAuxiliaryComponents t from constrainedAuxiliaryComponents_zero and constrainedAuxiliaryComponents_succ. Source/core/bridge triage: * source-facing: the affine model whose component 0 is the shifted objective affine term and whose successor components are the constraint affine terms; * core/canonical: maxTypeAffineApproximation (problem.constrainedAuxiliaryComponents t) xBar; * bridge/view: maxTypeAffineApproximation_apply together with the zero/successor component simplification lemmas from Lemma_2_21. Definition 2.46 therefore uses the chapter owner expression directly. This file is recall-only: it introduces no parallel public functionalConstraintAffineApproximation wrapper, and it does not add a second theorem surface whose statement only repackages the owner through implementation bookkeeping.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {m : ℕ} recall LagrangianProblem.constrainedAuxiliaryComponents

Theorem 2.46

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 2.46: every constant-step scheme III trajectory for a smooth μ-strongly convex objective satisfies the geometric objective-gap bound f(x_k) - f(x*) ≤ 2 (1 - √q[μ, L])^k (f(x₀) - f(x*)) for all k ≥ 0. The admissible range q[μ, L] ∈ (0, 1] is carried by the owner scheme hypothesis scheme : ConstantStepSchemeIII f L q[μ, L] x₀, so no separate public μ ≤ L binder is kept. The textbook recursion y_k = x_k + β (x_k - x_{k-1}), x_{k+1} = y_k - (1 / L) ∇ f(y_k) with x_{-1} = x₀ is encoded by ConstantStepSchemeIII via the shifted auxiliary sequence y_{k+1}.

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L : ℝ} {f : E → ℝ} local notation "qf" => q[μ, L] theorem constantStepSchemeIII_objective_gap_le_geometric_rate (hf : IsStrongConvexSmoothObjective μ L f) {xStar : E} (hxStar : IsMinOn f Set.univ xStar) (x0 : E) (scheme : ConstantStepSchemeIII f L qf x0) (k : ℕ) : f (scheme k) - f xStar ≤ 2 * (1 - Real.sqrt qf) ^ k * (f x0 - f xStar)

Definition 2.47

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.47: the constrained gradient mapping x_f(t; xBar; γ) is the chosen exact step of the quadratically regularized affine model for the fixed-t bridge problem on the ambient constraint set Q.

open scoped Gradient MaxTypeStep
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} {μ L : ℝ}
namespace SmoothFunctionalConstraintsMinimizationProblem
variable [ProperSpace E]
variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L) (t : ℝ)
abbrev constrainedGradientMapping
    (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L)
    (t : ℝ) (xBar : E) (γ : NNRealˣ) : E :=
  x_f[problem.ambientSet | (problem.toParametricSmoothMinimaxProblem t).components; γ](xBar)

Remark 2.47.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Remark 2.47.1 (1): for every t, the constrained gradient mapping is well defined as the unique feasible minimizer of the regularized affine model of the fixed-t bridge problem.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} {μ L : ℝ}
namespace SmoothFunctionalConstraintsMinimizationProblem
variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L)
variable (t : ℝ)
theorem existsUnique_constrainedGradientMapping
    (xBar : E) (γ : NNRealˣ) :
    ∃! xPlus : E,
      xPlus ∈ problem.ambientSet ∧
        IsMinOn
          (quadraticallyRegularizedObjective
            ((problem.toParametricSmoothMinimaxProblem t).affineApproximation xBar)
            γ
            xBar)
          problem.ambientSet
          xPlus

Definition 2.48

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.48: the textbook update t^*(xBar, t) is the infimum of the roots of the owner constrained regularized model value τ ↦ problem.regularizedModelValue τ xBar μ that are not smaller than the current parameter t.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} {μ L : ℝ}
namespace SmoothFunctionalConstraintsMinimizationProblem
def regularizedModelValueRoot
    (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L)
    (xBar : E) (t : ℝ) : ℝ :=
  sInf {τ : ℝ | t ≤ τ ∧ problem.regularizedModelValue τ xBar μ = 0}

Definition 2.49

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.49: the constrained regularized local-model value is the owner scalar function problem.regularizedModelValue.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} {μ L : ℝ}
variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L)
recall SmoothFunctionalConstraintsMinimizationProblem.regularizedModelValue

Definition 2.50

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 2.50: the quadratically regularized first-order local subproblem at xBar minimizes the regularized affine model of the objective over Q, subject to the regularized affine inequality constraints.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {m : ℕ} {μ L : ℝ} namespace SmoothFunctionalConstraintsMinimizationProblem variable (problem : SmoothFunctionalConstraintsMinimizationProblem E m μ L) variable (xBar : E) (γ : ℝ) local notation "regularizedAt" => fun f : E → ℝ ↦ quadraticallyRegularizedObjective (firstOrderTaylorModelAt f xBar) γ xBar def regularizedLocalSubproblem : FunctionalConstraintsMinimizationProblem E m

2.1 — Minimization of Smooth Functions

Example 2.1.1.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Example 2.1.1.1: Every function of the form x ↦ α + ⟪a, x⟫ on a real inner product space is convex on a convex set. The textbook ℝⁿ statement is the Euclidean specialization.

open scoped RealInnerProductSpace universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem convexOn_affine_inner (s : Set E) (hs : Convex ℝ s) (alpha : ℝ) (a : E) : ConvexOn ℝ s (fun x ↦ alpha + ⟪a, x⟫)

Example 2.1.1.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Example 2.1.1.2: the canonical quadratic objective on ℝ^n with positive-semidefinite Hessian data is convex.

open Matrix variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ open scoped RealInnerProductSpace namespace Matrix.PosSemidef theorem convexOn_quadraticObjective {A : Mat} (hA : A.PosSemidef) (alpha : ℝ) (a : E) : ConvexOn ℝ Set.univ (quadraticObjective alpha a A)

Example 2.1.1.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Example 2.1.1.3 (1): the exponential function belongs to 𝓕¹(ℝ).

open scoped ConvexC1 theorem exp_convexC1On_univ : Real.exp ∈ 𝓕¹(Set.univ)

Example 2.1.1.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Example 2.1.1.4 is a source-facing recall in finite-dimensional convex analysis of log-sum-exp. Sampled owner-style declarations in this domain: * project convexOn_log_sum_exp_of_convexOn, the owner theorem for finite-family log-sum-exp on a common convex domain * mathlib EuclideanSpace.projₗ, the canonical coordinate linear functional on Euclidean space * mathlib LinearMap.convexOn, which derives convexity of linear maps on convex domains Best owner abstraction: * core/canonical: convexOn_log_sum_exp_of_convexOn * source-facing bridge used here: the Set.univ specialization of convexOn_log_sum_exp_of_convexOn Primitive data: * the ambient Euclidean space E * the coordinate functionals EuclideanSpace.projₗ i * the positive arity n : ℕ+ Derived API: * convexity of each coordinate map from LinearMap.convexOn * the source-facing specialization x ↦ log (∑ i = 1, …, n, exp (x⁽ⁱ⁾)) Source/core/bridge triage: * source-facing: Example 2.1.1.4 as the convexity statement for x ↦ log (∑ i = 1, …, n, exp (x⁽ⁱ⁾)) * core/canonical: convexOn_log_sum_exp_of_convexOn * bridge/view: specialization of convexOn_log_sum_exp_of_convexOn to Set.univ, then to the canonical coordinate projections The previous whole-space bridge theorem added no owner-level API beyond the Set.univ specialization of convexOn_log_sum_exp_of_convexOn. This file therefore uses the owner theorem directly and checks the coordinate-projection specialization instead of depending on a parallel bridge name.

open scoped BigOperators variable {n : ℕ+} local notation "E" => EuclideanSpace ℝ (Fin n) #check (show ConvexOn ℝ Set.univ (fun x : E ↦ Real.log (∑ i : Fin n, Real.exp (x i))) from convexOn_log_sum_exp_of_convexOn Set.univ Finset.univ_nonempty (fun i _ ↦ (EuclideanSpace.projₗ i).convexOn convex_univ))

Supporting modules

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

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

  • _probe_214.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source