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.
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.
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.
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.
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.
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.
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.
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) : FDefinition 1.4.8
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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) 1Lemma 1.4.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 = 0Definition 1.4.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 HasDerivWithinAtProposition 1.4.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 = 0Theorem 1.4.14
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 lamStarDefinition 1.4.15
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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) :
PropTheorem 1.4.19
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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).IsSymmTheorem 1.4.20
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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) sTheorem 1.4.21
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 yDefinition 1.5.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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) QDefinition 1.5.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 HasLipschitzContinuousHessianLemma 1.5.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 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.
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.
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.
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 • 1Algorithm 1.6.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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) :
ℕ → EDefinition 1.6.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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.
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 - fStarDefinition 1.6.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 * φ NProposition 1.6.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 = 0Proposition 1.6.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 xLemma 1.8.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
Proposition 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.
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.minimizerLemma 1.8.8
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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).PosDefDefinition 1.8.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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 NDefinition 1.9.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.PosDefDefinition 1.9.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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)) = 0Corollary 1.9.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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) = 0Corollary 1.9.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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) = 0Algorithm 1.9.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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)
stepSizeDefinition 1.9.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.minimizerTheorem 1.9.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.minimizerTheorem 1.10.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 uDefinition 1.10.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 1Theorem 1.10.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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] problemProposition 1.10.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 < 1Example 1.10.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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] lagrangianRelaxationExampleProposition 1.10.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.primalOptimalValueDefinition 1.10.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.StrictlyFeasibleExample 1.10.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 quadraticPenaltyAlgorithm 1.10.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 = lagrangianRelaxationExampleLambdaStarDefinition 1.10.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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 atTopAlgorithm 1.10.20
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.HasLeConstraintsTheorem 1.10.22
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.NonemptyDefinition 1.1.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 xDefinition 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.
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.univDefinition 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.
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.
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.basicFeasibleSetDefinition 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.
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.IsSmoothDefinition 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.
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.IsPolyhedronDefinition 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.
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.IsLinearlyConstrainedDefinition 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.
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.IsLinearlyConstrainedDefinition 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.
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.constraintVectorExample 1.1.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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 StateDefinition 1.2.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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) → QueryDefinition 1.2.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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} NDefinition 1.2.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 NDefinition 1.2.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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).toLinearMapDefinition 1.3.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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.
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 ≤ kProposition 1.3.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 : ℝ) ^ 6Definition 1.3.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
-
FirstOrderTaylorModel.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.