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.
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.
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.
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.
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.
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.
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.
universe u
#check (BFGS.IsTrajectory :
∀ {ι : Type u} [Fintype ι] [DecidableEq ι],
(EuclideanSpace ℝ ι → ℝ) → Matrix ι ι ℝ →
(ℕ → EuclideanSpace ℝ ι) → (ℕ → Matrix ι ι ℝ) → (ℕ → ℝ) → Prop)Derivation 3.1
Lean contributors (project-level attribution): Chenyi Li.
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.
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.
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.quarterTurnMatrixNotation 3.1 Tangentrecurrence
Lean contributors (project-level attribution): Chenyi Li.
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.
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.
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.
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.
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_compactlySupportedInterpolationNotation 4.1
Lean contributors (project-level attribution): Chenyi Li.
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.
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.
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.
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.
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φ αφ)