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.
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 gradientMethodDefinition 2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 IsMinOnLemma 2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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_comboProposition 2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 2.1 is the direct owner recall of the dual-pairing estimate attached to Seminorm.dualNorm.
#check Seminorm.inner_le_dualNorm_mulText 2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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) ≥ finalRhsTheorem 2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 xStarAlgorithm 2.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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_affineMapProposition 2.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 fText 2.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 γ) xBarTheorem 2.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 yAlgorithm 2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 : ℝ) :
ℕ → StateDefinition 2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 ∈ QLemma 2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 ≥ finalRhsTheorem 2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 fAlgorithm 2.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 fLemma 2.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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‖ ^ 2Proposition 2.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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).IsPositiveAlgorithm 2.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 × EDefinition 2.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
Lemma 2.6 is the direct owner recall of nonnegative weighted-sum closure for StrongConvexOnWith.
recall StrongConvexOnWith.nonneg_combo_interProposition 2.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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) ^ 2Algorithm 2.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 fLemma 2.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 kAlgorithm 2.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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‖ ^ 2Algorithm 2.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 kLemma 2.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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_equationTheorem 2.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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_zeroAlgorithm 2.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 kLemma 2.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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_leProposition 2.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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_equationText 2.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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,*] ^ 2Definition 2.12
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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_epigraphProposition 2.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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) hDefinition 2.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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) = 0Text 2.13
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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‖ ^ 2Definition 2.14
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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‖ ^ 2Proposition 2.14
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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‖ ^ 2Text 2.14
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 xLemma 2.15
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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) / 3Theorem 2.16
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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 : ℝ → ℝ) 0Definition 2.19
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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 fLemma 2.20
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 simpleSetEstimatingModelProposition 2.20
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 ≥ finalRhsDefinition 2.21
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 tProposition 2.21
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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 tProposition 2.22
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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_intermediateDefinition 2.23
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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 quadraticallyRegularizedObjectiveLemma 2.24
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 SetConstrainedMinimizationProblemLemma 2.25
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Theorem 2.28 (1), (2), (3), and (9) are direct owner recalls.
open AffineMap
open PointedCone (hull)
open scoped Pointwise
recall Convex.interDefinition 2.29
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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.
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.dualFunctionProposition 2.31
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
Theorem 2.32 is the direct owner recall of the closed-set unique-minimizer theorem for StrongConvexOnWith.
recall StrongConvexOnWith.existsUnique_isMinOn_of_isClosedDefinition 2.33
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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₀ pDefinition 2.34
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 ^ 2Proposition 2.34
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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ˣ) :
EProposition 2.35
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 = tStarTheorem 2.35
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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) = xStarDefinition 2.35.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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ˣ) :
EDefinition 2.36
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 simpleSetEstimatingModelTheorem 2.37
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 maxTypeAffineApproximationTheorem 2.40
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Theorem 2.40 is the direct owner recall of constrained quadratic growth at a feasible minimizer.
recall StrongConvexOnWith.quadratic_growth_of_isMinOn_of_memDefinition 2.41
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
Theorem 2.41 is the direct owner recall of the unique feasible minimizer theorem for SmoothMinimaxProblem.
namespace SmoothMinimaxProblem
recall existsUnique_isMinOnRemark 2.41.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 SetConstrainedMinimizationProblemTheorem 2.43
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.constrainedAuxiliaryObjectiveTheorem 2.45
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.constrainedAuxiliaryComponentsTheorem 2.46
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 m2.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.
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.
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.
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.
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.
-
ReciprocalEpigraphOnPositiveRay.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
-
_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.