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.

Source header · Attribution source

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.

Source header · Attribution source

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_vectorOneNorm

Exercise 1.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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_norm

Exercise 1.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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_le

Exercise 1.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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_le

Exercise 1.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 ∈ S

Exercise 1.13

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 convexHull

Exercise 1.17

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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_sum

Exercise 1.18

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 exercise118Fun1

Exercise 1.19

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 x

Definition 1.2.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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).PosDef

Definition 1.2.9

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) u

Theorem 1.2.10

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 u

Definition 1.2.11

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 = 0

Definition 1.2.12

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 A

Theorem 1.2.14

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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_ball

Theorem 1.2.15

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 y

Algorithm 1.2.19

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 r

Definition 1.2.20

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 D

Definition 1.2.21

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 A

Definition 1.2.28

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.interior

Definition 1.3.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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_open

Theorem 1.3.13

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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⟫ ≥ 0

Theorem 1.3.16

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.univ

Theorem 1.3.17

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 c

Definition 1.3.23

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 p

Corollary 1.3.25

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 x

Definition 1.3.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 ∈ C

Definition 1.3.extra.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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_le

Remark 1.3.extra.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 IsLocalMin

Definition 1.4.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 xStar

Theorem 1.4.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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[ℝ] ℝ) xStar

Theorem 1.4.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 hf

Theorem 1.4.9

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 = 0

1.5 — Structure of Optimization Methods

Algorithm 1.5.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source