Chapter 01 — Nonlinear Optimization

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

Definition 1.4.1

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

Source header · Attribution source

Definition 1.4.1 is a source-facing recall in the order-theoretic monotonicity domain. Layer targeted by this refinement: * source-facing recall of the core/canonical owner predicate Antitone Sampled owner-style declarations: * Antitone, the owner notion of a decreasing sequence on a preorder * antitone_nat_of_succ_le, the canonical ℕ constructor from the one-step decrease condition Primitive data: * the antitonicity condition Antitone a Derived API: * the textbook successor-step criterion ∀ k, a (k + 1) ≤ a k, obtained by evaluating Antitone a on Nat.le_succ and conversely rebuilding Antitone a with antitone_nat_of_succ_le This file therefore introduces no parallel wrapper API for relaxation sequences.

#check (Antitone : (ℕ → ℝ) → Prop)

Proposition 1.4.2

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

Source header · Attribution source

Proposition 1.4.2: A bounded-below relaxation sequence converges to the infimum of its range.

open Filter universe u theorem relaxationSequence_tendsto_inf {α : Type u} [TopologicalSpace α] [ConditionallyCompletePartialOrderInf α] [InfConvergenceClass α] {a : ℕ → α} (ha : ∀ n : ℕ, a (n + 1) ≤ a n) (hbdd : BddBelow (Set.range a)) : Tendsto a atTop (nhds (sInf (Set.range a)))

Definition 1.4.3

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

Source header · Attribution source

Definition 1.4.3: an unconstrained smooth minimization problem on ℝⁿ is a set-constrained minimization problem whose canonical earlier Chapter 1 owner is both unconstrained and smooth.

namespace SetConstrainedMinimizationProblem variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) open FunctionalConstraintsMinimizationProblem open GeneralMinimizationProblem variable (problem : SetConstrainedMinimizationProblem E) #check ( ¬ problem.toGeneralMinimizationProblem.IsConstrained ∧ problem.toGeneralMinimizationProblem.IsSmooth )

Definition 1.4.4

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

Source header · Attribution source

Definition 1.4.4 lies in the finite-dimensional Euclidean inner-product-space domain. Relevant owner-style declarations sampled before refining: * inner ℝ, the canonical inner product on E * (fun x : E ↦ ‖x‖), the inherited norm on E * mathlib EuclideanSpace.inner_eq_star_dotProduct, the canonical coordinate bridge for the Euclidean inner product * mathlib EuclideanSpace.norm_eq, the canonical sum-of-squares norm formula Best owner abstraction: * the canonical InnerProductSpace and Norm structure on EuclideanSpace ℝ (Fin n) Primitive data: * vectors x y : E Derived API: * EuclideanSpace.inner_eq_star_dotProduct, the coordinate formula for the Euclidean inner product * EuclideanSpace.norm_eq, the coordinate formula for the Euclidean norm * the real-specialized textbook rewrites below, where absolute values disappear and the dot product may be read in the usual order Source/core/bridge triage: * source-facing: the Euclidean inner product and norm on ℝⁿ * core/canonical: inner ℝ and ‖·‖ on EuclideanSpace ℝ (Fin n) * bridge/view: EuclideanSpace.inner_eq_star_dotProduct and EuclideanSpace.norm_eq The canonical owner operations come from the InnerProductSpace and Norm structures on E, and the coordinate bridges are the upstream mathlib EuclideanSpace theorems. This file therefore reuses those owners directly instead of keeping parallel local copies.

open scoped BigOperators variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) #check (inner ℝ : E → E → ℝ)

Proposition 1.4.5

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

Source header · Attribution source

Proposition 1.4.5: for a real m × n matrix, the standard Euclidean inner products on ℝ^n and ℝ^m satisfy the adjointness identity ⟨Ax, y⟩ = ⟨x, Aᵀ y⟩.

open Matrix variable {m n : ℕ} -- Proof sketch: rewrite `⟪A x, y⟫` using the owner adjointness identity for `A.toEuclideanLin`, -- then identify the adjoint with `(Aᵀ).toEuclideanLin`. theorem matrix_transpose_adjointness (A : Matrix (Fin m) (Fin n) ℝ) (x : EuclideanSpace ℝ (Fin n)) (y : EuclideanSpace ℝ (Fin m)) : inner ℝ (A.toEuclideanLin x) y = inner ℝ x (Aᵀ.toEuclideanLin y)

Definition 1.4.6

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

Source header · Attribution source

Definition 1.4.6: for a scalar-valued function on a real inner-product space, and hence in particular on ℝⁿ, differentiability at xBar is equivalent to the existence of a gradient vector whose affine approximation at xBar differs from f by a term that is little-o of ‖y - xBar‖ as y → xBar; equivalently, g is the vector representing the first-order linear part of that affine approximation.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem differentiableAt_iff_exists_sub_affineApproximation_isLittleO {f : E → ℝ} {xBar : E} : DifferentiableAt ℝ f xBar ↔ ∃ g : E, (fun y ↦ f y - (f xBar + inner ℝ g (y - xBar))) =o[nhds xBar] fun y ↦ ‖y - xBar‖

Definition 1.4.7

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

Source header · Attribution source

Definition 1.4.7 is a source-facing bridge in first-order differential calculus on Euclidean space. Source/core/bridge triage: * source-facing: the coordinate formula for the gradient in the standard Euclidean basis * core/canonical: mathlib's gradient * bridge/view: identify each coordinate with the Fréchet derivative on the corresponding basis vector Primary domain: * first-order differential calculus on finite-dimensional Euclidean spaces Relevant owner-style declarations sampled before refining: * gradient from Mathlib.Analysis.Calculus.Gradient.Basic * inner_gradient_left, which identifies fderiv ℝ f xBar with pairing against ∇ f xBar * inner_basisFun_real, which recovers standard coordinates from the Euclidean basis Owner abstraction: * the gradient vector ∇ f xBar Primitive data: * a function f * a point xBar Derived API: * the directional derivative along the ith standard basis vector * the coordinate formula gradient_eq_pi_fderiv_stdBasis under differentiability at xBar Accordingly, this file keeps the owner notion gradient and exposes only the thin Euclidean coordinate bridge, rather than introducing any parallel local gradient definition.

open scoped Gradient open EuclideanSpace universe u v recall gradient {𝕜 : Type u} {F : Type v} [RCLike 𝕜] [NormedAddCommGroup F] [InnerProductSpace 𝕜 F] [CompleteSpace F] (f : F → 𝕜) (x : F) : F

Definition 1.4.8

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

Source header · Attribution source

Definition 1.4.8: the level set 𝓛[f](a) is the canonical lower-interval preimage f ⁻¹' Set.Iic a.

universe u v open scoped LevelSetNotation variable {E : Type u} {α : Type v} [Preorder α] variable (f : E → α) (a : α) variable {x : E} #check (𝓛[f](a) : Set E)

Definition 1.4.9

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

Source header · Attribution source

Definition 1.4.9: the directions tangent to the level set of f through xbar are the unit vectors in the positive tangent cone of the level set f ⁻¹' {f xbar} at xbar. The direct membership lemma mem_tangentDirectionsToLevelSet_iff records this owner-level decomposition, and the companion theorem mem_tangentDirectionsToLevelSet_iff_exists_level_set_secant_limit records the textbook normalized-secant characterization.

open Filter open scoped Topology universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] def tangentDirectionsToLevelSet (f : E → ℝ) (xbar : E) : Set E := posTangentConeAt (f ⁻¹' {f xbar}) xbar ∩ Metric.sphere (0 : E) 1

Lemma 1.4.10

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

Source header · Attribution source

Lemma 1.4.10: if f is differentiable at xbar, then every tangent direction to the level set of f at xbar is orthogonal to the gradient at xbar.

open Filter open scoped Gradient Topology universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem inner_gradient_eq_zero_of_mem_tangentDirectionsToLevelSet {f : E → ℝ} {xbar s : E} (hf : DifferentiableAt ℝ f xbar) (hs : s ∈ tangentDirectionsToLevelSet f xbar) : inner ℝ (∇ f xbar) s = 0

Definition 1.4.11

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

Source header · Attribution source

Definition 1.4.11 is source-facing in first-order differential calculus over real normed spaces. Relevant owner-style declarations sampled before refinement: - HasDerivWithinAt - HasLineDerivAt - HasLineDerivWithinAt - HasFDerivAt.hasLineDerivAt Best owner abstraction: - the one-variable right derivative HasDerivWithinAt (fun α ↦ f (xBar + α • s)) Δ (Set.Ici (0 : ℝ)) 0 Primitive data: - f, xBar, s, and the derivative value Δ Derived API: - ambient differentiability of f at xBar gives the line-derivative owner HasLineDerivAt ℝ f (fderiv ℝ f xBar s) xBar s; - restricting that ambient derivative at 0 to Set.Ici 0 yields the textbook one-sided directional derivative along the ray. Source/core/bridge triage: - source-facing: the right derivative of the directional slice along the ray α ↦ f (xBar + α • s) - core/canonical: HasDerivWithinAt on that scalar slice over Set.Ici 0 - bridge/view: the differentiability bridge through HasLineDerivAt The ambient space is generalized from ℝⁿ to an arbitrary real normed space because no Euclidean coordinates or finite-dimensional structure enter the owner notion or the bridge theorem. The scalar field remains ℝ because the source notion is explicitly the one-sided derivative for α ↓ 0 on Set.Ici 0.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] recall HasDerivWithinAt

Proposition 1.4.12

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

Source header · Attribution source

Proposition 1.4.12: if the gradient at xBar is nonzero, then the minimum directional derivative on the unit sphere is attained at the normalized negative gradient direction. Concretely, -normalize (∇ f xBar) lies on the unit sphere and minimizes lineDeriv ℝ f xBar there. The companion lemmas lineDeriv_ge_neg_norm_of_mem_unitSphere and lineDeriv_neg_normalize_gradient_eq_neg_norm isolate the lower-bound and value computations.

open scoped Gradient open NormedSpace variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] local notation "S" => Metric.sphere (0 : E) 1 theorem lineDeriv_isMinOn_unitSphere_at_neg_normalize_gradient {f : E → ℝ} {xBar : E} (hgrad : ∇ f xBar ≠ 0) : -normalize (∇ f xBar) ∈ S ∧ IsMinOn (lineDeriv ℝ f xBar) S (-normalize (∇ f xBar))

Theorem 1.4.13

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

Source header · Attribution source

Theorem 1.4.13: a local minimizer of a real-valued function on a real inner-product space has vanishing totalized gradient.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] -- Proof sketch: if `f` is differentiable at `xStar`, apply Fermat's theorem -- `IsLocalMin.fderiv_eq_zero` and recover the gradient from `hf.hasGradientAt`; otherwise the -- totalized gradient already vanishes by `gradient_eq_zero_of_not_differentiableAt`. theorem isLocalMin_gradient_eq_zero {f : E → ℝ} {xStar : E} (hmin : IsLocalMin f xStar) : ∇ f xStar = 0

Theorem 1.4.14

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

Source header · Attribution source

Theorem 1.4.14: if xStar is a local minimizer of a function f : ℝⁿ → ℝ on the linear level set {x | A.toEuclideanLin x = b} and f is differentiable at xStar, then there is a multiplier λStar ∈ ℝᵐ such that ∇ f xStar = Aᵀ.toEuclideanLin λStar.

open Matrix open scoped Gradient variable {m n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Λ" => EuclideanSpace ℝ (Fin m) theorem exists_lagrangeMultiplier_of_isLocalMinOn_linearLevelSet (f : E → ℝ) (A : Matrix (Fin m) (Fin n) ℝ) (b : Λ) {xStar : E} (hf : DifferentiableAt ℝ f xStar) (hxStar : A.toEuclideanLin xStar = b) (hmin : IsLocalMinOn f {x | A.toEuclideanLin x = b} xStar) : ∃ lamStar : Λ, ∇ f xStar = Aᵀ.toEuclideanLin lamStar

Definition 1.4.15

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

Source header · Attribution source

Definition 1.4.15: for a differentiable real-valued function, a point is stationary exactly when it satisfies the canonical zero-gradient owner condition HasGradientAt f 0 xBar.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {xBar : E} #check HasGradientAt f 0 xBar -- Proof sketch: use `hf.hasGradientAt` to identify the canonical gradient witness at `xBar` with -- `∇ f xBar`; then `HasGradientAt.gradient` turns `HasGradientAt f 0 xBar` into the zero-gradient -- equation, and conversely `hf.hasGradientAt` rewrites `∇ f xBar = 0` back to the stationary -- owner condition.

Definition 1.4.16

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

Source header · Attribution source

Definition 1.4.16: if f : ℝⁿ → ℝ, the Hessian of f at x is the matrix of the derivative of the gradient map in the standard orthonormal basis of ℝⁿ.

open scoped Gradient universe u variable {X : Type u} [NormedAddCommGroup X] [InnerProductSpace ℝ X] [CompleteSpace X] variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "e" => EuclideanSpace.basisFun (Fin n) ℝ abbrev hessianMatrix (f : E → ℝ) (x : E) : Matrix (Fin n) (Fin n) ℝ := LinearMap.toMatrixOrthonormal e (hessian f x)

Definition 1.4.17

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

Source header · Attribution source

Definition 1.4.17: the second-order Taylor model of f at x.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def secondOrderTaylorModelAt (f : E → ℝ) (x : E) : E → ℝ := fun y ↦ f x + inner ℝ (∇ f x) (y - x) + (1 / 2 : ℝ) * inner ℝ (hessian f x (y - x)) (y - x)

Definition 1.4.18

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

Source header · Attribution source

Definition 1.4.18 is a source-facing recall of positive semidefinite and positive definite real square matrices, implemented by the generic matrix-positivity owners below and specialized in the textbook to ℝ. Primary domain: - matrix positivity and the Loewner order on matrices over ℝ or ℂ. Sampled owner-style declarations: - Matrix.PosSemidef - Matrix.PosDef - Matrix.nonneg_iff_posSemidef - Matrix.isStrictlyPositive_iff_posDef Best owner abstraction: - the canonical matrix-positivity owners Matrix.PosSemidef and Matrix.PosDef Primitive data: - a square matrix B Derived API: - the order-notation bridges Matrix.nonneg_iff_posSemidef - the strict-positivity bridge Matrix.isStrictlyPositive_iff_posDef Source/core/bridge triage: - source-facing: the textbook notions B ≥ 0 and the positive-definite shorthand B > 0 for real square matrices - core/canonical: Matrix.PosSemidef and Matrix.PosDef - bridge/view: Matrix.nonneg_iff_posSemidef and the canonical strict-positivity bridge Matrix.isStrictlyPositive_iff_posDef This file therefore recalls the owner predicates directly, keeping the order-notation lemmas only as companion bridges for the textbook notation B ≥ 0 and the positive-definite shorthand B > 0; in mathlib, the latter is bridged by IsStrictlyPositive B ↔ B.PosDef, not by the plain strict order relation 0 < B.

open scoped ComplexOrder MatrixOrder recall Matrix.PosSemidef {n : Type*} {R : Type*} [Ring R] [PartialOrder R] [StarRing R] (B : Matrix n n R) : Prop

Theorem 1.4.19

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

Source header · Attribution source

Theorem 1.4.19: if f : ℝⁿ → ℝ is twice continuously differentiable at x, then the Hessian matrix of f at x is symmetric.

open InnerProductSpace open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {n : ℕ} local notation "EFin" => EuclideanSpace ℝ (Fin n) local notation "e" => EuclideanSpace.basisFun (Fin n) ℝ theorem hessianMatrix_isSymm_of_contDiffAt {f : EFin → ℝ} {x : EFin} (hf : ContDiffAt ℝ 2 f x) : (∇² f x).IsSymm

Theorem 1.4.20

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

Source header · Attribution source

Theorem 1.4.20: if a real-valued function on a real complete inner product space is differentiable at xStar and the gradient map ∇ f is differentiable at xStar, then every local minimizer xStar has vanishing gradient and nonnegative Hessian quadratic form in every direction at xStar.

open scoped Gradient variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem isLocalMin_gradient_eq_zero_and_hessian_quadratic_nonneg {f : E → ℝ} {xStar : E} (hf : DifferentiableAt ℝ f xStar) (hgradDiff : DifferentiableAt ℝ (∇ f) xStar) (hmin : IsLocalMin f xStar) : ∇ f xStar = 0 ∧ ∀ s : E, 0 ≤ inner ℝ (hessian f xStar s) s

Theorem 1.4.21

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

Source header · Attribution source

Theorem 1.4.21: if f : ℝⁿ → ℝ is stationary at xStar, the gradient map ∇ f is differentiable at xStar, and the Hessian matrix ∇² f xStar is positive definite, then xStar is a strict local minimizer of f.

open scoped Gradient universe u variable {n : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} {xStar : EuclideanSpace ℝ (Fin n)} theorem strict_local_minimizer_of_gradient_zero_of_hessian_posDef (hstationary : HasGradientAt f 0 xStar) (hgradDiff : DifferentiableAt ℝ (∇ f) xStar) (hH : (∇² f xStar).PosDef) : ∃ δ : ℝ, 0 < δ ∧ ∀ y : EuclideanSpace ℝ (Fin n), y ≠ xStar → dist y xStar < δ → f xStar < f y

Definition 1.5.1

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

Source header · Attribution source

Membership in the textbook class 𝒞^{k,p}_{L}(Q) yields the Taylor witness and the corresponding Lipschitz bound from Definition 1.5.1.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (k p : ℕ) (L : NNReal) (f : E → ℝ) (Q : Set E) local notation "TaylorSeries" => E → FormalMultilinearSeries ℝ E ℝ notation "𝒞^{" k "," p "}_{" L "}(" Q ")" => taylorCoeffLipschitzClass k p L Q namespace taylorCoeffLipschitzClass theorem exists_taylorSeries {k p : ℕ} {L : NNReal} {f : E → ℝ} {Q : Set E} (hf : f ∈ 𝒞^{k,p}_{L}(Q)) : ∃ P : TaylorSeries, HasFTaylorSeriesUpToOn k f P Q ∧ LipschitzOnWith L (fun x ↦ P x p) Q

Definition 1.5.2

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

Source header · Attribution source

Definition 1.5.2: the textbook class C_{L}^{1,1}(ℝ^n) is represented in this chapter by the conjunction ContDiff ℝ 1 f ∧ LipschitzWith L (∇ f), meaning that f is C¹ and its gradient is globally L-Lipschitz.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {L : NNReal} #check (ContDiff ℝ 1 f ∧ LipschitzWith L (∇ f))

Definition 1.5.3

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

Source header · Attribution source

Definition 1.5.3: the textbook class C_M^{2,2}(ℝⁿ) is represented in this project by the canonical owner HasLipschitzContinuousHessian M f, written on theorem surfaces as f ∈ C22[M]. Its defining consequences are the inherited C² regularity and the displayed Hessian Lipschitz estimate ‖∇² f(x) - ∇² f(y)‖ ≤ M ‖x - y‖.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {M : NNReal} {f : E → ℝ} recall HasLipschitzContinuousHessian

Lemma 1.5.4

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

Source header · Attribution source

Lemma 1.5.4 in textbook C² form: if f is twice continuously differentiable, then the gradient-Lipschitz condition is equivalent to the pointwise Hessian operator-norm bound.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {L : NNReal} {f : E → ℝ} theorem lipschitzGradient_iff_norm_hessian_le_of_contDiff (hf : ContDiff ℝ 2 f) : LipschitzWith L (∇ f) ↔ ∀ x : E, ‖hessian f x‖ ≤ (L : ℝ)

Proposition 1.5.5

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

Source header · Attribution source

Proposition 1.5.5: if two functions belong to the textbook class C^{k,p}_L(Q), written in this file as 𝒞^{k,p}_{L}(Q), then any linear combination remains in the same class, with Lipschitz constant ‖α₁‖₊ * L₁ + ‖α₂‖₊ * L₂.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {k p : ℕ} namespace taylorCoeffLipschitzClass theorem smul_add {Q : Set E} {L₁ L₂ : NNReal} {f₁ f₂ : E → ℝ} {α₁ α₂ : ℝ} (hf₁ : f₁ ∈ 𝒞^{k,p}_{L₁}(Q)) (hf₂ : f₂ ∈ 𝒞^{k,p}_{L₂}(Q)) : α₁ • f₁ + α₂ • f₂ ∈ 𝒞^{k,p}_{(‖α₁‖₊ * L₁ + ‖α₂‖₊ * L₂)}(Q)

Proposition 1.5.6

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

Source header · Attribution source

Proposition 1.5.6: the affine function x ↦ α + ⟪a, x⟫ is C¹ and its gradient is globally 0-Lipschitz, equivalently it belongs to the class C^{1,1}_0. This is the intrinsic Hilbert-space form of the textbook ℝⁿ statement.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem affineFunction_contDiff_and_gradient_lipschitz_zero (α : ℝ) (a : E) : ContDiff ℝ 1 (fun x : E ↦ α + inner ℝ a x) ∧ LipschitzWith 0 (∇ (fun x : E ↦ α + inner ℝ a x))

Proposition 1.5.7

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

Source header · Attribution source

Proposition 1.5.7: if A is symmetric, then the quadratic objective quadraticObjective α a A is C¹ on ℝⁿ and its gradient is globally Lipschitz with constant equal to the operator norm of A, i.e. it belongs to C^{1,1}_L(ℝⁿ) for L = ‖A‖.

open Matrix open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem symmetric_quadratic_contDiff_and_gradient_lipschitz (α : ℝ) (a : E) (A : Matrix (Fin n) (Fin n) ℝ) (hA : A.IsSymm) : ContDiff ℝ 1 (quadraticObjective α a A) ∧ LipschitzWith ‖A.toEuclideanLin.toContinuousLinearMap‖₊ (∇ (quadraticObjective α a A))

Proposition 1.5.8

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

Source header · Attribution source

open scoped Gradient theorem sqrt_one_add_sq_mem_contDiffOne_withLipschitzGradient_one : ContDiff ℝ 1 (fun x : ℝ ↦ √(1 + x ^ 2)) ∧ LipschitzWith 1 (∇ (fun x : ℝ ↦ √(1 + x ^ 2)))

Proposition 1.5.9

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

Source header · Attribution source

Proposition 1.5.9: if the affine-model remainder of f with respect to a field g is globally bounded by (L / 2) ‖y - x‖², then g is globally L-Lipschitz. This statement uses only the intrinsic field g, so it does not assume ambient completeness.

open scoped Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {L : NNReal} {f : E → ℝ} {g : E → E}
variable (hquad :
  ∀ x y,
    |f y - affineModelAt f g x y| ≤
      (L : ℝ) / 2 * ‖y - x‖ ^ 2)
include hquad
theorem lipschitzGradient_of_sub_affineApproximation_norm_sq_bound :
    LipschitzWith L g

Lemma 1.5.10

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

Source header · Attribution source

Lemma 1.5.10: if f belongs to the textbook class C^{1,1}_L(ℝⁿ), then the first-order Taylor remainder at x along y - x is bounded in absolute value by (L / 2) ‖y - x‖².

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {L : NNReal} {f : E → ℝ} variable (hf : ContDiff ℝ 1 f) (hgrad : LipschitzWith L (∇ f)) include hf hgrad omit hf hgrad include hf hgrad lemma norm_taylor_remainder_le_half_lipschitzGradient_mul_sq (x y : E) :

Lemma 1.5.11

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

Source header · Attribution source

Lemma 1.5.11 (1): if f ∈ C_M^{2,2}(ℝⁿ), then the first-order Taylor remainder of the gradient at x, linearized by the Hessian hessian f x, is bounded by (M / 2) ‖y - x‖².

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {M : NNReal} {f : E → ℝ} namespace HasLipschitzContinuousHessian theorem gradient_deviation_le (hf : f ∈ C22[M]) (x y : E) : ‖∇ f y - ∇ f x - hessian f x (y - x)‖ ≤ ((M : ℝ) / 2) * ‖y - x‖ ^ (2 : ℕ)

Theorem 1.5.12

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

Source header · Attribution source

Theorem 1.5.12: if f : ℝⁿ → ℝ has M-Lipschitz Hessian, then ∇² f x and ∇² f y differ by at most M ‖y - x‖ I in the Loewner order.

open scoped Gradient MatrixOrder universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {n : ℕ} local notation "EFin" => EuclideanSpace ℝ (Fin n) theorem hessianMatrix_loewner_bounds_of_hessian_lipschitz {M : NNReal} {f : EFin → ℝ} (hf : f ∈ C22[M]) (x y : EFin) : let s : ℝ := (M : ℝ) * ‖y - x‖ ∇² f x - s • 1 ≤ ∇² f y ∧ ∇² f y ≤ ∇² f x + s • 1

Algorithm 1.6.1

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

Source header · Attribution source

Algorithm 1.6.1: the gradient method associated to an initial point x₀, a step-size schedule hₖ, and an objective f is the trajectory defined recursively by xₖ₊₁ = xₖ - hₖ • ∇ f (xₖ).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def gradientMethod (stepSize : ℕ → ℝ) (f : E → ℝ) (x0 : E) : ℕ → E

Definition 1.6.2

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

Source header · Attribution source

Definition 1.6.2 is a source-facing recall in the gradient-method step-size domain. Layer targeted by this refinement: * source-facing recall of the owner schedule type already used by gradientMethod Primary domain: * preselected scalar schedules for first-order methods Relevant owner-style declarations sampled before refining: * gradientMethod in Algorithm_1_6_1.lean, whose primitive input already includes stepSize : ℕ → ℝ * SatisfiesExactLineSearchAlong in Definition_1_6_3.lean, which treats a schedule as owner data and adds optimization properties only as predicates * DampedNewton.Method.stepSize in Algorithm_1_7_2.lean, which likewise stores the schedule directly as ℕ → ℝ * the constant-step bridge gradientMethod_const_eq_iterate in Algorithm_1_6_1.lean, which uses the literal schedule fun _ ↦ α rather than a separate wrapper owner Source/core/bridge triage: * source-facing: the prescribed step-size rule k ↦ hₖ * core/canonical: the schedule type ℕ → ℝ * bridge/view: direct literal schedules such as fun _ ↦ h or fun k ↦ h / Real.sqrt (k + 1) Owner abstraction: * the preselected schedule type ℕ → ℝ Primitive data: * only the scalar rule k ↦ hₖ Derived API: * positivity and stronger analytic side conditions on a schedule * textbook examples, which should remain direct literal schedules rather than separate public owners This file therefore keeps the main entry as the canonical type expression itself and shows the textbook constant and inverse-square-root schedules directly by literal functions. It introduces no separate public wrapper for either example.

#check (ℕ → ℝ)

Definition 1.6.3

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

Source header · Attribution source

A step-size schedule satisfies the exact line-search rule along the trajectory xₖ and search directions pₖ when every hₖ is a nonnegative minimizer of h ↦ f (xₖ - h • pₖ) on [0, ∞).

universe u open scoped Gradient variable {X : Type u} [AddCommGroup X] [Module ℝ X] def SatisfiesExactLineSearchAlong (f : X → ℝ) (x p : ℕ → X) (stepSize : ℕ → ℝ) : Prop := ∀ k : ℕ, stepSize k ∈ Set.Ici (0 : ℝ) ∧ IsMinOn (fun h : ℝ ↦ f (x k - h • p k)) (Set.Ici (0 : ℝ)) (stepSize k)

Definition 1.6.4

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

Source header · Attribution source

Definition 1.6.4: a step-size schedule hₖ satisfies the Armijo rule for the gradient-method trajectory started at x₀ when the objective is differentiable at every iterate, so the displayed ∇ f(xₖ) is genuine, 0 < α < β < 1, every step size is positive, and the consecutive iterates satisfy the two-sided Armijo decrease bounds.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) (stepSize : ℕ → ℝ) (x0 : E) (α β : ℝ) def SatisfiesArmijoRule (f : E → ℝ) (stepSize : ℕ → ℝ) (x0 : E) (α β : ℝ) : Prop := let traj := gradientMethod stepSize f x0 (∀ k : ℕ, DifferentiableAt ℝ f (traj k)) ∧ 0 < α ∧ α < β ∧ β < 1 ∧ (∀ k : ℕ, 0 < stepSize k) ∧ ∀ k : ℕ, α * inner ℝ (∇ f (traj k)) (traj k - traj (k + 1)) ≤ f (traj k) - f (traj (k + 1)) ∧ f (traj k) - f (traj (k + 1)) ≤ β * inner ℝ (∇ f (traj k)) (traj k - traj (k + 1))

Definition 1.6.5

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

Source header · Attribution source

Definition 1.6.5 (1): an objective f : E → ℝ belongs to the textbook class 𝒢_* when f ∈ C^{1,1}_L and f is bounded below. Specializing E to ℝⁿ recovers the textbook formulation.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {L : NNReal} def IsGStar (f : E → ℝ) (L : NNReal) : Prop := ContDiff ℝ 1 f ∧ LipschitzWith L (∇ f) ∧ BddBelow (Set.range f)

Lemma 1.6.6

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

Source header · Attribution source

Lemma 1.6.6: specializing the owner quadratic upper bound at the trial point x - h • ∇ f x gives the standard gradient-step estimate f (x - h ∇ f x) ≤ f x - h (1 - L h / 2) ‖∇ f(x)‖².

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {L : NNReal} {f : E → ℝ} variable (hf : ContDiff ℝ 1 f) (hgrad : LipschitzWith L (∇ f)) include hf hgrad theorem gradient_step_value_decrease_of_contDiffOne_withLipschitzGradient (x : E) (h : ℝ) : f (x - h • ∇ f x) ≤ f x - (h * (1 - ((L : ℝ) * h) / 2)) * ‖∇ f x‖ ^ (2 : ℕ)

Proposition 1.6.7

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

Source header · Attribution source

Proposition 1.6.7 (1): if a gradient method for a C_L^{1,1}(ℝⁿ) objective uses the constant step size h, then f(x_k) - f(x_(k+1)) ≥ h (1 - L h / 2) ‖∇ f(x_k)‖² for every k.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {L : NNReal} {f : E → ℝ} {x0 : E} variable (h : ℝ) local notation "traj" => gradientMethod (fun _ ↦ h) f x0 -- Proof sketch: apply the owner one-step estimate -- `gradient_step_value_decrease_of_contDiffOne_withLipschitzGradient` at `x = traj k`, rewrite -- `traj (k + 1)` using `gradientMethod_succ`, and use that `traj` is already the constant-step -- trajectory. theorem gradientMethod_value_drop_ge_sqnorm_of_constant_stepsize (hf : ContDiff ℝ 1 f) (hgrad : LipschitzWith L (∇ f)) (k : ℕ) : f (traj k) - f (traj (k + 1)) ≥ (h * (1 - ((L : ℝ) * h) / 2)) * ‖∇ f (traj k)‖ ^ (2 : ℕ)

Theorem 1.6.8

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

Source header · Attribution source

Theorem 1.6.8: for the gradient-method trajectory gradientMethod stepSize f x0, any uniform descent bound of the form (ω / L) ‖∇ f(xₖ)‖² ≤ f(xₖ) - f(xₖ₊₁) yields the telescoping estimate (ω / L) ∑_{k=0}^N ‖∇ f(xₖ)‖² ≤ f(x₀) - f(x_{N+1}) ≤ f(x₀) - f^*, where fStar is the exact infimum value of f.

open scoped BigOperators Gradient MinGradientNormAlongIterates universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} variable {L ω fStar : ℝ} variable (stepSize : ℕ → ℝ) (x0 : E) local notation "traj" => gradientMethod stepSize f x0 variable (hdesc : ∀ k : ℕ, (ω / L) * ‖∇ f (traj k)‖ ^ (2 : ℕ) ≤ f (traj k) - f (traj (k + 1))) -- Proof sketch: sum the assumed descent inequalities over `k = 0, …, N` and telescope the left -- side to obtain the first inequality; the second follows from the lower-bound hypothesis -- applied to the iterate `traj (N + 1)`. theorem squared_gradient_norm_sum_le_and_value_gap_le (hdesc : ∀ k : ℕ, (ω / L) * ‖∇ f (traj k)‖ ^ (2 : ℕ) ≤ f (traj k) - f (traj (k + 1))) (hfStar : IsGLB (Set.range f) fStar) (N : ℕ) : ((ω / L) * ∑ k ∈ Finset.range (N + 1), ‖∇ f (traj k)‖ ^ (2 : ℕ)) ≤ f x0 - f (traj (N + 1)) ∧ f x0 - f (traj (N + 1)) ≤ f x0 - fStar

Definition 1.6.9

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

Source header · Attribution source

Definition 1.6.9: a minimization process has convergence rate of order φ when its optimization error sequence is nonnegative, converges to 0, and is eventually bounded above by a positive multiple of φ.

open Asymptotics Filter def HasConvergenceRateOfOrder (r φ : ℕ → ℝ) : Prop := IsOptimizationErrorSequence r ∧ ∃ C > 0, ∀ᶠ N in atTop, r N ≤ C * φ N

Proposition 1.6.10

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

Source header · Attribution source

Proposition 1.6.10: if the textbook rate estimate g_N^* ≤ [ω⁻¹ L (f(x₀) - f^*)]^{1/2} / (N + 1)^{1/2} holds and N + 1 ≥ L (f(x₀) - f^*) / (ω ε^2), then g_N^* ≤ ε.

universe u variable {α : Type u} {f : α → ℝ} {x0 : α} {gStar : ℕ → ℝ} {L ω fStar : ℝ} theorem le_of_complexity_bound_from_rate_estimate (hRate : ∀ N : ℕ, gStar N ≤ Real.sqrt ((L * (f x0 - fStar)) / ω) / Real.sqrt ((N : ℝ) + 1)) {N : ℕ} {ε : ℝ} (hε : 0 < ε) (hN : (L * (f x0 - fStar)) / (ω * ε ^ (2 : ℕ)) ≤ (N : ℝ) + 1) : gStar N ≤ ε

Example 1.6.11

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

Source header · Attribution source

Example 1.6.11 (1): for f(x₁, x₂) = (1 / 2) x₁² + (1 / 4) x₂⁴ - (1 / 2) x₂², the unit-step gradient method started at (1, 0) converges to (0, 0).

open Filter open scoped Gradient local notation "E" => EuclideanSpace ℝ (Fin 2) local notation "initialPoint" => EuclideanSpace.single 0 (1 : ℝ) theorem saddlePointConvergenceObjective_unitStepGradientMethod_tendsto_origin : Tendsto (gradientMethod (fun _ : ℕ ↦ (1 : ℝ)) saddlePointConvergenceObjective initialPoint) atTop (nhds (0 : E))

Proposition 1.6.12

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

Source header · Attribution source

Proposition 1.6.12 (1): every quartic-example gradient trajectory started at (1, 0) stays on the horizontal axis x₂ = 0.

open Filter open EuclideanSpace open scoped Gradient local notation "E" => EuclideanSpace ℝ (Fin 2) local notation "leftPoint" => single 1 (-1 : ℝ) local notation "rightPoint" => single 1 (1 : ℝ) local notation "initialPoint" => single 0 (1 : ℝ) theorem quarticGradientMethod_axisInvariant (stepSize : ℕ → ℝ) (k : ℕ) : (gradientMethod stepSize saddlePointConvergenceObjective initialPoint k) 1 = 0

Proposition 1.6.13

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

Source header · Attribution source

Proposition 1.6.13: if a_{k+1} = A_k a_k and each step operator has operator norm at most 1 - q, then the norm sequence satisfies the owner geometric-rate statement with constant ‖a_0‖. The textbook positivity hypothesis 0 < q < 1 is only needed later for the convergence corollary HasGeometricRateOfConvergence.tendsto_zero. The source specializes this to ℝⁿ; the proof only uses the normed-space operator estimate ContinuousLinearMap.le_opNorm.

open HasGeometricRateOfConvergence universe u v variable {𝕜 : Type u} {E : Type v} [NontriviallyNormedField 𝕜] [SeminormedAddCommGroup E] [NormedSpace 𝕜 E] theorem linear_iteration_contraction_estimate (q : ℝ) (A : ℕ → E →L[𝕜] E) (a : ℕ → E) (ha : ∀ k : ℕ, a (k + 1) = A k (a k)) (hA : ∀ k : ℕ, ‖A k‖ ≤ 1 - q) : HasGeometricRateOfConvergence (fun k : ℕ ↦ ‖a k‖) q ‖a 0‖

Theorem 1.6.14

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

Source header · Attribution source

Theorem 1.6.14 (1): if each h_k is the source minimizer h_k^* of max {a_k(h), b_k(h)}, the radius sequence is positive, and 0 < r_0 < 2 * μ / M, then the reciprocal-gap estimate (1.2.31) holds: radius / r_k - 1 ≥ (1 + q)^k (radius / r_0 - 1).

variable {r h : ℕ → ℝ} {μ L : ℝ} {M : NNRealˣ} local notation "radius" => localGradientRadius μ M local notation "step" => (2 / (L + μ) : ℝ) local notation "q" => (2 * μ / (L + μ) : ℝ) local notation "positiveSteps" => Set.Ioi (0 : ℝ) local notation "aCoeff" => fun k hStep ↦ 1 - hStep * (μ - (M : ℝ) * r k / 2) local notation "bCoeff" => fun k hStep ↦ hStep * (L + (M : ℝ) * r k / 2) - 1 local notation "bound" => fun k hStep ↦ max (aCoeff k hStep) (bCoeff k hStep) local notation "scaled" => fun k ↦ ((M : ℝ) / (L + μ)) * r k local notation "gap" => fun k ↦ r k / (radius - r k) variable (hμ : 0 < μ) (hμL : μ ≤ L) variable (hr0 : 0 < r 0 ∧ r 0 < radius) variable (hr_nonneg : ∀ k : ℕ, 0 ≤ r k) variable (hopt : ∀ k : ℕ, IsMinOn (bound k) positiveSteps (h k)) variable (hrec : ∀ k : ℕ, r (k + 1) ≤ bound k (h k) * r k) theorem localGradientScaledRadius_reciprocal_gap_lower_bound_of_optimal_step (hμ : 0 < μ) (hμL : μ ≤ L) (hr0 : 0 < r 0 ∧ r 0 < radius) (hr_nonneg : ∀ k : ℕ, 0 ≤ r k) (hopt : ∀ k : ℕ, IsMinOn (bound k) positiveSteps (h k)) (hrec : ∀ k : ℕ, r (k + 1) ≤ bound k (h k) * r k) (hr_pos : ∀ k : ℕ, 0 < r k) (k : ℕ) : radius / r k - 1 ≥ (1 + q) ^ k * (radius / r 0 - 1)

Theorem 1.6.15

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

Source header · Attribution source

Theorem 1.6.15: if f has M-Lipschitz Hessian, the Hessian at the stationary point xStar has quadratic form bounded between μ and L, and the initial point lies in the intrinsic ball of radius localGradientRadius μ M around xStar, then the fixed-step gradient method with step size 2 / (L + μ) satisfies the stated geometric error bound with rate parameter 2 * μ / (L + 3 * μ).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {μ L : ℝ} {M : NNRealˣ} variable {f : E → ℝ} {xStar x0 : E} local notation "radius" => (2 * μ / (M : ℝ) : ℝ) local notation "step" => 2 / (L + μ) local notation "q" => (2 * μ) / (L + μ) local notation "rate" => (2 * μ) / (L + 3 * μ) local notation "traj" => gradientMethod (fun _ : ℕ ↦ step) f x0 local notation "r" => fun k : ℕ ↦ ‖traj k - xStar‖ local notation "scaled" => fun k ↦ ((M : ℝ) / (L + μ)) * r k local notation "gap" => fun k ↦ r k / (radius - r k) theorem gradient_descent_local_linear_rate (hf : f ∈ C22[(M : NNReal)]) (hess_lower : ∀ z : E, μ * ‖z‖ ^ (2 : ℕ) ≤ inner ℝ (hessian f xStar z) z) (hess_upper : ∀ z : E, inner ℝ (hessian f xStar z) z ≤ L * ‖z‖ ^ (2 : ℕ)) (hgradStar : ∇ f xStar = 0) (h0 : ‖x0 - xStar‖ < radius) : HasGeometricRateOfConvergence (fun k : ℕ ↦ ‖traj k - xStar‖) rate (radius * ‖x0 - xStar‖ / (radius - ‖x0 - xStar‖))

Algorithm 1.7.1

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

Source header · Attribution source

Algorithm 1.7.1: a Newton method for the nonlinear system F(x) = 0 started at x₀ is a trajectory of admissible points whose successive iterates are obtained from the Newton update. The Jacobian nondegeneracy at each iterate is part of the data because the textbook algorithm assumes the Newton correction remains well defined along the orbit.

open ContinuousLinearMap universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] namespace NewtonSystem structure Method (F : E → E) (x0 : E) where /-- The Newton iterates, valued in the natural admissible domain. -/ x : ℕ → AdmissiblePoint F /-- The zeroth iterate is the prescribed initial point `x₀`. -/ x_zero : (x 0 : E) = x0 /-- The Newton iterates satisfy the recursive update rule. -/ step_eq : ∀ k : ℕ, (x (k + 1) : E) = step F (x k)

Algorithm 1.7.2

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

Source header · Attribution source

Algorithm 1.7.2: a damped Newton method for f started at x₀ is an iterate sequence x₀, x₁, x₂, ... through Hessian-nondegenerate points, together with positive damping factors hₖ, and the damped Newton recursion xₖ₊₁ = xₖ - hₖ [∇² f(xₖ)]⁻¹ ∇ f(xₖ) at every step.

open scoped Gradient open NewtonSystem (AdmissiblePoint) universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] namespace DampedNewton structure Method (f : E → ℝ) (x0 : E) where /-- The iterate sequence `x₀, x₁, x₂, ...`, valued in the natural admissible domain. -/ x : ℕ → AdmissiblePoint (∇ f) /-- The zeroth iterate is the prescribed initial point `x₀`. -/ x_zero : x 0 = x0 /-- The positive damping factors `hₖ`. -/ stepSize : ℕ → ℝ /-- Every damping factor is strictly positive. -/ stepSize_pos : ∀ k : ℕ, 0 < stepSize k /-- Each iterate is obtained from the previous one by the damped Newton update. -/ step_eq : ∀ k : ℕ, x (k + 1) = step f (x k) (stepSize k)

Example 1.7.3

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

Source header · Attribution source

Example 1.7.3: for the Newton iteration associated to φ(t) = t / √(1 + t²), the iterates started from t₀ satisfy |t_k| = |t₀|^(3^k). Consequently the method converges cubically to 0 on |t₀| < 1, is two-periodic at t₀ = ±1, and diverges in magnitude on |t₀| > 1.

open NewtonSystem theorem abs_newtonUnivariateRootIterates_eq_abs_start_pow_three_pow (t0 : ℝ) (k : ℕ) :

Proposition 1.7.4

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

Source header · Attribution source

Proposition 1.7.4 lies in the chapter's scalar convergence-rate and complexity-threshold domain. Primary domain: * square-root decay bounds for real-valued error sequences Sampled owner-style declarations: * sqrt_rate_complexity_bound * exists_power_law_bound_of_sqrt_bound * IsOptimizationErrorSequence.hasConvergenceRateOfOrder_of_sqrt_bound * HasGeometricRateOfConvergence.complexity_bound Best owner abstraction: * sqrt_rate_complexity_bound from Definition_1_2_5.lean Primitive data: * the sequence r * the constant c * the pointwise square-root estimate r k ≤ c / Real.sqrt (k : ℝ) on positive indices Derived API: * the explicit complexity threshold (c / ε)^2 Source/core/bridge triage: * source-facing: the textbook square-root complexity threshold * core/canonical: sqrt_rate_complexity_bound * bridge/view: the pointwise square-root rate hypothesis The former declaration in this file duplicated the owner theorem with exactly the same interface and no extra mathematics. This recall file therefore keeps Proposition 1.7.4 machine-checkable as a direct owner recall and introduces no parallel theorem name.

recall sqrt_rate_complexity_bound {r : ℕ → ℝ} {c ε : ℝ} (h : ∀ ⦃k : ℕ⦄, 0 < k → r k ≤ c / Real.sqrt (k : ℝ)) (hε : 0 < ε) {k : ℕ} (hk : 0 < k) (hkComplexity : (c / ε) ^ (2 : ℕ) ≤ (k : ℝ)) : r k ≤ ε

Proposition 1.7.5

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

Source header · Attribution source

namespace HasGeometricRateOfConvergence recall complexity_bound {r : ℕ → ℝ} {q c ε : ℝ} (h : HasGeometricRateOfConvergence r q c) (hc : 0 < c) (hq₀ : 0 < q) (hq₁ : q ≤ 1) (hε : 0 < ε) {k : ℕ} (hkComplexity : Real.log (c / ε) / q ≤ (k : ℝ)) : r k ≤ ε

Proposition 1.7.6

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

Source header · Attribution source

Proposition 1.7.6 lies in the chapter's scalar superlinear-convergence domain. Primary domain: * quadratic tail estimates and logarithmic complexity thresholds for real error sequences Relevant owner-style declarations sampled before refining: * HasEventuallySuperlinearErrorBound * quadratic_tail_bound * quadratic_tail_le_of_logb_bound * HasSuperlinearRateOfConvergence in Definition_1_8_15.lean Best owner abstraction: * HasEventuallySuperlinearErrorBound r 0 c 0 Primitive data: * the sequence r * the constant c * the base index K * the owner recurrence witness HasEventuallySuperlinearErrorBound r 0 c 0 Derived API: * the quadratic tail estimate from K * the logarithmic threshold consequence forcing r (K + j) ≤ ε Source/core/bridge triage: * source-facing: the explicit Proposition 1.7.6 tail and threshold consequences * core/canonical: the owner-namespace theorems quadratic_tail_bound and quadratic_tail_le_of_logb_bound * bridge/view: direct recall only; this file adds no extra mathematics beyond the owner hypotheses or their canonical local consequences The former file kept standalone theorem names for owner-derived consequences. Those consequences now live with the owner abstraction, and Proposition 1.7.6 reuses them directly.

open HasEventuallySuperlinearErrorBound variable {r : ℕ → ℝ} {c : ℝ} #check (quadratic_tail_bound : HasEventuallySuperlinearErrorBound r 0 c 0 → (∀ k : ℕ, 0 ≤ r k) → 0 < c → (k0 j : ℕ) → r (k0 + j) ≤ (1 / c) * (c * r k0) ^ (2 ^ j : ℕ))

Theorem 1.7.7

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

Source header · Attribution source

Theorem 1.7.7: if f : E → ℝ has M-Lipschitz Hessian for a positive constant encoded by M : NNRealˣ, xStar is critical, and the Hessian at xStar dominates μ I, then the recursively defined Newton orbit for the stationarity system ∇ f = 0 started at an initial point in the closed ball of radius 2 μ / (3 M) around xStar is well defined, stays in that closed ball, and satisfies the standard quadratic one-step error estimate.

open scoped Gradient open NewtonSystem (AdmissiblePoint) universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {μ : ℝ} {M : NNRealˣ} {f : E → ℝ} {xStar x0 : E} theorem newtonOptimizationIterates_mem_ball_and_quadratic_error_bound (hμ : 0 < μ) (hf : f ∈ C22[M]) (hgrad : ∇ f xStar = 0) (hHstar : (fderiv ℝ (∇ f) xStar - μ • (1 : E →L[ℝ] E)).IsPositive) (hx0 : ‖x0 - xStar‖ ≤ localQuadraticNewtonRadius μ M) : let traj := localQuadraticNewtonOrbit hμ hf hgrad hHstar hx0 (∀ k, ‖traj k - xStar‖ ≤ localQuadraticNewtonRadius μ M) ∧ (∀ k, (fderiv ℝ (∇ f) (traj k)).det ≠ 0) ∧ ∀ k, ‖traj (k + 1) - xStar‖ ≤ ((M : ℝ) * ‖traj k - xStar‖ ^ (2 : ℕ)) / (2 * (μ - (M : ℝ) * ‖traj k - xStar‖))

Proposition 1.8.1

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

Source header · Attribution source

Proposition 1.8.1 (1): the regularized first-order Taylor model with quadratic parameter 1 / h is minimized at the first iterate of the constant-step gradient method.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem gradientMethodUpperModel_isMinOn (f : E → ℝ) (xBar : E) {h : ℝ} (hh : 0 < h) : IsMinOn (quadraticallyRegularizedObjective (firstOrderTaylorModelAt f xBar) (1 / h) xBar) Set.univ (gradientMethod (fun _ ↦ h) f xBar 1)

Proposition 1.8.2

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

Source header · Attribution source

Proposition 1.8.2: if the Hessian matrix ∇² f xBar is positive definite, then the quadratic Taylor model φ₂ = secondOrderTaylorModelAt f xBar is minimized at the canonical Newton step for the stationarity equation ∇ f = 0. The source-facing inverse-Hessian formula for that step is recovered from DampedNewton.step_eq_hessianMatrixFormula at h = 1; the matrix quadratic problem is used only as an internal bridge to Lemma 1.8.8.

open scoped Gradient open NewtonSystem (AdmissiblePoint) variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem newtonQuadraticModel_isMinOn (f : E → ℝ) (xBar : E) (hH : (∇² f xBar).PosDef) : IsMinOn (secondOrderTaylorModelAt f xBar) Set.univ (NewtonSystem.step (∇ f) ⟨xBar, hessian_det_ne_zero_of_posDef f xBar hH⟩)

Definition 1.8.3

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

Source header · Attribution source

Definition 1.8.3 is a source-facing recall in the positive-definite matrix geometry of ℝ^n, modeled as Fin n → ℝ. Primary domain: - inner products and norms induced by positive-(semi)definite matrices. Sampled owner-style declarations: - Matrix.toNormedAddCommGroup, the canonical norm owner attached to a positive-definite matrix; - Matrix.toInnerProductSpace, the canonical inner-product owner attached to a positive semidefinite matrix; - Matrix.PosDef.posSemidef, the bridge from the positive-definite hypothesis needed for the norm owner to the positive-semidefinite hypothesis needed for the inner-product owner; - Matrix.dotProduct_mulVec, the coordinate formula used in the textbook expansion. Best owner abstraction: - the canonical induced structures Matrix.toNormedAddCommGroup A hA and Matrix.toInnerProductSpace A hA.posSemidef. Primitive data: - A : Mat - hA : A.PosDef Derived API: - the source-facing notation ‖x‖[A] and ⟪x, y⟫_[A] for A : {A : Mat // A.PosDef}; - the textbook coordinate formulas recorded below as thin bridge lemmas. Source/core/bridge triage: - source-facing: the induced norm and inner product attached to a positive-definite matrix; - core/canonical: Matrix.toNormedAddCommGroup and Matrix.toInnerProductSpace; - bridge/view: the notation layer ‖x‖[A], ⟪x, y⟫_[A], and the formula companions inner_eq_dotProduct_mulVec, norm_eq_sqrt_dotProduct_mulVec, implemented through abbreviation-level notation bridges. This file therefore keeps Definition 1.8.3 as direct canonical recall/use of the induced owner structures, rather than introducing a second public wrapper API for the same norm and inner product.

open Matrix open scoped ComplexOrder variable {n : ℕ} local notation "E" => Fin n → ℝ local notation "Mat" => Matrix (Fin n) (Fin n) ℝ local notation "PosMat" => {A : Mat // Matrix.PosDef A} local notation "Euclid" => EuclideanSpace ℝ (Fin n) local notation "coordEquiv" => EuclideanSpace.equiv (Fin n) ℝ recall Matrix.toNormedAddCommGroup {n : Type*} {𝕜 : Type*} [Fintype n] [RCLike 𝕜] (M : Matrix n n 𝕜) (hM : M.PosDef) : NormedAddCommGroup (n → 𝕜)

Definition 1.8.4

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

Source header · Attribution source

Definition 1.8.4: on the weighted Hilbert space determined by A, the source-facing notion is the weighted quadratic expansion clause HasWeightedGradientSecondOrderExpansionAt A f g H x.

open Matrix open scoped Topology Gradient MatrixPosDef variable {n : ℕ} local notation "Mat" => Matrix (Fin n) (Fin n) ℝ local notation "PosMat" => {A : Mat // Matrix.PosDef A} local notation "WeightedSpace" => Matrix.PosDef.WeightedSpace variable {A : PosMat} variable {f : WeightedSpace A → ℝ} {x g : WeightedSpace A} variable {H : WeightedSpace A →L[ℝ] WeightedSpace A} #check HasWeightedGradientSecondOrderExpansionAt A f g H x

Lemma 1.8.5

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

Source header · Attribution source

Lemma 1.8.5: the weighted norm owner induced by a positive-definite real matrix is equivalent to the identity-matrix norm owner on ℝⁿ.

open Matrix open scoped MatrixOrder MatrixPosDef variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Coord" => Fin n → ℝ local notation "Mat" => Matrix (Fin n) (Fin n) ℝ local notation "coordEquiv" => EuclideanSpace.equiv (Fin n) ℝ theorem posDef_exists_weightedNorm_bounds (A : {A : Mat // A.PosDef}) : ∃ c₁ > 0, ∃ c₂ > 0, ∀ x : Coord, c₁ * ‖x‖[⟨(1 : Mat), PosDef.one⟩] ≤ ‖x‖[A] ∧ ‖x‖[A] ≤ c₂ * ‖x‖[⟨(1 : Mat), PosDef.one⟩]

Proposition 1.8.6

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

Source header · Attribution source

Proposition 1.8.6 (1): after transporting the intrinsic weighted gradient on Matrix.PosDef.WeightedSpace A to Euclidean coordinates, one obtains A⁻¹ applied to the Euclidean gradient of the transported function.

open Matrix
open scoped Gradient
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
local notation "PosMat" => {A : Mat // Matrix.PosDef A}
namespace Matrix.PosDef
variable (A : PosMat)
theorem gradient_eq_inverse_gradient (f : WeightedSpace A → ℝ) (x : E) :
    let e : E ≃L[ℝ] WeightedSpace A :=
      (EuclideanSpace.equiv (Fin n) ℝ).toLinearEquiv.toContinuousLinearEquiv
    e.symm (∇ f (e x)) = (A.1⁻¹).toEuclideanLin (∇ (f ∘ e) x)

Example 1.8.7

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

Source header · Attribution source

Example 1.8.7: the canonical Newton step for the quadratic stationarity system ∇ f = 0 lands at the minimizer in one iteration.

open scoped Gradient open Matrix variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ namespace UnconstrainedQuadraticMinimizationProblem theorem newtonStep_eq_minimizer (problem : UnconstrainedQuadraticMinimizationProblem n) (x : E) : NewtonSystem.step (∇ problem.objective) ⟨x, gradient_det_ne_zero problem x⟩ = problem.minimizer

Lemma 1.8.8

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

Source header · Attribution source

Lemma 1.8.8, owner-centered form: translating the ambient coordinates of an unconstrained quadratic minimization problem by xBar translates its global minimizer by the same amount.

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace UnconstrainedQuadraticMinimizationProblem theorem isMinOn_translate (problem : UnconstrainedQuadraticMinimizationProblem n) (xBar : E) : IsMinOn (fun x ↦ problem (x - xBar)) Set.univ (xBar + problem.minimizer)

Lemma 1.8.9

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

Source header · Attribution source

Lemma 1.8.9 lies in the variable-metric / quasi-Newton recursion domain. Primary domain: * variable-metric and quasi-Newton methods on Euclidean space Sampled owner-style declarations: * VariableMetricMethod.metric * VariableMetricMethod.metric_inv_eq_inverseMetric * VariableMetricMethod.x_succ_eq_sub_metric_inv_gradient * hessianMatrix Best owner abstraction: * VariableMetricMethod.x_succ_eq_sub_metric_inv_gradient Primitive data: * a variable-metric method method * the unit-step specialization method.stepSize = 1 Derived/contextual API: * the metric sequence Gₖ = Hₖ⁻¹ * the local-minimum and Hessian-limit quasi-Newton context often used around this recursion Source/core/bridge triage: * source-facing: the unit-step quasi-Newton iterate identity * core/canonical: VariableMetricMethod.x_succ_eq_sub_metric_inv_gradient * bridge/view: the surrounding local-minimum / Hessian-limit interpretation, which does not alter the displayed recursion formula The former file packaged extra quasi-Newton context into a separate predicate and then restated the owner theorem through that wrapper. The recursion formula itself only depends on the unit-step specialization, so this refinement keeps the owner theorem directly as the public entry.

open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) recall VariableMetricMethod.x_succ_eq_sub_metric_inv_gradient {f : E → ℝ} {x0 : E} (method : VariableMetricMethod f x0) (hstep : method.stepSize = 1) (k : ℕ) : method (k + 1) = method k - ((method.metric k)⁻¹).toEuclideanLin (∇ f (method k))

Algorithm 1.8.10

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

Source header · Attribution source

Algorithm 1.8.10 together with regularity hypotheses: a variable metric method is determined by a step-size schedule hₖ and a quasi-Newton update rule for Hₖ₊₁, while the iterate and inverse-metric sequences are the canonical recursive ones generated from that data. The structure records that f has the displayed gradients along those iterates, every step size is positive, and every generated inverse metric is positive definite.

open Matrix open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ local notation "Update" => ℕ → E → E → E → E → Mat → Mat structure VariableMetricMethod (f : E → ℝ) (x0 : E) where stepSize : ℕ → ℝ update : Update hasGradientAt (k : ℕ) : HasGradientAt f (∇ f (variableMetricIterates stepSize f x0 update k)) (variableMetricIterates stepSize f x0 update k) stepSize_pos (k : ℕ) : 0 < stepSize k inverseMetric_posDef (k : ℕ) : (variableMetricInverseMetrics stepSize f x0 update k).PosDef

Definition 1.8.11

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

Source header · Attribution source

Definition 1.8.11: a quasi-Newton inverse-Hessian approximation Hₖ₊₁ is required to be symmetric positive definite and to satisfy the secant equation Hₖ₊₁ γₖ = δₖ. Using the chapter's canonical owners, this is the proposition HkNext.PosDef ∧ HkNext.toEuclideanLin γk = δk, where Matrix.PosDef packages Hₖ₊₁ = Hₖ₊₁ᵀ > 0.

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ variable (HkNext : Mat) (γk δk : E) #check (HkNext.PosDef ∧ HkNext.toEuclideanLin γk = δk : Prop)

Definition 1.8.12

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

Source header · Attribution source

Definition 1.8.12: ΔHₖ is the standard-basis matrix of the canonical rank-one correction operator built from the secant residual δₖ - Hₖ γₖ, equivalently the textbook SR1 outer-product update. The nonzero denominator hypothesis belongs on the secant consequences rather than on this source-facing matrix formula itself.

open Matrix InnerProductSpace variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ def rankOneCorrectionMatrixDifference (Hk : Mat) (γk δk : E) : Mat := let r := sr1Residual Hk γk δk toEuclideanLin.symm ((inner ℝ r γk)⁻¹ • rankOne ℝ r r)

Definition 1.8.13

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

Source header · Attribution source

Definition 1.8.13: the Davidon--Fletcher--Powell update defines the next inverse-Hessian approximation by Hₖ₊₁ = Hₖ + δₖ δₖᵀ / ⟪γₖ, δₖ⟫ - Hₖ γₖ γₖᵀ Hₖ / ⟪γₖ, Hₖ γₖ⟫.

open Matrix InnerProductSpace LinearMap variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ def dfpUpdatedMatrix (Hk : Mat) (γk δk : E) : Mat := toEuclideanLin.symm (dfpUpdateOperator Hk γk δk)

Definition 1.8.14

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

Source header · Attribution source

Definition 1.8.14: ΔHₖ is the Broyden--Fletcher--Goldfarb--Shanno (BFGS) correction (βₖ / ⟪γₖ, δₖ⟫) δₖ δₖᵀ - (Hₖ γₖ δₖᵀ + δₖ γₖᵀ Hₖ) / ⟪γₖ, δₖ⟫, where βₖ = 1 + ⟪Hₖ γₖ, γₖ⟫ / ⟪γₖ, δₖ⟫. The curvature hypotheses belong on the secant and positivity theorems rather than on this source-facing matrix formula.

open Matrix InnerProductSpace LinearMap variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ def bfgsMatrixDifference (Hk : Mat) (γk δk : E) : Mat := toEuclideanLin.symm (bfgsDifferenceOperator Hk γk δk - Hk.toEuclideanLin)

Definition 1.8.15

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

Source header · Attribution source

Definition 1.8.15: a trajectory family has a superlinear rate of convergence to xStar with lag lag if there are positive constants ε and c such that every initial point x₀ with ‖x₀ - xStar‖ < ε generates a trajectory starting at x₀, the induced error sequence ‖x_k - xStar‖ is eventually controlled by the superlinear recurrence, while the trajectory itself converges to xStar, and from some index N ≥ lag onward, satisfying ‖x_{k+1} - xStar‖ ≤ c * ‖x_k - xStar‖ * ‖x_{k-lag} - xStar‖.

universe u variable {E : Type u} [SeminormedAddCommGroup E] def HasSuperlinearRateOfConvergence (trajectory : E → ℕ → E) (xStar : E) (lag : ℕ) : Prop := ∃ ε > 0, ∃ c > 0, ∀ ⦃x0 : E⦄, ‖x0 - xStar‖ < ε → trajectory x0 0 = x0 ∧ Filter.Tendsto (trajectory x0) Filter.atTop (nhds xStar) ∧ ∃ N, HasEventuallySuperlinearErrorBound (fun k ↦ ‖trajectory x0 k - xStar‖) lag c N

Definition 1.9.1

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

Source header · Attribution source

Definition 1.9.1: An unconstrained quadratic minimization problem on ℝⁿ is determined by a constant term α, a linear coefficient a, and a symmetric positive-definite matrix A, with objective function x ↦ α + ⟪a, x⟫ + (1 / 2) ⟪Ax, x⟫, minimized over all x ∈ ℝⁿ. The symmetry is carried canonically by Matrix.PosDef, while the ambient unconstrained minimization problem is recovered through toSetConstrainedMinimizationProblem.

open Matrix structure UnconstrainedQuadraticMinimizationProblem (n : ℕ) where α : ℝ a : EuclideanSpace ℝ (Fin n) A : Matrix (Fin n) (Fin n) ℝ posDef : A.PosDef

Definition 1.9.2

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

Source header · Attribution source

Definition 1.9.2: for an unconstrained quadratic minimization problem problem, a starting point x₀, and k ≥ 1, the Krylov subspace 𝓛ₖ is the subspace generated by A (x₀ - x*), ..., Aᵏ (x₀ - x*), implemented canonically as the standard Krylov subspace of problem.A generated by the initial gradient ∇ problem.objective x₀.

open scoped Gradient namespace UnconstrainedQuadraticMinimizationProblem variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) def krylovSubspace (problem : UnconstrainedQuadraticMinimizationProblem n) (x0 : E) (k : ℕ+) : Submodule ℝ E := let A := problem.A.toEuclideanLin A.krylovSubspace k (∇ problem.objective x0)

Definition 1.9.3

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

Source header · Attribution source

Definition 1.9.3: A positive-indexed sequence is generated by the conjugate gradient method when each iterate xₖ minimizes the quadratic objective over the affine space x₀ + 𝓛ₖ, where 𝓛ₖ is the standard Krylov subspace generated by A and the initial seed A (x₀ - x*), with x* = -A⁻¹ a.

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) def IsConjugateGradientSequence (problem : UnconstrainedQuadraticMinimizationProblem n) (x0 : E) (xs : ℕ+ → E) : Prop := ∀ k, xs k ∈ problem.affineKrylovSearchSpace x0 k ∧ IsMinOn problem.objective (problem.affineKrylovSearchSpace x0 k : Set E) (xs k)

Lemma 1.9.4

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

Source header · Attribution source

Lemma 1.9.4: along a conjugate-gradient sequence, the kth Krylov space 𝓛ₖ is exactly the span of the gradients at the first k trajectory points x₀, x₁, …, xₖ₋₁. Equivalently, the nonzero gradients/residuals generated by the minimizing Krylov process span 𝓛ₖ.

open Filter open scoped Gradient open scoped Topology variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace UnconstrainedQuadraticMinimizationProblem theorem IsConjugateGradientSequence.krylovSubspace_eq_span_gradients {problem : UnconstrainedQuadraticMinimizationProblem n} {x0 : E} {xs : ℕ+ → E} (hcg : IsConjugateGradientSequence problem x0 xs) (k : ℕ+) : 𝓛(problem, x0, k) = Submodule.span ℝ (Set.range fun i : Fin k ↦ ∇ problem.objective (conjugateGradientTrajectory x0 xs i))

Lemma 1.9.5

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

Source header · Attribution source

Lemma 1.9.5: if each iterate xₖ with k > 0 lies in and minimizes f on the affine subspace x₀ + span {∇ f(x₀), …, ∇ f(xₖ₋₁)}, then the gradients at distinct iterates are orthogonal.

open Filter open scoped Topology open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem gradients_pairwise_orthogonal_of_isMinOn_affineSpan_gradients (f : E → ℝ) (x : ℕ → E) (hdiff : ∀ k : ℕ, DifferentiableAt ℝ f (x k)) (hmin : ∀ k : ℕ, 0 < k → let searchSpace : AffineSubspace ℝ E := AffineSubspace.mk' (x 0) (Submodule.span ℝ (Set.range fun j : Fin k ↦ ∇ f (x j))) x k ∈ searchSpace ∧ IsMinOn f (searchSpace : Set E) (x k)) {k i : ℕ} (hki : k ≠ i) : inner ℝ (∇ f (x k)) (∇ f (x i)) = 0

Corollary 1.9.6

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

Source header · Attribution source

Corollary 1.9.6: a conjugate-gradient trajectory for problem (1.3.2) is finite in the sense that some iterate among the first n + 1 points of the full trajectory has vanishing gradient.

open scoped Gradient open UnconstrainedQuadraticMinimizationProblem.IsConjugateGradientSequence variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace IsConjugateGradientSequence theorem zero_gradient_within_dimension {problem : UnconstrainedQuadraticMinimizationProblem n} {x0 : E} {xs : ℕ+ → E} (hcg : IsConjugateGradientSequence problem x0 xs) : ∃ k ≤ n, ∇ problem.objective (conjugateGradientTrajectory x0 xs k) = 0

Corollary 1.9.7

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

Source header · Attribution source

Corollary 1.9.7: in the conjugate-gradient method for an unconstrained quadratic problem, the gradient at the kth iterate lies in the orthogonal complement of the kth Krylov subspace 𝓛ₖ.

open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem IsConjugateGradientSequence.gradient_mem_krylovSubspace_orthogonal {problem : UnconstrainedQuadraticMinimizationProblem n} {x0 : E} {xs : ℕ+ → E} (hcg : IsConjugateGradientSequence problem x0 xs) (k : ℕ+) : ∇ problem.objective (xs k) ∈ (𝓛(problem, x0, k))ᗮ

Lemma 1.9.8

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

Source header · Attribution source

Lemma 1.9.8: along a conjugate-gradient sequence for an unconstrained quadratic problem, distinct step differences are A-orthogonal.

open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace IsConjugateGradientSequence theorem stepDifferences_pairwise_A_orthogonal {problem : UnconstrainedQuadraticMinimizationProblem n} {x0 : E} {xs : ℕ+ → E} (hcg : IsConjugateGradientSequence problem x0 xs) {k i : ℕ} (hki : k ≠ i) : inner ℝ (problem.A.toEuclideanLin (conjugateGradientTrajectory x0 xs (k + 1) - conjugateGradientTrajectory x0 xs k)) (conjugateGradientTrajectory x0 xs (i + 1) - conjugateGradientTrajectory x0 xs i) = 0

Algorithm 1.9.9

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

Source header · Attribution source

Algorithm 1.9.9: a nonlinear conjugate-gradient method for minimizing f is determined by an initial point x₀, step sizes hₖ, and coefficients βₖ such that f is differentiable at every derived iterate, each hₖ minimizes the line-search objective over all h ≥ 0, and the iterate and search-direction sequences are the canonical recursive ones generated from x₀, hₖ, and βₖ.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] structure NonlinearConjugateGradientMethod (f : E → ℝ) (x0 : E) where stepSize : ℕ → ℝ beta : ℕ → ℝ differentiableAt : ∀ k : ℕ, DifferentiableAt ℝ f (nonlinearConjugateGradientIterates f x0 stepSize beta k) lineSearch : SatisfiesExactLineSearchAlong f (nonlinearConjugateGradientIterates f x0 stepSize beta) (nonlinearConjugateGradientDirections f x0 stepSize beta) stepSize

Definition 1.9.10

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

Source header · Attribution source

Definition 1.9.10 (1): the Dai--Yuan nonlinear conjugate-gradient coefficient sequence is given by βₖ = ‖∇f(xₖ₊₁)‖² / ⟪∇f(xₖ₊₁) - ∇f(xₖ), pₖ⟫.

universe u open scoped Gradient namespace NonlinearConjugateGradientMethod variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) (x p : ℕ → E) def daiYuanBeta : ℕ → ℝ := fun k ↦ ‖∇ f (x (k + 1))‖ ^ 2 / inner ℝ (∇ f (x (k + 1)) - ∇ f (x k)) (p k)

Proposition 1.9.11

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

Source header · Attribution source

Proposition 1.9.11 first reuses the existing owner theorem that problem.minimizer is a global minimizer.

open scoped Gradient open Matrix variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace UnconstrainedQuadraticMinimizationProblem recall minimizer_isMinOn (problem : UnconstrainedQuadraticMinimizationProblem n) : IsMinOn problem Set.univ problem.minimizer

Theorem 1.9.12

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

Source header · Attribution source

Theorem 1.9.12: for an unconstrained quadratic minimization problem on ℝⁿ, every conjugate-gradient trajectory reaches the unique minimizer x* within at most n iterations.

open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace IsConjugateGradientSequence theorem eq_minimizer_within_dimension {problem : UnconstrainedQuadraticMinimizationProblem n} {x0 : E} {xs : ℕ+ → E} (hcg : IsConjugateGradientSequence problem x0 xs) : ∃ m ≤ n, conjugateGradientTrajectory x0 xs m = problem.minimizer

Theorem 1.10.1

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

Source header · Attribution source

Theorem 1.10.1: for a payoff on nonempty index sets valued in a conditionally complete lattice, if each lower slice {F(x, u) | x ∈ Q₁} is bounded below and each upper slice {F(x, u) | u ∈ Q₂} is bounded above, then the maximin value is bounded above by the minimax value. Specializing to α = ℝ recovers the textbook real-valued weak-duality inequality.

universe u v w theorem maximin_le_minimax {Q₁ : Type u} {Q₂ : Type v} {α : Type w} [ConditionallyCompleteLattice α] [Nonempty Q₁] [Nonempty Q₂] (F : Q₁ → Q₂ → α) (hbelow : ∀ u, BddBelow (Set.range fun x ↦ F x u)) (habove : ∀ x, BddAbove (Set.range (F x))) : (⨆ u, ⨅ x, F x u) ≤ ⨅ x, ⨆ u, F x u

Definition 1.10.2

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

Source header · Attribution source

Definition 1.10.2: A Lagrangian problem is specified by a domain Q, an objective function f₀ : Q → ℝ, and finitely many inequality constraint functions fⱼ : Q → ℝ for j = 1, ..., m; the feasible set, primal optimal value, Lagrangian, dual function and its domain, the Lagrangian minimizers, and the dual optimal value are the derived notions defined below.

universe u open scoped ConstrainedArgmin structure LagrangianProblem (Q : Type u) (m : ℕ) where objective : Q → ℝ constraints : Fin m → Q → ℝ

Definition 1.10.3

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

Source header · Attribution source

Definition 1.10.3: The example constrained optimization problem on ℝ² has objective f₀(x) = (1 / 2) ‖x - (1,1)‖² and the single inequality constraint f₁(x) = x₁ - (1 / 2) x₂² ≤ 0.

open EuclideanSpace local notation "X" => EuclideanSpace ℝ (Fin 2) def lagrangianRelaxationExample : LagrangianProblem X 1

Theorem 1.10.4

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

Source header · Attribution source

Theorem 1.10.4: a dual-feasible maximizer of the dual function together with a convergent family of Lagrangian minimizers on a punctured ℝ₊^m-neighborhood certifies that the limit point is a globally optimal primal solution.

open Filter open scoped ConstrainedArgmin EuclideanOrthant universe u variable {Q : Type u} [TopologicalSpace Q] {m : ℕ} namespace LagrangianProblem local notation "Λ" => EuclideanSpace ℝ (Fin m) variable (problem : LagrangianProblem Q m) {lamStar : Λ} {ε : ℝ} local notation "N" => Metric.closedBall lamStar ε ∩ ℝ₊^m theorem globalOptimality_of_dualCertificate {lamStar : Λ} {ε : ℝ} (xPath : Λ → Q) (xStar : Q) (hlamStar : lamStar ∈ problem.dualFeasibleSet) (hmax : IsMaxOn problem.dualFunction problem.dualFeasibleSet lamStar) (hε : 0 < ε) (hxPath : ∀ ⦃lam : Λ⦄, lam ∈ Metric.closedBall lamStar ε ∩ ℝ₊^m → lam ≠ lamStar → xPath lam ∈ problem.lagrangianMinimizers lam) (hlim : Tendsto xPath (nhdsWithin lamStar ((Metric.closedBall lamStar ε ∩ ℝ₊^m) \ {lamStar})) (nhds xStar)) (hcont : ContinuousAt problem.constraintVector xStar) (hxStar : xStar ∈ problem.lagrangianMinimizers lamStar) : xStar ∈ argmin[problem.feasibleSet] problem

Proposition 1.10.5

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

Source header · Attribution source

Proposition 1.10.5 (1): along the scalar multiplier parametrization, the effective domain of the example dual function is (-∞, 1).

open EuclideanSpace local notation "X" => EuclideanSpace ℝ (Fin 2) local notation "ψ" => lagrangianRelaxationExample.dualFunction ∘ single 0 local notation "X⋆" => lagrangianRelaxationExample.lagrangianMinimizers ∘ single 0 theorem lagrangianRelaxationExampleMultiplier_mem_dualDomain_iff (lam : ℝ) : single 0 lam ∈ lagrangianRelaxationExample.dualDomain ↔ lam < 1

Example 1.10.6

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

Source header · Attribution source

Example 1.10.6: the point x(λ_*) = (2^(-1 / 3), 2^(1 / 3)) obtained from the explicit dual maximizer λ_* = 1 - (1 / 2)^(1 / 3) is a global optimal solution of the example constrained problem.

open EuclideanSpace Filter open scoped ConstrainedArgmin EuclideanOrthant local notation "Λ" => EuclideanSpace ℝ (Fin 1) local notation "λ⋆" => lagrangianRelaxationExampleLambdaStar local notation "Λ⋆" => single 0 λ⋆ theorem lagrangianRelaxationExampleOptimalPoint_isGlobalOptimal : WithLp.toLp 2 ![Real.rpow (2 : ℝ) (-(1 / 3 : ℝ)), Real.rpow (2 : ℝ) (1 / 3 : ℝ)] ∈ argmin[lagrangianRelaxationExample.feasibleSet] lagrangianRelaxationExample

Proposition 1.10.7

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

Source header · Attribution source

Proposition 1.10.7: if x₁ ∈ X*(λ₁), then the dual function is bounded above by the affine support determined by x₁ at λ₁.

universe u namespace LagrangianProblem variable {Q : Type u} {m : ℕ} (problem : LagrangianProblem Q m) local notation "Λ" => EuclideanSpace ℝ (Fin m) local notation "ψ" => problem.dualFunction local notation "X⋆" => problem.lagrangianMinimizers theorem dualFunction_le_affine_support_of_mem_lagrangianMinimizers {lam₁ lam₂ : Λ} {x₁ : Q} (hx₁ : x₁ ∈ X⋆ lam₁) : ψ lam₂ ≤ ψ lam₁ + (inner ℝ (problem.constraintVector x₁) (lam₂ - lam₁) : EReal)

Proposition 1.10.8

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

Source header · Attribution source

Proposition 1.10.8: weak duality bounds the dual optimal value of a Lagrangian problem by its primal optimal value.

universe u open scoped EuclideanOrthant namespace LagrangianProblem variable {Q : Type u} {m : ℕ} local notation "Λ" => EuclideanSpace ℝ (Fin m) theorem dualOptimalValue_le_primalOptimalValue (problem : LagrangianProblem Q m) : problem.dualOptimalValue ≤ problem.primalOptimalValue

Definition 1.10.9

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

Source header · Attribution source

Definition 1.10.9: the Slater condition for a Lagrangian problem is strict feasibility of the associated functional-constraint problem obtained by viewing every scalar constraint as an inequality fⱼ(x) ≤ 0.

universe u namespace LagrangianProblem variable {Q : Type u} {m : ℕ} def SlaterCondition (problem : LagrangianProblem Q m) : Prop := problem.toFunctionalConstraintsMinimizationProblem.StrictlyFeasible

Example 1.10.10

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

Source header · Attribution source

Example 1.10.10: the quadratic positive-part sum is the concrete owner quadraticPenalty constraints.

variable {X : Type*} [TopologicalSpace X] {ι : Type*} [Fintype ι] variable (constraints : ι → C(X, ℝ)) recall quadraticPenalty

Algorithm 1.10.11

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

Source header · Attribution source

Algorithm 1.10.11: a penalty function method for a nonlinear optimization problem with functional constraints consists of a penalty function Φ for the feasible set, penalty coefficients tₖ with 0 < tₖ < tₖ₊₁ and tₖ → ∞, and iterates xₖ ∈ Q such that each xₖ minimizes the penalized objective x ↦ f₀(x) + tₖ Φ(x) on the basic feasible set Q.

open Filter Set universe u variable {X : Type u} {m : ℕ} variable [TopologicalSpace X] structure PenaltyFunctionMethod (problem : FunctionalConstraintsMinimizationProblem X m) where penalty : C(problem.basicFeasibleSet, ℝ) isPenalty : IsPenaltyFunction problem.feasibleSet penalty penaltyCoefficients : ℕ+ → ℝ penaltyCoefficients_pos : ∀ k : ℕ+, 0 < penaltyCoefficients k penaltyCoefficients_strictMono : StrictMono penaltyCoefficients penaltyCoefficients_tendsto_atTop : Tendsto penaltyCoefficients atTop atTop iterates : ℕ+ → problem.basicFeasibleSet isMinOn_auxiliaryObjective : ∀ k : ℕ+, IsMinOn (fun x ↦ problem x + penaltyCoefficients k * penalty x) univ (iterates k)

Proposition 1.10.12

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

Source header · Attribution source

Proposition 1.10.12: a scalar λ lies in (-∞, 1) and is a global maximizer of the example dual function on that interval exactly when λ = 1 - (1 / 2)^(1 / 3).

open Set EuclideanSpace local notation "D" => Iio (1 : ℝ) local notation "ψ" => lagrangianRelaxationExample.dualFunction ∘ single 0 theorem lagrangianRelaxationExample_dualFunction_isMaxOn_iff (lam : ℝ) : lam ∈ D ∧ IsMaxOn ψ D lam ↔ lam = lagrangianRelaxationExampleLambdaStar

Definition 1.10.13

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

Source header · Attribution source

Definition 1.10.13: A sequential unconstrained minimization scheme for a nonlinear optimization problem with functional constraints consists of auxiliary unconstrained objective functions Φₖ : Q → ℝ and iterates xₖ ∈ Q such that each xₖ minimizes Φₖ on Q. The owner abstraction is the intrinsic feasible type Q; any surrounding constrained-problem package or ambient-set presentation is auxiliary context used only when specializing this generic scheme. The auxiliary objectives are intended to approximate a solution of the original constrained problem.

universe u structure SequentialUnconstrainedMinimizationScheme (Q : Type u) where auxiliaryObjectives : ℕ+ → Q → ℝ iterates : ℕ+ → Q isMinOn_auxiliaryObjective (k : ℕ+) : IsMinOn (auxiliaryObjectives k) Set.univ (iterates k)

Definition 1.10.14

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

Source header · Attribution source

Definition 1.10.14: for a set F in the ambient space, a continuous real-valued map is a penalty function for F if it is nonnegative and vanishes exactly on F. The customary strict-positivity statement on the complement is derived API.

open Set universe u -- Declarations for this item will be appended below by the statement pipeline. variable {E : Type u} [TopologicalSpace E] class IsPenaltyFunction (F : Set E) (Phi : C(E, ℝ)) : Prop where nonneg (x : E) : 0 ≤ Phi x zeroSet_eq : F = Phi ⁻¹' ({0} : Set ℝ)

Definition 1.10.15

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

Source header · Attribution source

Definition 1.10.15: for continuous constraint functions f₁, …, f_m : ℝⁿ → ℝ, the feasible set constraintSet constraints is cut out by the inequalities constraints j x ≤ 0, and one quadratic penalty for it is x ↦ ∑ j, ((fⱼ x)⁺)^2, where a⁺ = max a 0 is mathlib's positive-part notation. The nonsmooth penalty is introduced below as a companion definition.

open scoped BigOperators variable {X : Type*} [TopologicalSpace X] variable {ι : Type*} variable [Fintype ι] (constraints : ι → C(X, ℝ)) def quadraticPenalty : C(X, ℝ) := ∑ j : ι, ((constraints j)⁺) ^ (2 : ℕ)

Proposition 1.10.16

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

Source header · Attribution source

Proposition 1.10.16: if F₁ and F₂ are barrier functions for 𝓕₁ and 𝓕₂ and interior (𝓕₁ ∩ 𝓕₂) is nonempty, then their pointwise sum, restricted to the common interior, is a barrier function for 𝓕₁ ∩ 𝓕₂.

open Filter Set Topology universe u variable {α : Type u} [TopologicalSpace α] namespace IsBarrierFunctionOn variable {𝓕₁ 𝓕₂ : Set α} variable (F₁ : C(interior 𝓕₁, ℝ)) (F₂ : C(interior 𝓕₂, ℝ)) theorem add_inter (h₁ : IsBarrierFunctionOn 𝓕₁ F₁) (h₂ : IsBarrierFunctionOn 𝓕₂ F₂) (hinter : (interior (𝓕₁ ∩ 𝓕₂)).Nonempty) : IsBarrierFunctionOn (𝓕₁ ∩ 𝓕₂) (F₁.comp (ContinuousMap.inclusion (interior_mono inter_subset_left)) + F₂.comp (ContinuousMap.inclusion (interior_mono inter_subset_right)))

Proposition 1.10.17

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

Source header · Attribution source

The feasible set cut out by the continuous inequalities f j x ≤ 0.

open ContinuousMap Filter Set Topology open scoped BigOperators universe u v variable {α : Type u} [TopologicalSpace α] variable {ι : Type v} def constraintSet (f : ι → C(α, ℝ)) : Set α := {x | ∀ j : ι, f j x ≤ 0}

Definition 1.10.18

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

Source header · Attribution source

Definition 1.10.18: a barrier function for 𝓕 is a bundled continuous map F : C(interior 𝓕, ℝ) on the interior of a closed set 𝓕 with nonempty interior, such that the values of F along every sequence in interior 𝓕 converging to a boundary point of 𝓕 tend to +∞. The owner object is the continuous map on interior 𝓕; the closedness and nonempty-interior hypotheses remain part of the public predicate because they are part of the textbook notion.

open Filter Set Topology universe u variable {α : Type u} [TopologicalSpace α] class IsBarrierFunctionOn (𝓕 : Set α) (F : C(interior 𝓕, ℝ)) : Prop extends Fact (IsClosed 𝓕) where interior_nonempty : (interior 𝓕).Nonempty tendsTo_atTop_of_tendsto_frontier (x : ℕ → interior 𝓕) {xBar : α} (hx : Tendsto (fun k ↦ (x k : α)) atTop (nhds xBar)) (hxBar : xBar ∈ frontier 𝓕) : Tendsto (fun k ↦ F (x k)) atTop atTop

Algorithm 1.10.20

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

Source header · Attribution source

Algorithm 1.10.20: A barrier function method for 𝓕₀ = Q ∩ interior 𝓕 with barrier F consists of an interior-feasible iterate sequence xₖ ∈ 𝓕₀ and a strictly increasing parameter sequence tₖ > 0 with tₖ → ∞, such that for every k the next iterate xₖ₊₁ minimizes x ↦ f₀(x) + (1 / tₖ) F(x) over 𝓕₀.

open Filter Set Topology universe u variable {α : Type u} [TopologicalSpace α] structure BarrierFunctionMethod (Q 𝓕 : Set α) (objective : ↥(Q ∩ interior 𝓕) → ℝ) (F : C(interior 𝓕, ℝ)) [IsBarrierFunctionOn 𝓕 F] where iterates : ℕ → ↥(Q ∩ interior 𝓕) barrierParameters : ℕ → ℝ barrierParameters_pos : ∀ k : ℕ, 0 < barrierParameters k barrierParameters_strictMono : StrictMono barrierParameters barrierParameters_tendsto_atTop : Tendsto barrierParameters atTop atTop isMinOn_auxiliaryObjective : ∀ k : ℕ, IsMinOn (fun x ↦ objective x + (1 / barrierParameters k) * F (inclusion inter_subset_right x)) univ (iterates (k + 1))

Definition 1.10.21

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

Source header · Attribution source

Definition 1.10.21: a nonlinear optimization problem with functional constraints is a functional-constraint minimization problem whose basic feasible set is closed, whose objective and constraint functions are continuous on that feasible subtype, and whose scalar constraints are all of the form fⱼ(x) ≤ 0. The textbook GeneralMinimizationProblem n m case is the Euclidean specialization of this owner. The primitive continuity data are the scalar constraints; continuity of the packaged owner map problem.constraintVector is derived.

universe u namespace FunctionalConstraintsMinimizationProblem variable {X : Type u} [TopologicalSpace X] {m : ℕ} class IsFunctionalConstraintProblem (problem : FunctionalConstraintsMinimizationProblem X m) : Prop where basicFeasibleSet_isClosed : IsClosed problem.basicFeasibleSet objective_continuous : Continuous problem.objective constraint_continuous (j : Fin m) : Continuous (problem.constraints j) hasLeConstraints : problem.HasLeConstraints

Theorem 1.10.22

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

Source header · Attribution source

Theorem 1 10 22: if some penalized sublevel set {x ∈ Q | f₀(x) + tBar * Φ(x) ≤ f₀(xStar)} with tBar > 0 is bounded, then along the iterates xₖ of the penalty function method the pair (f₀(xₖ), Φ(xₖ)) converges to (f₀(xStar), 0), where xStar is a feasible global optimizer.

open Filter Set open scoped LevelSetNotation universe u variable {X : Type u} [PseudoMetricSpace X] [ProperSpace X] {m : ℕ} namespace PenaltyFunctionMethod variable {problem : FunctionalConstraintsMinimizationProblem X m} theorem tendsto_objective_and_penalty_of_bounded_penalized_sublevel (method : PenaltyFunctionMethod problem) (hbasicFeasibleSet : IsClosed problem.basicFeasibleSet) (hobjective : Continuous problem.objective) (xStar : problem.feasibleSet) (hoptimal : IsMinOn problem problem.feasibleSet xStar) (tBar : ℝ) (htBar : 0 < tBar) (hbounded : Bornology.IsBounded (𝓛[(method.penalizedObjective tBar)]((problem xStar)))) : Tendsto (fun k ↦ (problem (method k), method.penalty (method k))) atTop (nhds (problem xStar, 0))

Theorem 1.10.23

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

Source header · Attribution source

Theorem 1.10.23: if the barrier F is bounded below on 𝓕₀ = Q ∩ interior 𝓕, then the global optimal values Ψₖ* of the auxiliary objectives x ↦ f₀(x) + (1 / tₖ) F(x) converge to the optimal value f* of f₀ on 𝓕₀.

open Filter Set Topology universe u variable {α : Type u} [TopologicalSpace α] variable {Q 𝓕 : Set α} variable {objective : ↥(Q ∩ interior 𝓕) → ℝ} {F : C(interior 𝓕, ℝ)} variable [IsBarrierFunctionOn 𝓕 F] local notation "Q₀" => {x // x ∈ Q ∩ interior 𝓕} local notation "F₀" => ((F.comp (ContinuousMap.inclusion inter_subset_right)) : Q₀ → ℝ) local notation "primalProblem" => SetConstrainedMinimizationProblem.unconstrained objective theorem BarrierFunctionMethod.auxiliaryOptimalValue_tendsto_optimalValue (method : BarrierFunctionMethod Q 𝓕 objective F) (hF : BddBelow (Set.range F₀)) : Tendsto method.auxiliaryOptimalValue atTop (nhds (primalProblem).optimalValue)

1.1 — The World of Nonlinear Optimization

Definition 1.1.1

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

Source header · Attribution source

Definition 1.1.1: the textbook general minimization problem on ℝⁿ is represented by GeneralMinimizationProblem n m, the Euclidean specialization of the ambient owner FunctionalConstraintsMinimizationProblem. The companion owner-level declarations below record the objective-function coercion, the packaged constraint vector, and the inequality-only feasible set from the textbook terminology.

universe u variable {n m : ℕ} #check (GeneralMinimizationProblem n m)

Definition 1.1.2

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

Source header · Attribution source

Definition 1.1.2 lies in the constrained-optimization feasibility domain. Sampled owner-style declarations: * ConstraintSense.Holds, ConstraintSense.StrictHolds, and the owner feasible predicate problem.IsFeasible in Chap01/Definition_1_1_3 * the owner feasible set problem.feasibleSet in Chap01/Definition_1_1_3 * LagrangianProblem.SlaterCondition in Chap01/Definition_1_10_9 Best owner abstraction: * FunctionalConstraintsMinimizationProblem X m Primitive data: * basicFeasibleSet * constraints * senses Derived API: * the owner recall problem.feasibleSet.Nonempty * the source-facing point predicate problem.IsStrictlyFeasible * the owner strict feasible set problem.strictFeasibleSet * the problem-level predicate problem.StrictlyFeasible * the implication to ordinary feasibility and the resulting feasible-set nonemptiness theorem Source/core/bridge triage: * source-facing: problem.IsStrictlyFeasible, problem.StrictlyFeasible * core/canonical: ConstraintSense.StrictHolds, FunctionalConstraintsMinimizationProblem X m * bridge/view: problem.strictFeasibleSet, the implication from strict feasibility to ordinary feasibility, and the Euclidean specialization GeneralMinimizationProblem n m The later LagrangianProblem.SlaterCondition should therefore reuse this owner through its canonical bridge to FunctionalConstraintsMinimizationProblem, rather than restating the same strict-feasibility data.

namespace FunctionalConstraintsMinimizationProblem variable {X : Type*} {m : ℕ} (problem : FunctionalConstraintsMinimizationProblem X m) #check problem.feasibleSet.Nonempty

Definition 1.1.3

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

Source header · Attribution source

Definition 1.1.3: A feasible point is a strict local minimum when it is strictly better than every distinct feasible point in some neighborhood inside the feasible set.

universe u namespace FunctionalConstraintsMinimizationProblem variable {X : Type u} {m : ℕ} {problem : FunctionalConstraintsMinimizationProblem X m} variable [TopologicalSpace X] def IsStrictLocalMinimum (problem : FunctionalConstraintsMinimizationProblem X m) (xStar : problem.feasibleSet) : Prop := ∃ N : Set problem.basicFeasibleSet, N ∈ nhdsWithin (xStar : problem.basicFeasibleSet) problem.feasibleSet ∧ ∀ x : problem.basicFeasibleSet, x ∈ N → x ≠ xStar → problem.objective xStar < problem.objective x

Definition 1.1.4.1

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

Source header · Attribution source

Definition 1.1.4.1: a minimization problem is constrained when its feasible set is a proper subset of the ambient space.

namespace FunctionalConstraintsMinimizationProblem variable {X : Type*} {m : ℕ} def IsConstrained (problem : FunctionalConstraintsMinimizationProblem X m) : Prop := (problem.feasibleSet : Set X) ⊂ Set.univ

Definition 1.1.4.2

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

Source header · Attribution source

Definition 1.1.4.2: a general minimization problem is unconstrained exactly when the owner predicate IsConstrained does not hold.

namespace GeneralMinimizationProblem variable {n m : ℕ} variable (problem : GeneralMinimizationProblem n m) #check (¬ problem.IsConstrained)

Definition 1.1.4.3

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

Source header · Attribution source

Definition 1.1.4.3: a functional-constraint minimization problem is smooth when the ambient extensions of the objective and the packaged constraint vector are differentiable on the basic feasible set. The textbook family f₀, f₁, …, f_m is recovered from these owner maps.

universe u namespace FunctionalConstraintsMinimizationProblem variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X] {m : ℕ} def IsSmooth (problem : FunctionalConstraintsMinimizationProblem X m) : Prop := DifferentiableOn ℝ problem.objectiveOnAmbient problem.basicFeasibleSet ∧ DifferentiableOn ℝ problem.constraintVectorOnAmbient problem.basicFeasibleSet

Definition 1.1.4.4

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

Source header · Attribution source

Definition 1.1.4.4: a general minimization problem is nonsmooth exactly when the owner predicate IsSmooth from the previous item does not hold.

namespace GeneralMinimizationProblem variable {n m : ℕ} variable (problem : GeneralMinimizationProblem n m) #check ¬ problem.IsSmooth

Definition 1.1.4.5

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

Source header · Attribution source

Definition 1.1.4.5: A minimization problem is linearly constrained when its packaged owner constraint family is affine on the basic feasible set and that basic feasible set is polyhedral.

open AffineMap namespace FunctionalConstraintsMinimizationProblem variable {X : Type*} [AddCommGroup X] [Module ℝ X] {m : ℕ} local notation "F" => EuclideanSpace ℝ (Fin m) def IsLinearlyConstrained (problem : FunctionalConstraintsMinimizationProblem X m) : Prop := Set.AffineOn problem.basicFeasibleSet ℝ problem.constraintVector ∧ problem.basicFeasibleSet.IsPolyhedron

Definition 1.1.4.6

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

Source header · Attribution source

Definition 1.1.4.6: a linear optimization problem is a minimization problem whose objective function is affine and which is linearly constrained in the sense of Definition 1.1.4.5.

namespace FunctionalConstraintsMinimizationProblem variable {X : Type*} [AddCommGroup X] [Module ℝ X] {m : ℕ} def IsLinearOptimizationProblem (problem : FunctionalConstraintsMinimizationProblem X m) : Prop := Set.AffineOn problem.basicFeasibleSet ℝ problem.objective ∧ problem.IsLinearlyConstrained

Definition 1.1.4.7

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

Source header · Attribution source

Definition 1.1.4.7: a quadratic optimization problem is a minimization problem whose objective function is quadratic and which is linearly constrained in the sense of Definition 1.1.4.5.

open AffineMap namespace FunctionalConstraintsMinimizationProblem variable {X : Type*} [AddCommGroup X] [Module ℝ X] {m : ℕ} local notation "F" => EuclideanSpace ℝ (Fin m) def IsQuadraticOptimizationProblem (problem : FunctionalConstraintsMinimizationProblem X m) : Prop := Set.QuadraticOn problem.basicFeasibleSet ℝ problem.objective ∧ problem.IsLinearlyConstrained

Definition 1.1.4.8

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

Source header · Attribution source

Definition 1.1.4.8: a quadratically constrained quadratic problem is a minimization problem whose objective function and packaged constraint vector, equivalently every scalar constraint, are quadratic on the basic feasible set.

namespace FunctionalConstraintsMinimizationProblem variable {X : Type*} [AddCommGroup X] [Module ℝ X] {m : ℕ} def IsQuadraticallyConstrainedQuadraticProblem (problem : FunctionalConstraintsMinimizationProblem X m) : Prop := Set.QuadraticOn problem.basicFeasibleSet ℝ problem.objective ∧ Set.QuadraticOn problem.basicFeasibleSet ℝ problem.constraintVector

Example 1.1.5

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

Source header · Attribution source

Example 1.1.5: Functional characteristics with lower and upper bounds define a general minimization problem on the structural set Q: the distinguished characteristic f₀ is the objective, and the remaining characteristics appear as paired lower and upper scalar constraints. The textbook Euclidean formulation is the specialization of this owner to X = ℝⁿ.

universe u variable {m : ℕ} {X : Type u} variable (Q : Set X) (objective : Q → ℝ) variable (characteristics : Fin m → Q → ℝ) (lowerBounds upperBounds : Fin m → ℝ) def boundedCharacteristicProblem : FunctionalConstraintsMinimizationProblem X (m + m)

Example 1.1.6

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

Source header · Attribution source

Example 1.1.6: A system of equations f_j(x) = a_j on a set Q ⊆ ℝⁿ can be converted into the minimization of the canonical squared residual norm on Q; for the coordinate residual map attached to f_j(x) = a_j, this is exactly the textbook sum of squared residuals. The set Q may encode any additional constraints imposed on x.

open scoped BigOperators
universe u
variable {m : ℕ} {X : Type u}
local notation "R" => EuclideanSpace ℝ (Fin m)
noncomputable def equationSystemOptimizationProblem
    {Q : Set X}
    (f : Fin m → Q → ℝ)
    (a : Fin m → ℝ) : SetConstrainedMinimizationProblem Q

Example 1.1.7

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

Source header · Attribution source

Example 1.1.7: Integer constraints can be encoded by adjoining the transcendental equalities sin (π x_i) = 0 to the bounded optimization problem on Q.

variable {n m : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) noncomputable def transcendentalIntegerOptimizationProblem (Q : Set E) (objective : Q → ℝ) (characteristics : Fin m → Q → ℝ) (lowerBounds upperBounds : Fin m → ℝ) : GeneralMinimizationProblem n (m + m + n) := let boundedProblem := boundedCharacteristicProblem Q objective characteristics lowerBounds upperBounds { boundedProblem with constraints := Fin.append boundedProblem.constraints (fun i x ↦ Real.sin (Real.pi * (x.1 i))) senses := Fin.append boundedProblem.senses (fun _ ↦ .eq) }

1.2 — Local Methods in Unconstrained Minimization

Definition 1.2.1

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

Source header · Attribution source

Definition 1.2.1: for a problem P, its model Σ is the part of P known to a numerical method; in this source-facing black-box optimization layer, that model is represented directly by its carrier type.

universe u #check (Type u)

Definition 1.2.2

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

Source header · Attribution source

Definition 1.2.2 is a source-facing recall item in the Chapter 1 black-box optimization domain. Layer targeted by this refinement: * source-facing recall of the core/canonical owner object already used elsewhere in the chapter Primary domain: * black-box optimization oracles as answer maps on a query space Relevant owner-style declarations sampled before refining: * GeneralIterativeScheme.oracle in Algorithm_1_2_10.lean, which stores a single-problem oracle directly as Query → Answer; * OptimizationOracle.IsLocal in Definition_1_2_13.lean, which treats class-level oracles as the curried answer rule Problem → Query → Answer; * the direct zero-, first-, and second-order answer maps in Definition_1_2_9.lean, which use the same owner shape without introducing separate wrapper objects. Owner abstraction: * the function type Query → Answer Primitive data: * the query type Query * the answer type Answer Derived API: * the class-of-problems generalization Problem → Query → Answer from Definition 1.2.8 * locality properties such as OptimizationOracle.IsLocal from Definition 1.2.13 * transcript-based algorithms that consume the oracle by evaluation This recall file intentionally introduces no separate public wrapper such as ProblemOracle. Downstream chapter files should use the function type Query → Answer directly.

universe u v variable {Query : Type u} {Answer : Type v} #check (Query → Answer)

Definition 1.2.3

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

Source header · Attribution source

Definition 1.2.3 is a source-facing recall in the black-box stopping-criterion domain. Layer targeted by this refinement: * source-facing recall of the core/canonical owner expression already used elsewhere in Chapter 1 Primary domain: * stopping predicates on the informational state of a black-box method Relevant owner-style declarations sampled before refining: * Set in mathlib, the owner type of accepted-state predicates; * Set.mem_setOf in mathlib, the canonical bridge between the set and predicate views; * GeneralIterativeScheme.shouldStop in Algorithm_1_2_10.lean, which stores the stopping rule directly as Set (Set (Query × Answer)); * GeneralIterativeScheme.HaltsAt in Algorithm_1_2_10.lean, which derives halting from membership in that accepted-state set. Source/core/bridge triage: * source-facing: the ε-stopping rule itself; * core/canonical: the accepted-state set Set State; * bridge/view: Set.mem_setOf, which converts between set-builder and predicate syntax. Owner abstraction: * the accepted-state predicate/set Set State Primitive data: * the informational-state type State * the accepted-state set itself Derived API: * set-builder membership via Set.mem_setOf * downstream consumers such as GeneralIterativeScheme.shouldStop * halting predicates such as GeneralIterativeScheme.HaltsAt This recall file intentionally introduces no separate public wrapper such as StoppingCriterion. The positivity witness 0 < ε belongs to the ambient method/problem data that owns the stopping rule, not to the stopping rule itself.

universe u variable {State : Type u} #check (Set State)

Definition 1.2.4

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

Source header · Attribution source

Definition 1.2.4: a black-box optimization problem class is the triple 𝒫 ≡ (Σ, 𝒪, 𝒯_ε), where Σ is a model of problems, 𝒪 is the class oracle, and 𝒯_ε is the chosen stopping criterion. The accuracy threshold is already part of the source-facing stopping criterion 𝒯_ε, so it is not stored as separate primitive data in the owner.

universe u v w x structure BlackBoxOptimizationProblemClass (Query : Type v) (Answer : Type w) (State : Type x) where /-- The model `Σ` of optimization problems. -/ model : Type u /-- The class oracle `𝒪`, as a model-indexed family of fixed-problem oracles. -/ oracle : model → Query → Answer /-- The fixed `ε`-stopping criterion `𝒯_ε`, in the canonical owner form `Set State`. -/ stoppingCriterion : Set State

Definition 1.2.5

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

Source header · Attribution source

Definition 1.2.5 is the source-facing existential statement ∃ c > 0, ∃ p > 0, ∀ ⦃k : ℕ⦄, 0 < k → r k ≤ c / Real.rpow (k : ℝ) p. Unlike Definitions 1.2.6 and 1.2.7, this file has no reused fixed-parameter owner elsewhere in the chapter. The previous alias HasSublinearRateOfConvergence therefore added no owner-level mathematics and only duplicated the source statement. The numbered item is now recalled directly, while the square-root specialization and later-rate bridge remain as the actual reusable API.

variable {r : ℕ → ℝ} #check (∃ c > 0, ∃ p > 0, ∀ ⦃k : ℕ⦄, 0 < k → r k ≤ c / Real.rpow (k : ℝ) p)

Definition 1.2.6

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

Source header · Attribution source

Definition 1.2.6 is the source-facing existence statement ∃ c > 0, ∃ q : ℝ, 0 < q ∧ q ≤ 1 ∧ HasGeometricRateOfConvergence r q c. The owner abstraction is HasGeometricRateOfConvergence; the numbered item only restricts the admissible witnesses c and q.

open Asymptotics Filter variable {r : ℕ → ℝ} #check (∃ c > 0, ∃ q : ℝ, 0 < q ∧ q ≤ 1 ∧ HasGeometricRateOfConvergence r q c)

Definition 1.2.7

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

Source header · Attribution source

Definition 1.2.7 is recalled by the canonical specialization ∃ c > 0, HasEventuallySuperlinearErrorBound r 0 c 0.

variable {r : ℕ → ℝ} #check (∃ c > 0, HasEventuallySuperlinearErrorBound r 0 c 0)

Definition 1.2.8

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

Source header · Attribution source

Definition 1.2.8: an optimization oracle for problem instances in Problem and query points in Query is just a curried answer rule Problem → Query → Answer.

universe u v w variable {Problem : Type u} {Query : Type v} {Answer : Type w} #check (Problem → Query → Answer)

Definition 1.2.9

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

Source header · Attribution source

Definition 1.2.9 (1): a zero-order oracle for the objective function f returns the value f x at the query point x.

open scoped Gradient universe u variable {E : Type u} variable (f : E → ℝ) #check (f : E → ℝ)

Algorithm 1.2.10

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

Source header · Attribution source

Algorithm 1.2.10: a general iterative scheme is organized around the accumulated informational set 𝓘_k of oracle samples. The current query point, the stopping criterion, and the output are all chosen from that informational set; in particular, the initial point is query ∅ = x₀. This uses the informational state owner from Definition 1.2.13 directly, rather than an auxiliary ordered transcript.

universe u v variable {Query : Type u} {Answer : Type v} structure GeneralIterativeScheme (Query : Type u) (Answer : Type v) where oracle : Query → Answer query : Set (Query × Answer) → Query shouldStop : Set (Set (Query × Answer)) output : Set (Query × Answer) → Query

Definition 1.2.11

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

Source header · Attribution source

Definition 1.2.11: a natural number N is the analytical complexity of a general iterative scheme when N is the first oracle-call count at which the scheme reaches the chosen stopping criterion. If the scheme never reaches that stopping criterion, no such N exists.

universe u v variable {Query : Type u} {Answer : Type v} namespace GeneralIterativeScheme variable (scheme : GeneralIterativeScheme Query Answer) def IsAnalyticalComplexity (N : ℕ) : Prop := IsLeast {k : ℕ | scheme.HaltsAt k} N

Definition 1.2.12

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

Source header · Attribution source

Definition 1.2.12: A natural number M is the arithmetical complexity of a method when M is the total number of arithmetic operations, counting both oracle work and method work, required to reach the analytical complexity threshold for the chosen stopping criterion.

universe u v variable {Query : Type u} {Answer : Type v} namespace GeneralIterativeScheme variable (scheme : GeneralIterativeScheme Query Answer) variable (oracleWork : Query → Answer → ℕ) variable (methodWork : Set (Query × Answer) → ℕ) def IsArithmeticalComplexity (M : ℕ) : Prop := ∃ N : ℕ, scheme.IsAnalyticalComplexity N ∧ M = scheme.totalArithmeticWork oracleWork methodWork N

Definition 1.2.13

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

Source header · Attribution source

Definition 1.2.13 lies in the informational-state/locality domain of black-box optimization. Layer targeted by this refinement: * source-facing informational-state and locality declarations built from the core/canonical owner expressions already used in Chapter 1 Primary domain: * information-set-based black-box methods and local optimization oracles Relevant owner-style declarations sampled before refining: * #check (Problem → Query → Answer) in Definition_1_2_8.lean, the class-level oracle owner; * GeneralIterativeScheme.query, GeneralIterativeScheme.shouldStop, and GeneralIterativeScheme.output in Algorithm_1_2_10.lean, which use the informational state Set (Query × Answer); * Set.insert in mathlib, the canonical update operation for adjoining one new oracle sample to an informational set; * DeterministicValueOracleMethod.oracleTranscript in Theorem_1_3_9.lean, a downstream ordered sample-history view kept separate from the owner informational set. Owner abstractions: * the informational state is the oracle-sample set Set (Query × Answer); * locality for a class of optimization problems is `OptimizationOracle.IsLocal oracle sameDataNear`. Primitive data: * query/answer pairs (x, oracle x) recorded as members of an accumulated informational set; * an oracle Problem → Query → Answer together with the local-data relation sameDataNear. Derived API: * information-set-based query, stopping, and output rules in Algorithm_1_2_10.lean; * direct use of the locality hypothesis by application, without an extra wrapper lemma. This file therefore exposes the informational-state type expression directly and defines the owner locality predicate where the chapter first uses that notion, instead of keeping a parallel public wrapper for "informational state" or "local method".

universe u v w variable {Problem : Type u} {Query : Type v} {Answer : Type w} #check (Set (Query × Answer))

1.3 — First-Order Methods in Nonlinear Optimization

Definition 1.3.1

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

Source header · Attribution source

Definition 1.3.1: the textbook box B_n = [0,1]^n in ℝⁿ.

abbrev zeroOneBox (n : ℕ) : Set (EuclideanSpace ℝ (Fin n)) := {x | ∀ i : Fin n, x i ∈ Set.Icc (0 : ℝ) 1}

Definition 1.3.2

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

Source header · Attribution source

Definition 1.3.2: the canonical coordinate ℓ∞ seminorm on ℝⁿ, obtained by pulling back the ordinary sup norm on Fin n → ℝ along the Euclidean coordinate linear equivalence. The textbook ℓ∞ norm is the derived source-facing owner EuclideanSpace.linftyNorm.

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Coord" => Fin n → ℝ local notation "coordEquiv" => EuclideanSpace.equiv (Fin n) ℝ namespace EuclideanSpace abbrev linftySeminorm (n : ℕ) : Seminorm ℝ (EuclideanSpace ℝ (Fin n)) := Seminorm.comp (normSeminorm ℝ (Fin n → ℝ)) (coordinateLinftyEquiv n).toLinearMap

Definition 1.3.3

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

Source header · Attribution source

Definition 1.3.3: the textbook box problem min_{x ∈ B_n} f(x) with B_n = [0,1]^n.

universe u v open scoped ConstrainedArgmin variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) abbrev zeroOneBoxProblem (n : ℕ) (f : EuclideanSpace ℝ (Fin n) → ℝ) : SetConstrainedMinimizationProblem (EuclideanSpace ℝ (Fin n))

Definition 1.3.4

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

Source header · Attribution source

Definition 1.3.4: the textbook class 𝒫∞[n, L] of objectives on B_n = [0,1]^n that are L-Lipschitz in the ℓ∞ geometry. Its primitive owner is the canonical coordinate-cube predicate LipschitzOnWith.

universe u v variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Coord" => Fin n → ℝ local notation "coordEquiv" => EuclideanSpace.equiv (Fin n) ℝ local notation "coordBox" => (Set.Icc (0 : Coord) 1) def linftyLipschitzClass (n : ℕ) (L : NNReal) : Set (EuclideanSpace ℝ (Fin n) → ℝ) := {f | LipschitzOnWith L (f ∘ (EuclideanSpace.equiv (Fin n) ℝ).symm) (Set.Icc (0 : Fin n → ℝ) 1)}

Algorithm 1.3.5

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

Source header · Attribution source

Algorithm 1.3.5 as a deterministic value-oracle method: query the midpoint grid uniformGrid n p in a canonical order and return the sampled grid point with minimal observed value.

variable (n : ℕ) open scoped ConstrainedArgmin local notation "E" => EuclideanSpace ℝ (Fin n) noncomputable def uniformGridMethod (p : ℕ+) : DeterministicValueOracleMethod (zeroOneBox n)

Theorem 1.3.6

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

Source header · Attribution source

Theorem 1.3.6: if f ∈ 𝒫∞[n, L] and the value f xBar is minimal on the midpoint grid of mesh 1 / p, then f xBar is at most L / (2p) above the canonical optimal value of the box problem min_{x ∈ B_n} f(x).

variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) open SetConstrainedMinimizationProblem theorem uniformGrid_value_le_optimalValue_add_of_isMinOn (f : E → ℝ) (L : NNReal) (p : ℕ+) (xBar : E) (hf_lipschitz : f ∈ 𝒫∞[n, L]) (hxBar_min : IsMinOn f (uniformGrid n p) xBar) : (f xBar : EReal) ≤ (zeroOneBoxProblem n f).optimalValue + (L : ℝ) / (2 * (p : ℝ))

Definition 1.3.7

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

Source header · Attribution source

Definition 1.3.7: xBar is an ε-approximate minimizer in function value for a set-constrained minimization problem when it is feasible and its objective value is at most ε above the optimal value.

universe u namespace SetConstrainedMinimizationProblem open scoped ConstrainedArgmin variable {X : Type u} def IsApproximateMinimizer (problem : SetConstrainedMinimizationProblem X) (ε : ℝ) (xBar : X) : Prop := xBar ∈ problem.feasibleSet ∧ (problem xBar : EReal) ≤ problem.optimalValue + ε

Corollary 1.3.8

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

Source header · Attribution source

Corollary 1.3.8: for the uniform grid method on the L-Lipschitz box problem class, the analytical complexity is at most (\lfloor L / (2 ε) \rfloor + 1)^n.

variable (n : ℕ) open DeterministicValueOracleMethod theorem uniformGridMethod_analyticalComplexity_bound (L : NNReal) {ε : ℝ} (hε : 0 < ε) : (uniformGridMethod n (Nat.floor ((L : ℝ) / (2 * ε))).succPNat).SolvesLinftyLipschitzProblemClassWithin L ε ((Nat.floor ((L : ℝ) / (2 * ε)) + 1) ^ n)

Theorem 1.3.9

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

Source header · Attribution source

Theorem 1.3.9: if 1 ≤ n and ε < L / 2, then any deterministic value-oracle method that guarantees for every objective in the textbook class 𝒫∞ a feasible output x̄ ∈ B_n = [0,1]^n with function-value gap f x̄ - f^* < ε after k calls must satisfy ⌊L / (2 ε)⌋^n ≤ k.

universe u variable {n : ℕ} open SetConstrainedMinimizationProblem open DeterministicValueOracleMethod local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Coord" => Fin n → ℝ local notation "coordEquiv" => EuclideanSpace.equiv (Fin n) ℝ theorem linftyLipschitz_value_oracle_complexity_lower_bound (hn : 1 ≤ n) {L : NNReal} {ε : ℝ} (hεL : ε < (L : ℝ) / 2) {k : ℕ} (method : DeterministicValueOracleMethod (zeroOneBox n)) (hmethod : method.SolvesLinftyLipschitzProblemClassWithin L ε k) : Nat.floor ((L : ℝ) / (2 * ε)) ^ n ≤ k

Proposition 1.3.10

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

Source header · Attribution source

Proposition 1.3.10: there are absolute constants c, C₁, and C₂ such that whenever ε > 0 and ε ≤ c (L : ℝ) / n, the canonical upper and lower complexity estimates from Corollary 1.3.8 and Theorem 1.3.9 are comparable up to the multiplicative constants C₁ and C₂.

variable {L : NNReal} {ε : ℝ} {n : ℕ} theorem exists_absolute_constants_gridComplexity_bounds : ∃ c C₁ C₂ : Set.Ioi (0 : ℝ), ∀ {L : NNReal} {ε : ℝ} {n : ℕ} (_ : 0 < ε) (_ : ε ≤ (c : ℝ) * (L : ℝ) / (n : ℝ)), let m := Nat.floor ((L : ℝ) / (2 * ε)) (C₁ : ℝ) * (m ^ n : ℝ) ≤ ((m + 1) ^ n : ℝ) ∧ ((m + 1) ^ n : ℝ) ≤ (C₂ : ℝ) * (m ^ n : ℝ)

Example 1.3.11

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

Source header · Attribution source

Example 1.3.11: for the box-Lipschitz problem class with L = 2, n = 10, and ε = 0.01, any deterministic value-oracle method needs at least 10^20 oracle calls; with at least 10 arithmetic operations per call and processor throughput 10^6 operations per second, this yields lower bounds 10^21 on arithmetic operations and 10^15 seconds on runtime.

local notation "L0" => (2 : NNReal) local notation "eps0" => (1 / 100 : ℝ) variable {k : ℕ} (method : DeterministicValueOracleMethod (zeroOneBox 10)) theorem complexityBounds_n10_L2_eps001 (hmethod : method.SolvesLinftyLipschitzProblemClassWithin L0 eps0 k) : 10 ^ 20 ≤ k ∧ 10 ^ 21 ≤ 10 * k ∧ (10 : ℝ) ^ 15 ≤ ((10 : ℝ) * k) / (10 : ℝ) ^ 6

Definition 1.3.12

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

Source header · Attribution source

Definition 1.3.12: The uniform-grid Riemann-sum approximation on [0, 1] with right-endpoint grid points x_i = i / N for a positive number N of subintervals is (1 / N) * ∑_{i=1}^N f(x_i). The exact comparison quantity remains the canonical interval integral ∫ x in (0 : ℝ)..1, f x = ∫_0^1 f(x) dx.

noncomputable def uniformGridRiemannSum (f : ℝ → ℝ) (N : ℕ+) : ℝ := (1 / (N : ℝ)) * ∑ i ∈ Finset.range (N : ℕ), f ((i + 1 : ℝ) / N)

Proposition 1.3.13

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

Source header · Attribution source

Proposition 1.3.13: If f is Lipschitz on [0, 1] with constant L, then the right-endpoint uniform-grid Riemann sum with N subintervals approximates the integral over [0, 1] with error at most L / (2 N).

open MeasureTheory intervalIntegral variable (f : ℝ → ℝ) (L : NNReal) (N : ℕ+) variable (hLip : LipschitzOnWith L f (Set.Icc (0 : ℝ) 1)) include hLip theorem abs_intervalIntegral_sub_uniformGridRiemannSum_le :

Supporting modules

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

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

Source header · Attribution source