Chapter 01 — Introduction
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 1.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.1: if A is a nonsingular real square matrix, then every x : Fin n → ℝ satisfies v x / N A⁻¹ ≤ v (A *ᵥ x) for every vector norm v and every compatible matrix norm N. This keeps the labeled exercise at the source-facing matrix-norm layer, while div_matrixBound_inv_le_vectorNorm_mulVec records the weaker consistency-only generalization.
open Matrix
-- This exercise reuses the chapter's matrix-norm owners from `Definition_1_2_2` rather than
-- duplicating local norm wrappers.
theorem div_invMatrixNorm_le_vectorNorm_mulVec
{n : ℕ} (v : (Fin n → ℝ) → ℝ) (N : Matrix (Fin n) (Fin n) ℝ → ℝ)
(hv : IsVectorNorm v) (hNorm : IsMatrixNorm N) (hCons : MatrixNormConsistent v v N)
(A : Matrix (Fin n) (Fin n) ℝ) (hA : IsUnit A) (x : Fin n → ℝ) :
v x / N A⁻¹ ≤ v (A *ᵥ x)Exercise 1.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.2 Domain sampling for this item: - primitive data: the lpNorm owner and the standard vector-norm notation ‖·‖₁, ‖·‖₂, ‖·‖∞ live in Definition_1_2_1.lean; - chapter owner abstraction: the six canonical vector-norm comparison inequalities already live in Definition_1_2_3.lean as vectorTwoNorm_le_vectorOneNorm, vectorOneNorm_le_sqrt_mul_vectorTwoNorm, vectorInfNorm_le_vectorTwoNorm, vectorTwoNorm_le_sqrt_mul_vectorInfNorm, vectorInfNorm_le_vectorOneNorm, and vectorOneNorm_le_nat_mul_vectorInfNorm. This exercise therefore stays recall-only: it adds no new source-facing owner beyond those existing chapter theorems.
variable {n : ℕ}
#check vectorTwoNorm_le_vectorOneNormExercise 1.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.3 Canonical recall for Exercise 1.3 (1): the Euclidean Cauchy-Schwarz inequality on ℝ^n is the mathlib theorem abs_real_inner_le_norm.
open Matrix
-- Semantic recall hits verified for this item: `abs_real_inner_le_norm` is the canonical
-- Euclidean Cauchy-Schwarz statement, and `LinearMap.BilinForm.apply_sq_le_of_symm` is the
-- core bilinear-form Cauchy-Schwarz inequality behind the positive-definite matrix variant.
#check abs_real_inner_le_normExercise 1.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.4 Domain sampling for this item: - primitive data: a matrix norm N : Matrix (Fin n) (Fin n) ℝ → ℝ, its matrix-norm hypothesis IsMatrixNorm N, its submultiplicativity hypothesis MatrixNormSubmultiplicative N, and the perturbation data A, B, α, β; - chapter owner abstractions: IsMatrixNorm and MatrixNormSubmultiplicative already live in Definition_1_2_2.lean; - derived API already available upstream: vonNeumannLemma_isUnit_and_inv_norm_le_of_norm_sub_le, vonNeumannLemma_isUnit_of_norm_sub_le, vonNeumannLemma_inv_norm_le_of_norm_sub_le from Theorem_1_2_6.lean. This exercise is therefore recall-only: the source-facing inverse-norm estimate (1.2.45) is already stated canonically by vonNeumannLemma_inv_norm_le_of_norm_sub_le, so this file keeps no parallel local matrix-norm owners and no renamed wrapper theorem.
#check vonNeumannLemma_inv_norm_le_of_norm_sub_leExercise 1.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.5: if A = U * D * Vᴴ is a singular value decomposition, then A⁺ = V * D⁺ * Uᴴ. For rectangular diagonal D, the preceding theorem identifies D⁺ with the source formula (1.2.54).
open scoped Matrix
namespace Matrix
open LinearMap
scoped postfix:max "⁺" => Matrix.pseudoinverse
theorem pseudoinverse_eq_mul_pseudoinverse_of_singularValueDecomposition {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℂ) (U : Matrix (Fin m) (Fin m) ℂ)
(D : Matrix (Fin m) (Fin n) ℂ) (V : Matrix (Fin n) (Fin n) ℂ)
(hSVD : IsSingularValueDecomposition A U D V) :
A⁺ = V * D⁺ * Uᴴ
Exercise 1.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.6 (1): the Sherman-Morrison formula (1.2.67) as the m = Fin 1, C = 1 specialization of the Woodbury identity.
universe u v
theorem shermanMorrisonFormula
{n : Type u} [Fintype n] [DecidableEq n] {α : Type v} [CommRing α]
(A : Matrix n n α) (U : Matrix n (Fin 1) α) (V : Matrix (Fin 1) n α)
(hA : IsUnit A)
(hRankOne : IsUnit ((1 : Matrix (Fin 1) (Fin 1) α) + V * A⁻¹ * U)) :
(A + U * V)⁻¹ =
A⁻¹ - A⁻¹ * U * ((1 : Matrix (Fin 1) (Fin 1) α) + V * A⁻¹ * U)⁻¹ * V * A⁻¹Exercise 1.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.7 Recall-only entry: this exercise asks for Theorem 1.2.6, whose owner declaration is vonNeumannLemma_isUnit_and_inv_norm_le_of_norm_sub_le.
#check vonNeumannLemma_isUnit_and_inv_norm_le_of_norm_sub_leExercise 1.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.8 Recall-only entry: the two formulas requested here are exactly the source-facing chapter owners norm_image_sub_le_of_segment_fderiv_bound and norm_image_sub_sub_le_of_segment_fderiv_deviation_bound.
#check norm_image_sub_le_of_segment_fderiv_bound
Exercise 1.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.9 (1): the general Fréchet-to-Gateaux implication is already owned in Definition_1_2_28 at the intrinsic normed-space level.
local notation "Point2" => EuclideanSpace ℝ (Fin 2) #check gateauxDifferentiableWithinAt_of_hasFDerivAt
Exercise 1.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.10 Recall-only entry: this exercise asks for Theorem 1.2.23, whose owner declaration is cubicRemainderBound_of_hessian_lipschitzOn.
#check cubicRemainderBound_of_hessian_lipschitzOn
Exercise 1.11
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.11: if (S i)_{i ∈ t} is a finite family of convex subsets of EuclideanSpace ℝ (Fin n), then ⋂ i ∈ t, S i is convex.
variable {n : ℕ}
universe u
variable {ι : Type u} (t : Finset ι) {S : ι → Set (EuclideanSpace ℝ (Fin n))}
theorem convex_iInter_finset (hS : ∀ i ∈ t, Convex ℝ (S i)) :
Convex ℝ (⋂ i ∈ t, S i)Exercise 1.12
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.12: a set S is convex if and only if every finite convex combination of points of S still belongs to S. This is the finite-family bridge to the canonical Convex API.
universe u
variable {R E : Type*} [Field R] [LinearOrder R] [IsStrictOrderedRing R]
[AddCommGroup E] [Module R E]
theorem convex_iff_sum_smul_mem {S : Set E} :
Convex R S ↔
∀ (ι : Type u) [Fintype ι] (x : ι → E) (α : ι → R),
(∀ i, x i ∈ S) →
(∀ i, 0 ≤ α i) → (∑ i, α i) = 1 → ∑ i, α i • x i ∈ SExercise 1.13
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.13: for A : Matrix (Fin m) (Fin n) ℝ and b : EuclideanSpace ℝ (Fin m), the feasible set {x : EuclideanSpace ℝ (Fin n) | Matrix.toEuclideanLin A x = b ∧ ∀ i : Fin n, 0 ≤ x i} is convex.
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem convex_linearEqNonnegativeSet
(A : Matrix (Fin m) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin m)) :
Convex ℝ {x : Point | Matrix.toEuclideanLin A x = b ∧ ∀ i : Fin n, 0 ≤ x i}
Exercise 1.14
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.14 (1): the set D₁ is convex.
open scoped RealInnerProductSpace
-- Semantic recall hits verified for this item: the primitive pieces are closed half-spaces, with
-- canonical owner declarations `closedLowerHalfSpace` and `closedUpperHalfSpace`; convexity is
-- derived from `convex_halfSpace_le`, `convex_halfSpace_ge`, and `Convex.inter`.
local notation "Point" => EuclideanSpace ℝ (Fin 2)
theorem convexUnionCounterexampleD₁_convex :
Convex ℝ convexUnionCounterexampleD₁Exercise 1.15
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.15: the convex hull of Set.insert 0 (Set.range (fun i : Fin 2 ↦ EuclideanSpace.single i 1)) = {(0, 0), (1, 0), (0, 1)} is the triangle {x | 0 ≤ x 0 ∧ 0 ≤ x 1 ∧ x 0 + x 1 ≤ 1}.
open scoped BigOperators
local notation "Point" => EuclideanSpace ℝ (Fin 2)
local notation "e0" => (EuclideanSpace.single 0 (1 : ℝ) : Point)
local notation "e1" => (EuclideanSpace.single 1 (1 : ℝ) : Point)
theorem convexHull_originAndUnitBasisSet_eq :
convexHull ℝ
(Set.insert (0 : EuclideanSpace ℝ (Fin 2))
(Set.range (fun i : Fin 2 ↦ EuclideanSpace.single i (1 : ℝ)))) =
{x : EuclideanSpace ℝ (Fin 2) | 0 ≤ x 0 ∧ 0 ≤ x 1 ∧ x 0 + x 1 ≤ 1}Exercise 1.16
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.16 Core/canonical owner: convexHull. For S : Set (EuclideanSpace ℝ (Fin n)), mathlib already provides the two equivalent textbook descriptions of convexHull ℝ S. - convexHull_eq: convexHull ℝ S is the set of all finite convex combinations of points of S. - convexHull_eq_iInter: convexHull ℝ S is the intersection of all convex sets containing S.
#check convexHullExercise 1.17
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.17 Layer triage: - source-facing: finite nonnegative sums of convex functions on ℝ^n - core/canonical: ConvexOn - bridge/view: convexOn_nonneg_finset_sum The Chapter 1 theorem convexOn_nonneg_finset_sum is the owner abstraction for this exercise. The source normalization hypothesis ∑ i, α i = 1 is stronger than needed for convexity of a finite weighted sum, so the refined file reuses the upstream owner directly instead of keeping a parallel Fin m-indexed proof term.
#check convexOn_nonneg_finset_sumExercise 1.18
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.18 (1): the function exercise118Fun1 on ℝ² is not convex.
local notation "Point2" => EuclideanSpace ℝ (Fin 2)
local notation "Point3" => EuclideanSpace ℝ (Fin 3)
theorem exercise118Fun1_not_convex :
¬ ConvexOn ℝ Set.univ exercise118Fun1Exercise 1.19
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.19 This exercise is already recorded upstream in Theorem_1_3_11.lean. Parts (1) and (2) are direct recalls of mathlib's owner theorems ConvexOn.smul and ConvexOn.add, while part (3) reuses the Chapter 1 theorem convexOn_nonneg_finset_sum.
#check fun {n : ℕ} {S : Set (EuclideanSpace ℝ (Fin n))} {f : EuclideanSpace ℝ (Fin n) → ℝ}
{α : ℝ} (hf : ConvexOn ℝ S f) (hα : 0 ≤ α) ↦
(hf.smul hα : ConvexOn ℝ S (α • f))Exercise 1.20
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Exercise 1.20 This exercise adds no new primitive owner beyond the existing Chapter 1 local-optimality results. Its three clauses are already recorded upstream by the canonical chapter theorems gradient_eq_zero_of_isLocalMinOn, iteratedFDeriv_nonneg_of_isLocalMinOn_secondOrderNecessary, and isStrictLocalMin_of_isStationaryPoint_of_iteratedFDeriv_pos. The refined file therefore stays at the recall layer and deletes the parallel exercise-local theorem names.
#check gradient_eq_zero_of_isLocalMinOn
1.1 — Introduction
Definition 1.1.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.1-extra-1 (1). An optimization problem on ℝ^n consists of an objective function and a feasible set of decision variables.
variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
structure OptimizationProblem (n : ℕ) where
objective : (Fin n → ℝ) → ℝ
feasibleSet : Set (Fin n → ℝ)1.2 — Mathematics Foundations
Definition 1.2.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.1: for 1 ≤ p, the ℓ^p norm is a vector norm on ℝ^n.
open Matrix
open scoped BigOperators
-- Analogues checked for this item: `Seminorm`, `NormedSpace.Core`,
-- `PiLp.norm_seminormedAddCommGroupToPi`, `PiLp.norm_eq_of_nat`, `lp.norm_eq_ciSup`,
-- `Finset.sup'`, `Matrix.PosDef`.
variable {n : ℕ}
instance lpNorm_isVectorNorm (p : ENNReal) [Fact (1 ≤ p)] :
IsVectorNorm (fun x : Fin n → ℝ ↦ lpNorm p x)Definition 1.2.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.2 (10): for rectangular A, there is a greatest real root of (Aᵀ * A).charpoly whose square root equals the induced ℓ^2 matrix norm.
open Matrix
open scoped BigOperators Matrix
-- This file builds on the Chapter 1 vector-norm owner from `Definition_1_2_1` and adds only the
-- matrix-norm-specific source-facing definitions and companion statements used in the sequel.
variable {n : ℕ}
open scoped Matrix.Norms.L2Operator
theorem l2MatrixNorm_eq_sqrt_maxEigenvalue_transpose_mul {m n : ℕ} [Nonempty (Fin n)]
(A : Matrix (Fin m) (Fin n) ℝ) :
∃ μ : ℝ, IsGreatest (Aᵀ * A).charpoly.roots.toFinset μ ∧
lpMatrixNorm (2 : ENNReal) A = Real.sqrt μDefinition 1.2.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.3: clause (8), the lower spectral-eigenvalue bound for the positive-definite A-norm.
open Matrix
open Matrix.IsHermitian
theorem sqrt_lambdaMin_mul_vectorTwoNorm_le_matrixInducedVectorNorm {n : ℕ}
(A : Matrix (Fin n) (Fin n) ℝ) (hA : A.PosDef) (lambdaMin : ℝ)
(hLambdaMin : IsLeast (Set.range (posDefEigenvalues A hA)) lambdaMin)
(x : Fin n → ℝ) :
Real.sqrt lambdaMin * ‖x‖₂ ≤
ellipsoidNorm A xDefinition 1.2.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.4 (1): in ℝ^n, a sequence is Cauchy iff it satisfies the textbook ε-N characterization.
open Filter
universe v
-- Mathlib recall: `Metric.cauchySeq_iff`, `cauchySeq_tendsto_of_complete`, and
-- `Metric.complete_of_cauchySeq_tendsto` provide the canonical API behind these
-- source-facing specializations.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem euclideanCauchySeq_iff (x : ℕ → Point) :
CauchySeq x ↔
∀ ε > 0, ∃ N : ℕ, ∀ m > N, ∀ l > N, ‖x m - x l‖ < εTheorem 1.2.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.5: if N is a submultiplicative matrix norm on Matrix (Fin n) (Fin n) ℝ, with N 1 = 1, then the Neumann series gives the inverse formula and inverse-norm bound for 1 - E whenever N E < 1; moreover, if A is nonsingular and N (A⁻¹ * (B - A)) < 1, then B is nonsingular with the corresponding perturbation-series formula and norm bound for B⁻¹.
open scoped BigOperators
-- Semantic recall: these statements reuse the chapter's source-facing matrix
-- norm owners from Definition 1.2.2. The proof works by wrapping matrices so
-- the abstract norm `N` becomes the ambient norm and then transporting the
-- resulting geometric-series identities back to ordinary matrices.
variable {n : ℕ}
variable {N : Matrix (Fin n) (Fin n) ℝ → ℝ}
theorem vonNeumannLemma
(hNorm : IsMatrixNorm N) (hSub : MatrixNormSubmultiplicative N)
(hN_one : N 1 = 1) :
(∀ E : Matrix (Fin n) (Fin n) ℝ, N E < 1 →
IsUnit (1 - E) ∧
(1 - E)⁻¹ = ∑' k : ℕ, E ^ k ∧
N ((1 - E)⁻¹) ≤ 1 / (1 - N E)) ∧
(∀ A B : Matrix (Fin n) (Fin n) ℝ, IsUnit A → N (A⁻¹ * (B - A)) < 1 →
IsUnit B ∧
B⁻¹ = ∑' k : ℕ, (1 - A⁻¹ * B) ^ k * A⁻¹ ∧
N B⁻¹ ≤ N A⁻¹ / (1 - N (A⁻¹ * (B - A))))Theorem 1.2.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.6: if N is a matrix norm on Matrix (Fin n) (Fin n) ℝ and is submultiplicative with N 1 = 1, if A is invertible with N A⁻¹ ≤ α, if N (A - B) ≤ β, and if α * β < 1, then B is invertible and N B⁻¹ ≤ α / (1 - α * β).
variable {n : ℕ}
variable {N : Matrix (Fin n) (Fin n) ℝ → ℝ}
theorem vonNeumannLemma_isUnit_and_inv_norm_le_of_norm_sub_le
(hNorm : IsMatrixNorm N) (hSub : MatrixNormSubmultiplicative N) (hN_one : N 1 = 1)
{A B : Matrix (Fin n) (Fin n) ℝ} {α β : ℝ}
(hA : IsUnit A) (hAinv : N A⁻¹ ≤ α) (hAB : N (A - B) ≤ β) (hαβ : α * β < 1) :
IsUnit B ∧ N B⁻¹ ≤ α / (1 - α * β)Theorem 1.2.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.7: for A ∈ ℂ^(m × n) and b ∈ ℂ^m, a vector x equals Matrix.pseudoinverseMulVec A b = A⁺ b if and only if it is a least-squares solution of Matrix.toEuclideanLin A x = b with minimal norm among all least-squares solutions. This expresses that A⁺ b is the unique minimal least-squares solution of `Matrix.toEuclideanLin A x = b` in the Euclidean norm.
namespace Matrix
open LinearMap
variable {m n : Type} [Fintype m] [Fintype n]
theorem eq_pseudoinverseMulVec_iff_isMinimalLeastSquaresSolution
(A : Matrix m n ℂ) (b : EuclideanSpace ℂ m)
(x : EuclideanSpace ℂ n) :
x = Matrix.pseudoinverseMulVec A b ↔ IsMinimalLeastSquaresSolution A b x
Definition 1.2.8
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.8 (1): for a symmetric real square matrix A, negative definiteness means that -A is positive definite.
namespace Matrix
variable {n : ℕ}
abbrev NegDef (A : Matrix (Fin n) (Fin n) ℝ) : Prop :=
(-A).PosDefDefinition 1.2.9
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.9: the matrix-side complex Rayleigh quotient is the quotient uᴴ A u / uᴴ u, written in coordinates as (dotProduct (star u) (A.mulVec u)) / dotProduct (star u) u. The source's Hermitian and nonzero hypotheses are companion theorem assumptions rather than data of the quotient itself.
noncomputable def rayleighQuotient {n : ℕ} (A : Matrix (Fin n) (Fin n) ℂ)
(u : Fin n → ℂ) : ℂ :=
dotProduct (star u) (A.mulVec u) / dotProduct (star u) uTheorem 1.2.10
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.10 (1): the matrix Rayleigh quotient is homogeneous on nonzero complex scalar multiples.
open ContinuousLinearMap
-- Source/core/bridge triage for this file:
-- * source-facing owner: `rayleighQuotient` from `Definition_1_2_9`
-- * core/canonical owner: `ContinuousLinearMap.rayleighQuotient`
-- * bridge/view kept here: `A.toEuclideanLin.toContinuousLinearMap`, comparing the matrix
-- quotient with the canonical Euclidean Hermitian Rayleigh quotient on
-- `EuclideanSpace ℂ (Fin n)`
--
-- This file extends the chapter's matrix-side Rayleigh quotient owner with the extremal-value
-- statements of Theorem 1.2.10 on the canonical Euclidean space `EuclideanSpace ℂ (Fin n)`.
theorem rayleighQuotient_smul {n : ℕ} (A : Matrix (Fin n) (Fin n) ℂ)
(u : EuclideanSpace ℂ (Fin n)) {α : ℂ} (hα : α ≠ 0) :
rayleighQuotient A (α • u) = rayleighQuotient A uDefinition 1.2.11
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.11. A square matrix indexed by a finite type is subset reducible if there is a nonempty proper subset J of indices such that A k j = 0 for every k ∈ J and j ∉ J. For A : Matrix (Fin n) (Fin n) ℝ, this is exactly the source definition.
namespace Matrix
variable {ι : Type*} [Fintype ι] [DecidableEq ι]
variable {R : Type*} [Zero R]
-- `Mathlib.LinearAlgebra.Matrix.Irreducible.Defs` already owns `Matrix.IsIrreducible`
-- for the nonnegative-matrix notion, so this file keeps the source's unrestricted
-- subset-witness notion under distinct names. Specializing to `Matrix (Fin n) (Fin n) ℝ`
-- recovers the textbook real-matrix definition.
def IsSubsetReducible (A : Matrix ι ι R) : Prop :=
∃ J : Finset ι,
J.Nonempty ∧ J.card < Fintype.card ι ∧
∀ ⦃k j : ι⦄, k ∈ J → j ∉ J → A k j = 0Definition 1.2.12
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.12 (1): a square matrix is diagonally dominant when, in each row, the sum of the absolute values of the off-diagonal entries is bounded by the absolute value of the diagonal entry. Specializing to Matrix (Fin n) (Fin n) ℝ recovers the textbook notion.
open scoped BigOperators
-- Semantic recall: `Matrix.IsSubsetIrreducible` from Definition 1.2.11 is the
-- source-facing irreducibility owner used below, and
-- `det_ne_zero_of_sum_row_lt_diag` in `Mathlib.LinearAlgebra.Matrix.Gershgorin`
-- uses the exact strict rowwise inequality defining strict diagonal dominance.
namespace Matrix
variable {ι R : Type*} [Fintype ι] [DecidableEq ι] [AddCommGroup R] [LinearOrder R]
def IsDiagonallyDominant (A : Matrix ι ι R) : Prop :=
∀ i : ι, ∑ j ∈ Finset.univ.erase i, |A i j| ≤ |A i i|Theorem 1.2.13
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.13 (Diagonal Dominant Theorem): if a real square matrix is either strictly diagonally dominant or irreducibly diagonally dominant, then it is invertible. The canonical Lean surface for matrix invertibility is IsUnit A.
namespace Matrix
variable {n : ℕ}
theorem isUnit_of_isStrictlyDiagonallyDominant_or_isIrreduciblyDiagonallyDominant
(A : Matrix (Fin n) (Fin n) ℝ)
(hA : A.IsStrictlyDiagonallyDominant ∨ A.IsIrreduciblyDiagonallyDominant) :
IsUnit ATheorem 1.2.14
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.14 (1): every eigenvalue of a complex square matrix lies in one of its Gershgorin disks. This is exactly eigenvalue_mem_ball.
open Matrix
-- Semantic recall: `eigenvalue_mem_ball` in
-- `Mathlib.LinearAlgebra.Matrix.Gershgorin` is the canonical Gershgorin API for clause (1).
-- Semantic recall: `Matrix.IsHermitian.eigenvalues` is the source-facing owner for Hermitian
-- spectral statements in this chapter. The real matrix spectrum and `A.mulVecLin` spectrum are
-- companion bridge views, related by `hA.spectrum_real_eq_range_eigenvalues`.
variable {𝕜 : Type*} [RCLike 𝕜]
variable {n : Type*} [Fintype n]
#check eigenvalue_mem_ballTheorem 1.2.15
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.15 (1): if A is nonsingular and 1 + v ⬝ᵥ (A⁻¹ *ᵥ u) ≠ 0, then the rank-one update A + Matrix.vecMulVec u v is nonsingular.
universe u v
open Matrix
open scoped Matrix
-- Semantic recall: `Matrix.add_mul_mul_inv_eq_sub` is the Woodbury identity in mathlib.
-- This item keeps the source-facing vector form and derives it from that owner theorem.
variable {n : Type u} [Fintype n] [DecidableEq n]
variable {α : Type v} [Field α]
theorem isUnit_rankOneUpdate_of_one_add_dotProduct_nonsingInv_mulVec_ne_zero
(A : Matrix n n α) (u v : n → α)
(hA : IsUnit A)
(hScalar : 1 + v ⬝ᵥ (A⁻¹ *ᵥ u) ≠ 0) :
IsUnit (A + Matrix.vecMulVec u v)Theorem 1.2.16
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.16 (1): if A is nonsingular and 1 + Vᴴ * A⁻¹ * U is invertible, then A + U * Vᴴ is invertible.
universe u
open scoped Matrix
-- Semantic recall: `Matrix.add_mul_mul_inv_eq_sub` specializes to the formula below
-- with `C = 1` and `V = Vᴴ`.
theorem shermanMorrisonWoodbury_isUnit
{n m : ℕ} {α : Type u} [CommRing α] [Star α]
(A : Matrix (Fin n) (Fin n) α)
(U V : Matrix (Fin n) (Fin m) α)
(hA : IsUnit A) (hSchur : IsUnit (1 + Vᴴ * A⁻¹ * U)) :
IsUnit (A + U * Vᴴ)Theorem 1.2.17
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.17 (1): if 0 < σ, then each ordered eigenvalue of A is bounded above by the corresponding ordered eigenvalue of A + σ • Matrix.vecMulVec u u.
open Matrix
open scoped MatrixOrder
-- Semantic recall: `Matrix.IsHermitian.eigenvalues₀` is mathlib's ordered Hermitian eigenvalue API.
variable {n : ℕ} {A : Matrix (Fin n) (Fin n) ℝ}
variable (hA : A.IsHermitian) (u : Fin n → ℝ) {σ : ℝ}
theorem eigenvalues_le_rankOneUpdate_eigenvalues_of_pos
(hσ : 0 < σ) (i : Fin n) :
hA.eigenvalues₀ (Fin.cast (Fintype.card_fin n).symm i) ≤
(hA.add_smul_vecMulVec_self σ u).eigenvalues₀
(Fin.cast (Fintype.card_fin n).symm i)Algorithm 1.2.18
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Algorithm 1.2.18: Algorithm 1.2.18 produces factors of the rank-one update L * diagonal d * Lᵀ + α • vecMulVec y y. Equivalently, if B = L D Lᵀ, then the output barL, barD satisfies barL * diagonal barD * barLᵀ = B + α y yᵀ.
open Matrix
open scoped BigOperators
-- Domain sampling:
-- * `Matrix.IsUnitLowerTriangular` is the project owner for the unit-lower hypothesis on the LDL
-- factor.
-- * `Matrix.mulVec` is the canonical owner for the solve equation `L.mulVec p = y`.
-- * `Matrix.inv_mulVec_eq_vec` and `Matrix.mulVec_mulVec` are the canonical bridge lemmas for the
-- inverse-based solve `L⁻¹ *ᵥ y`.
-- * `Theorem_1_2_15` and `Exercise_1_6` keep nearby Chapter 1 rank-one matrix updates over a
-- field-valued matrix owner rather than fixing `ℝ`; this file should live at the same algebraic
-- owner level.
-- * `NegativeRankOneCholeskyUpdate` in `Algorithm_1_2_19` keeps the textbook algorithm owner
-- separate from its inverse-based solve bridge; the same source/core/bridge split is used here.
-- * `Matrix.vecMulVec` is the canonical rank-one update owner for `α y yᵀ`.
-- * `Fin n` already carries the canonical order on stage/row indices, so strict lower-triangular
-- positions should be expressed as `j < r` rather than through projection arithmetic.
-- Source/core/bridge triage:
-- * source-facing: Algorithm 1.2.18 outputs `α_j`, `barD_j`, `β_j`, `w^(j)`, and `barL`.
-- * core/canonical: `Matrix.IsUnitLowerTriangular`, `Matrix.mulVec`, `Matrix.diagonal`,
-- `Matrix.transpose`, and `Matrix.vecMulVec`.
-- * bridge/view: the solve equation `L.mulVec p = y`, and under invertibility the specialized
-- solve vector `L⁻¹ *ᵥ y`.
-- * owner abstraction: square matrices over a field together with the canonical matrix solve and
-- rank-one update owners above; the recursive algorithm data is source-facing API derived from
-- that ambient owner.
namespace RankOneCholeskyUpdate
variable {n : Nat} {𝕜 : Type*} [Field 𝕜]
local notation "Hessian" => Matrix (Fin n) (Fin n) 𝕜
variable (L : Hessian) (d y : Fin n → 𝕜) (α : 𝕜)
theorem barL_mul_diagonal_transpose_eq_rankOneUpdate
(L : Hessian) (d y : Fin n → 𝕜) (α : 𝕜)
(h : wellDefined L d y α) :
((barL L d y α : Hessian) * diagonal (barD L d y α) * transpose (barL L d y α) : Hessian) =
L * diagonal d * transpose L + α • vecMulVec y yAlgorithm 1.2.19
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Algorithm 1.2.19 (Cholesky Factorization of Negative Rank-One Update): the source-facing outputs t, barD, beta, w, and barL satisfy the textbook backward recurrences once the solve vector p is fixed.
open Matrix
open scoped BigOperators
-- Domain sampling:
-- * `Mathlib.Analysis.Matrix.LDL` provides the ambient canonical `LDL` owner.
-- * `Matrix.IsUnitLowerTriangular` is the project owner for the unit-lower hypothesis on `L`,
-- and `Matrix.mulVec` is the canonical owner for the forward-substitution equation
-- `L.mulVec p = y`.
-- * `Matrix.inv_mulVec_eq_vec` and `Matrix.mulVec_mulVec` are the canonical bridge lemmas for
-- recovering the inverse-based solve from a source-facing solution equation when `L` is
-- invertible.
-- * `Algorithm_1_2_18` keeps its source-facing stagewise outputs over the textbook inputs while
-- leaving the iterative working state private.
-- Source/core/bridge triage:
-- * source-facing: the algorithm outputs `t`, `barD`, `beta`, `w`, and `barL` over
-- `(L, d, p, εM)`, where `p` is the solve vector from the first step `L.mulVec p = y`.
-- * core/canonical: `Matrix.mulVec`.
-- * bridge/view: under extra invertibility, one may recover the same solve vector as
-- `L⁻¹.mulVec y`, but that inverse formula is not the main public owner.
namespace NegativeRankOneCholeskyUpdate
variable {n : Nat}
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
variable (L : Hessian) (d p : Fin n → ℝ) (εM : ℝ)
theorem negative_rank_one_update_recurrences :
t d p εM (Fin.last n) =
max εM (1 - Finset.sum Finset.univ (fun i : Fin n ↦ (p i) ^ 2 / d i)) ∧
(∀ j : Fin n, t d p εM (Fin.castSucc j) = t d p εM j.succ + (p j) ^ 2 / d j) ∧
(∀ j : Fin n, barD d p εM j = d j * t d p εM j.succ / t d p εM (Fin.castSucc j)) ∧
(∀ j : Fin n, beta d p εM j = -(p j) / (d j * t d p εM j.succ)) ∧
(∀ j : Fin n, w L p j j = p j) ∧
(∀ (r j : Fin n) (hjr : j.1 < r.1),
let jNext : Fin n := ⟨j.1 + 1, lt_of_le_of_lt (Nat.succ_le_of_lt hjr) r.is_lt⟩
w L p j r = w L p jNext r + p j * L r j) ∧
∀ (r j : Fin n) (hjr : j.1 < r.1),
let jNext : Fin n := ⟨j.1 + 1, lt_of_le_of_lt (Nat.succ_le_of_lt hjr) r.is_lt⟩
barL L d p εM r j = L r j + beta d p εM j * w L p jNext rDefinition 1.2.20
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.20 (1): in the textbook special case F : D ⊆ ℝⁿ → ℝᵐ, F is Hölder continuous on D if there exist γ ≥ 0 and p ∈ (0, 1] such that F is (γ, p)-Hölder on D. The formalization is stated for arbitrary pseudoemetric spaces, since only the metric structure is used.
open scoped Topology NNReal ENNReal
-- Semantic recall: `HolderOnWith`, `holderOnWith_one`, and
-- `HolderOnWith.continuousOn` are the canonical mathlib Hölder owners for fixed parameters.
-- The textbook definition below is source-facing and existential in those parameters, so it is
-- kept as a thin bridge on top of that owner. The local-at-a-point notion is also phrased through
-- `HolderOnWith` on a neighborhood within the set, rather than re-stating the same inequality
-- entrywise.
variable {X Y : Type*} [PseudoEMetricSpace X] [PseudoEMetricSpace Y]
class HolderContinuousOn (D : Set X) (F : X → Y) : Prop where
/-- There exist Hölder parameters witnessing that `F` is Hölder on `D`. -/
exists_holderOnWith :
∃ γ : ℝ≥0, ∃ p : ℝ≥0, p ∈ Set.Ioc (0 : ℝ≥0) 1 ∧ HolderOnWith γ p F DDefinition 1.2.21
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.21 (1): DirectionalHemicontinuousWithinAt D F x is equivalent to the source directional ε-δ condition ‖F (x + t • d) - F x‖ < ε for sufficiently small t with x + t • d ∈ D.
open scoped Topology
-- Semantic recall checked: mathlib's canonical owner notions here are `ContinuousWithinAt`,
-- `UpperSemicontinuousWithinAt`, and `LowerSemicontinuousWithinAt`. The source's directional
-- variants are the corresponding one-dimensional within-set properties along every line
-- `t ↦ x + t • d` inside `D`.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Value" => EuclideanSpace ℝ (Fin m)
theorem directionalHemicontinuousWithinAt_iff
(D : Set Point)
(F : Point → Value)
(x : Point) :
DirectionalHemicontinuousWithinAt D F x ↔
x ∈ D ∧
∀ d : Point, ∀ ε > 0,
∃ δ > 0, ∀ t : ℝ,Theorem 1.2.22
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.22: if F : E → G is differentiable on an open convex set D and fderiv ℝ F is γ-Lipschitz on D, then the first-order Taylor remainder at x + d is bounded by (γ / 2) * ‖d‖ ^ 2.
open Set
variable {E G : Type*}
variable [NormedAddCommGroup E] [NormedSpace ℝ E]
variable [NormedAddCommGroup G] [NormedSpace ℝ G]
-- Source/core/bridge triage:
-- * core/canonical owner: `holderRemainderBound`
-- * source-facing declaration here: the `p = 1` specialization with derivative field `fderiv ℝ F`
-- * no extra wrapper owner is introduced; the Euclidean `ℝⁿ → ℝᵐ` statement is now a specialization
theorem quadraticRemainderBound_of_fderiv_lipschitzOn
(D : Set E)
(F : E → G)
(x d : E)
(γ : NNReal)
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hx : x ∈ D)
(hF : DifferentiableOn ℝ F D)
(hLip : LipschitzOnWith γ (fderiv ℝ F) D)
(hxd : x + d ∈ D) :
‖F (x + d) - F x - (fderiv ℝ F x) d‖ ≤ ((γ : ℝ) / 2) * ‖d‖ ^ 2
Theorem 1.2.23
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.23, source-facing bridge: if f : E → ℝ is C² on an open convex set D and its Hessian obeys the centered basepoint estimate at x on D with constant γ, then the quadratic Taylor remainder at x is bounded by ((γ : ℝ) / 6) * ‖d‖ ^ 3 for any x + d ∈ D.
open Set
-- Semantic recall: `Convex.taylor_approx_two_segment` and the one-dimensional Taylor API
-- inform the remainder shape, but no direct multivariate cubic scalar remainder theorem
-- surfaced for this source-facing basepoint Hessian estimate, so the bridge theorem below is
-- stated directly and the canonical `LipschitzOnWith` owner is derived from it.
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable
(D : Set E)
(f : E → ℝ)
(x d : E)
(γ : NNReal)
theorem cubicRemainderBound_of_hessian_basepointLipschitzOn
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hx : x ∈ D)
(hf : ContDiffOn ℝ 2 f D)
(hHessianBasepointLipschitz :
∀ y ∈ D,
‖iteratedFDeriv ℝ 2 f y - iteratedFDeriv ℝ 2 f x‖ ≤ (γ : ℝ) * ‖y - x‖)
(hxd : x + d ∈ D) :
Theorem 1.2.24
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.24: if F is continuously differentiable on the open convex set D and fderiv ℝ F is γ-Lipschitz there, then the first-order linearization error at x is bounded by γ * max ‖u - x‖ ‖v - x‖ * ‖u - v‖.
open Set
open scoped Interval
variable {E G : Type*}
variable [NormedAddCommGroup E] [NormedSpace ℝ E]
variable [NormedAddCommGroup G] [NormedSpace ℝ G]
-- Source/core/bridge triage:
-- * source-facing: the three textbook first-order linearization-error bounds
-- * core/canonical owner: `norm_image_sub_sub_le_of_segment_fderiv_deviation_bound`
-- * bridge/view: the `C¹` specialization via `ContDiffOn ℝ 1 F D` and the
-- derivative-Lipschitz corollaries used later in the chapter
-- Semantic recall: Chapter 1 already contains the more general derivative-field
-- deviation estimate in `Definition_1_2_28.lean`; this file keeps the `C¹`
-- surface used later in the chapter, together with the supremum and Lipschitz
-- corollaries stated in the text. The source `ℝⁿ → ℝᵐ` statement is the
-- Euclidean specialization of the intrinsic real normed-space formulation below.
variable (D : Set E) (F : E → G) (γ : NNReal)
variable {u v x : E}
variable (hD_open : IsOpen D)
variable (hD_convex : Convex ℝ D)
variable (hF : ContDiffOn ℝ 1 F D)
variable (hu : u ∈ D) (hv : v ∈ D) (hx : x ∈ D)
variable (hLip : LipschitzOnWith γ (fderiv ℝ F) D)
theorem linearizationError_le_lipschitz_maxDistance
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hF : ContDiffOn ℝ 1 F D)
(hu : u ∈ D)
(hv : v ∈ D)
(hx : x ∈ D)
(hLip : LipschitzOnWith γ (fderiv ℝ F) D)
:
‖F u - F v - (fderiv ℝ F x) (u - v)‖ ≤
(γ : ℝ) * max ‖u - x‖ ‖v - x‖ * ‖u - v‖
Theorem 1.2.25
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.2.25: if F : E → E is C¹ on the open convex set D, fderiv ℝ F is Lipschitz on D, and fderiv ℝ F x is invertible, then F is locally bi-Lipschitz near x on D.
open Set
variable {E : Type*}
variable [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Source/core/bridge triage:
-- * source-facing: the local two-sided norm bounds near `x`
-- * core/canonical: the invertibility predicate `(fderiv ℝ F x).IsInvertible`
-- * bridge/view: an explicit `ContinuousLinearEquiv` identifying `fderiv ℝ F x`
--
-- Semantic recall: local Chapter 1 precedent used a `ContinuousLinearEquiv` witness for
-- `[F′(x)]⁻¹` existing, while later chapters use the canonical
-- `ContinuousLinearMap.IsInvertible` owner. This file keeps the Chapter 1 bridge theorem and
-- adds the canonical invertibility surface for reuse elsewhere in the repository.
theorem norm_image_sub_bounds_near_of_fderiv_isInvertible
(D : Set E)
(F : E → E)
(x : E)
(γ : NNReal)
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hx : x ∈ D)
(hcont : ContDiffOn ℝ 1 F D)
(hLip : LipschitzOnWith γ (fderiv ℝ F) D)
(hInv : (fderiv ℝ F x).IsInvertible) :
∃ ε α β : ℝ, NormImageSubBoundsNear D F x ε α βCorollary 1.2.26
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Corollary 1.2.26: under the hypotheses of Theorem 1.2.25, if A : E ≃L[ℝ] E identifies the derivative fderiv ℝ F x at x and ω t = max ‖u t - x‖ ‖v t - x‖ tends to 0 along l, then the limsup of the error ratio, viewed in ENNReal via ENNReal.ofReal, is bounded by the condition number ‖(A : E →L[ℝ] E)‖ * ‖(A.symm : E →L[ℝ] E)‖ times the limsup of the corresponding image ratio in the same canonical codomain.
open Filter Set
universe u
variable {E : Type*}
variable [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Source/core/bridge triage:
-- * source-facing: the Chapter 1 corollary comparing asymptotic error ratios under the
-- hypotheses of `Theorem_1_2_25`
-- * core/canonical owner: `Filter.limsup`
-- * bridge/view: `ENNReal.ofReal`, which records potentially unbounded nonnegative ratios
-- in the canonical extended-real codomain used elsewhere in the chapter
theorem limsup_normRatio_le_conditionNumber_mul_limsup_imageNormRatio
{α : Type u}
(D : Set E)
(F : E → E)
(x : E)
(γ : NNReal)
(A : E ≃L[ℝ] E)
(u v : α → E)
(l : Filter α)
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hx : x ∈ D)
(hcont : ContDiffOn ℝ 1 F D)
(hLip : LipschitzOnWith γ (fderiv ℝ F) D)
(hA : fderiv ℝ F x = (A : E →L[ℝ] E))
(hω : Tendsto (fun t ↦ max ‖u t - x‖ ‖v t - x‖) l (nhds 0))
(hv_ne : ∀ᶠ t in l, v t ≠ x)
(hFv_ne : ∀ᶠ t in l, F (v t) ≠ F x) :
l.limsup (fun t ↦ ENNReal.ofReal (‖u t - x‖ / ‖v t - x‖)) ≤
ENNReal.ofReal (‖(A : E →L[ℝ] E)‖ * ‖(A.symm : E →L[ℝ] E)‖) *
l.limsup (fun t ↦ ENNReal.ofReal (‖F (u t) - F x‖ / ‖F (v t) - F x‖))Definition 1.2.27
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.27, expressed at the generic normed-space owner level: f is Gateaux differentiable at x on the open set D if D is open, x ∈ D, and there is a continuous linear map A such that every directional line derivative of f within D at x is A d. The source ℝⁿ → ℝᵐ statement is recovered by specializing to Euclidean spaces over ℝ. This uses HasLineDerivWithinAt as the mathlib encoding of the limit formula lim α → 0, ‖α‖⁻¹ * ‖f (x + α • d) - f x - α • A d‖ = 0.
variable (𝕜 : Type*) [NontriviallyNormedField 𝕜]
variable {E G : Type*}
variable [NormedAddCommGroup E] [NormedSpace 𝕜 E]
variable [NormedAddCommGroup G] [NormedSpace 𝕜 G]
def SunYuanGateauxDifferentiableWithinAt
(D : Set E)
(f : E → G)
(x : E) : Prop :=
IsOpen D ∧ x ∈ D ∧ ∃ A : E →L[𝕜] G, IsGateauxDerivativeWithinAt 𝕜 D f x ADefinition 1.2.28
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.2.28 (3): Fréchet differentiability at x implies continuity at x.
open Set
open scoped Interval Topology
-- Domain sampling:
-- * core/canonical owners: `HasFDerivAt`, `HasStrictFDerivAt`
-- * chapter bridge/view owner for Gateaux differentiability:
-- `IsGateauxDerivativeWithinAt` / `SunYuanGateauxDifferentiableWithinAt`
-- * chapter bridge/view owner for linewise within-set continuity:
-- `AlongLineWithinAt`
-- * chapter source-facing owner for Euclidean-valued directional hemicontinuity:
-- `DirectionalHemicontinuousWithinAt`
variable {E G : Type*}
variable [NormedAddCommGroup E] [NormedSpace ℝ E]
variable [NormedAddCommGroup G] [NormedSpace ℝ G]
#check HasFDerivAt.continuousAt
Notation 1.2.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
open scoped Matrix
variable {m n : ℕ}
#check EuclideanSpace ℝ (Fin n)1.3 — Convex Sets and Convex Functions
Definition 1.3.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3.1: for S : Set Point, the statement that S is convex is formalized by Convex ℝ S.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check (Convex ℝ : Set Point → Prop)Example 1.3.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Example 1.3.2 (1): for a real inner-product space, the sunYuanHyperplane {x : E | inner ℝ p x = α} is the canonical sunYuanHyperplane cut out by the linear functional inner ℝ p.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
#check fun (p : E) (α : ℝ) ↦ convex_hyperplane (isLinearMap_inner_right p) αExample 1.3.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Example 1.3.3: the ray ray 𝕜 x₀ d = {x | ∃ t : 𝕜, 0 ≤ t ∧ x = x₀ + t • d} is a convex set. The source states this for d ≠ 0, but the convexity argument does not use that hypothesis.
open AffineMap
variable {𝕜 : Type*} [Ring 𝕜] [PartialOrder 𝕜] [IsOrderedRing 𝕜]
variable {V : Type*} [AddCommGroup V] [Module 𝕜 V]
-- Semantic recall hits verified for this item: `AffineMap.lineMap`,
-- `AffineMap.lineMap_apply_module'`, and `Convex.affine_image`.
theorem ray_convex (x₀ d : V) : Convex 𝕜 (ray 𝕜 x₀ d)Theorem 1.3.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.4: if S₁, S₂ ⊆ ℝ^n are convex, then their intersection, pointwise sum, and pointwise difference are convex. This item is a canonical recall of mathlib's exact owner lemmas Convex.inter, Convex.add, and Convex.sub, specialized here to Point = EuclideanSpace ℝ (Fin n).
open scoped Pointwise
-- Semantic recall hits verified for this item: `Convex.inter`, `Convex.add`, and `Convex.sub`.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check fun {S₁ S₂ : Set Point} (hS₁ : Convex ℝ S₁) (hS₂ : Convex ℝ S₂) ↦ hS₁.inter hS₂Theorem 1.3.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.5: if S ⊆ ℝ^n is convex, then both interior S and closure S are convex. Primary domain: convex subsets of topological vector spaces. Core/canonical owner: Convex ℝ S. Primitive data: the convexity proof hS. Derived API: hS.interior and hS.closure. This item is therefore a direct canonical recall of mathlib's owner lemmas Convex.interior and Convex.closure, specialized here to Point = ℝ^n.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check fun {S : Set Point} (hS : Convex ℝ S) ↦ hS.interiorDefinition 1.3.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3.6 (1): for S : Set E and f : E → ℝ, convexity of f on S is formalized by ConvexOn ℝ S f. The source's ℝ^n setting is a downstream specialization of this canonical owner.
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
#check (ConvexOn ℝ : Set E → (E → ℝ) → Prop)Definition 1.3.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3.7 (1): the epigraph of f over s. The source states this for a nonempty set S ⊆ ℝ^n, but the defining set itself does not depend on nonemptiness.
universe u v
variable {E : Type u} {α : Type v} [LE α]
def epigraph (s : Set E) (f : E → α) : Set (E × α) :=
{p | p.1 ∈ s ∧ f p.1 ≤ p.2}Theorem 1.3.8
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.8: a function is convex on s if and only if its epigraph epigraph s f is convex. This is the source-facing epigraph bridge for mathlib's canonical convexOn_iff_convex_epigraph; the book's ambient specialization to S ⊆ ℝ^n and f : S → ℝ is a special case, and the extra source hypothesis S.Nonempty does not affect this equivalence.
variable {𝕜 E β : Type*}
variable [Semiring 𝕜] [PartialOrder 𝕜]
variable [AddCommMonoid E] [SMul 𝕜 E]
variable [AddCommMonoid β] [PartialOrder β] [IsOrderedAddMonoid β]
variable [Module 𝕜 β] [PosSMulMono 𝕜 β]
theorem convexOn_iff_convex_epigraph_over (s : Set E) (f : E → β) :
ConvexOn 𝕜 s f ↔ Convex 𝕜 (epigraph s f)Theorem 1.3.9
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.9: for f : α → WithTop ℝ, the following are equivalent: 1. LowerSemicontinuous f; 2. IsClosed {p : α × ℝ | f p.1 ≤ (p.2 : WithTop ℝ)}; 3. ∀ r : ℝ, IsClosed (f ⁻¹' Iic (r : WithTop ℝ)).
open Set
variable {α : Type*} [TopologicalSpace α]
theorem lowerSemicontinuous_realEpigraph_sublevelSet_tfae (f : α → WithTop ℝ) :
List.TFAE [
LowerSemicontinuous f,
IsClosed {p : α × ℝ | f p.1 ≤ (p.2 : WithTop ℝ)},
∀ r : ℝ, IsClosed (f ⁻¹' Iic (r : WithTop ℝ))
]Definition 1.3.10
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3.10 is a source-facing recall of the canonical owner LowerSemicontinuous for WithTop ℝ-valued functions. The source's ambient specialization to ℝⁿ is a downstream specialization of this topological-domain owner. Chapter01 Theorem 1.3.9 is the bridge/view layer: it identifies the same notion with closedness of the real-height epigraph and of all real sublevel sets.
variable {α : Type*} [TopologicalSpace α]
#check (LowerSemicontinuous : (α → WithTop ℝ) → Prop)Theorem 1.3.11
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.11 (1) and (2): if f is convex on S ⊆ ℝ^n and α ≥ 0, then α • f is convex on S; if f and g are convex on S, then f + g is convex on S. These are direct Point = EuclideanSpace ℝ (Fin n) specializations of mathlib's exact owner theorems ConvexOn.smul and ConvexOn.add, so this file records them as recall entries instead of keeping parallel local wrappers.
open scoped BigOperators
-- Semantic recall hits verified for this item:
-- `ConvexOn.smul`, `ConvexOn.add`, `convexOn_const`.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check fun {S : Set Point} {f : Point → ℝ} {α : ℝ} (hf : ConvexOn ℝ S f) (hα : 0 ≤ α) ↦
(hf.smul hα : ConvexOn ℝ S (α • f))Theorem 1.3.12
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.12: if S ⊆ D ⊆ ℝ^n, S is open and convex, and f is convex on D, then f is continuous on S. This is the canonical composite of mathlib's ConvexOn.subset and ConvexOn.continuousOn, specialized here to Point = ℝ^n.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check fun {D S : Set Point} {f : Point → ℝ}
(hSD : S ⊆ D) (hS_open : IsOpen S) (hS_convex : Convex ℝ S) (hf : ConvexOn ℝ D f) ↦
(hf.subset hSD hS_convex).continuousOn hS_openTheorem 1.3.13
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.13 (1). The source states this on ℝ^n; the canonical Lean statement uses an arbitrary real complete inner product space. If S is open and convex and f : E → ℝ is differentiable on S, then f is convex on S if and only if f y ≥ f x + inner ℝ (gradient f x) (y - x) for all x, y ∈ S.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {S : Set E} {f : E → ℝ}
theorem convexOn_iff_ge_gradient_inner_sub
(hS_open : IsOpen S) (hS_convex : Convex ℝ S) (hf : DifferentiableOn ℝ f S) :
ConvexOn ℝ S f ↔
∀ x ∈ S, ∀ y ∈ S,
f y ≥ f x + inner ℝ (gradient f x) (y - x)Theorem 1.3.14
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.14 (1). The source states this on ℝ^n; the canonical Lean statement uses an arbitrary real complete inner product space. If S is open and convex and f : E → ℝ is twice continuously differentiable on S, then f is convex on S if and only if the Hessian quadratic form, formalized by iteratedFDeriv ℝ 2 f, is nonnegative in every direction at each point of S.
open Filter Set
open scoped Topology
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {S : Set E} {f : E → ℝ}
-- The textbook states these criteria for nonempty open convex sets, but nonemptiness is
-- redundant for the Lean statements below.
theorem convexOn_iff_iteratedFDeriv_nonneg
(hS_open : IsOpen S) (hS_convex : Convex ℝ S) (hC2 : ContDiffOn ℝ 2 f S) :
ConvexOn ℝ S f ↔
∀ x ∈ S, ∀ u : E, 0 ≤ (iteratedFDeriv ℝ 2 f x) ![u, u]
Definition 1.3.15
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3.15 (1). A mapping F : D → E is monotone on D₀ : Set D when ⟪F x - F y, (x : E) - y⟫ ≥ 0 for every x, y ∈ D₀.
open scoped RealInnerProductSpace
-- Semantic recall: mathlib exposes order-theoretic owners such as `MonotoneOn` and convex-analytic
-- owners such as `StrongConvexOn`, but no canonical owner for the source's inner-product
-- monotone-operator notion on subset domains was found. The source-facing API below therefore
-- keeps local `Prop`-valued owners for maps `F : D → E` on subtype domains `D` of a real inner
-- product space `E`.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {D : Set E} {D₀ : Set D}
def monotoneOperatorOn (F : D → E) (D₀ : Set D) : Prop :=
∀ ⦃x y : D⦄, x ∈ D₀ → y ∈ D₀ → ⟪F x - F y, (x : E) - y⟫ ≥ 0Theorem 1.3.16
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.16 (1): let D be open in a real inner product space, let S ⊆ D be convex, and let f : E → ℝ be differentiable on D. Then f is convex on S if and only if its gradient is monotone on S, i.e. inner ℝ (gradient f x - gradient f y) (x - y) ≥ 0 for all x, y ∈ S. The source statement on ℝ^n is the corresponding specialization.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {D S : Set E} {f : E → ℝ}
variable (hD_open : IsOpen D) (hSD : S ⊆ D) (hS_convex : Convex ℝ S)
variable (hf : DifferentiableOn ℝ f D)
theorem convexOn_iff_gradient_monotoneOn
(hD_open : IsOpen D) (hSD : S ⊆ D) (hS_convex : Convex ℝ S)
(hf : DifferentiableOn ℝ f D)
:
ConvexOn ℝ S f ↔
monotoneOperatorOn (fun x : S ↦ gradient f x) Set.univTheorem 1.3.17
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.17 (1). The source states this on ℝ^n; the canonical Lean statement uses an arbitrary real complete inner product space. If S is open and convex and f : E → ℝ is twice continuously differentiable on S, then ∇ f is monotone on S if and only if the Hessian quadratic form, formalized by iteratedFDeriv ℝ 2 f, is nonnegative in every direction at each point of S.
open scoped Gradient
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {S : Set E} {f : E → ℝ}
-- The textbook states these criteria for nonempty open convex sets, but nonemptiness is
-- redundant for the Lean statements below.
theorem gradientMonotoneOn_iff_iteratedFDeriv_nonneg
(hS_open : IsOpen S) (hS_convex : Convex ℝ S) (hC2 : ContDiffOn ℝ 2 f S) :
monotoneOperatorOn (fun x : S ↦ ∇ f x) Set.univ ↔
∀ x ∈ S, ∀ u : E, 0 ≤ (iteratedFDeriv ℝ 2 f x) ![u, u]
Theorem 1.3.18
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.18: if f : Point → ℝ is convex on S ⊆ ℝ^n, then each lower level set {x ∈ S | f x ≤ α} is convex. This is the direct Point = ℝ^n specialization of mathlib's canonical owner theorem ConvexOn.convex_le, so this file records the item as a recall block instead of keeping a parallel local wrapper for the lower level set.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check fun {S : Set Point} {f : Point → ℝ} (hf : ConvexOn ℝ S f) (α : ℝ) ↦
(hf.convex_le α : Convex ℝ {x ∈ S | f x ≤ α})Theorem 1.3.19
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.19 (1): the anchored lower level set is closed as a subset of S whenever f is continuous on S. The stronger Hessian hypotheses belong to the later convexity and boundedness consequences, not to this relative-closedness statement.
universe u
theorem isClosed_lowerLevelSetOn
{E : Type u} [TopologicalSpace E]
(S : Set E) (f : E → ℝ) (x0 : E)
(hCont : ContinuousOn f S) :
IsClosed ({y : S | f y ≤ f x0} : Set S)
Theorem 1.3.20
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.20 (1). If S is a nonempty, closed, convex subset of a complete real inner product space, then for every y there exists a unique point xbar ∈ S with minimal distance from y, formalized as ‖y - xbar‖ = ⨅ x : S, ‖y - x‖. This is the intrinsic owner abstraction of the textbook ℝ^n statement, and the source hypothesis y ∉ S is redundant for this canonical nearest-point formulation.
variable {F : Type*} [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F]
theorem existsUnique_norm_eq_iInf_of_nonempty_isClosed_convex
(S : Set F) (hS_nonempty : S.Nonempty) (hS_closed : IsClosed S) (hS_convex : Convex ℝ S)
(y : F) :
∃! xbar : F, xbar ∈ S ∧ ‖y - xbar‖ = ⨅ x : S, ‖y - x‖Theorem 1.3.21
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.21: if S is a nonempty closed convex subset of a complete real inner-product space and y ∉ S, then there exist a nonzero vector p and a real number α such that α < inner ℝ p y and inner ℝ p x ≤ α for every x ∈ S. The source states this on ℝ^n; here the owner theorem is stated on the chapter's abstract real inner-product-space level, which preserves the same separation semantics.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem existsNonzeroSeparatingVector
(S : Set E) (hS_nonempty : S.Nonempty) (hS_closed : IsClosed S)
(hS_convex : Convex ℝ S) (y : E) (hy : y ∉ S) :
∃ p : E, p ≠ 0 ∧ ∃ α : ℝ, α < inner ℝ p y ∧ ∀ x ∈ S, inner ℝ p x ≤ αTheorem 1.3.22
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.22: for A : Matrix (Fin m) (Fin n) ℝ and c : EuclideanSpace ℝ (Fin n), at least one of the two systems in Farkas' lemma has a solution.
open Matrix
open EuclideanSpace
-- Domain sampling:
-- * primary domain: linear inequality alternatives and cone duality in finite-dimensional real
-- inner-product spaces
-- * sampled owners: Chapter 1 `halfSpaceIntersection`, mathlib `ConvexCone.positive`,
-- mathlib `ConvexCone.mem_map`, the matrix-model bridge `Matrix.toEuclideanLin`,
-- and the coordinate equivalence `EuclideanSpace.equiv`
-- * source-facing layer: `farkasSystem1` / `farkasSystem2` are the textbook systems
-- `Ax ≤ 0, ⟪c, x⟫ > 0` and `Aᵀ y = c, y ≥ 0`
-- * core/canonical layer: `halfSpaceIntersection (matrixRowFamily A)` and the image of
-- `ConvexCone.positive ℝ DualCoords` under the canonical transpose-coordinate action
-- * bridge/view layer: `matrixRowFamily`, `matrixTransposeCoordMap`, and the equivalence lemmas
-- relating the textbook systems to those canonical owners
-- * primitive data: the matrix `A` and the right-hand-side vector `c`
-- * derived API: the two Farkas alternatives and the exclusion/existence theorems
variable {m n : ℕ}
local notation "PrimalPoint" => EuclideanSpace ℝ (Fin n)
local notation "DualCoords" => Fin m → ℝ
theorem farkasLemmaOneHasSolution
(A : Matrix (Fin m) (Fin n) ℝ) (c : PrimalPoint) :
farkasSystem1 A c ∨ farkasSystem2 A cDefinition 1.3.23
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3.23 (1): the source states this for a nonempty set S ⊆ ℝ^n, but the supporting-sunYuanHyperplane predicate itself only uses the real inner-product-space sunYuanHyperplane sunYuanHyperplane p ⟪p, xbar⟫ and its two closed half-spaces.
open Set
open scoped RealInnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
def IsSupportingHyperplaneAt (S : Set E) (xbar p : E) : Prop :=
S.Nonempty ∧
xbar ∈ frontier S ∧
p ≠ 0 ∧
(S ⊆ closedUpperHalfSpace p ⟪p, xbar⟫ ∨
S ⊆ closedLowerHalfSpace p ⟪p, xbar⟫)Theorem 1.3.24
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.24: if S is convex and xbar ∈ frontier S, then there exists a supporting sunYuanHyperplane of S at xbar. The source states this in ℝ^n; here the owner theorem is stated on an abstract finite-dimensional real inner-product space, which is source-faithful up to linear isometry and avoids choosing coordinates. The source's explicit nonemptiness hypothesis is redundant because xbar ∈ frontier S already implies S.Nonempty.
open Set
open scoped RealInnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
theorem existsSupportingHyperplaneAt_of_mem_frontier
(S : Set E) (hS_convex : Convex ℝ S) (xbar : E) (hxbar : xbar ∈ frontier S) :
∃ p : E, IsSupportingHyperplaneAt S xbar pCorollary 1.3.25
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Corollary 1.3.25: if S is a nonempty convex subset of a complete real inner-product space and xbar ∉ S, then there exists a nonzero vector p such that ⟪p, x - xbar⟫ ≤ 0 for every x ∈ closure S. The source states this on ℝ^n; the abstract Hilbert-space statement is the canonical owner level because the proof uses Hahn-Banach separation on closure S together with the Fréchet-Riesz identification.
open Set
open scoped RealInnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem existsNonzeroSupportingVectorOnClosureOfNotMem
(S : Set E) (hS_nonempty : S.Nonempty) (hS_convex : Convex ℝ S)
(xbar : E) (hxbar : xbar ∉ S) :
∃ p : E, p ≠ 0 ∧ ∀ x ∈ closure S, ⟪p, x - xbar⟫ ≤ (0 : ℝ)
Definition 1.3.26
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3.26 (1): the source states this for nonempty convex subsets of ℝ^n, but the defining separation condition itself only uses the real inner-product-space sunYuanHyperplane data p ≠ 0 together with the two half-space inclusions. The sunYuanHyperplane sunYuanHyperplane p α separates S₁ and S₂ exactly when p ≠ 0, α ≤ ⟪p, x⟫ for all x ∈ S₁, and ⟪p, x⟫ ≤ α for all x ∈ S₂.
open Set
open scoped RealInnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem separates_iff {S₁ S₂ : Set E} {p : E} {α : ℝ} :
separates S₁ S₂ p α ↔
p ≠ 0 ∧ (∀ x ∈ S₁, α ≤ ⟪p, x⟫) ∧ ∀ x ∈ S₂, ⟪p, x⟫ ≤ αTheorem 1.3.27
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.27 (Separation Theorem): if S₁, S₂ are nonempty convex sets in a complete real inner-product space and S₁ ∩ S₂ = ∅, then the closures of S₂ and S₁ admit a separating sunYuanHyperplane. The source states this on ℝ^n; the Hilbert-space formulation is the natural owner level because the proof is exactly Corollary 1.3.25 applied to the difference set S₁ - S₂, and the chapter’s canonical separation owner is separates.
open Set
open scoped Pointwise RealInnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem existsNonzeroSeparatingVectorOnClosures
(S₁ S₂ : Set E) (hS₁_nonempty : S₁.Nonempty) (hS₂_nonempty : S₂.Nonempty)
(hS₁_convex : Convex ℝ S₁) (hS₂_convex : Convex ℝ S₂) (hdisj : Disjoint S₁ S₂) :
∃ p : E, ∃ α : ℝ, separates (closure S₂) (closure S₁) p α
Theorem 1.3.28
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.28 (Strong Separation Theorem). If S₁, S₂ are closed convex subsets of a nontrivial proper real inner-product space, S₂ is nonempty bounded, and S₁ and S₂ are disjoint, then there exist a nonzero vector p and real numbers α and ε > 0 such that α + ε ≤ inner ℝ p z for every z ∈ S₂ and inner ℝ p x ≤ α for every x ∈ S₁. This is the source's explicit margin form of strong separation, with S₂ on the upper side of the separating sunYuanHyperplane and S₁ on the lower side. The chapter owner for exactly this data is stronglySeparates S₂ S₁ p α, so the theorem returns that owner directly rather than a parallel tuple of subtype witnesses and pointwise inequalities.
open scoped RealInnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
[Nontrivial E]
theorem existsNonzeroStrongSeparatingVector
(S₁ S₂ : Set E) (hS₂_nonempty : S₂.Nonempty)
(hS₁_closed : IsClosed S₁) (hS₂_closed : IsClosed S₂)
(hS₁_convex : Convex ℝ S₁) (hS₂_convex : Convex ℝ S₂)
(hS₂_bounded : Bornology.IsBounded S₂) (hdisj : Disjoint S₁ S₂) :
∃ p : E, ∃ α : ℝ, stronglySeparates S₂ S₁ p αTheorem 1.3.29
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.3.29 (Strict Separation Theorem). If S₁, S₂ ⊆ ℝ^n are nonempty closed convex sets, S₂ is bounded, and S₁ and S₂ are disjoint, then there exist a nonzero vector p and real numbers α < β such that inner ℝ p x < α for every x ∈ S₁ and β < inner ℝ p x for every x ∈ S₂. The companion theorem below repackages the same conclusion using a single separating level.
open scoped RealInnerProductSpace
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem existsNonzeroStrictSeparatingVector
(S₁ S₂ : Set Point) (hS₁_nonempty : S₁.Nonempty) (hS₂_nonempty : S₂.Nonempty)
(hS₁_closed : IsClosed S₁) (hS₂_closed : IsClosed S₂)
(hS₁_convex : Convex ℝ S₁) (hS₂_convex : Convex ℝ S₂)
(hS₂_bounded : Bornology.IsBounded S₂) (hdisj : Disjoint S₁ S₂) :
∃ p : Point, p ≠ 0 ∧ ∃ α β : ℝ, α < β ∧
(∀ x ∈ S₁, inner ℝ p x < α) ∧ ∀ x ∈ S₂, β < inner ℝ p xDefinition 1.3.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3-extra-1 Core/canonical owner: for S : Set Point, the convex hull of S is convexHull ℝ S. This item is a direct canonical recall, not a new source-facing wrapper. The source assumes S is nonempty, but that hypothesis is redundant for the owner itself, which is defined for arbitrary sets and specializes directly to the textbook setting. Primitive data: only the set S. Derived API already available in mathlib: - convexHull_eq_iInter: convexHull ℝ S is the intersection of all convex sets containing S. - convexHull_eq: convexHull ℝ S is the set of finite convex combinations of points of S. The statement that convexHull ℝ S is the smallest convex set containing S is expressed by subset_convexHull and convexHull_min.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this file:
-- * `convexHull` is the canonical mathlib owner for convex hulls of subsets of a real vector space.
-- * `convexHull_eq_iInter` is the canonical lattice-style description as the intersection of all
-- convex supersets.
-- * `convexHull_eq` is the canonical finite-convex-combination description.
-- * `subset_convexHull` and `convexHull_min` express the minimality statement.
#check (convexHull ℝ : Set Point → Set Point)Definition 1.3.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.3-extra-2 (1): a nonempty set is a cone if it is closed under multiplication by positive scalars.
open scoped Pointwise RealInnerProductSpace
-- Domain sampling for this file:
-- * Primary domain: convex cones in ordered modules.
-- * Source-facing layer: `SunYuanIsCone` and `positiveHull` keep the textbook set-level notions used in
-- the statement of Definition 1.3-extra-2.
-- * Core/canonical layer: `ConvexCone 𝕜 E` is the bundled owner for convex-cone structure, with
-- `ConvexCone.hull` as the canonical owner of the smallest convex cone containing a set.
-- * Bridge/view layer: `IsConvexCone` is a nonempty set-level view of that bundled owner, while
-- `positiveHull_eq_hull` and `nonnegativeOrthant_eq_positive` connect the source wording to the
-- canonical objects where the semantics agree exactly.
variable {𝕜 E : Type*}
def SunYuanIsCone (𝕜 : Type*) [Zero 𝕜] [LT 𝕜] [SMul 𝕜 E] (C : Set E) : Prop :=
Set.Nonempty C ∧ ∀ ⦃a : 𝕜⦄, 0 < a → ∀ ⦃x : E⦄, x ∈ C → a • x ∈ CDefinition 1.3.extra.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Property (1) for Chapter01 Definition 1.3-extra-3: for S : Set E, the polar cone of S is the proper cone of all vectors p such that ⟪p, x⟫ ≤ 0 for every x ∈ S.
open Pointwise
open scoped RealInnerProductSpace
-- Domain sampling for this file:
-- * `ProperCone.innerDual`, `ProperCone.mem_innerDual`, and
-- `ProperCone.innerDual_innerDual` are the core/canonical dual-cone API in complete real
-- inner-product spaces.
-- * `ConvexCone` is the source-facing bundled owner for convex cones, and closed nonempty
-- convex cones lift canonically to `ProperCone`.
--
-- The declaration `polarCone` below is a source-facing bridge/view: it keeps the textbook sign
-- convention `⟪p, x⟫ ≤ 0` by reusing the core owner `ProperCone.innerDual` on `-S`.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
noncomputable abbrev polarCone (S : Set E) : ProperCone ℝ E :=
ProperCone.innerDual (-S)Definition 1.3.extra.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The normal cone of S at xbar is the set of vectors whose inner product with every feasible displacement x - xbar is nonpositive.
open scoped RealInnerProductSpace
universe u
open Filter
def normalConeAt
{E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
(S : Set E) (xbar : E) : Set E :=
{ y | ∀ x ∈ S, ⟪y, x - xbar⟫ ≤ (0 : ℝ) }Remark 1.3.extra.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Remark 1.3-extra-5 Canonical recall: the textbook Minkowski inequality on ℝ^n is exactly the finite-set specialization of Real.Lp_add_le, with the coordinate index set taken to be Fin n.
#check Real.Lp_add_leRemark 1.3.extra.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Remark 1.3-extra-6: if S is an affine subspace, xbar ∈ S, and ⟪y -ᵥ xbar, x -ᵥ xbar⟫ ≤ 0 for every x ∈ S, then y -ᵥ xbar is orthogonal to the direction subspace of S. This is the canonical formalization of the source conclusion (y -ᵥ xbar) ⟂ S.
open Affine
open scoped RealInnerProductSpace
-- Semantic recall hits verified for this item: this remark is `source-facing`, while the
-- `core/canonical` owner of its conclusion is `S.directionᗮ`. The needed primitives are
-- `AffineSubspace.vadd_mem_of_mem_direction`, `AffineSubspace.vsub_mem_direction`, and
-- `Submodule.mem_orthogonal'`; no projection or minimizer bridge is needed.
variable {V P : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V]
variable [AffineSpace V P]
theorem sub_mem_direction_orthogonal_of_forall_inner_sub_nonpos
{S : AffineSubspace ℝ P} {xbar y : P} (hxbar : xbar ∈ S)
(h_nonpos : ∀ x ∈ S, ⟪y -ᵥ xbar, x -ᵥ xbar⟫ ≤ (0 : ℝ)) :
y -ᵥ xbar ∈ S.directionᗮ1.4 — Optimality Conditions for Unconstrained Case
Definition 1.4.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.4.1 (1): the canonical owner for a local minimizer is mathlib's IsLocalMin. The norm-ball formula from the source is recorded below only as a normed-group bridge theorem.
open scoped Topology
variable {X : Type*} [SeminormedAddCommGroup X]
variable {α : Type*} [Preorder α]
-- Domain sampling:
-- * primary domain: local extrema in topological and normed-group spaces
-- * core/canonical owner: `IsMinFilter` specialized to neighborhood filters
-- * related canonical project/mathlib declarations inspected:
-- `IsMinFilter`, `IsLocalMin`, `nhdsNE_sup_pure`, `Metric.mem_nhdsWithin_iff`
-- * source-facing owner kept here: `IsStrictLocalMin`
-- * primitive data: eventual strict inequality on the punctured neighborhood filter `𝓝[≠] xStar`
-- * derived API kept here: metric-ball and norm-ball reformulations
#check IsLocalMinDefinition 1.4.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.4.2 (1): the canonical owner for an unconstrained global minimizer of f : Point → ℝ at xStar is IsMinOn f Set.univ xStar. The exact pointwise characterization is already the mathlib theorem isMinOn_univ_iff, so this item is a direct canonical recall rather than a new local wrapper. Core/canonical owner: - IsMinOn f Set.univ xStar Derived API already available in mathlib: - isMinOn_univ_iff
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check (IsMinOn : (Point → ℝ) → Set Point → Point → Prop)Definition 1.4.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.4.3: a descent direction strictly decreases the objective along sufficiently small positive steps in that direction.
open Filter
open SignType
open scoped Topology
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem IsDescentDirectionAt.exists_localDecrease {f : E → ℝ} {x d : E}
(h : IsDescentDirectionAt f x d) :
∃ δ > 0, ∀ α : ℝ, 0 < α → α < δ → f (x + α • d) < f x
Theorem 1.4.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.4.4 (First-Order Necessary Condition): if xStar ∈ D is a local minimizer of f on the open set D and f is differentiable at xStar, then xStar is a stationary point of f. This is the source-facing open-set bridge to isStationaryPoint_of_isLocalMin.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling:
-- * primary domain: first-order calculus at local extrema on real inner-product spaces
-- * core/canonical owner abstractions inspected:
-- `IsLocalMin`, `IsLocalMinOn.isLocalMin`, `IsLocalMin.hasFDerivAt_eq_zero`,
-- `IsStationaryPoint`
-- * source-facing data: an open domain `D`, a local minimizer `xStar ∈ D`, and differentiability
-- at `xStar`
-- * derived API: the stationary-point conclusion and its zero-gradient corollary
theorem isStationaryPoint_of_isLocalMinOn
(D : Set E) (f : E → ℝ) (xStar : E)
(hD_open : IsOpen D) (hxStar : xStar ∈ D) (hdiff : DifferentiableAt ℝ f xStar)
(hmin : IsLocalMinOn f D xStar) :
IsStationaryPoint f xStarTheorem 1.4.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.4.5 (Second-Order Necessary Condition): on a real normed space, if f is C² at a local minimizer xStar, then the Hessian quadratic form at xStar, expressed as (iteratedFDeriv ℝ 2 f xStar) ![y, y], is nonnegative in every direction. This is the Fréchet calculus core behind the textbook open-set statement on ℝⁿ.
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Semantic recall: `lean_leansearch` surfaced `IsLocalMin.hasFDerivAt_eq_zero` and
-- `IsLocalMin.fderiv_eq_zero`, while the local Chapter 1 precedent records Hessian positivity
-- through `(iteratedFDeriv ℝ 2 f xStar) ![y, y]`.
theorem iteratedFDeriv_nonneg_of_isLocalMin
(f : E → ℝ) (xStar : E) (hC2 : ContDiffAt ℝ 2 f xStar) (hmin : IsLocalMin f xStar)
(y : E) : 0 ≤ (iteratedFDeriv ℝ 2 f xStar) ![y, y]Theorem 1.4.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.4.6 (Second-Order Sufficient Condition): on a finite-dimensional real inner-product space, if f is C² at xStar, xStar is a stationary point of f, and the Hessian quadratic form at xStar is positive in every nonzero direction, then xStar is a strict local minimizer of f, formalized by the Chapter 1 owner IsStrictLocalMin. This is the invariant form of the book's ℝⁿ statement.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
open AffineMap
open scoped Topology
-- Domain sampling:
-- * primary domain: second-order local optimality in finite-dimensional real inner-product spaces
-- * source-facing layer: Chapter 1 second-order sufficient condition
-- * owner abstractions inspected:
-- `IsStrictLocalMin`, `IsStationaryPoint`, `IsLocalMin`, `ContDiffAt`
-- * Hessian positivity surface inspected:
-- `QuadraticMap.PosDef` is a canonical quadratic-form owner in mathlib, but this chapter's
-- Hessian API is already standardized on the multilinear evaluation
-- `(iteratedFDeriv ℝ 2 f x) ![y, y]`, so the theorem keeps that owner surface
-- Primitive data vs derived API:
-- * primitive data: local `C²` regularity at `xStar`, a stationary-point owner, and positive
-- Hessian quadratic form in every nonzero direction
-- * derived API: the strict-local-minimum conclusion
-- The main theorem should use the chapter owners `IsStationaryPoint` and `IsStrictLocalMin`;
-- the raw zero-gradient form is kept only as a thin bridge.
theorem isStrictLocalMin_of_isStationaryPoint_of_iteratedFDeriv_pos
(f : E → ℝ) (xStar : E) (hC2 : ContDiffAt ℝ 2 f xStar)
(hStat : IsStationaryPoint f xStar)
(hPosDef :
∀ y : E, y ≠ 0 → 0 < (iteratedFDeriv ℝ 2 f xStar) ![y, y]) :
IsStrictLocalMin f xStar
Definition 1.4.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Definition 1.4.7: a point xStar is a stationary (critical) point for f when the Fréchet derivative of f vanishes at xStar. On complete spaces this is equivalent to the usual gradient-zero formulation HasGradientAt f 0 xStar.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
def IsStationaryPoint (f : E → ℝ) (xStar : E) : Prop :=
HasFDerivAt f (0 : E →L[ℝ] ℝ) xStarTheorem 1.4.8
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.4.8 (1): let S ⊆ ℝⁿ be a nonempty convex set, let f : Point → ℝ, and let xStar ∈ S be a local minimizer of f on S. If f is convex on S, then xStar is a global minimizer of f on S. This is the direct Point = ℝ^n specialization of the canonical mathlib owner theorem IsMinOn.of_isLocalMinOn_of_convexOn; the source hypothesis S.Nonempty is redundant once xStar ∈ S.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall hits verified for this item: `IsMinOn.of_isLocalMinOn_of_convexOn` is the
-- canonical owner for the convex case, while `StrictConvexOn.eq_of_isMinOn` is the canonical
-- uniqueness lemma for the strict-convex companion.
#check fun {S : Set Point} {f : Point → ℝ} {xStar : Point} (hxStar : xStar ∈ S)
(hmin : IsLocalMinOn f S xStar) (hf : ConvexOn ℝ S f) ↦
IsMinOn.of_isLocalMinOn_of_convexOn hxStar hmin hfTheorem 1.4.9
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.4.9: in a real complete inner product space, a differentiable convex function on the whole space has a global minimizer at xStar if and only if gradient f xStar = 0. The textbook's ℝⁿ statement is the Euclidean specialization.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
open AffineMap
-- Primary mathematical domain: first-order optimality for convex differentiable functions.
-- Core/canonical owners: `ConvexOn`, `IsMinOn`, and the Chapter 1 stationary-point owner
-- `IsStationaryPoint`.
-- Bridge/view layer used here:
-- * `gradient_eq_zero_of_isLocalMinOn` for the first-order necessary condition;
-- * `ConvexOn.isMinOn_of_rightDeriv_eq_zero` on the line segment through `xStar` and `y`.
-- Primitive data: convexity on `Set.univ` and differentiability at `xStar`.
-- Derived API: the global-minimizer/stationary-point criterion.
theorem isMinOn_univ_iff_gradient_eq_zero_of_convex
(f : E → ℝ) (xStar : E)
(hconv : ConvexOn ℝ Set.univ f) (hdiff : DifferentiableAt ℝ f xStar) :
IsMinOn f Set.univ xStar ↔ gradient f xStar = 01.5 — Structure of Optimization Methods
Algorithm 1.5.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Algorithm 1.5.1: a basic descent method for f : E → ℝ consists of a positive tolerance ε, an initial point x₀, iterates x k, descent directions d k, and step sizes α k such that x 0 = x₀. The source text is written on ℝ^n, but the data only use the real complete inner-product-space layer already underlying IsDescentDirectionAt. At every nonterminal index with ε < ‖gradient f (x k)‖, the method uses a descent direction, chooses a positive step size, strictly decreases the objective value, and updates by x (k + 1) = x k + α k • d k.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
structure BasicDescentMethod (f : E → ℝ) where
ε : ℝ
x0 : E
x : ℕ → E
d : ℕ → E
α : ℕ → ℝ
epsilon_pos : 0 < ε
x_zero : x 0 = x0
differentiableAt : ∀ k : ℕ, DifferentiableAt ℝ f (x k)
descentDirection :
∀ k : ℕ, ε < ‖gradient f (x k)‖ → IsDescentDirectionAt f (x k) (d k)
stepSize_pos :
∀ k : ℕ, ε < ‖gradient f (x k)‖ → 0 < α k
objectiveDecrease :
∀ k : ℕ, ε < ‖gradient f (x k)‖ → f (x k + α k • d k) < f (x k)
update :
∀ k : ℕ, ε < ‖gradient f (x k)‖ → x (k + 1) = x k + α k • d k
Theorem 1.5.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter01 Theorem 1.5.2 (1): if a sequence converges Q-superlinearly to xStar and the current errors are nonzero on a tail, then the normalized step lengths ‖x (k + 1) - x k‖ / ‖x k - xStar‖ tend to 1.
open Filter
universe u
variable {E : Type u} [NormedAddCommGroup E]
theorem hasQSuperlinearConvergenceTo_stepRatio_tendsto_one {E : Type u}
[NormedAddCommGroup E] (x : ℕ → E) (xStar : E)
(hq : HasQSuperlinearConvergenceTo x xStar)
(hne : ∀ᶠ k in atTop, x k ≠ xStar) :
Tendsto (fun k ↦ ‖x (k + 1) - x k‖ / ‖x k - xStar‖) atTop (nhds 1)Definition 1.5.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The Q-error ratio of order α for x relative to xStar. As a raw function this uses Lean's totalized real division when the denominator vanishes; the quotient-limit predicates below add eventual nonvanishing hypotheses where needed.
open Filter
universe u
variable {E : Type u} [NormedAddCommGroup E]
-- Semantic recall: mathlib does not provide a canonical owner for textbook `Q`-convergence
-- rates, and this file is the chapter owner reused by `Theorem_1_5_2` and
-- `Definition_1_5_extra_2`.
def qErrorRatio (x : ℕ → E) (xStar : E) (α : ℝ) : ℕ → ℝ :=
fun k ↦ ‖x (k + 1) - xStar‖ / Real.rpow ‖x k - xStar‖ αDefinition 1.5.extra.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
A linear companion to Chapter01 Definition 1.5-extra-2: the sequence x is R-linearly convergent in the source's broader reformulation precisely when there is a nonnegative scalar majorant sequence q with ‖x k - xStar‖ ≤ q k for all k and q converging Q-linearly to 0.
open Filter
universe u
variable {E : Type u} [NormedAddCommGroup E]
theorem rAtLeastLinearConvergenceTo_iff_exists_nonneg_qLinearMajorant
(x : ℕ → E) (xStar : E) :
rAtLeastLinearConvergenceTo x xStar ↔
∃ q : ℕ → ℝ,
IsNonnegErrorMajorant x xStar q ∧
HasQLinearConvergenceTo q 0
Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Definition_1_5_extra_2/Majorant.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Definition_1_5_extra_2/Rate.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.