The Minimum Q-Order of BFGS with Exact Line Search Is One (Liu et al., 2026)

Source excerpts; proofs omitted.

Notation 1.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Notation 1.1 (1): the standard quadratic on ℝⁿ.

open scoped Distributions Matrix.Norms.L2Operator MatrixOrder variable (n : ℕ) variable (x : EuclideanSpace ℝ (Fin n)) (r : ℝ) variable (f : EuclideanSpace ℝ (Fin n) → ℝ) variable (A B : Matrix (Fin n) (Fin n) ℝ) #check (standardQuadratic : EuclideanSpace ℝ (Fin n) → ℝ)

Theorem 1.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Theorem 1.1 (1) (Main result). For every finite dimension n ≥ 2, every ε > 0, and every R > 0, there exist an explicit smooth globally strongly convex objective and an identity-initialized nonterminating exact-line-search BFGS run that is localized in Metric.ball 0 R, is Q-superlinear, and has Q-order exactly one.

open scoped EuclideanSpace Topology #check (BFGS.exists_orderOneExample : ∀ (n : ℕ), 2 ≤ n → ∀ (ε R : ℝ), 0 < ε → 0 < R → ∃ (F : EuclideanSpace ℝ (Fin n) → ℝ) (x₀ : EuclideanSpace ℝ (Fin n)) (x : ℕ → EuclideanSpace ℝ (Fin n)) (B : ℕ → Matrix (Fin n) (Fin n) ℝ) (α : ℕ → ℝ), BFGS.IsOrderOneExample ε R F x₀ x B α)

Algorithm 2.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Algorithm 2.1 (1): differentiability, the positive-definite Hessian approximation, the inverse-Hessian search direction, and an explicit exact-line-search choice.

variable {n : ℕ} (F : EuclideanSpace ℝ (Fin n) → ℝ) variable (x : EuclideanSpace ℝ (Fin n)) (B : Matrix (Fin n) (Fin n) ℝ) variable (s y : EuclideanSpace ℝ (Fin n)) (φ : ℝ) #check (BFGS.Step F x B)

Definition 2.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Definition 2.1 (1): Q-order at least p is the eventual uniform power estimate for a convergent, eventually nonstationary sequence in Euclidean space.

universe u open scoped Topology variable {ι : Type u} [Fintype ι] [DecidableEq ι] #check (QConvergence.hasOrderAtLeast_iff : ∀ (x : ℕ → EuclideanSpace ℝ ι) (xStar : EuclideanSpace ℝ ι) (p : ℝ), QConvergence.HasOrderAtLeast x xStar p ↔ Filter.Tendsto x Filter.atTop (𝓝 xStar) ∧ (∀ᶠ k in Filter.atTop, x k ≠ xStar) ∧ 1 ≤ p ∧ ∃ C > 0, ∀ᶠ k in Filter.atTop, QConvergence.error x xStar (k + 1) ≤ C * QConvergence.error x xStar k ^ p)

Proposition 2.2

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Proposition 2.2 (Universal lower bound): every convergent, eventually nonstationary sequence whose steps arise from exact nonnegative line searches near a critical point with positive-definite Hessian has Q-order at least one.

open scoped Topology #check (QConvergence.hasOrderAtLeast_one_of_exactLineSearch : ∀ {n : ℕ} (F : EuclideanSpace ℝ (Fin n) → ℝ) (xStar : EuclideanSpace ℝ (Fin n)) (x : ℕ → EuclideanSpace ℝ (Fin n)) (h_smooth : ContDiffAt ℝ 2 F xStar) (h_gradient : gradient F xStar = 0) (h_hessian : Matrix.PosDef ((Matrix.toEuclideanCLM : Matrix (Fin n) (Fin n) ℝ ≃⋆ₐ[ℝ] (EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))).symm (fderiv ℝ (gradient F) xStar))) (h_tendsto : Filter.Tendsto x Filter.atTop (𝓝 xStar)) (h_ne : ∀ᶠ k in Filter.atTop, x k ≠ xStar) (h_step : ∀ k, ∃ (d : EuclideanSpace ℝ (Fin n)) (α : ℝ), LineSearch.IsExact F (x k) d α ∧ x (k + 1) = x k + α • d), QConvergence.HasOrderAtLeast x xStar 1)

Lemma 2.3

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Lemma 2.3: a pairwise-distinct sequence in a two-dimensional Euclidean subspace satisfying the gradient membership, orthogonality, nonzero span, and positive initial-step relations is exactly an identity-initialized exact-line-search BFGS trajectory, and every Hessian approximation has block form B|V ⊕ 1 on V ⊕ Vᗮ.

#check (BFGS.existsTrajectory_of_planarRelations : ∀ {n : ℕ} (V : Submodule ℝ (EuclideanSpace ℝ (Fin n))) (F : EuclideanSpace ℝ (Fin n) → ℝ) (x : ℕ → EuclideanSpace ℝ (Fin n)) (m β₀ : ℝ) (h_dim : Module.finrank ℝ V = 2) (h_differentiable : Differentiable ℝ F) (h_m : 0 < m) (h_strongConvex : StrongConvexOn Set.univ m F) (h_distinct : Function.Injective x) (h_point_mem : ∀ k, x k ∈ V) (h_gradient_mem : ∀ k, gradient F (x k) ∈ V) (h_orthogonal : ∀ k, inner ℝ (gradient F (x (k + 1))) (x (k + 1) - x k) = 0) (h_gradient_span : ∀ k, gradient F (x (k + 2)) ∈ Submodule.span ℝ {gradient F (x (k + 1)) - gradient F (x k)}) (h_gradient_ne : ∀ k, gradient F (x (k + 2)) ≠ 0) (h_beta : 0 < β₀) (h_initial : x 1 - x 0 = (-β₀) • gradient F (x 0)), ∃ (B : ℕ → Matrix (Fin n) (Fin n) ℝ) (α : ℕ → ℝ), BFGS.IsTrajectory F (1 : Matrix (Fin n) (Fin n) ℝ) x B α ∧ ∀ k, Matrix.IsBlockIdentityOn (B k) V)

Lemma 2.3 Trajectory

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

universe u #check (BFGS.IsTrajectory : ∀ {ι : Type u} [Fintype ι] [DecidableEq ι], (EuclideanSpace ℝ ι → ℝ) → Matrix ι ι ℝ → (ℕ → EuclideanSpace ℝ ι) → (ℕ → Matrix ι ι ℝ) → (ℕ → ℝ) → Prop)

Derivation 3.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Derivation 3.1 (1): positive initial angular separation remains positive along a nonzero planar gradient recurrence.

open scoped BigOperators universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [Fact (Module.finrank ℝ E = 2)] #check (PlanarGradient.angularSeparation_pos_of_recurrence (E := E) : ∀ (o : Orientation ℝ E (Fin 2)) (g : ℕ → E) (δ : ℕ → ℝ) (hNonzero : ∀ k, g k ≠ 0) (hDistinct : ∀ k, 0 < k → g k ≠ g (k - 1)) (hPre : ∀ k, 0 < k → inner ℝ (g k - g (k - 1)) (g k) = inner ℝ (g k) (PlanarGradient.perturbation o (g (k - 1)) (δ (k - 1)))) (hScale : ∀ k, 0 < k → PlanarGradient.scale o (g (k - 1)) (g k) (δ k) ≠ 0) (hNext : ∀ k, 0 < k → g (k + 1) = PlanarGradient.next o (g (k - 1)) (g k) (δ k)) (hInitial : 0 < PlanarGradient.angularSeparation o (g 0) (g 1)), ∀ k, 0 < k → 0 < PlanarGradient.angularSeparation o (g (k - 1)) (g k))

Lemma 3.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Lemma 3.1 (1): the parallel coefficient under the pre-step relation.

universe u namespace PlanarGradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [Fact (Module.finrank ℝ E = 2)] #check (PlanarGradient.parallelCoefficient_eq_of_preStep : ∀ (o : Orientation ℝ E (Fin 2)) (gPrev g : E) (δPrev : ℝ), gPrev ≠ 0 → g ≠ 0 → g ≠ gPrev → inner ℝ (g - gPrev) g = inner ℝ g (perturbation o gPrev δPrev) → parallelCoefficient gPrev g = δPrev * ‖g‖ * o.areaForm (NormedSpace.normalize gPrev) (NormedSpace.normalize g) / ‖g - gPrev‖)

Notation 3.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Notation 3.1 (1): the standard quarter-turn J, radial normalization, oriented tangent, and tangential perturbation δ k • q k.

open scoped EuclideanSpace variable (g : ℕ → EuclideanSpace ℝ (Fin 2)) (δ : ℕ → ℝ) (k : ℕ) #check EuclideanPlane.quarterTurnMatrix

Notation 3.1 Tangentrecurrence

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

open scoped EuclideanSpace #check (PlanarGradient.next EuclideanPlane.orientation : EuclideanSpace ℝ (Fin 2) → EuclideanSpace ℝ (Fin 2) → ℝ → EuclideanSpace ℝ (Fin 2))

Derivation 3.2

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Derivation 3.2 (1): a nonzero affine expression can be made arbitrarily small by choosing its target value first and then solving for the perturbation.

universe u #check (PlanarGradient.exists_nearCancellation : ∀ (P D ε : ℝ) (hP : P ≠ 0) (hD : D ≠ 0) (hε : 0 < ε), ∃ τ δ : ℝ, 0 < |τ| ∧ |τ| < min ε (|P| / 2) ∧ δ = (τ - P) / D ∧ P + D * δ = τ)

Lemma 3.2

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Lemma 3.2 (Alternating scale construction). For every σ ∈ Set.Ioo 0 1, there are planar gradients, scalar perturbations, and positive initial scales satisfying the recurrence, all-order flatness, limiting, summability, initial-value, and uniform-smallness conditions.

#check (PlanarGradient.exists_alternatingScale : ∀ (σ : ℝ), σ ∈ Set.Ioo 0 1 → ∃ (g : ℕ → EuclideanSpace ℝ (Fin 2)) (δ : ℕ → ℝ) (a b : ℝ), PlanarGradient.IsAlternatingScale σ g δ a b)

Remark 3.3

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Remark 3.3 (1). The adjacent-radius decay in an alternating-scale construction yields Q-superlinear convergence of its gradient sequence to zero.

#check (PlanarGradient.IsAlternatingScale.isSuperlinear : ∀ {σ : ℝ} {g : ℕ → EuclideanSpace ℝ (Fin 2)} {δ : ℕ → ℝ} {a b : ℝ}, PlanarGradient.IsAlternatingScale σ g δ a b → QConvergence.IsSuperlinear g 0)

Lemma 4.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Lemma 4.1 (Compactly supported interpolation). For every ambient dimension at least two, there is a positive dimension-dependent constant such that every embedded alternating-scale sequence is interpolated by the gradient of a smooth function with a compactly supported quadratic tail and a uniform operator-norm Hessian bound.

open scoped EuclideanSpace Matrix.Norms.L2Operator #check PlanarGradient.exists_compactlySupportedInterpolation

Notation 4.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Notation 4.1: for 2 ≤ n, transport the alternating-scale planar gradients, perturbations, and candidate iterates through a chosen linear isometry ι; their images lie in the fixed two-dimensional subspace LinearMap.range ι.toLinearMap.

open scoped EuclideanSpace variable (n : ℕ) (h_n : 2 ≤ n) variable (ι : EuclideanSpace ℝ (Fin 2) →ₗᵢ[ℝ] EuclideanSpace ℝ (Fin n)) variable (σ : ℝ) (hσ : σ ∈ Set.Ioo 0 1) variable (g : ℕ → EuclideanSpace ℝ (Fin 2)) (δ : ℕ → ℝ) (a b : ℝ) variable (hdata : PlanarGradient.IsAlternatingScale σ g δ a b) #check ( let V := LinearMap.range ι.toLinearMap let gEmbedded := fun k ↦ ι (g k) let ΔEmbedded := fun k ↦ ι (PlanarGradient.perturbation EuclideanPlane.orientation (g k) (δ k)) let xEmbedded := fun k ↦ ι (PlanarGradient.candidate EuclideanPlane.orientation (g k) (δ k)) (⟨h_n, hσ, hdata, (LinearMap.finrank_range_of_inj ι.injective).trans finrank_euclideanSpace_fin, fun k ↦ LinearMap.mem_range_self ι.toLinearMap (g k), fun k ↦ LinearMap.mem_range_self ι.toLinearMap (PlanarGradient.perturbation EuclideanPlane.orientation (g k) (δ k)), fun k ↦ LinearMap.mem_range_self ι.toLinearMap (PlanarGradient.candidate EuclideanPlane.orientation (g k) (δ k))⟩ : 2 ≤ n ∧ σ ∈ Set.Ioo 0 1 ∧ PlanarGradient.IsAlternatingScale σ g δ a b ∧ Module.finrank ℝ V = 2 ∧ (∀ k, gEmbedded k ∈ V) ∧ (∀ k, ΔEmbedded k ∈ V) ∧ ∀ k, xEmbedded k ∈ V))

Lemma 4.2

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Lemma 4.2 (1): the gradient of a smooth quadratic-tail function is a global smooth diffeomorphism.

open scoped ContDiff Manifold Matrix.Norms.L2Operator MatrixOrder #check (QuadraticTail.gradientDiffeomorph : ∀ {n : ℕ} (H : EuclideanSpace ℝ (Fin n) → ℝ) (θ : ℝ), ContDiff ℝ ⊤ H → ContDiff ℝ ⊤ (H - (standardQuadratic : EuclideanSpace ℝ (Fin n) → ℝ)) → HasCompactSupport (H - (standardQuadratic : EuclideanSpace ℝ (Fin n) → ℝ)) → (∀ z : EuclideanSpace ℝ (Fin n), ‖ConvexAnalysis.hessian H z - 1‖ ≤ θ) → θ < 1 → gradient H 0 = 0 → ConvexAnalysis.hessian H 0 = 1 → ∃ e : EuclideanSpace ℝ (Fin n) ≃ₘ[ℝ] EuclideanSpace ℝ (Fin n), ∀ x, e x = gradient H x)

Lemma 4.2 Hessian

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

The reusable Euclidean Hessian matrix.

#check (ConvexAnalysis.hessian : ∀ {n : ℕ}, (EuclideanSpace ℝ (Fin n) → ℝ) → EuclideanSpace ℝ (Fin n) → Matrix (Fin n) (Fin n) ℝ)

Lemma 4.3

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Lemma 4.3 (2): the Hessian of the scaled objective at z equals the original Hessian at the inverse-scaled point.

universe u open scoped Pointwise namespace BFGS.Scale theorem hessian {n : ℕ} (F : EuclideanSpace ℝ (Fin n) → ℝ) (x : ℕ → EuclideanSpace ℝ (Fin n)) (B : ℕ → Matrix (Fin n) (Fin n) ℝ) (α : ℕ → ℝ) (B₀ : Matrix (Fin n) (Fin n) ℝ) (c : ℝ) (hF : ContDiff ℝ 2 F) (hRun : BFGS.IsTrajectory F B₀ x B α) (hc : 0 < c) (z : EuclideanSpace ℝ (Fin n)) : ConvexAnalysis.hessian (objective c F) z = ConvexAnalysis.hessian F (c⁻¹ • z)

Corollary 5.1

Lean contributors (project-level attribution): Chenyi Li.

Source header · Attribution source

Corollary 5.1 (1) (Convex Broyden class). Every parameter sequence in Set.Icc 0 1 admits an identity-initialized exact-line-search convex Broyden trajectory on the point sequence of the order-one BFGS example.

#check (BFGS.IsOrderOneExample.existsBroydenTrajectory : ∀ {n : ℕ} {ε R : ℝ} {F : EuclideanSpace ℝ (Fin n) → ℝ} {x₀ : EuclideanSpace ℝ (Fin n)} {x : ℕ → EuclideanSpace ℝ (Fin n)} {B : ℕ → Matrix (Fin n) (Fin n) ℝ} {α : ℕ → ℝ}, BFGS.IsOrderOneExample ε R F x₀ x B α → ∀ (φ : ℕ → ℝ), (∀ k, φ k ∈ Set.Icc (0 : ℝ) 1) → ∃ (Bφ : ℕ → Matrix (Fin n) (Fin n) ℝ) (αφ : ℕ → ℝ), Broyden.IsTrajectory F φ (1 : Matrix (Fin n) (Fin n) ℝ) x Bφ αφ)

Formalization contributors

Chenyi Li

Imported DFP infrastructure: Zichen Wang

Project-level credit · Source roster