Chapter 05 — Quasi-Newton Methods
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 5.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.1: using the DFP method, minimize rosenbrockFunction from Appendix 1.1 and extendedRosenbrockFunction from Appendix 1.2.
#check rosenbrockFunctionExercise 5.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.2: use the BFGS method to minimize extendedRosenbrockFunction from Appendix 1.2 and powellSingularFunction from Appendix 1.4.
#check extendedRosenbrockFunctionExercise 5.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.3 (1): the canonical DFP inverse-Hessian update satisfies the inverse-form quasi-Newton equation Hₖ₊₁ y = s.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem dfpInverseUpdate_satisfiesQuasiNewtonEquation
(H : MatrixN) (s y : Point)
(hsy : dotProduct s y ≠ 0) (hyHy : dotProduct y (H.mulVec y) ≠ 0) :
satisfiesQuasiNewtonEquation (dfpInverseUpdate H s y).toEuclideanLin y s
Exercise 5.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.4: if f is strongly convex and yk = ∇ f (xk + sk) - ∇ f xk, then y_kᵀ s_k > 0, written in the Euclidean model as 0 < dotProduct (∇ f (xk + sk) - ∇ f xk) sk for every nonzero step sk. This is the Euclidean bridge from the Chapter 5 curvature owner to the textbook scalar pairing.
open scoped Gradient
variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
[CompleteSpace Point]
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem secantCurvature_pos_of_strongConvex
(f : Point → ℝ) (m : ℝ) (xk sk : Point)
(hm : 0 < m)
(hStrong : StrongConvexOn Set.univ m f)
(h_hasGradient : ∀ x : Point, HasGradientAt f (∇ f x) x)
(hsk : sk ≠ 0) :
0 < dotProduct (∇ f (xk + sk) - ∇ f xk) sk
Exercise 5.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.5: the inverse-Hessian BFGS update in formula (5.1.49) is the unique solution of the dual least-change problem (5.1.79). Concretely, if H and M are symmetric, M is nonsingular, 0 < dotProduct s y, and M.mulVec s = (M⁻¹).mulVec y, then bfgsInverseUpdate H s y is symmetric, satisfies the canonical inverse-form secant equation, minimizes the weighted Frobenius change weightedFrobeniusNorm M (Hhat - H) among symmetric matrices Hhat satisfying that secant equation, and is the unique feasible symmetric minimizer.
open Matrix
open scoped Matrix.Norms.Frobenius
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem bfgsInverseUpdate_isUniqueWeightedFrobeniusMinimizer
(H M : MatrixN) (s y : Point)
(hH : H.IsSymm) (hM : M.IsSymm) (hMdet : IsUnit M.det)
(hsy : 0 < dotProduct s y) (hMs : M.mulVec s = (M⁻¹).mulVec y) :
let Hbar := bfgsInverseUpdate H s y
let objective : MatrixN → ℝ := fun Hhat ↦ weightedFrobeniusNorm M (Hhat - H)
let feasibleSet : Set MatrixN :=
{Hhat | Hhat.IsSymm ∧ satisfiesQuasiNewtonEquation Hhat.toEuclideanLin y s}
(Hbar.IsSymm ∧ satisfiesQuasiNewtonEquation Hbar.toEuclideanLin y s) ∧
IsMinOn objective feasibleSet Hbar ∧
∀ Hhat : MatrixN, Hhat ∈ feasibleSet →
IsMinOn objective feasibleSet Hhat → Hhat = Hbar
Exercise 5.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
variable {G : MatrixN} {b : Point} {c : ℝ}
local notation "f" => quadraticObjective G b c
variable (A : GeneralQuasiNewtonMethod f) (φ : ℕ → ℝ)
#check A.IsBroydenClassMethod φ
Exercise 5.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Exercise 5.7: the inverse-Hessian Broyden owner is already defined canonically in Definition_5_2_extra_1.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * primary domain: inverse-Hessian Broyden/Huang updates on the concrete Chapter 5 matrix
-- model;
-- * sampled project owners:
-- `broydenClassInverseUpdate`,
-- `broydenClassInverseUpdate_mulVec`,
-- `broydenClassInverseUpdate_isSymm`,
-- `IsHuangUpdate.satisfiesQuasiNewtonEquation`;
-- * best owner abstraction inside the minimal closure: the source-facing owner
-- `broydenClassInverseUpdate` from `Definition_5_2_extra_1`;
-- * source/core/bridge triage for this file:
-- source-facing: the exercise theorem asserting that the Broyden update is a Huang update;
-- core/canonical: `broydenClassInverseUpdate` and `satisfiesQuasiNewtonEquation`;
-- bridge/view: `IsHuangUpdate` from `Definition_5_2_extra_2`;
-- * primitive data is owned upstream in `Definition_5_2_extra_1` and
-- `Definition_5_2_extra_2`; this file keeps only derived exercise-level API.
#check broydenClassInverseUpdate
Exercise 5.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.8: prove Theorem 5.4.3. This exercise is a canonical recall item. The result is already formalized as quasiNewton_superlinear_iff_secantErrorRatio_tendsto_zero in SunYuanOptimizationTheoryMethods.Chap05.Theorem_5_4_3, so the exercise reuses that owner directly and introduces no duplicate local theorem surface.
#check quasiNewton_superlinear_iff_secantErrorRatio_tendsto_zero
Exercise 5.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.9 (1): the canonical inverse DFP update is the φ = 0 specialization of the inverse-Hessian Broyden class. This is already the upstream owner broydenClassInverseUpdate_zero, so the exercise reuses that result directly.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
#check broydenClassInverseUpdate_zero
Exercise 5.10
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Exercise 5.10: recall the canonical Chapter 5 L-BFGS implementation owners.
#check LBFGSHistoryEntry5.1 — Quasi-Newton Methods
Algorithm 5.1.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Algorithm 5.1.1: a general quasi-Newton method consists of a nonnegative tolerance ε, iterates x k, inverse-approximation operators H k, explicit gradient data g k, search directions d k, and step sizes α k. At every nonterminal stage with ε < ‖g k‖, the direction is given by d k = -H k (g k), the line search returns a positive step size α k > 0, the iterate update is x (k + 1) = x k + α k • d k, and the next matrix satisfies the inverse-form quasi-Newton equation for H (k + 1) and secant data g (k + 1) - g k, x (k + 1) - x k. On the Euclidean model E = EuclideanSpace ℝ (Fin n), the canonical bridge A.matrix k := Matrix.toEuclideanLin.symm (A.H k) recovers the concrete textbook matrices, so the matrix-vector equations remain available as thin downstream specializations. The source does not fix a particular line-search rule, so the public surface records its explicit positivity output. Once the stopping condition ‖g k‖ ≤ ε is reached, the run stays at the same iterate; this frozen-tail convention is primitive run data on the canonical owner rather than a theorem-local extra hypothesis.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
structure GeneralQuasiNewtonMethod (f : E → ℝ) where
ε : ℝ
x : ℕ → E
H : ℕ → E →ₗ[ℝ] E
g : ℕ → E
d : ℕ → E
α : ℕ → ℝ
epsilon_nonneg : 0 ≤ ε
hasGradientAt (k : ℕ) : HasGradientAt f (g k) (x k)
direction_eq (k : ℕ) (hNotStopped : ε < ‖g k‖) :
d k = -(H k (g k))
stepSize_pos (k : ℕ) (hNotStopped : ε < ‖g k‖) : 0 < α k
update (k : ℕ) (hNotStopped : ε < ‖g k‖) :
x (k + 1) = x k + α k • d k
stationaryContinuation (k : ℕ) (hTerminated : ‖g k‖ ≤ ε) :
x (k + 1) = x k
quasiNewtonEquation (k : ℕ) (hNotStopped : ε < ‖g k‖) :
satisfiesQuasiNewtonEquation (H (k + 1)) (g (k + 1) - g k) (x (k + 1) - x k)
Theorem 5.1.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.1.2: if G is the positive-definite Hessian of a quadratic objective, A is an SR1 run for quadraticObjective G b c, the run is generated through stage n, and the generated step vectors broydenStep A k for k = 0, ..., n - 1 are linearly independent, then the SR1 method terminates after n + 1 steps, formalized here as A.matrix n = G⁻¹.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
variable {G : MatrixN} {b : Point} {c : ℝ}
local notation "f" => quadraticObjective G b c
theorem sr1TerminalMatrix_eq_inv_of_linearIndependent_steps
(A : GeneralQuasiNewtonMethod f)
(hSR1 : A.IsSR1Run)
(hPosDef : G.PosDef)
(hGenerated : A.GeneratedThrough n)
(hstep : LinearIndependent ℝ (fun k : Fin n ↦ broydenStep A k)) :
A.matrix n = G⁻¹
Theorem 5.1.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.1.3: if f admits a local Lipschitz Hessian matrix field G at xStar (hence G is bounded on some neighborhood of xStar), x k → xStar, the secant data satisfy s k = x (k + 1) - x k and y k = gradient f (x (k + 1)) - gradient f (x k), the SR1 skipping rule (5.1.26) holds for every k, the steps are uniformly linearly independent, and the limit Hessian matrix G xStar is invertible, then the inverse-Hessian SR1 matrices converge in norm to (G xStar)⁻¹.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall:
-- * `HasLocalLipschitzHessianMatrixAt` is the Chapter 3 owner for the local Hessian model.
-- * `sr1Update` and `sr1Residual` are the Chapter 5 owners for the SR1 update formula.
--
-- This file keeps the source-facing SR1-with-skipping recursion and uniform linear independence
-- hypothesis explicit, while reusing the canonical Hessian owner directly.
theorem sr1InverseHessian_tendsto_limitHessianInverse
(f : Point → ℝ) (G : Point → MatrixN) (x : ℕ → Point) (s y : ℕ → Point)
(H : ℕ → MatrixN) (xStar : Point) (r : ℝ)
(h_hessian : HasLocalLipschitzHessianMatrixAt f G xStar)
(h_hessian_unit : IsUnit (G xStar))
(h_s : ∀ k : ℕ, s k = x (k + 1) - x k)
(h_y : ∀ k : ℕ, y k = gradient f (x (k + 1)) - gradient f (x k))
(h_tendsto : Tendsto x atTop (nhds xStar))
(h_sr1 : IsSR1InverseSequenceWithSkippingRule H s y r)
(h_steps : HasUniformlyLinearlyIndependentSteps s) :
Tendsto (fun k ↦ ‖H k - (G xStar)⁻¹‖) atTop (nhds (0 : ℝ))
Algorithm 5.1.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Algorithm 5.1.4: a DFP method on ℝ^n is a general quasi-Newton run whose initial Euclidean matrix representative is positive definite and whose nonterminal stages satisfy the two denominator conditions required by the DFP inverse update together with the textbook DFP matrix recursion on A.matrix. The iterate, search-direction, step-size, stopping, and secant equation data are inherited from GeneralQuasiNewtonMethod.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
variable {f : Point → ℝ}
structure DfpMethod (f : Point → ℝ) extends GeneralQuasiNewtonMethod f where
matrix0_posDef : (Matrix.toEuclideanLin.symm (H 0)).PosDef
secant_denom_ne_zero (k : ℕ) (_ : ε < ‖g k‖) :
dotProduct (x (k + 1) - x k) (g (k + 1) - g k) ≠ 0
metric_denom_ne_zero (k : ℕ) (_ : ε < ‖g k‖) :
dotProduct (g (k + 1) - g k)
((Matrix.toEuclideanLin.symm (H k)).mulVec (g (k + 1) - g k)) ≠ 0
update_eq (k : ℕ) (_ : ε < ‖g k‖) :
Matrix.toEuclideanLin.symm (H (k + 1)) =
dfpInverseUpdate
(Matrix.toEuclideanLin.symm (H k)) (x (k + 1) - x k) (g (k + 1) - g k)
Theorem 5.1.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.1.5 (Positive Definiteness of DFP Update): if H is a positive definite real matrix, then on the DFP update domain dotProduct s y ≠ 0 the canonical DFP inverse-Hessian update dfpInverseUpdate H s y is positive definite if and only if the secant pair satisfies the Chapter 5 curvature condition.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem dfpInverseUpdate_posDef_iff
(H : MatrixN) (hH : H.PosDef) (s y : Point) (hsy : dotProduct s y ≠ 0) :
(dfpInverseUpdate H s y).PosDef ↔ satisfiesCurvatureCondition s y
Corollary 5.1.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Corollary 5.1.6 (1): if the matrix A.matrix k is generated by DFP Algorithm 5.1.4, formalized by the source-facing DFP stage predicate A.GeneratedThrough k, then A.matrix k is positive definite.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
variable {f : Point → ℝ}
-- Domain sampling for this file:
-- * primary domain: DFP inverse-Hessian positive-definiteness and descent directions on Euclidean
-- quasi-Newton runs;
-- * sampled project owners in the same domain:
-- `DfpMethod`,
-- `DfpMethod.GeneratedThrough`,
-- `IsDescentDirectionAt`,
-- `satisfiesCurvatureCondition`,
-- `Matrix.PosDef`;
-- * best owner abstractions: the general quasi-Newton stage predicate
-- `DfpMethod.GeneratedThrough` for the DFP recursion, and the Chapter 1
-- predicate `IsDescentDirectionAt` for the descent-direction conclusion;
-- * primitive data kept explicit here: the current nonterminal stage `k`;
-- * derived/source-facing extra hypotheses kept here: the DFP generated-through-stage predicate
-- and the current nonterminal stage `k`.
theorem dfpMethod_matrix_posDef
(A : DfpMethod f) (k : ℕ)
(hGenerated : A.GeneratedThrough k) :
(A.matrix k).PosDef
Theorem 5.1.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.1.7 (Quadratic Termination Theorem of DFP Method): for a positive-definite quadratic objective with exact line search whose first DFP step is generated, there is an index m such that the DFP run is generated through stage m + 1, the hereditary property H (i + 1) y j = s j holds for every j ≤ i ≤ m, the conjugate-direction property s iᵀ G s j = 0 holds for every j < i ≤ m, the method terminates at stage m + 1 ≤ n, and, in the full-length case m + 1 = n, the final identity H n = G⁻¹ holds.
variable {n : ℕ}
variable {G : Matrix (Fin n) (Fin n) ℝ} {b : EuclideanSpace ℝ (Fin n)} {c : ℝ}
-- This file only needs the explicit quadratic objective, not the broader Chapter 4 theorem
-- package that also owns its gradient and conjugate-direction API.
open DfpMethod
open DfpMethod.IsExactLineSearchOnQuadratic
theorem dfpPrefixInvariants
(A : DfpMethod (dfpQuadraticObjective G b c))
(hDFP : A.IsExactLineSearchOnQuadratic G b c)
(hStart : A.GeneratedThrough 1) :
∃ m : ℕ,
And (A.GeneratedThrough (m + 1))
(And (A.terminatedAt (m + 1))
(And (m + 1 ≤ n)
(And
(∀ ⦃i j : ℕ⦄, i ≤ m → j ≤ i →
(A.matrix (i + 1)).mulVec (A.g (j + 1) - A.g j) = A (j + 1) - A j)
(And
(∀ ⦃i j : ℕ⦄, i ≤ m → j < i →
dotProduct (A (i + 1) - A i) (G.mulVec (A (j + 1) - A j)) = 0)
(m + 1 = n → A.matrix n = G⁻¹)))))
Theorem 5.1.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.1.8: the alternating rank-one quasi-Newton sequence (5.1.55) converges to the explicit matrix (5.1.56), already owned upstream by symmetrizedBroydenSequence_tendsto_limit.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Source/core/bridge triage:
-- * source-facing: Theorem 5.1.8 is the convergence statement for the alternating rank-one
-- sequence `(5.1.55)` and its explicit limit `(5.1.56)`.
-- * core/canonical owner: `symmetrizedBroydenSequence_tendsto_limit`.
-- * bridge/view: none; this file is recall-only.
--
-- Domain sampling in the same Chapter 5 quasi-Newton matrix API:
-- * `dfpInverseUpdate` in `Algorithm_5_1_4` is the earlier owner for the DFP inverse update;
-- * `dfpInverseUpdate_eq_symmetricMatrixForm` in `Definition_5_1_extra_3` is the symmetric-matrix
-- bridge to that owner;
-- * `symmetrizedBroydenSequence` and `symmetrizedBroydenLimit` in
-- `Definition_5_1_extra_4` are the primitive data for the source sequence and its limit.
-- The public theorem surface here should therefore reuse the existing convergence owner directly
-- instead of introducing a parallel local theorem or wrapper.
#check
fun (B : MatrixN) (s y c : Point) (hcs : dotProduct c s ≠ 0) ↦
(symmetrizedBroydenSequence_tendsto_limit B s y c hcs :
Tendsto (symmetrizedBroydenSequence B s y c) atTop
(nhds (symmetrizedBroydenLimit B s y c)))
Theorem 5.1.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.1.9: for B : Matrix (Fin n) (Fin n) ℝ and s y : Fin n → ℝ with s ≠ 0, a matrix Bhat equals the Broyden rank-one update B + (dotProduct s s)⁻¹ • Matrix.vecMulVec (y - B.mulVec s) s if and only if Bhat is a solution of the constrained minimization problem min {‖C - B‖ : C.mulVec s = y} in the Frobenius norm. In particular, this update is the unique Frobenius-nearest matrix satisfying the quasi-Newton equation Bhat.mulVec s = y.
open scoped Matrix.Norms.Frobenius
-- Semantic recall: `IsLeastChangeSecantUpdateHessianForm` is already the Chapter 5 owner for
-- Hessian-side least-change secant updates, while Chapter 1 provides the Frobenius norm as an
-- `IsMatrixNorm`. The primitive Broyden rank-one update formula is already a Chapter 5 owner in
-- `Definition_5_1_extra_4`, so this item reuses that owner directly at the Frobenius
-- specialization.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem eq_broydenRankOneUpdate_iff_isLeastChangeSecantUpdateHessianForm
(B : MatrixN) (s y : Point) (Bhat : MatrixN) (hs : s ≠ 0) :
Bhat = broydenRankOneUpdate B s y ↔
IsLeastChangeSecantUpdateHessianForm (fun A : MatrixN ↦ ‖A‖) B Bhat s y
Theorem 5.1.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.1.10: if B is symmetric, M is symmetric and nonsingular, 0 < dotProduct c s, and M.mulVec c = (M⁻¹).mulVec s, then symmetrizedBroydenLimit B s y c is feasible for the secant and symmetry constraints and is the unique minimizer of the weighted Frobenius change weightedFrobeniusNorm M (Bhat - B) among symmetric matrices Bhat satisfying the Hessian-form quasi-Newton equation Bhat.mulVec s = y.
open Matrix
open scoped Matrix.Norms.Frobenius
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem symmetrizedBroydenLimit_isUniqueWeightedFrobeniusMinimizer
(B M : MatrixN) (c s y : Point)
(hB : B.IsSymm) (hM : M.IsSymm) (hMdet : IsUnit M.det)
(hcs : 0 < dotProduct c s) (hMc : M.mulVec c = (M⁻¹).mulVec s) :
let Bbar := symmetrizedBroydenLimit B s y c
let objective : MatrixN → ℝ := fun Bhat ↦ weightedFrobeniusNorm M (Bhat - B)
let feasibleSet : Set MatrixN :=
{Bhat | Bhat.IsSymm ∧ satisfiesQuasiNewtonEquationHessianForm Bhat.toEuclideanLin s y}
(Bbar.IsSymm ∧ satisfiesQuasiNewtonEquationHessianForm Bbar.toEuclideanLin s y) ∧
IsMinOn objective feasibleSet Bbar ∧
∀ Bhat : MatrixN, Bhat ∈ feasibleSet →
IsMinOn objective feasibleSet Bhat → Bhat = Bbar
Definition 5.1.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Definition 5.1-extra-1 (1): the inverse-Hessian form of the quasi-Newton equation for an endomorphism H and secant data y s is H y = s.
open scoped InnerProductSpace
variable {𝕜 : Type*} [Semiring 𝕜]
variable {E : Type*} [AddCommMonoid E] [Module 𝕜 E]
def satisfiesQuasiNewtonEquation (H : E →ₗ[𝕜] E) (y s : E) : Prop :=
H y = sDefinition 5.1.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Definition 5.1-extra-2: the symmetric rank-one inverse-Hessian update is `H + (dotProduct (sr1Residual H y s) y)⁻¹ • Matrix.vecMulVec (sr1Residual H y s) (sr1Residual H y s)`.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this file:
-- * primary domain: quasi-Newton SR1 inverse updates on Euclidean matrix models
-- * sampled same-domain owners: `sr1Update`, `sr1Residual`, `Matrix.toEuclideanLin`,
-- `Matrix.IsSymm`
-- * best owner abstraction: the Chapter 5 matrix owner `sr1Update`
-- * primitive data: a current matrix `H` and secant pair `s y`
-- * derived API: formula expansion, the concrete secant equation, and symmetry preservation
--
-- This file therefore keeps the SR1 owner local to the textbook item and develops only the
-- concrete matrix API that the later Chapter 5 results use.
def sr1Update (H : MatrixN) (s y : Point) : MatrixN :=
H + (dotProduct (sr1Residual H y s) y)⁻¹ •
Matrix.vecMulVec (sr1Residual H y s) (sr1Residual H y s)Definition 5.1.extra.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Definition 5.1-extra-3: the DFP inverse-Hessian update is the existing Chapter 5 owner dfpInverseUpdate.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
#check dfpInverseUpdate
Definition 5.1.extra.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The BFGS Hessian update satisfies the Hessian-form quasi-Newton equation Bₖ₊₁ s = y.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall hits verified for this item via `lean_leansearch`: `Matrix.vecMulVec`,
-- `Matrix.toEuclideanLin`, and `Matrix.IsSymm` support the canonical concrete-matrix surface
-- for the BFGS and PSB updates.
theorem bfgsHessianUpdate_mulVec
(B : MatrixN) (s y : Point)
(hys : dotProduct y s ≠ 0) (hBs : dotProduct s (Matrix.toEuclideanLin B s) ≠ 0) :
Matrix.toEuclideanLin (bfgsHessianUpdate B s y) s = y
Definition 5.1.extra.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling in the Chapter 5 quasi-Newton update family shows that
-- `symmetrizedBroydenLimit` from `Definition_5_1_extra_4` is already the owner of the
-- general PSB matrix. Its SR1/DFP/BFGS specializations are likewise recorded there by the
-- canonical declarations `sr1Residual`, `sr1DualBFormUpdate`, `dfpDualHessianUpdate`,
-- `bfgsHessianUpdate`, and `powellSymmetricBroydenUpdate`. This file therefore keeps only
-- the additional source-facing specialization statements from the current entry.
#check symmetrizedBroydenLimit
Definition 5.1.extra.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Definition 5.1-extra-6 (1): the least-change secant property for an inverse-Hessian update Hk1 from Hk with secant data y s : Point and change objective δ means that Hk1 satisfies the inverse-form quasi-Newton equation and minimizes δ (H - Hk) among all matrices H satisfying the same secant equation.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
variable {δ : MatrixN → ℝ}
def IsLeastChangeSecantUpdate
(δ : MatrixN → ℝ) (Hk Hk1 : MatrixN) (y s : Point) : Prop :=
satisfiesQuasiNewtonEquation Hk1.toEuclideanLin y s ∧
∀ H : MatrixN,
satisfiesQuasiNewtonEquation H.toEuclideanLin y s → δ (Hk1 - Hk) ≤ δ (H - Hk)Definition 5.1.extra.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Definition 5.1-extra-7: the explicit PSB matrix is the previously introduced owner symmetrizedBroydenLimit.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling across the local Chapter 5 PSB files shows that the owner object for the
-- explicit PSB matrix is already `symmetrizedBroydenLimit`. This file is therefore recall-only.
#check symmetrizedBroydenLimit
5.2 — The Broyden Class
Theorem 5.2.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.2.1 (1): for a positive-definite quadratic objective and an exact line-search Broyden-class run, the hereditary property holds along every generated stage up to m, namely H (i + 1) y j = s j for all j ≤ i ≤ m.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this file:
-- * primary domain: exact-line-search Broyden-class quasi-Newton runs on Euclidean quadratic
-- objectives;
-- * sampled project owners in the minimal closure:
-- `GeneralQuasiNewtonMethod`,
-- `GeneralQuasiNewtonMethod.HasExactLineSearchOnNonnegativeRay`,
-- `quadraticObjective`,
-- `broydenStep` / `broydenSecant`,
-- `broydenClassInverseUpdate`;
-- * core/canonical owner reused for exact line search: `A.HasExactLineSearchOnNonnegativeRay`;
-- * source-facing owner for the Broyden update data:
-- `GeneralQuasiNewtonMethod.IsBroydenClassRun`;
-- * source-facing specialization for Theorem 5.2.1:
-- `GeneralQuasiNewtonMethod.IsBroydenClassMethod`;
-- * primitive data: a quasi-Newton run together with the secant denominators and Broyden
-- inverse-update data at each nonterminal stage, reusing the upstream exact-line-search owner;
-- * derived API: `GeneralQuasiNewtonMethod.GeneratedThrough`, the stagewise `stepSpec`, and the
-- five quadratic-termination theorems below.
namespace GeneralQuasiNewtonMethod
variable {G : MatrixN} {b : Point} {c : ℝ}
local notation "f" => quadraticObjective G b c
theorem broydenClassMethod_hereditary
(A : GeneralQuasiNewtonMethod f)
(φ : ℕ → ℝ)
(hBroyden : A.IsBroydenClassMethod φ) {m : ℕ}
(hGenerated : A.GeneratedThrough (m + 1)) :
∀ ⦃i j : ℕ⦄, i ≤ m → j ≤ i →
(A.matrix (i + 1)).mulVec (broydenSecant A.g j) = broydenStep A j
Theorem 5.2.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.2.2 (Positive Definiteness of Broyden Class of Update): let φ ≥ 0. For a positive-definite inverse-Hessian approximation H, on the Broyden-class inverse-update domain dotProduct s y ≠ 0, the canonical Chapter 5 Broyden update remains positive definite if and only if 0 < dotProduct s y.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem broydenClassInverseUpdate_posDef_iff
(H : MatrixN) (hH : H.PosDef) (s y : Point) (φ : ℝ)
(hφ : 0 ≤ φ) (hsy : dotProduct s y ≠ 0) :
let hyHy :=
posDef_dotProduct_mulVec_ne_zero hH (right_ne_zero_of_dotProduct_ne_zero hsy)
(broydenClassInverseUpdate H s y φ).PosDef ↔ 0 < dotProduct s y
Theorem 5.2.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.2.3: the degenerate value of the Broyden class update is 1 / (1 - yᵀ H y * sᵀ B s / (sᵀ y)^2), i.e. formula (5.2.20).
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: `Definition_5_2_extra_1` owns the Chapter 5 scalar `broydenClassMu`.
-- This file keeps only the degenerate-parameter bridge theorems attached to that owner.
theorem broydenClassDegenerateValue_eq_formula
(H B : MatrixN) (s y : Point) :
1 / (1 - broydenClassMu H B s y) =
1 / (
1 - dotProduct y (H.mulVec y) * dotProduct s (B.mulVec s) / (dotProduct s y) ^ 2
)
Theorem 5.2.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.2.4 common assumptions: f is C¹, the level set quasiNewtonLevelSet f A.x₀ is bounded, both sequences are exact-line-search Broyden-class runs satisfying the stagewise positive secant-curvature and parameter lower-bound hypotheses, the initial iterates agree, the initial inverse matrices agree, and the common initial matrix is positive definite.
open Matrix
open GeneralQuasiNewtonMethod
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this file:
-- * primary domain: exact-line-search Broyden-class quasi-Newton runs on `ℝ^n`;
-- * sampled Chapter 5 owners: `GeneralQuasiNewtonMethod.IsBroydenClassRun` from `Theorem_5_2_1`,
-- `GeneralQuasiNewtonMethod` from `Algorithm_5_1_1`, `bfgsInverseUpdate` from
-- `Definition_5_1_extra_4`, and `broydenClassMu` from `Definition_5_2_extra_1`;
-- * core/canonical owner abstraction:
-- `A.IsBroydenClassRun φ` from `Theorem_5_2_1`;
-- * source-facing layer here: the common assumption bundle
-- `ParameterIndependenceAssumptions A A' φ φ'` together with the two
-- parameter-independence conclusions for Broyden-class runs;
-- * primitive data added here beyond the upstream owner: the stagewise positive secant
-- curvature and the parameter lower bound `(5.2.20)`;
-- * derived API:
-- `GeneralQuasiNewtonMethod.GeneratedThrough` and the tail-agreement hypothesis
-- `Set.EqOn φ φ' (Set.Ici k)` used in the theorem statements.
variable {f : Point → ℝ}
def ParameterIndependenceAssumptions
(A A' : GeneralQuasiNewtonMethod f) (φ φ' : ℕ → ℝ) : Prop
Definition 5.2.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Definition 5.2-extra-1: on the source denominator domain dotProduct s y ≠ 0 and dotProduct y (H.mulVec y) ≠ 0, the inverse-Hessian Broyden class update is the weighted combination (1 - φ) • dfpInverseUpdate H s y + φ • bfgsInverseUpdate H s y. When 0 ≤ φ ≤ 1, this is the Broyden convex class.
open Matrix
variable {n : ℕ}
-- Local declaration justification (source-local notation): the source formulas in this item are
-- written repeatedly on the fixed Euclidean space `ℝ^n`, and this file keeps that notation local
-- rather than introducing a reusable owner-level alias.
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Local declaration justification (source-local notation): the source formulas in this item are
-- stated on one fixed real `n × n` matrix space, and the alias is used only to keep those local
-- source-facing statements readable.
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- `broydenStep` and `broydenSecant` are reused from `Algorithm_5_1_1`, the owner file of the
-- quasi-Newton run data.
def broydenClassInverseUpdate (H : MatrixN) (s y : Point) (φ : ℝ) : MatrixN :=
(1 - φ) • dfpInverseUpdate H s y + φ • bfgsInverseUpdate H s y
Definition 5.2.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The Huang auxiliary vector u = a11 • s + a12 • Hᵀ y.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this item:
-- * primary domain: Huang rank-two inverse-Hessian updates on the Chapter 5 Euclidean matrix
-- model;
-- * sampled canonical declarations in this domain:
-- `satisfiesQuasiNewtonEquation`,
-- `satisfiesQuasiNewtonEquation_toEuclideanLin_iff`,
-- `broydenClassInverseUpdate`,
-- `Matrix.toEuclideanLin`;
-- * best owner abstraction in the minimal closure: the Chapter 5 Euclidean point model together
-- with the operator-valued secant owner from `Definition_5_1_extra_1`;
-- * source/core/bridge triage for this file:
-- source-facing: `huangUpdateU`, `huangUpdateV`, `huangUpdate`, `IsHuangUpdate`;
-- core/canonical: `satisfiesQuasiNewtonEquation`;
-- bridge/view: the concrete matrix-model secant theorem
-- `satisfiesQuasiNewtonEquation_toEuclideanLin_smul_iff`;
-- * primitive data: the Huang auxiliary vectors, the raw Huang rank-two matrix formula, and the
-- source predicate `IsHuangUpdate`;
-- * derived API: the secant theorem and the symmetric specialization.
-- The public surface therefore stays on the chapter's canonical Euclidean owner and uses the
-- matrix/Euclidean conversion only as a thin bridge.
def huangUpdateU (a11 a12 : ℝ) (H : MatrixN) (s y : Point) : Point :=
a11 • s + a12 • matrixMulVecPoint H.transpose y5.3 — Global Convergence of Quasi-Newton Methods
Assumption 5.3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Assumption 5.3.1: f is twice continuously differentiable on a convex set D, the level set L(x0) = {x | f x ≤ f x0} is contained in D, and there are positive constants m and M giving lower and upper Hessian bounds on all of D. The canonical lower-level-set bounds used later are derived by restriction.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
class HasQuasiNewtonGlobalConvergenceAssumptions
(D : Set Point) (f : Point → ℝ) (x0 : Point) : Prop where
open_domain : IsOpen D
convex_domain : Convex ℝ D
contDiffOn : ContDiffOn ℝ 2 f D
levelSet_subset : quasiNewtonLevelSet f x0 ⊆ D
lower_hessian :
∃ m > 0, HasHessianLowerBoundOn D f m
upper_hessian :
∃ M > 0, HasHessianUpperBoundOn D f M
Lemma 5.3.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.3.2: if Chapter05 Assumption 5.3.1 holds and lower and upper Hessian bounds with constants 0 < m and M hold on the level set quasiNewtonLevelSet f x0, then the reciprocal curvature ratio ‖yk‖ ^ 2 / dotProduct sk yk is bounded above by M. The lower bound makes the denominator positivity part of the mathematical input instead of leaving it hidden behind totalized division.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * source-facing layer: Lemma 5.3.2 secant estimates under
-- `HasQuasiNewtonGlobalConvergenceAssumptions`;
-- * core/canonical project owners: `quasiNewtonLevelSet`, `lowerLevelSetOn`,
-- `HasLowerLevelHessianLowerBound`, and `HasLowerLevelHessianUpperBound`;
-- * bridge/view layer: the explicit constants `m` and `M` extracted from the Chapter 5
-- assumption package.
-- The gradient-difference estimates in this file use the Chapter 5 convexity and `C²` regularity
-- on the level set segment between `xk` and `xk + sk`, so the source-facing assumption package
-- remains part of the public theorem surface.
theorem secantNormSq_div_secantCurvature_le_M_of_lowerLevelHessianBounds
{D : Set Point}
(f : Point → ℝ) (x0 xk sk yk : Point) {m M : ℝ}
(hm : 0 < m)
(hA : HasQuasiNewtonGlobalConvergenceAssumptions D f x0)
(hLower : HasLowerLevelHessianLowerBound D f x0 m)
(hUpper : HasLowerLevelHessianUpperBound D f x0 M)
(hxk : xk ∈ quasiNewtonLevelSet f x0)
(hxk_add_sk : xk + sk ∈ quasiNewtonLevelSet f x0)
(hyk : yk = gradient f (xk + sk) - gradient f xk)
(hsk : sk ≠ 0) :
‖yk‖ ^ (2 : ℕ) / dotProduct sk yk ≤ M
Lemma 5.3.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.3.3 (1): under Chapter05 Assumption 5.3.1, if A is an exact-line-search quasi-Newton run whose iterates stay in quasiNewtonLevelSet f A.x0 and whose realized displacements broydenStep A k = A (k + 1) - A k are exact line-search steps of length 1, then the step-square series ∑ ‖s_k‖ ^ 2 is convergent, formalized canonically as Summable (fun k ↦ ‖broydenStep A k‖ ^ (2 : ℕ)).
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
variable {D : Set Point} {f : Point → ℝ} (A : GeneralQuasiNewtonMethod f)
variable (hA : HasQuasiNewtonGlobalConvergenceAssumptions D f A.x0)
variable (hIterates : ∀ k : ℕ, A k ∈ quasiNewtonLevelSet f A.x0)
variable
(hExactLineSearch :
∀ k : ℕ, IsExactLineSearchStepOnNonnegativeRay f (A k) (broydenStep A k) 1)
include hA hIterates hExactLineSearch
theorem stepNormSq_summable_of_exactLineSearch :
Summable (fun k ↦ ‖broydenStep A k‖ ^ (2 : ℕ))
Lemma 5.3.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.3.4: if f : ℝ^n → ℝ is strongly convex on the ambient space with modulus m > 0, f xStar is the minimum value of f, and f is differentiable at x, then ‖gradient f x‖ ^ (2 : ℕ) ≥ m * (f x - f xStar).
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling: the source statement is the ambient "for all vectors `x`" inequality, and the
-- canonical owner for that route in this project is global strong convexity on `Set.univ`.
-- The Chapter 5 level-set/Hessian package is proof-route data for later corollaries, not the main
-- labeled statement surface here.
theorem gradientNormSqLowerBound
(f : Point → ℝ) (x xStar : Point)
(m : ℝ)
(hm : 0 < m)
(hStrong : StrongConvexOn Set.univ m f)
(hx : DifferentiableAt ℝ f x)
(hMin : IsMinOn f Set.univ xStar) :
m * (f x - f xStar) ≤ ‖gradient f x‖ ^ (2 : ℕ)
Theorem 5.3.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.3.5: suppose f satisfies Chapter05 Assumption 5.3.1. Then, for a source-facing DFP method A with exact line search on the nonnegative ray and zero stopping tolerance, the iterate sequence converges to the given minimizer xStar of f on the Chapter 5 level set quasiNewtonLevelSet f A.x0. The exact-line-search property is carried by the canonical owner A.toGeneralQuasiNewtonMethod.HasExactLineSearchOnNonnegativeRay, and the post-termination frozen-tail convention is already primitive owner data on GeneralQuasiNewtonMethod, so no extra theorem-local bridge hypothesis is needed. The secant-curvature facts needed by the DFP positivity machinery are still derived from the Chapter 5 assumption package rather than stored as extra run data.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * primary domain: exact-line-search DFP quasi-Newton runs on the Chapter 5 Euclidean surface;
-- * sampled project owners in the minimal closure:
-- `DfpMethod`,
-- `DfpMethod.IsExactLineSearchOnQuadratic`,
-- `GeneralQuasiNewtonMethod.HasExactLineSearchOnNonnegativeRay`,
-- `HasQuasiNewtonGlobalConvergenceAssumptions`,
-- `bfgsWithWolfePowell_tendsto_to_minimizer`;
-- * best owner abstraction: the source-facing DFP owner `DfpMethod`, together with the
-- canonical exact-line-search owner
-- `A.toGeneralQuasiNewtonMethod.HasExactLineSearchOnNonnegativeRay` and the canonical
-- quasi-Newton termination/tail owner `GeneralQuasiNewtonMethod`;
-- * source-facing minimizer layer: Chapter 5 convergence theorems are organized around
-- `IsMinOn f (quasiNewtonLevelSet f A.x0) xStar`;
-- * primitive source-facing data used here: exact line search, zero stopping tolerance, and the
-- owner-level frozen-tail convention already carried by `GeneralQuasiNewtonMethod`;
-- * derived API here: level-set membership, secant-curvature positivity, and the generated-stage
-- DFP curvature conditions forced by Assumption 5.3.1.
theorem dfpWithExactLineSearch_tendsto_to_minimizer
{n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (D : Set (EuclideanSpace ℝ (Fin n)))
(A : DfpMethod f)
(hExactLineSearch : A.toGeneralQuasiNewtonMethod.HasExactLineSearchOnNonnegativeRay)
(hε : A.ε = 0)
(h_assumption : HasQuasiNewtonGlobalConvergenceAssumptions D f A.x0)
(xStar : EuclideanSpace ℝ (Fin n))
(hxStar : IsMinOn f (quasiNewtonLevelSet f A.x0) xStar) :
Tendsto A atTop (nhds xStar)
Theorem 5.3.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.3.6: let x₀ and B₀ be a starting point and a symmetric positive definite initial matrix, respectively. Suppose f satisfies Chapter05 Assumption 5.3.1. Then, under the Wolfe-Powell inexact line-search inequalities (2.5.3) and (2.5.7), the sequence generated by the Hessian-side BFGS/Wolfe run A converges to the given minimizer xStar of f on the level set quasiNewtonLevelSet f A.x0. The canonical run owner is GeneralQuasiNewtonMethod; the additional Hessian-side BFGS/Wolfe content is the bridge hypothesis A.HessianBFGSOn D.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * primary domain: Hessian-side BFGS runs with Wolfe-Powell line search on `ℝ^n`;
-- * sampled project declarations in the same owner family:
-- `GeneralQuasiNewtonMethod` and `GeneralQuasiNewtonMethod.stepSpec` from
-- `Algorithm_5_1_1`,
-- `WolfePowellCondition` and `WolfePowellParameters` from Chapter 2,
-- `GeneralQuasiNewtonMethod.IsFullStepBFGSOn`,
-- `bfgsHessianUpdate`,
-- `HasQuasiNewtonGlobalConvergenceAssumptions`;
-- * layer triage:
-- source-facing theorem: `bfgsWithWolfePowell_tendsto_to_minimizer`;
-- core/canonical owner: `GeneralQuasiNewtonMethod`;
-- bridge/view data here: `GeneralQuasiNewtonMethod.HessianBFGSOn`, adding the theorem-specific
-- Wolfe-Powell line-search data and the Hessian-side BFGS secant-curvature and update laws;
-- * primitive data owned upstream by `GeneralQuasiNewtonMethod`: the iterate / inverse-operator
-- / gradient / direction / step-size sequences and the quasi-Newton step data;
-- * primitive data added here: iterate membership in `D`, positive-definite Hessian-side
-- matrices, Wolfe-Powell parameters and accepted-step inequalities, and the Hessian-side BFGS
-- secant-curvature positivity and update `(5.1.45)`.
theorem bfgsWithWolfePowell_tendsto_to_minimizer
(f : Point → ℝ) (D : Set Point)
(A : GeneralQuasiNewtonMethod f)
(hA : A.HessianBFGSOn D)
(h_assumption : HasQuasiNewtonGlobalConvergenceAssumptions D f A.x0)
(xStar : Point) (hxStar : IsMinOn f (quasiNewtonLevelSet f A.x0) xStar) :
Tendsto A atTop (nhds xStar)
5.4 — Local Convergence of Quasi-Newton Methods
Assumption 5.4.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Assumption 5.4.1: F : ℝ^n → ℝ^n is continuously differentiable on an open convex set D, there is xStar ∈ D with F xStar = 0 and invertible derivative fderiv ℝ F xStar, and there is a constant gamma such that ‖fderiv ℝ F x - fderiv ℝ F xStar‖ ≤ gamma * ‖x - xStar‖ for every x ∈ D.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall: `lean_leansearch` surfaced local-inverse and local Lipschitz lemmas for
-- `ContDiffAt`/`ContDiffOn`, but no canonical bundled owner for this exact assumption package,
-- so this item keeps the source-faithful `ContDiffOn`/`fderiv` formulation explicit.
structure HasQuasiNewtonLocalConvergenceAssumptions
(D : Set Point) (F : Point → Point) where
open_domain : IsOpen D
convex_domain : Convex ℝ D
contDiffOn : ContDiffOn ℝ 1 F D
xStar : Point
xStar_mem : xStar ∈ D
map_xStar : F xStar = 0
fderiv_isInvertible : (fderiv ℝ F xStar).IsInvertible
gamma : ℝ
lipschitz_fderiv :
∀ x ∈ D, ‖fderiv ℝ F x - fderiv ℝ F xStar‖ ≤ gamma * ‖x - xStar‖Assumption 5.4.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Assumption 5.4.2: f : ℝ^n → ℝ is twice continuously differentiable on an open convex set D, there is a distinguished point xStar that is a strong local minimizer of f on D, the canonical Hessian matrix quasiNewtonHessianMatrix f xStar is positive definite, hence symmetric, and on some neighborhood Metric.ball xStar ε ⊆ D this Hessian matrix field is γ-Lipschitz for a nonnegative Lipschitz constant γ.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: `lean_leansearch` surfaced `IsLocalMin`, `StrongConvexOn`, and
-- `ContDiffAt.exists_lipschitzOnWith`, but no canonical owner for the source's strong
-- local-minimizer plus Hessian-Lipschitz assumption package. The item is therefore stated
-- directly with a quadratic-growth predicate and the canonical Hessian of `f`.
structure HasQuasiNewtonStrongLocalMinimizerAssumptions
(D : Set Point) (f : Point → ℝ) where
open_domain : IsOpen D
convex_domain : Convex ℝ D
contDiffOn : ContDiffOn ℝ 2 f D
xStar : Point
strong_local_min : IsStrongLocalMinOn f D xStar
xStar_hessian_posDef : (quasiNewtonHessianMatrix f xStar).PosDef
ε : ℝ
ε_pos : 0 < ε
ball_subset_domain : Metric.ball xStar ε ⊆ D
γ : NNReal
hessian_lipschitz (x xBar : Point)
(hx : x ∈ Metric.ball xStar ε)
(hxBar : xBar ∈ Metric.ball xStar ε) :
‖quasiNewtonHessianMatrix f xBar - quasiNewtonHessianMatrix f x‖ ≤ γ * ‖xBar - x‖
Theorem 5.4.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.3: let F : ℝ^n → ℝ^n satisfy HasQuasiNewtonLocalConvergenceAssumptions D F. Let B k be a sequence of nonsingular linear maps, written with their canonical inverses (B k).inverse, and let x (k + 1) = x k - (B k).inverse (F (x k)) be a quasi-Newton iterate sequence that stays in D and converges to hF.xStar. Then x converges to hF.xStar Q-superlinearly, in the canonical Chapter 1 sense, exactly when the secant-error ratio ‖(B k - fderiv ℝ F hF.xStar) (x (k + 1) - x k)‖ / ‖x (k + 1) - x k‖ tends to 0.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling:
-- * primary domain: convergence rates of sequences in normed spaces.
-- * core/canonical owners sampled for this file: `qErrorRatio` and
-- `HasQSuperlinearConvergenceTo` from `Chapter01.Definition_1_5_extra_1`,
-- `HasSuperlinearConvergenceTo` from `Chapter03.Theorem_3_4_4`, mathlib's
-- `Asymptotics.IsLittleO` / `=o` API, `HasFDerivAt` / `fderiv`, and
-- `ContinuousLinearMap.IsInvertible` with `.inverse`.
-- * source/core/bridge triage: the only new source-facing owner here is the secant-error ratio
-- `(5.4.4)`; the superlinear convergence notion itself is already owned upstream, and the
-- theorem below is a Chapter 5 bridge from that canonical owner to the secant-error criterion.
theorem quasiNewton_superlinear_iff_secantErrorRatio_tendsto_zero
{D : Set Point}
(F : Point → Point)
(hF : HasQuasiNewtonLocalConvergenceAssumptions D F)
(B : ℕ → Point →L[ℝ] Point)
(x : ℕ → Point)
(hB_invertible : ∀ k : ℕ, (B k).IsInvertible)
(h_update : ∀ k : ℕ, x (k + 1) = x k - (B k).inverse (F (x k)))
(h_iterates_mem : ∀ k : ℕ, x k ∈ D)
(hx : Tendsto x atTop (nhds hF.xStar)) :
HasQSuperlinearConvergenceTo x hF.xStar ↔
Tendsto (quasiNewtonSecantErrorRatio F hF.xStar B x) atTop (nhds 0)
Theorem 5.4.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.4 uses the same local differentiability, convexity, invertibility, and derivative-Lipschitz hypotheses as Theorem 5.4.3, but it does not assume in advance that the distinguished limit point is a zero of F.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Source/core/bridge triage:
-- * `HasScaledQuasiNewtonLocalAssumptions` is the source-facing weak local theory from
-- Theorem 5.4.4, which intentionally does not assume `F xStar = 0`.
-- * `HasQuasiNewtonLocalConvergenceAssumptions` from Assumption 5.4.1 remains the stronger
-- Chapter 5 core owner, recovered here by a thin bridge when `F xStar = 0`.
-- * `ScaledQuasiNewtonSetup` is the source-facing iteration data for the damped update
-- `x (k + 1) = x k - α k • BInv k (F (x k))`.
structure HasScaledQuasiNewtonLocalAssumptions
(D : Set Point) (F : Point → Point) where
open_domain : IsOpen D
convex_domain : Convex ℝ D
contDiffOn : ContDiffOn ℝ 1 F D
xStar : Point
xStar_mem : xStar ∈ D
fderiv_isInvertible : (fderiv ℝ F xStar).IsInvertible
gamma : ℝ
lipschitz_fderiv :
∀ x ∈ D, ‖fderiv ℝ F x - fderiv ℝ F xStar‖ ≤ gamma * ‖x - xStar‖
Lemma 5.4.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.4.5 (4): if 0 < ⟪u, v⟫_ℝ and the two inequalities in (5.4.17) hold, then ‖u - v‖ ≤ (3 * α) * ‖u‖.
open scoped InnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem norm_sub_le_three_mul_of_inner_pos_and_controls
(u v : E) (α : ℝ) (hpos : 0 < ⟪u, v⟫_ℝ)
(hnorm : |1 - ‖v‖ / ‖u‖| ≤ α)
(hangle : 1 - (⟪u, v⟫_ℝ / (‖u‖ * ‖v‖)) ^ (2 : ℕ) ≤ α ^ (2 : ℕ)) :
‖u - v‖ ≤ (3 * α) * ‖u‖Theorem 5.4.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.6: let f : ℝ^n → ℝ satisfy HasQuasiNewtonStrongLocalMinimizerAssumptions D f. Consider the quasi-Newton iteration x (k + 1) = x k - B k⁻¹ ∇f(x k), where the Hessian approximations B k are positive definite. If x converges to the limit point h.xStar, then x converges to h.xStar Q-superlinearly exactly when the Hessian-side secant-error ratio ‖(B k - quasiNewtonHessianMatrix f h.xStar) (x (k + 1) - x k)‖ / ‖x (k + 1) - x k‖ tends to 0.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * primary domain: local quasi-Newton superlinear convergence for smooth objectives on the
-- Euclidean matrix model of `ℝ^n`.
-- * sampled owner declarations in this domain:
-- `quasiNewtonSecantErrorRatio` from `Theorem_5_4_3`,
-- `HasQSuperlinearConvergenceTo` from `Chapter01.Definition_1_5_extra_1`,
-- `quasiNewtonHessianMatrix` from `Assumption_5_4_2`,
-- `Matrix.toEuclideanLin` / `Matrix.toEuclideanCLM` for the concrete matrix action bridge.
-- * best owner abstraction: `quasiNewtonSecantErrorRatio` is the core/canonical secant-error
-- owner; the Hessian-side ratio below is only a source-facing matrix-model bridge/view.
-- * primitive data for the theorem: the objective `f`, the Assumption 5.4.2 package `h`, the
-- Hessian-approximation sequence `B`, the iterate sequence `x`, and the quasi-Newton update.
-- * derived API: the Hessian-side secant-error ratio expressed by reusing the canonical owner
-- from `Theorem_5_4_3`.
theorem quasiNewton_superlinear_iff_hessianSecantErrorRatio_tendsto_zero
{D : Set Point}
(f : Point → ℝ)
(h : HasQuasiNewtonStrongLocalMinimizerAssumptions D f)
(B : ℕ → MatrixN)
(x : ℕ → Point)
(hB_posDef : ∀ k : ℕ, (B k).PosDef)
(h_update :
∀ k : ℕ, x (k + 1) = x k - Matrix.toEuclideanLin ((B k)⁻¹) (gradient f (x k)))
(hx : Tendsto x atTop (nhds h.xStar)) :
HasQSuperlinearConvergenceTo x h.xStar ↔
Tendsto (quasiNewtonHessianSecantErrorRatio f h.xStar B x) atTop (nhds 0)
Theorem 5.4.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.7 (1): let f : ℝ^n → ℝ satisfy HasQuasiNewtonStrongLocalMinimizerAssumptions D f, and let A : ScaledQuasiNewtonSetup (gradient f) D be the scaled quasi-Newton run owner. If A.x converges to h.xStar and the canonical secant-error ratio for gradient f tends to 0, then the step sizes satisfy A.α k → 1. The source Hessian-side ratio from Theorem_5_4_6 is the Euclidean matrix-model view of this owner-level hypothesis.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem scaledQuasiNewton_stepsizes_tendsto_one_of_secantErrorRatio_tendsto_zero
{D : Set Point}
(f : Point → ℝ)
(h : HasQuasiNewtonStrongLocalMinimizerAssumptions D f)
(A : ScaledQuasiNewtonSetup (gradient f) D)
(hx : Tendsto A.x atTop (nhds h.xStar))
(h_secantError :
Tendsto (quasiNewtonSecantErrorRatio (gradient f) h.xStar A.B A.x) atTop (nhds 0)) :
Tendsto A.α atTop (nhds 1)
Theorem 5.4.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.8 (1): on the canonical scaled quasi-Newton owner A : ScaledQuasiNewtonSetup (gradient f) D, the Hessian-side source ratio (5.4.25) is only the Euclidean matrix-model view of the secant-error owner from Theorem_5_4_7. The step-size conclusion is therefore a thin bridge to scaledQuasiNewton_stepsizes_tendsto_one_of_secantErrorRatio_tendsto_zero, with no additional Wolfe-Powell or noncollision hypotheses in the public statement.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * primary domain: local scaled quasi-Newton convergence on the Euclidean matrix model of
-- `ℝ^n`;
-- * sampled owner declarations in the minimal closure:
-- `quasiNewtonHessianSecantErrorRatio` from `Theorem_5_4_6`,
-- `ScaledQuasiNewtonSetup (gradient f) D`,
-- `ScaledQuasiNewtonSetup.matrix`,
-- `scaledQuasiNewton_stepsizes_tendsto_one_of_secantErrorRatio_tendsto_zero`,
-- and `scaledQuasiNewton_qsuperlinear_of_secantErrorRatio_tendsto_zero`
-- from `Theorem_5_4_7`,
-- together with `HasQuasiNewtonStrongLocalMinimizerAssumptions` from `Assumption_5_4_2`;
-- * layer triage:
-- source-facing theorem item: the Hessian-side matrix specialization of the local secant-error
-- hypothesis from Theorem 5.4.8;
-- core/canonical owner: `ScaledQuasiNewtonSetup (gradient f) D`;
-- bridge/view reused here: `A.matrix` and `quasiNewtonHessianSecantErrorRatio`;
-- * primitive data: `f`, the local-minimizer assumptions `h`, the scaled quasi-Newton run owner
-- `A`, convergence of `A.x`, and the Hessian-side secant-error limit;
-- * derived API reused here: the step-size and `Q`-superlinear conclusions already owned by
-- `Theorem_5_4_7`.
theorem scaledQuasiNewton_stepsizes_tendsto_one_of_hessianSecantError
{D : Set Point}
(f : Point → ℝ)
(h : HasQuasiNewtonStrongLocalMinimizerAssumptions D f)
(A : ScaledQuasiNewtonSetup (gradient f) D)
(hx : Tendsto A.x atTop (nhds h.xStar))
(h_secantError :
Tendsto (quasiNewtonHessianSecantErrorRatio f h.xStar A.matrix A.x) atTop (nhds 0)) :
Tendsto A.α atTop (nhds 1)
Theorem 5.4.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.9: if F : ℝ^n → ℝ^n satisfies HasQuasiNewtonLocalConvergenceAssumptions D F, and U is a set-valued Jacobian update rule such that either all admissible updates satisfy the additive estimate (5.4.40) with some constant γu, or all admissible updates satisfy the σ-estimate (5.4.41) for some constants α₁, α₂, on an admissibility set domU, with the source-side well-definedness conditions for small admissible starts and admissible update selections folded into that update hypothesis, where σ(xₖ, xₖ₊₁) = max ‖xₖ - hF.xStar‖ ‖xₖ₊₁ - hF.xStar‖, then there exist constants ε and δ such that every initial pair (x₀, B₀) with ‖x₀ - hF.xStar‖ < ε and ‖B₀ - fderiv ℝ F hF.xStar‖ < δ generates a well-defined iteration (5.4.38)-(5.4.39), and every such iteration has iterate sequence converging linearly to hF.xStar.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Operator" => Point →L[ℝ] Point
theorem jacobianQuasiNewtonSmallStartConvergence_of_update_condition
(D : Set Point) (F : Point → Point)
(hF : HasQuasiNewtonLocalConvergenceAssumptions D F)
(domU : Set (Point × Operator))
(U : JacobianUpdateFunction Point)
(h_update :
(∃ γu : ℝ,
SatisfiesAdditiveLocalUpdateBound U F hF.xStar (fderiv ℝ F hF.xStar) domU γu) ∨
∃ α1 α2,
SatisfiesSigmaLocalUpdateBound U F hF.xStar (fderiv ℝ F hF.xStar) domU α1 α2) :
∃ ε > 0, ∃ δ > 0, ∀ x0 B0,
‖x0 - hF.xStar‖ < ε →
‖B0 - fderiv ℝ F hF.xStar‖ < δ →
JacobianQuasiNewtonSmallStartConvergence D F domU U hF.xStar x0 B0
Theorem 5.4.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.10: let F : ℝ^n → ℝ^n satisfy Chapter05 Assumption 5.4.1, and let U be a set-valued inverse quasi-Newton update rule on pairs (xₖ, Hₖ). Assume that every admissible update satisfies either the inverse-side additive estimate (5.4.60) or the inverse-side σ-estimate (5.4.61) relative to the reference inverse derivative hF.referenceInverse = F'(x*)⁻¹, with the source-side small-start admissibility and update well-definedness conditions folded into that inverse update hypothesis. Then there exist constants ε and δ such that every initial pair (x₀, H₀) with ‖x₀ - hF.xStar‖ < ε and ‖H₀ - hF.referenceInverse‖ < δ admits a canonical inverse-side run whose underlying Jacobian-side realization lives on the inverse-induced bridge data jacobianDomOfInverse domU, jacobianUpdateOfInverse U; every such inverse-side run has iterate sequence converging linearly to hF.xStar.
variable {n : ℕ}
-- Local declaration justification (source-local notation): this file formalizes one fixed
-- Euclidean ambient space from the source statement, and a public alias for that ambient model
-- would be a vacuous wrapper with no reuse outside the numbered item surface.
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Local declaration justification (source-local notation): this numbered item uses one ambient
-- operator space throughout, and introducing a public owner only for the alias would add a
-- meaningless wrapper instead of mathematical API.
local notation "Operator" => Point →L[ℝ] Point
namespace InverseJacobianQuasiNewtonSmallStartConvergence
theorem ofUpdateCondition
{D : Set Point} {F : Point → Point}
(hF : HasQuasiNewtonLocalConvergenceAssumptions D F)
(domU : Set (Point × Operator))
(U : JacobianUpdateFunction Point)
(h_update :
(∃ γ : ℝ,
SatisfiesInverseAdditiveLocalUpdateBound U F hF.xStar hF.referenceInverse domU γ) ∨
∃ α₁ α₂ : ℝ,
SatisfiesInverseSigmaLocalUpdateBound U F hF.xStar hF.referenceInverse domU α₁ α₂) :
∃ ε > 0, ∃ δ > 0,
∀ x0 : Point, ∀ H0 : Operator,
‖x0 - hF.xStar‖ < ε →
‖H0 - hF.referenceInverse‖ < δ →
InverseJacobianQuasiNewtonSmallStartConvergence D F domU U hF.xStar x0 H0
Corollary 5.4.11
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Corollary 5.4.11: under the assumptions and small-start regime of Theorem 5.4.9, if some subsequence of the Jacobian approximation errors ‖B k - fderiv ℝ F xStar‖ converges to 0, then the quasi-Newton iterates converge to xStar Q-superlinearly.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Operator" => Point →L[ℝ] Point
-- Domain sampling:
-- * primary domain: Jacobian-side quasi-Newton local convergence and superlinear rates.
-- * core/canonical owners inspected: `HasQuasiNewtonLocalConvergenceAssumptions` from
-- `Assumption_5_4_1`, `JacobianQuasiNewtonSmallStartConvergence` and
-- `JacobianQuasiNewtonIteration` from `Theorem_5_4_9`, and
-- `HasQSuperlinearConvergenceTo`.
-- * layer choice: this corollary is a source-facing bridge statement. The vanishing-subsequence
-- hypothesis is expressed through the reusable Chapter 5 owner `HasSubsequenceTendstoTo`
-- applied to the Jacobian-error norm sequence, while the ambient local-convergence
-- assumptions and small-start conclusion are expressed through the chapter owners above.
theorem jacobianQuasiNewton_qSuperlinearConvergence_of_vanishingJacobianErrorSubsequence
{D : Set Point} {F : Point → Point}
(hF : HasQuasiNewtonLocalConvergenceAssumptions D F)
(domU : Set (Point × Operator))
(U : JacobianUpdateFunction Point)
(h_update :
(∃ γu : ℝ,
SatisfiesAdditiveLocalUpdateBound U F hF.xStar (fderiv ℝ F hF.xStar) domU γu) ∨
∃ α1 α2,
SatisfiesSigmaLocalUpdateBound U F hF.xStar (fderiv ℝ F hF.xStar) domU α1 α2) :
∃ ε > 0, ∃ δ > 0, ∀ x0 B0,
‖x0 - hF.xStar‖ < ε →
‖B0 - fderiv ℝ F hF.xStar‖ < δ →
JacobianQuasiNewtonSmallStartConvergence D F domU U hF.xStar x0 B0 ∧
∀ A : JacobianQuasiNewtonIteration D F domU U x0 B0,
HasSubsequenceTendstoTo (fun k ↦ ‖A.B k - fderiv ℝ F hF.xStar‖) 0 →
HasQSuperlinearConvergenceTo A.x hF.xStar
Corollary 5.4.12
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Corollary 5.4.12: under the assumptions and small-start regime of inverseJacobianQuasiNewtonSmallStartConvergence_of_update_condition, if some subsequence of the inverse-approximation errors ‖H k - hF.referenceInverse‖ converges to 0, then every inverse-side quasi-Newton run from the same small start converges to hF.xStar Q-superlinearly.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Operator" => Point →L[ℝ] Point
-- Domain sampling:
-- * primary domain: inverse-Jacobian-side quasi-Newton local convergence and `Q`-superlinear
-- rates;
-- * core/canonical owners inspected: `HasQuasiNewtonLocalConvergenceAssumptions` from
-- `Assumption_5_4_1`, `InverseJacobianQuasiNewtonSmallStartConvergence` and
-- `InverseJacobianQuasiNewtonIteration` from `Theorem_5_4_10`, and
-- `HasQSuperlinearConvergenceTo`, together with the reusable Chapter 5 subsequence owner
-- `HasSubsequenceTendstoTo`;
-- * layer choice: this corollary is a source-facing bridge statement. The vanishing-subsequence
-- hypothesis is expressed through `HasSubsequenceTendstoTo` applied to the inverse-error norm
-- sequence, while the ambient local-convergence assumptions and
-- inverse small-start owner are expressed through the chapter owners above.
theorem inverseJacobianQuasiNewton_qSuperlinearConvergence_of_vanishingInverseErrorSubsequence
{D : Set Point} {F : Point → Point}
(hF : HasQuasiNewtonLocalConvergenceAssumptions D F)
(domU : Set (Point × Operator))
(U : JacobianUpdateFunction Point)
(h_update :
(∃ γ : ℝ,
SatisfiesInverseAdditiveLocalUpdateBound U F hF.xStar hF.referenceInverse domU γ) ∨
∃ α₁ α₂ : ℝ,
SatisfiesInverseSigmaLocalUpdateBound U F hF.xStar hF.referenceInverse domU α₁ α₂) :
∃ ε > 0, ∃ δ > 0,
∀ x0 : Point, ∀ H0 : Operator,
‖x0 - hF.xStar‖ < ε →
‖H0 - hF.referenceInverse‖ < δ →
InverseJacobianQuasiNewtonSmallStartConvergence D F domU U hF.xStar x0 H0 ∧
∀ A : InverseJacobianQuasiNewtonIteration D F domU U x0 H0,
HasSubsequenceTendstoTo (fun k ↦ ‖A.H k - hF.referenceInverse‖) 0 →
HasQSuperlinearConvergenceTo A.x hF.xStar
Theorem 5.4.13
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.13: if F : ℝ^n → ℝ^n satisfies HasQuasiNewtonLocalConvergenceAssumptions D F, then there exist ε, δ > 0 such that every initial point x0 and initial Jacobian approximation B0 with ‖x0 - hF.xStar‖ < ε and ‖B0 - fderivMatrix F hF.xStar‖ < δ have the property that every sequence pair x, B generated by Broyden's rank-one update (5.4.63)-(5.4.64) from x0, B0 is well-defined and the iterate sequence x converges to hF.xStar Q-superlinearly.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
theorem broydenRankOne_qSuperlinearConvergence_of_small_initial_pair
(D : Set (BroydenPoint n)) (F : BroydenPoint n → BroydenPoint n)
(hF : HasQuasiNewtonLocalConvergenceAssumptions D F) :
∃ ε > 0, ∃ δ > 0, ∀ x0 : BroydenPoint n, ∀ B0 : BroydenMatrix n,
‖x0 - hF.xStar‖ < ε →
‖B0 - fderivMatrix F hF.xStar‖ < δ →
∀ x : ℕ → BroydenPoint n, ∀ B : ℕ → BroydenMatrix n,
IsGeneratedBroydenRankOneIteration F x0 B0 x B →
IsWellDefinedBroydenRankOneIteration D F x0 B0 x B ∧
HasQSuperlinearConvergenceTo x hF.xStar
Theorem 5.4.14
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.14: if F : ℝ^n → ℝ^n satisfies HasQuasiNewtonLocalConvergenceAssumptions D F, then there are radii ε, δ > 0 such that every initial point x0 and initial inverse-Jacobian approximation H0 with ‖x0 - hF.xStar‖ < ε and ‖H0 - fderivInverseMatrix F hF.xStar‖ < δ have the property that every inverse-Broyden rank-one sequence pair x, H generated by (5.4.77)-(5.4.78) from x0, H0 is well-defined and the iterate sequence x converges to hF.xStar Q-superlinearly.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: the canonical `Q`-superlinear convergence owner already lives upstream in
-- Chapter 1, but the inverse-Broyden rank-one update `(5.4.78)` itself is still source-facing
-- local API here. This file therefore reuses `HasQSuperlinearConvergenceTo` and keeps only the
-- theorem-specific inverse-update and recursion surface on matrices.
theorem broydenRankOneInverse_qSuperlinearConvergence_of_small_initial_pair
(D : Set Point) (F : Point → Point)
(hF : HasQuasiNewtonLocalConvergenceAssumptions D F) :
∃ ε > 0, ∃ δ > 0, ∀ x0 H0,
‖x0 - hF.xStar‖ < ε →
‖H0 - fderivInverseMatrix F hF.xStar‖ < δ →
∀ x : ℕ → Point, ∀ H : ℕ → MatrixN,
IsGeneratedBroydenRankOneInverseIteration F x0 H0 x H →
IsWellDefinedBroydenRankOneInverseIteration D F x0 H0 x H ∧
HasQSuperlinearConvergenceTo x hF.xStar
Theorem 5.4.15
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.15: let f : ℝ^n → ℝ satisfy HasQuasiNewtonStrongLocalMinimizerAssumptions D f. Assume the neighborhood one-third condition dfpOneThirdConditionInNeighborhood h, namely (5.4.83) with μ = ‖(∇²f(h.xStar))⁻¹‖ and σ(x, xNext) = max {‖x - h.xStar‖, ‖xNext - h.xStar‖}. Then there exist ε > 0 and δ > 0 such that every initial pair (x0, B0) with ‖x0 - h.xStar‖ < ε and dfpMatrixNorm (dfpReferenceHessian h) (B0 - dfpReferenceHessian h) < δ admits a well-defined DFP iteration (5.4.79)-(5.4.80) on D, and the produced iterate sequence converges linearly to h.xStar. The small-start conclusion is packaged into the reusable owner DFPSmallStartConvergence.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * primary domain: local DFP convergence for Hessian-side quasi-Newton iterations;
-- * owner declarations reused here: `DFPHessianRun`,
-- `dfpReferenceHessian`, `dfpMatrixNorm`, and
-- `dfpOneThirdConditionInNeighborhood` from
-- `Lemma_5_4_19`, together with the canonical Chapter 5 rate owner `LinearlyConvergesTo`
-- from `Theorem_5_4_9`;
-- * layer choice: this file is source-facing for the DFP small-start conclusion, while the DFP
-- run data and auxiliary local-start quantities are reused from the earlier owner files;
-- * primitive data: the source-facing Hessian-side run owner is `DFPHessianRun D f`, and the
-- prescribed initial data are imposed by the equalities `A.x0 = x0` and `A.B0 = B0`;
-- * derived API in this file is only the small-start linear-convergence statement over that
-- owner.
class DFPSmallStartConvergence
(D : Set Point) (f : Point → ℝ) (xStar : outParam Point) (x0 : Point) (B0 : MatrixN) :
Prop where
exists_run :
∃ A : DFPHessianRun D f, A.x0 = x0 ∧ A.B0 = B0 ∧ LinearlyConvergesTo A xStar
linear :
∀ A : DFPHessianRun D f, A.x0 = x0 → A.B0 = B0 → LinearlyConvergesTo A xStar
Theorem 5.4.16
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.16: if f is twice continuously differentiable, G is a local Lipschitz Hessian matrix field at the local minimizer xStar, A is a BFGS sequence converging to xStar, and ∑' k, ‖A k - xStar‖ < ∞, then A converges to xStar at a Q-superlinear rate.
open Filter
open scoped Matrix.Norms.L2Operator
open scoped Topology
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * `GeneralQuasiNewtonMethod` is the Chapter 5 owner for quasi-Newton trajectory data.
-- * `bfgsInverseUpdate` is the Chapter 5 owner for the inverse-BFGS matrix formula.
-- * `HasLocalLipschitzHessianMatrixAt` is the Chapter 3 owner for the local Hessian model.
-- * `HasQSuperlinearConvergenceTo` is the canonical Chapter 1 owner for the
-- `Q`-superlinear rate predicate.
--
theorem bfgs_hasQSuperlinearConvergenceTo_of_tendsto_minimizer_and_summable_dist
(f : Point → ℝ) (G : Point → MatrixN) (xStar : Point)
(A : GeneralQuasiNewtonMethod f)
(hBFGS : IsBFGSMethod A)
(hC2 : ContDiff ℝ 2 f)
(h_hessian : HasLocalLipschitzHessianMatrixAt f G xStar)
(h_min : IsLocalMin f xStar)
(h_tendsto : Tendsto A atTop (nhds xStar))
(h_summable : Summable (fun k ↦ ‖A k - xStar‖)) :
HasQSuperlinearConvergenceTo A xStar
Lemma 5.4.17
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.4.17 (1): if M is symmetric and nonsingular and ‖M y - M⁻¹ s‖ ≤ β * ‖M⁻¹ s‖, then the curvature pairing dotProduct s y lies between (1 - β) * ‖M⁻¹ s‖ ^ 2 and (1 + β) * ‖M⁻¹ s‖ ^ 2. This is the Euclidean matrix bridge of inner_bounds_of_norm_sub_le, specialized to u = (M⁻¹).toEuclideanLin s and v = M.toEuclideanLin y.
open scoped InnerProductSpace
open scoped Matrix.Norms.Frobenius
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem curvaturePairing_bounds_of_inverseSecantResidual_le
(M : MatrixN) (hM : M.IsSymm) (hMdet : IsUnit M.det)
(β : ℝ)
(s y : Point)
(hres : ‖M.toEuclideanLin y - (M⁻¹).toEuclideanLin s‖ ≤ β * ‖(M⁻¹).toEuclideanLin s‖) :
(1 - β) * ‖(M⁻¹).toEuclideanLin s‖ ^ 2 ≤ dotProduct s y ∧
dotProduct s y ≤ (1 + β) * ‖(M⁻¹).toEuclideanLin s‖ ^ 2Lemma 5.4.18
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.4.18: if nonnegative real sequences φ and δ satisfy φ (k + 1) ≤ (1 + δ k) * φ k + δ k for every k, and δ is summable, then φ converges. This is the standard ℕ-indexed reindexing of the textbook sequence starting at k = 1.
open Filter
-- Semantic recall: `lean_leansearch` did not expose a canonical ready-made mathlib theorem for
-- this perturbed scalar recurrence, so the source-faithful convergence statement is recorded
-- directly on real sequences indexed by `ℕ`.
theorem exists_tendsto_of_nonneg_recurrence_of_summable
{φ δ : ℕ → ℝ}
(hφ_nonneg : ∀ k, 0 ≤ φ k)
(hδ_nonneg : ∀ k, 0 ≤ δ k)
(hrec : ∀ k, φ (k + 1) ≤ (1 + δ k) * φ k + δ k)
(hδ_summable : Summable δ) :
∃ l : ℝ, Tendsto φ atTop (nhds l)Lemma 5.4.19
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.4.19: under the assumptions of Chapter05 Theorem 5.4.15, namely HasQuasiNewtonStrongLocalMinimizerAssumptions D f together with the neighborhood one-third condition dfpOneThirdConditionInNeighborhood h, there exist ρ > 0 and positive constants β₁, β₂, and β₃ such that every DFP step with A.x k, A.x (k + 1) ∈ Metric.ball h.xStar ρ satisfies the local DFP error contraction `dfpSqrtWeightedMatrixNorm (dfpReferenceHessian h) (A.B (k + 1) - dfpReferenceHessian h) ≤ (Real.sqrt (1 - β₁ * dfpErrorAngle (dfpReferenceHessian h) (A.B k) (A.x (k + 1) - A.x k)^2) + β₂ * dfpSigma (A.x k) (A.x (k + 1)) h.xStar) * dfpSqrtWeightedMatrixNorm (dfpReferenceHessian h) (A.B k - dfpReferenceHessian h) + β₃ * dfpSigma (A.x k) (A.x (k + 1)) h.xStar`.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
open scoped Matrix.Norms.Frobenius
open scoped Matrix.Norms.L2Operator
open scoped MatrixOrder
-- This file reuses the source-facing Assumption 5.4.2 owner from
-- `SunYuanOptimizationTheoryMethods.Chap05.Assumption_5_4_2`.
-- Semantic recall: `lean_leansearch` exposed `Matrix.PosDef.posDef_sqrt` and
-- `Matrix.PosSemidef.inv_sqrt`, so the source-faithful Hessian `±1 / 2` weights are expressed
-- through `CFC.sqrt`.
theorem exists_local_dfp_error_contraction_constants
(D : Set Point) (f : Point → ℝ)
(h : HasQuasiNewtonStrongLocalMinimizerAssumptions D f)
(h_oneThird : dfpOneThirdConditionInNeighborhood h) :
∃ ρ > 0, ∃ β1 > 0, ∃ β2 > 0, ∃ β3 > 0, ∀ (A : DFPHessianRun D f) (k : ℕ),
A.x k ∈ Metric.ball h.xStar ρ →
A.x (k + 1) ∈ Metric.ball h.xStar ρ →
dfpSqrtWeightedMatrixNorm (dfpReferenceHessian h) (A.B (k + 1) - dfpReferenceHessian h) ≤
(Real.sqrt
(1 -
β1 *
(dfpErrorAngle (dfpReferenceHessian h) (A.B k) (A.x (k + 1) - A.x k)) ^
(2 : ℕ)) +
β2 * dfpSigma (A.x k) (A.x (k + 1)) h.xStar) *
dfpSqrtWeightedMatrixNorm (dfpReferenceHessian h) (A.B k - dfpReferenceHessian h) +
β3 * dfpSigma (A.x k) (A.x (k + 1)) h.xStar
Theorem 5.4.20
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.20: under the assumptions of Chapter05 Theorem 5.4.15, there exist ε > 0 and δ > 0 such that every Hessian-side DFP run generated by (5.4.79)-(5.4.80) from initial data x0, B0 satisfying ‖x0 - h.xStar‖ < ε and dfpMatrixNorm (dfpReferenceHessian h) (B0 - dfpReferenceHessian h) < δ converges to h.xStar superlinearly. The small-start DFP data are recorded by the Chapter 5 owner DFPSmallStartConvergence, and this theorem packages the superlinear refinement into the reusable owner DFPSmallStartSuperlinearConvergence, whose rate conclusion is expressed by the canonical Chapter 3 owner HasSuperlinearConvergenceTo.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * primary domain: DFP local convergence rates for Hessian-side quasi-Newton runs;
-- * sampled owners: `DFPHessianRun`, `DFPSmallStartConvergence`,
-- `dfpReferenceHessian`, `dfpMatrixNorm`, and `dfpOneThirdConditionInNeighborhood` from the
-- Chapter 5 DFP files, together with the canonical Chapter 3 rate owner
-- `HasSuperlinearConvergenceTo`;
-- * source/core/bridge triage: the source-facing owner introduced here is the superlinear
-- refinement `DFPSmallStartSuperlinearConvergence`, while the inherited small-start run data
-- are already canonically owned by `DFPSmallStartConvergence`;
-- * primitive data: the primitive run object remains `DFPHessianRun D f`, with prescribed
-- initial data imposed by `A.x0 = x0` and `A.B0 = B0`;
-- * derived API: linear convergence is inherited from `DFPSmallStartConvergence`, and
-- superlinear convergence is expressed by the canonical owner
-- `HasSuperlinearConvergenceTo A xStar`.
theorem dfpMethod_tendsto_and_superlinear_of_small_initial_errors
(D : Set Point) (f : Point → ℝ)
(h : HasQuasiNewtonStrongLocalMinimizerAssumptions D f)
(h_oneThird : dfpOneThirdConditionInNeighborhood h) :
∃ ε > 0, ∃ δ > 0, ∀ x0 B0,
‖x0 - h.xStar‖ < ε →
dfpMatrixNorm (dfpReferenceHessian h) (B0 - dfpReferenceHessian h) < δ →
DFPSmallStartSuperlinearConvergence D f h.xStar x0 B0
Theorem 5.4.21
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.21: under the assumptions of Chapter05 Theorem 5.4.15, there exist ε > 0 and δ > 0 such that every Hessian-side BFGS run generated by (5.4.79) and the BFGS update (5.1.45) from initial data x0, B0 satisfying ‖x0 - h.xStar‖ < ε and dfpMatrixNorm (dfpReferenceHessian h) (B0 - dfpReferenceHessian h) < δ converges to h.xStar superlinearly. This file does not keep a second theorem-local small-start owner: it reuses DFPSmallStartSuperlinearConvergence from the neighboring DFP theorem and translates that source-facing package to the canonical Chapter 5 owner GeneralQuasiNewtonMethod with the bridge GeneralQuasiNewtonMethod.IsFullStepHessianBFGSOn. The rate conclusion is expressed by the canonical Chapter 3 owner HasSuperlinearConvergenceTo.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * primary domain: local superlinear convergence for Hessian-side full-step BFGS runs;
-- * sampled owners in the minimal semantic closure:
-- `GeneralQuasiNewtonMethod.IsFullStepHessianBFGSOn` from
-- `Chapter05.HessianBFGSMethod`,
-- `DFPHessianRun` and `DFPSmallStartSuperlinearConvergence` from
-- `Chapter05.Theorem_5_4_20`,
-- and the canonical Chapter 3 rate owner `HasSuperlinearConvergenceTo`;
-- * source/core/bridge triage:
-- source-facing layer in this file: the theorem statement itself;
-- core/canonical owner: `GeneralQuasiNewtonMethod`;
-- bridge/view reused here: the already existing small-start DFP owner
-- `DFPSmallStartSuperlinearConvergence` together with the BFGS bridge
-- `GeneralQuasiNewtonMethod.IsFullStepHessianBFGSOn`;
-- * primitive data remain an existing Hessian-side run object, viewed either as
-- `DFPHessianRun D f` or as `GeneralQuasiNewtonMethod f` with the full-step Hessian-BFGS
-- bridge;
-- * derived API: the superlinear rate is the canonical Chapter 3 owner
-- `HasSuperlinearConvergenceTo`, so no additional theorem-local owner is introduced here.
theorem bfgsMethod_tendsto_and_superlinear_of_small_initial_errors
(D : Set Point) (f : Point → ℝ)
(h : HasQuasiNewtonStrongLocalMinimizerAssumptions D f)
(h_oneThird : dfpOneThirdConditionInNeighborhood h) :
∃ ε > 0, ∃ δ > 0, ∀ x0 B0,
‖x0 - h.xStar‖ < ε →
dfpMatrixNorm (dfpReferenceHessian h) (B0 - dfpReferenceHessian h) < δ →
(∃ A : GeneralQuasiNewtonMethod f,
A.x0 = x0 ∧
A.hessian 0 = B0 ∧
A.IsFullStepHessianBFGSOn D) ∧
∀ A : GeneralQuasiNewtonMethod f,
A.x0 = x0 →
A.hessian 0 = B0 →
A.IsFullStepHessianBFGSOn D →
HasSuperlinearConvergenceTo A h.xStar
Theorem 5.4.22
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.22: let f : ℝ^n → ℝ satisfy HasQuasiNewtonStrongLocalMinimizerAssumptions D f; assume the neighborhood one-third condition bfgsOneThirdConditionInNeighborhood h, i.e. (5.4.133) with μ = ‖∇²f(h.xStar)⁻¹‖, σ(x, xNext) = max {‖x - h.xStar‖, ‖xNext - h.xStar‖}. Then there exist ε > 0 and δ > 0 such that every initial pair (x0, H0) with ‖x0 - h.xStar‖ < ε and bfgsMatrixNorm (quasiNewtonHessianMatrix f h.xStar) (H0 - bfgsReferenceInverse h) < δ admits a well-defined full-step BFGS run on D, every such run converges linearly to h.xStar, and summable error norms imply the little-o superlinear refinement. The run owner is the canonical GeneralQuasiNewtonMethod, and the theorem-specific BFGS hypotheses are recorded by GeneralQuasiNewtonMethod.IsFullStepBFGSOn.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * `GeneralQuasiNewtonMethod` is the Chapter 5 owner for quasi-Newton trajectory data.
-- * `IsBFGSMethod` from `BFGSMethod` is the Chapter 5 bridge for the inverse-BFGS update.
-- * the additional source-facing data in this theorem are that the iterates stay in `D`, the
-- inverse-Hessian matrices remain positive definite, and every generated step is the full
-- inverse-BFGS step `xₖ₊₁ = xₖ - Hₖ gₖ`.
--
-- In this file, `GeneralQuasiNewtonMethod.IsFullStepBFGSOn` is the theorem-specific bridge/view
-- layer. The run owner itself remains the canonical `GeneralQuasiNewtonMethod`.
theorem inverseBfgsMethod_converges_of_small_initial_errors
(D : Set Point) (f : Point → ℝ)
(h : HasQuasiNewtonStrongLocalMinimizerAssumptions D f)
(h_oneThird : bfgsOneThirdConditionInNeighborhood h) :
∃ ε > 0, ∃ δ > 0, ∀ x0 H0,
‖x0 - h.xStar‖ < ε →
bfgsMatrixNorm (quasiNewtonHessianMatrix f h.xStar) (H0 - bfgsReferenceInverse h) < δ →
(∃ A : GeneralQuasiNewtonMethod f,
A.x0 = x0 ∧ A.matrix0 = H0 ∧ A.IsFullStepBFGSOn D) ∧
(∀ A : GeneralQuasiNewtonMethod f,
A.x0 = x0 →
A.matrix0 = H0 →
A.IsFullStepBFGSOn D →
LinearlyConvergesTo A h.xStar) ∧
∀ A : GeneralQuasiNewtonMethod f,
A.x0 = x0 →
A.matrix0 = H0 →
A.IsFullStepBFGSOn D →
Summable (fun k ↦ ‖A k - h.xStar‖) →
((fun k ↦ ‖A (k + 1) - h.xStar‖) =o[atTop] fun k ↦ ‖A k - h.xStar‖)
Theorem 5.4.23
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.23: under the bundled hypotheses unpacked by HasRestrictedBroydenLocalSuperlinearAssumptions.spec and RestrictedBroydenMethod.spec, D is convex, f : ℝ^n → ℝ is C² on D, h.xStar belongs to D and is the intended local minimizer/solution, h.hessian differentiates gradient f on D, the Hessian field satisfies the uniform lower bound h.m * ‖u‖² ≤ uᵀ ∇²f(x) u on D, the Hessian is Lipschitz on a neighborhood of h.xStar, and A is a restricted-Broyden run with a fixed θ ∈ (0, 1) and Wolfe-Powell parameters ρ, σ satisfying WolfePowellParameters ρ σ, whose initial iterate lies in the local ball Metric.ball h.xStar h.ε. Then a positive-definite initial matrix A.B0 implies that the generated sequence converges to h.xStar Q-superlinearly.
open Filter
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: `lean_leansearch` surfaced the asymptotic `=o` API. Nearby Chapter 5 files
-- already use the canonical matrix action `Matrix.toEuclideanLin`, so this item keeps the
-- source-faithful restricted-Broyden data on that same surface.
theorem restrictedBroyden_tendsto_and_qSuperlinear_of_uniformConvex_and_wolfePowell
(f : Point → ℝ) (D : Set Point)
(h : HasRestrictedBroydenLocalSuperlinearAssumptions D f)
(A : RestrictedBroydenMethod D f)
(hA0_local : A 0 ∈ Metric.ball h.xStar h.ε)
(hB0_posDef : A.B0.PosDef) :
RestrictedBroydenRun.ConvergesQSuperlinearlyTo h.xStar A.toRestrictedBroydenRun
Theorem 5.4.24
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.24: suppose the assumptions of Chapter05 Theorem 5.4.23 hold for the restricted-Broyden run A; assume in addition that each step size A.α k is chosen by exact line search on the ray Set.Ici 0, expressed by the canonical Chapter 5 exact-line-search owner A.toGeneralQuasiNewtonMethod.HasExactLineSearchOnNonnegativeRay on the inverse-form bridge from RestrictedBroydenRun. Then the generated sequence converges to h.xStar Q-superlinearly, expressed by the reusable convergence owner RestrictedBroydenRun.ConvergesQSuperlinearlyTo.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem restrictedBroyden_tendsto_and_superlinear_of_uniformConvex_and_exactLineSearch
(f : Point → ℝ) (D : Set Point)
(h : HasRestrictedBroydenLocalSuperlinearAssumptions D f)
(A : RestrictedBroydenRun D f)
(hA0_local : A 0 ∈ Metric.ball h.xStar h.ε)
(hB0_posDef : A.B0.PosDef)
(hExactLineSearch : A.toGeneralQuasiNewtonMethod.HasExactLineSearchOnNonnegativeRay) :
RestrictedBroydenRun.ConvergesQSuperlinearlyTo h.xStar A
Theorem 5.4.25
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.4.25: let x, B, BInv, g, and α be sequences on ℝ^n such that BInv k is a chosen inverse for B k, x (k + 1) = x k - α k • BInv k g_k, and g k is the gradient of f at x k. Assume the iterates converge to xStar, assume gradient f xStar = 0, and assume the Hessian of f at xStar is the canonical matrix quasiNewtonHessianMatrix f xStar, with the corresponding derivative and positive-definiteness hypotheses. Assume moreover that the denominators in the source ratios (5.4.134), (5.4.135), and (5.4.136) are eventually nonzero. Then the superlinear error ratio in (5.4.134) tends to 0 if and only if the source angle condition (5.4.135) and the source curvature ratio condition (5.4.136) both tend to 1.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling pass:
-- * source-facing layer here: the ratio conditions from `(5.4.135)`-`(5.4.136)`.
-- * core/canonical owners already upstream: `qErrorRatio x xStar 1` for `(5.4.134)` from
-- `Chapter01.Definition_1_5_extra_1`, `quasiNewtonHessianMatrix` for the Hessian owner from
-- `Assumption_5_4_2`, and the angle owner `InnerProductGeometry.angle` with
-- `InnerProductGeometry.cos_angle` for the squared-cosine term in `(5.4.135)`.
-- * matrix action is the mathlib owner `Matrix.toEuclideanLin`, so this file keeps only the
-- genuinely new source-facing curvature ratio from `(5.4.136)`.
theorem quasiNewton_superlinearErrorRatio_tendsto_zero_iff
(f : Point → ℝ)
(x : ℕ → Point)
(B BInv : ℕ → MatrixN)
(g : ℕ → Point)
(α : ℕ → ℝ)
(xStar : Point)
(h_gradient : ∀ k : ℕ, HasGradientAt f (g k) (x k))
(h_inverse : ∀ k : ℕ, BInv k * B k = 1 ∧ B k * BInv k = 1)
(h_update :
∀ k : ℕ,
x (k + 1) = x k - α k • Matrix.toEuclideanLin (BInv k) (g k))
(hx_tendsto : Tendsto x atTop (nhds xStar))
(h_stationary : gradient f xStar = 0)
(h_hessian :
HasFDerivAt (gradient f)
((Matrix.toEuclideanCLM : MatrixN ≃⋆ₐ[ℝ] Point →L[ℝ] Point)
(quasiNewtonHessianMatrix f xStar))
xStar)
(h_posDef : (quasiNewtonHessianMatrix f xStar).PosDef)
(h_errorRatio_denominator_ne :
∀ᶠ k in atTop, ‖x k - xStar‖ ≠ 0)
(h_searchDirection_ne :
∀ᶠ k in atTop, Matrix.toEuclideanLin (BInv k) (g k) ≠ 0)
(h_hessianDirection_ne :
∀ᶠ k in atTop,
Matrix.toEuclideanLin ((quasiNewtonHessianMatrix f xStar)⁻¹) (g k) ≠ 0)
(h_curvatureRatio_denominator_ne :
∀ᶠ k in atTop,
α k * dotProduct (x (k + 1) - x k) (g (k + 1) - g k) ≠ 0) :
Tendsto (qErrorRatio x xStar 1) atTop (nhds (0 : ℝ)) ↔
Tendsto
(fun k : ℕ ↦
(Real.cos
(InnerProductGeometry.angle
(Matrix.toEuclideanLin (BInv k) (g k))
(-Matrix.toEuclideanLin ((quasiNewtonHessianMatrix f xStar)⁻¹) (g k)))) ^
(2 : ℕ))
atTop
(nhds (1 : ℝ)) ∧
Tendsto (quasiNewtonCurvatureRatio x B g α) atTop (nhds (1 : ℝ))
Definition 5.4.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
A sequence u has a subsequence converging to a when there is a strictly monotone extraction φ such that u ∘ φ → a.
open Filter
variable {α : Type*} [TopologicalSpace α]
def HasSubsequenceTendstoTo (u : ℕ → α) (a : α) : Prop :=
∃ φ : ℕ → ℕ, StrictMono φ ∧ Tendsto (u ∘ φ) atTop (nhds a)5.5 — Self-Scaling Variable Metric (SSVM) Methods
Theorem 5.5.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.5.1 (1): if xStar is a minimizer of the positive-definite quadratic objective quadraticObjective G b c, Hk is positive definite, gk is the gradient at xk, xk1 = xk - αk • Matrix.toEuclideanLin Hk gk is the exact-line-search Newton-like step on the nonnegative ray in direction quadraticNewtonLikeDirection Hk gk, and λ₁, λₙ are respectively the largest and smallest eigenvalues of Hk * G, then the single-step objective gap contracts by kantorovichContractionFactor lambda1 lambdaN.
open Matrix
open scoped MatrixOrder
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem quadraticNewtonLikeSuboptimality_le_kantorovichContractionFactor
{G Hk : MatrixN} {b xStar xk xk1 gk : Point} {c αk lambda1 lambdaN : ℝ}
(hMin : IsMinOn (quadraticObjective G b c) Set.univ xStar)
(hGpos : G.PosDef)
(hHkpos : Hk.PosDef)
(hGrad : HasGradientAt (quadraticObjective G b c) gk xk)
(hStep : xk1 = quadraticNewtonLikePoint Hk xk gk αk)
(hExactLineSearch :
IsQuadraticNewtonLikeExactLineSearchStep (quadraticObjective G b c) Hk xk gk αk)
(hlambda1 : lambda1 ∈ spectrum ℝ (Hk * G))
(hlambdaN : lambdaN ∈ spectrum ℝ (Hk * G))
(hSpectrum : spectrum ℝ (Hk * G) ⊆ Set.Icc lambdaN lambda1)
(hlambdaN_pos : 0 < lambdaN) :
quadraticSuboptimality G b c xStar xk1 ≤
kantorovichContractionFactor lambda1 lambdaN *
quadraticSuboptimality G b c xStar xk
Theorem 5.5.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.5.2: if a Hermitian representative R_k has all eigenvalues in Set.Icc lambdaMin lambdaMax and the specialized self-scaling update ssvmInverseUpdate R_k r r φ 1 is explicitly similar to the updated product matrix, then the complex spectrum of (broydenClassInverseUpdate Hk s y φ) * G lies in Complex.ofReal '' Set.Icc lambdaMin lambdaMax.
open Matrix
open scoped ComplexOrder MatrixOrder
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
variable {Hk G R : MatrixN} {Q : MatrixNˣ} (s y r : Point) {φ lambdaMin lambdaMax : ℝ}
theorem broydenClassInverseUpdate_mul_spectrum_subset_Icc
(hR : R.IsHermitian)
(hrr : dotProduct r r ≠ 0) (hrRr : dotProduct r (R.mulVec r) ≠ 0)
(hSimilarity :
ssvmInverseUpdate R r r φ 1 =
Q * (broydenClassInverseUpdate Hk s y φ * G) * Q⁻¹)
(hLambdaMin_pos : 0 < lambdaMin) (hOne : 1 ∈ Set.Icc lambdaMin lambdaMax)
(hBounds : ∀ i : Fin n, hR.eigenvalues i ∈ Set.Icc lambdaMin lambdaMax)
(hφ : φ ∈ Set.Icc (0 : ℝ) 1) :
spectrum ℂ
(((broydenClassInverseUpdate Hk s y φ) * G).map (algebraMap ℝ ℂ)) ⊆
(Complex.ofReal '' Set.Icc lambdaMin lambdaMax : Set ℂ)
Algorithm 5.5.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Algorithm 5.5.3: a self-scaling variable-metric method on ℝ^n extends a general quasi-Newton run by a fixed Broyden-class parameter φ ≥ 0 and positive self-scaling parameters γ k on every nonterminal stage. At each such stage, the source step data is the canonical quasi-Newton step α k • d k and gradient difference g (k + 1) - g k, the two denominator-nonzero side conditions needed for the SSVM inverse update hold, and the Euclidean matrix representative of the inverse approximation satisfies the textbook self-scaling inverse update formula. The inherited quasi-Newton owner retains the stopping condition A.terminatedAt k :↔ ‖A.g k‖ ≤ A.ε, the positive step-size output 0 < A.α k, the iterate update, and the inverse-form secant equation.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
structure SelfScalingVariableMetricMethod
(f : Point → ℝ) extends GeneralQuasiNewtonMethod f where
phi : ℝ
gamma : ℕ → ℝ
phi_nonneg : 0 ≤ phi
gamma_pos (k : ℕ) (hNotStopped : ε < ‖g k‖) : 0 < gamma k
secant_denom_ne_zero (k : ℕ) (hNotStopped : ε < ‖g k‖) :
dotProduct (α k • d k) (g (k + 1) - g k) ≠ 0
curvature_denom_ne_zero (k : ℕ) (hNotStopped : ε < ‖g k‖) :
dotProduct (g (k + 1) - g k)
((Matrix.toEuclideanLin.symm (H k)).mulVec (g (k + 1) - g k)) ≠ 0
update_eq (k : ℕ) (hNotStopped : ε < ‖g k‖) :
Matrix.toEuclideanLin.symm (H (k + 1)) =
ssvmInverseUpdate
(Matrix.toEuclideanLin.symm (H k)) (α k • d k) (g (k + 1) - g k) phi (gamma k)
Theorem 5.5.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.5.4 (1): if H is positive definite, dotProduct s y > 0, φ ≥ 0, and γ > 0, then the SSVM update ssvmInverseUpdate H s y φ γ is positive definite.
open scoped BigOperators
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem ssvmInverseUpdate_posDef
(H : MatrixN) (hH : H.PosDef) (s y : Point) (φ γ : ℝ)
(hφ : 0 ≤ φ) (hγ : 0 < γ) (hsy : 0 < dotProduct s y) :
(ssvmInverseUpdate H s y φ γ).PosDef
Theorem 5.5.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.5.5 (1): if φ ∈ Set.Icc (0 : ℝ) 1, 0 < γ, the SSVM denominators dotProduct r r and dotProduct r (R.mulVec r) are valid with 0 < dotProduct r (R.mulVec r), and the smallest eigenvalue of γ • R is at least 1, then the smallest eigenvalue of the self-scaling SSVM representative update is 1, and each remaining updated eigenvalue lies between consecutive eigenvalues of γ • R.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem ssvmInverseUpdate_self_eigenvalues_case_ge_one
{R : MatrixN} (hR : R.IsHermitian) (r : Point)
(hrr : dotProduct r r ≠ 0) (hrRr : 0 < dotProduct r (R.mulVec r)) {φ γ : ℝ}
(hn : 0 < n) (hφ : φ ∈ Set.Icc (0 : ℝ) 1) (hγ : 0 < γ)
(hLast : 1 ≤ γ * hR.eigenvalues ⟨n - 1, Nat.sub_lt hn (Nat.succ_pos 0)⟩) :
let hRφ : (ssvmInverseUpdate R r r φ γ).IsHermitian :=
ssvmInverseUpdate_self_isHermitian hR r φ γ
hRφ.eigenvalues ⟨n - 1, Nat.sub_lt hn (Nat.succ_pos 0)⟩ = 1 ∧
∀ i : ℕ, ∀ hi : i + 1 < n,
1 ≤ γ * hR.eigenvalues ⟨i + 1, hi⟩ ∧
γ * hR.eigenvalues ⟨i + 1, hi⟩ ≤ hRφ.eigenvalues ⟨i, Nat.lt_of_succ_lt hi⟩ ∧
hRφ.eigenvalues ⟨i, Nat.lt_of_succ_lt hi⟩ ≤
γ * hR.eigenvalues ⟨i, Nat.lt_of_succ_lt hi⟩
Corollary 5.5.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Corollary 5.5.6: if φ ∈ Set.Icc (0 : ℝ) 1, then for the γ_k = 1 self-scaling SSVM representative update the corresponding ordered eigenvalue μ_i^φ lies in the unordered closed interval between 1 and the corresponding ordered eigenvalue λ_i of R. This is the source-facing interval form of Theorem 5.5.5 specialized to γ = 1.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem ssvmUpdatedEigenvalue_mem_uIcc_one
{R : MatrixN} (hR : R.IsHermitian) (r : Point)
(hrr : dotProduct r r ≠ 0) (hrRr : 0 < dotProduct r (R.mulVec r)) {φ : ℝ}
(hφ : φ ∈ Set.Icc (0 : ℝ) 1) (i : Fin n) :
(ssvmInverseUpdate_self_one_isHermitian hR r φ).eigenvalues i ∈
Set.uIcc 1 (hR.eigenvalues i)
Corollary 5.5.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Corollary 5.5.7: if φ ∈ Set.Icc (0 : ℝ) 1, 0 < γ, the SSVM step in (5.5.24) is nonzero in the sense dotProduct r r ≠ 0, and the reciprocal scaling 1 / γ lies between the smallest and largest ordered eigenvalues of R, then the spectral condition number does not increase: κ(R_(k + 1)^φ) ≤ κ(R_k).
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem ssvmUpdatedRepresentativeConditionNumber_le
{R : MatrixN} (hRpos : R.PosDef) (r : Point)
(hrr : dotProduct r r ≠ 0) {φ γ : ℝ}
(hn : 0 < n) (hφ : φ ∈ Set.Icc (0 : ℝ) 1) (hγ : 0 < γ)
(hLower : smallestOrderedRepresentativeEigenvalue hRpos hn ≤ 1 / γ)
(hUpper : 1 / γ ≤ largestOrderedRepresentativeEigenvalue hRpos hn) :
ssvmUpdatedRepresentativeConditionNumber r φ γ
(ssvmInverseUpdate_self_posDef hRpos r hrr hφ hγ) hn ≤
ssvmRepresentativeConditionNumber hRpos hn
Definition 5.5.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The correction vector (sᵀ y)⁻¹ • s - (yᵀ H y)⁻¹ • H y appearing in the inverse self-scaling variable-metric update.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
def ssvmCorrectionVector (H : MatrixN) (s y : Point) : Point :=
(dotProduct s y)⁻¹ • s - (dotProduct y (H.mulVec y))⁻¹ • Matrix.toEuclideanLin H y
5.6 — Sparse Quasi-Newton Methods
Theorem 5.6.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.6.1: the sparse quasi-Newton matrix Q from (5.6.27) is positive definite under the exact owner-level nondegeneracy condition det Q ≠ 0.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem sparseQuasiNewtonQ_posDef
(J : Set (Fin n × Fin n)) (s : Point)
(h_det : (sparseQuasiNewtonQ J s).det ≠ 0) :
(sparseQuasiNewtonQ J s).PosDef5.7 — Limited Memory BFGS Method
Algorithm 5.7.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Algorithm 5.7.1: the L-BFGS two-loop recursion for Hₖ gₖ. The input history is the memory of stored correction pairs (sᵢ, yᵢ) ordered from (s_{k-m}, y_{k-m}) to (s_{k-1}, y_{k-1}), so its length is the memory parameter m. For each stored pair, Algorithm 5.7.1 uses the derived reciprocal curvature scalar ρᵢ := ⟪sᵢ, yᵢ⟫_ℝ⁻¹. Step 1 sets q := gₖ. Step 2 runs the reverse loop αᵢ := ρᵢ * ⟪sᵢ, q⟫_ℝ, q := q - αᵢ • yᵢ. Step 3 sets r := Hₖ⁽⁰⁾ q. Step 4 runs the forward loop β := ρᵢ * ⟪yᵢ, r⟫_ℝ, r := r + (αᵢ - β) • sᵢ. On the Euclidean matrix model, the textbook matrix Hₖ⁽⁰⁾ is recovered by passing through Matrix.toEuclideanLin.
open scoped InnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
def lbfgsTwoLoopRecursion
(Hk0 : E →ₗ[ℝ] E) (gk : E) (history : List (LBFGSHistoryEntry E)) : E :=
let backward := lbfgsBackwardLoop gk history
lbfgsForwardLoop (Hk0 backward.1) history backward.2Algorithm 5.7.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Algorithm 5.7.2: an L-BFGS method on ℝ^n consists of a starting point x₀, an initial symmetric positive-definite matrix H₀, a memory parameter m, a positive tolerance ε, iterate/gradient/direction/step-size/secant data, Wolfe-Powell line-search parameters, and the source-faithful step relations. At every nonterminal stage with ε < ‖g k‖, the search direction is computed by the two-loop recursion from Algorithm_5_7_1 using the last min k m stored pairs, the step size satisfies the Wolfe rule, the iterate update is x (k + 1) = x k + α k • d k, the new secant data are s k = x (k + 1) - x k and y k = g (k + 1) - g k, and the secant pair satisfies the canonical Chapter 5 curvature condition. The positivity of dotProduct (s k) (y k) and the nonvanishing of ‖y k‖ ^ 2, needed to read the scaled identity Hₖ⁽⁰⁾ = ((dotProduct (s k) (y k)) / ‖y k‖ ^ 2) • 1, are derived API. The intrinsic owner from Algorithm_5_7_1 is operator-valued, and this Euclidean matrix model is fed into it through Matrix.toEuclideanLin. After the stopping test ‖g k‖ ≤ ε is reached, the source-facing run stays at the same iterate; equality of the next recorded gradient is derived from the uniqueness of gradients.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * primary domain: Euclidean L-BFGS method data on Chapter 5's real Hilbert-space model;
-- * sampled owners in this domain:
-- `lbfgsTwoLoopRecursion`,
-- `LBFGSHistoryEntry`,
-- `satisfiesCurvatureCondition`,
-- `HasGradientAt`;
-- * source-facing owner kept here: `LBFGSMethod`;
-- * core/canonical owners reused here: the Algorithm 5.7.1 two-loop-recursion surface, the
-- Chapter 5 curvature owner, and the Chapter 2 Wolfe-Powell parameter owner;
-- * primitive data here: iterate / gradient / direction / line-search / secant sequences, the
-- initial Euclidean matrix, the memory bound, and the L-BFGS-specific step laws;
-- * derived API here: secant-curvature positivity, symmetry of the initial matrix, gradient
-- equality, post-termination gradient stabilization, and the nonzero scaling denominator.
structure LBFGSMethod (n : ℕ) (f : EuclideanSpace ℝ (Fin n) → ℝ) where
ε : ℝ
x0 : EuclideanSpace ℝ (Fin n)
H0 : Matrix (Fin n) (Fin n) ℝ
m : ℕ
x : ℕ → EuclideanSpace ℝ (Fin n)
g : ℕ → EuclideanSpace ℝ (Fin n)
d : ℕ → EuclideanSpace ℝ (Fin n)
α : ℕ → ℝ
s : ℕ → EuclideanSpace ℝ (Fin n)
y : ℕ → EuclideanSpace ℝ (Fin n)
rho : ℝ
sigma : ℝ
wolfeParameters : WolfePowellParameters rho sigma
epsilon_pos : 0 < ε
x_zero : x 0 = x0
H0_posDef : H0.PosDef
hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k)
direction_eq :
∀ k : ℕ, ε < ‖g k‖ →
d k =
-lbfgsTwoLoopRecursion
(lbfgsInitialMatrix H0 s y k).toEuclideanLin
(g k)
(lbfgsHistoryWindow s y m k)
stepSize_pos :
∀ k : ℕ, ε < ‖g k‖ → 0 < α k
update :
∀ k : ℕ, ε < ‖g k‖ → x (k + 1) = x k + α k • d k
armijo :
∀ k : ℕ, ε < ‖g k‖ →
f (x k + α k • d k) ≤ f (x k) + rho * α k * inner ℝ (g k) (d k)
curvature :
∀ k : ℕ, ε < ‖g k‖ →
sigma * inner ℝ (g k) (d k) ≤ inner ℝ (g (k + 1)) (d k)
stationaryContinuation :
∀ k : ℕ, ‖g k‖ ≤ ε → x (k + 1) = x k
step_eq :
∀ k : ℕ, ε < ‖g k‖ → s k = x (k + 1) - x k
gradientDifference_eq :
∀ k : ℕ, ε < ‖g k‖ → y k = g (k + 1) - g k
curvatureCondition :
∀ k : ℕ, ε < ‖g k‖ → satisfiesCurvatureCondition (s k) (y k)Lemma 5.7.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.7.3 (1): under Chapter05 Assumption 5.3.1 and lower and upper Hessian bounds with constants m > 0 and M on quasiNewtonLevelSet f x0, every nonzero secant pair yk = gradient f (xk + sk) - gradient f xk with xk, xk + sk ∈ quasiNewtonLevelSet f x0 satisfies ‖yk‖ / ‖sk‖ ≤ M. This is an exact recall of the canonical Chapter 5 estimate secantNorm_div_stepNorm_le_M_of_lowerLevelHessianBounds.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * source-facing layer: Lemma 5.7.3 secant estimates on `quasiNewtonLevelSet f x0` under
-- Chapter05 Assumption 5.3.1;
-- * core/canonical project owners: `lowerLevelSetOn`, `HasLowerLevelHessianLowerBound`,
-- `HasLowerLevelHessianUpperBound`;
-- * derived API used here: the secant norm and curvature estimates from `Lemma_5_3_2`.
-- Primitive data for this file is the Chapter 5 assumption package together with the explicit
-- lower and upper Hessian constants extracted from it; the three labeled estimates here stay
-- downstream of that source-facing owner layer rather than introducing a separate Hessian-matrix
-- bridge.
#check secantNorm_div_stepNorm_le_M_of_lowerLevelHessianBounds
Theorem 5.7.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.7.4 (1): let f : ℝ^n → ℝ be uniformly, equivalently strongly, convex on ℝ^n with modulus m > 0. If A is the sequence generated by Chapter05 Algorithm 5.7.2 and the Chapter 5 quasi-Newton global-convergence assumptions hold on a convex set D containing the level set quasiNewtonLevelSet f A.x0, then the L-BFGS iterates converge to a global minimizer of f. The regularity needed on D is owned by HasQuasiNewtonGlobalConvergenceAssumptions D f A.x0.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * primary domain: Chapter 5 L-BFGS convergence under the global quasi-Newton assumption
-- owner and strong convexity on `ℝ^n`;
-- * sampled owner declarations in the minimal closure:
-- `LBFGSMethod`,
-- `HasQuasiNewtonGlobalConvergenceAssumptions`,
-- `StrongConvexOn.strictConvexOn`,
-- `StrictConvexOn.eq_of_isMinOn`;
-- * layer triage:
-- source-facing item: `lbfgs_tendsto_globalMinimizer_of_strongConvex`;
-- core/canonical owners: `LBFGSMethod`, `HasQuasiNewtonGlobalConvergenceAssumptions`, and the
-- mathlib strong/strict-convexity owners;
-- bridge/view layer: the uniqueness clause is only the canonical bridge
-- `StrongConvexOn.strictConvexOn` into `StrictConvexOn.eq_of_isMinOn`, so it should remain
-- recall-only instead of being reintroduced as a local theorem.
-- * primitive data for the main source-facing theorem: the L-BFGS run owner, the global
-- convergence-assumption owner on `D`, and the global strong-convexity hypothesis; the
-- `C²` regularity needed on the relevant domain is already derived from
-- `hAssumption.contDiffOn`, so it should not be duplicated as a separate public binder.
theorem lbfgs_tendsto_globalMinimizer_of_strongConvex
(f : Point → ℝ) (A : LBFGSMethod n f) (D : Set Point) (m : ℝ)
(hm : 0 < m)
(hStrong : StrongConvexOn Set.univ m f)
(hAssumption : HasQuasiNewtonGlobalConvergenceAssumptions D f A.x0) :
∃ xStar : Point,
Tendsto A atTop (nhds xStar) ∧
IsMinOn f Set.univ xStar
Lemma 5.7.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.7.5, stated on a real inner product space: if f : E → ℝ is strongly convex on E with modulus m > 0, differentiable at x, and xStar is a global minimizer of f, then f x - f xStar ≤ (1 / m) * ‖∇ f x‖ ^ (2 : ℕ) for every x. This is the coordinate-free form of the source's ℝ^n statement.
open scoped Gradient
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling for this refine pass:
-- * core/canonical owner `StrongConvexOn`
-- * canonical bridge `strongConvexOn_iff_convex`
-- * canonical first-order gradient interfaces `DifferentiableAt.hasGradientAt`
-- and `inner_gradient_left`
-- * project companion `Lemma_5_3_4.gradientNormSqLowerBound`
-- This theorem is source-facing. Its primitive data are the strong-convexity owner, the
-- minimizer, and the first-order differentiability needed to speak about `∇ f x`; higher-order
-- smoothness is derived/proof-route data and does not belong in the public statement.
theorem sub_globalMin_le_inv_mul_norm_gradient_sq_of_strongConvex
(f : E → ℝ) (m : ℝ) (x xStar : E)
(hm : 0 < m)
(hStrong : StrongConvexOn Set.univ m f)
(hx : DifferentiableAt ℝ f x)
(hMin : IsMinOn f Set.univ xStar) :
f x - f xStar ≤ (1 / m) * ‖∇ f x‖ ^ (2 : ℕ)
Lemma 5.7.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Lemma 5.7.6 (1), stated on a real inner product space: let f : E → ℝ be twice continuously differentiable and uniformly, equivalently strongly, convex with modulus m > 0, assume the global upper Hessian bound (iteratedFDeriv ℝ 2 f y) ![u, u] ≤ M * ‖u‖ ^ (2 : ℕ) for every y and u, and let xkp1 = xk + αk • dk be a Wolfe-Powell step for the ray profile lineSearchObjective f xk dk with parameters ρ, σ. Writing cos θk = Real.cos (angle dk (-∇ f xk)), the step displacement xkp1 - xk satisfies `((1 - σ) / M) * ‖∇ f xk‖ * cos θk ≤ ‖xkp1 - xk‖ ≤ (2 * (1 - ρ) / m) * ‖∇ f xk‖ * cos θk`.
open scoped Gradient
open InnerProductGeometry
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (f : E → ℝ) (m M : ℝ) (xk xkp1 dk : E) (αk ρ σ : ℝ)
variable (hC2 : ContDiff ℝ 2 f)
variable (hm : 0 < m)
variable (hM : 0 < M)
variable (hStrong : StrongConvexOn Set.univ m f)
variable
(hUpperHessian :
∀ y u : E,
(iteratedFDeriv ℝ 2 f y) ![u, u] ≤ M * ‖u‖ ^ (2 : ℕ))
variable (hStep : xkp1 = xk + αk • dk)
variable (hDescent : IsDescentDirectionAt f xk dk)
-- Domain sampling for this refine pass:
-- * primary domain: Wolfe-Powell line search on strongly convex objectives
-- * sampled canonical owners:
-- `lineSearchObjective`,
-- `HasGradientAt.deriv_lineSearchObjective_apply`,
-- `StrongConvexOn`,
-- `WolfePowellCondition`,
-- `InnerProductGeometry.angle`
-- * bridge/view reused from Chapter 2:
-- `deriv (lineSearchObjective f xk dk)`,
-- `cos_angle_searchDirection_negGradient`
-- * best owner abstraction: the intrinsic real inner-product-space layer, since no coordinate
-- data is used in the statements
-- Primitive data here is the strong-convexity owner, the global Hessian quadratic-form upper
-- bound, the accepted Wolfe-Powell step, and the descent-direction owner.
-- The cosine term is derived from the canonical angle owner rather than from a Euclidean
-- coordinate model.
-- The source-facing theorems should therefore use the Chapter 2 search-profile owner
-- `lineSearchObjective f xk dk`, its canonical derivative bridge
-- `deriv (lineSearchObjective f xk dk)`, the chapter owner `WolfePowellCondition` for the
-- accepted step, and the canonical cosine surface `Real.cos (angle dk
-- (-∇ f xk))`, rather than duplicating those one-dimensional surfaces as local raw lambdas.
local notation "φ" => lineSearchObjective f xk dk
local notation "cosθk" => Real.cos (angle dk (-∇ f xk))
theorem stepNormBounds_of_wolfePowell_of_strongConvex
(hC2 : ContDiff ℝ 2 f)
(hm : 0 < m)
(hM : 0 < M)
(hStrong : StrongConvexOn Set.univ m f)
(hUpperHessian :
∀ y u : E,
(iteratedFDeriv ℝ 2 f y) ![u, u] ≤ M * ‖u‖ ^ (2 : ℕ))
(hStep : xkp1 = xk + αk • dk)
(hDescent : IsDescentDirectionAt f xk dk)
(hWolfe : WolfePowellCondition φ (deriv φ) ρ σ αk) :
((1 - σ) / M) * ‖∇ f xk‖ * cosθk ≤
‖xkp1 - xk‖ ∧
‖xkp1 - xk‖ ≤
(2 * (1 - ρ) / m) * ‖∇ f xk‖ * cosθk
Theorem 5.7.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter05 Theorem 5.7.7: let f : ℝ^n → ℝ be twice continuously differentiable, with uniform strong convexity modulus m > 0. Assume A is the sequence generated by Chapter05 Algorithm 5.7.2; A converges to the unique global minimizer xStar of f; xStar is characterized by IsMinOn f Set.univ xStar, and uniqueness is the canonical consequence of strong convexity already exposed in Chapter 5. Then the convergence rate is at least R-linear, expressed by the canonical Chapter 1 owner rLinearConvergenceTo A xStar.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * project owner `LBFGSMethod` from `Algorithm_5_7_2.lean`
-- * project owner `LBFGSMethod.terminatedAt` from `Algorithm_5_7_2.lean`
-- * project owner `rLinearConvergenceTo` from Chapter 1
-- * mathlib owner `StrongConvexOn`
-- The L-BFGS method data are canonical upstream; this file only owns the geometric
-- error-bound conclusion through the canonical Chapter 1 `R`-linear convergence owner.
theorem lbfgs_atLeastRLinear_of_tendsto_uniqueGlobalMinimizer_of_strongConvex
(f : Point → ℝ) (A : LBFGSMethod n f) (m : ℝ) (xStar : Point)
(hC2 : ContDiff ℝ 2 f)
(hm : 0 < m)
(hStrong : StrongConvexOn Set.univ m f)
(hMin : IsMinOn f Set.univ xStar)
(hTendsto : Tendsto A atTop (nhds xStar)) :
rLinearConvergenceTo A xStar
Remark 5.7.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Remark 5.7-extra-1 auxiliary result (1): setting Hₖ = 1 in the inverse-form BFGS update gives the memoryless BFGS matrix. This is the H = 1 specialization of the Chapter 5 owner bfgsInverseUpdate.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * project owner `lbfgsTwoLoopRecursion` from `Algorithm_5_7_1.lean`
-- * project owner `lbfgsTwoLoopRecursion_singleton` from `Algorithm_5_7_1.lean`
-- * project owner `bfgsInverseUpdate` from `Definition_5_1_extra_4.lean`
-- * project owner `bfgsInverseUpdate_mulVec` / `bfgsInverseUpdate_eq_expandedForm`
-- The source-facing memoryless matrix is therefore a bridge/view: the `H = 1`
-- specialization of the canonical inverse-BFGS owner, while the one-pair L-BFGS
-- statement should reuse the Algorithm 5.7.1 owner and its derived `rho` API rather than
-- restating that scalar as primitive data.
abbrev memorylessBfgsInverseUpdate (s y : Point) : MatrixN :=
bfgsInverseUpdate (1 : MatrixN) s y
Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
BFGSMethod.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Definition_5_2_extra_1/Direction.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Definition_5_2_extra_1/Parameters.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
HessianBFGSMethod.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
SR1Update.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_10/Convergence.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_10/Iteration.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_10/Update.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_13/Iteration.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_13/Transport.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_9/Convergence.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_9/Iteration.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_5_4_9/Update.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.