The Minimum Q-Order of BFGS with Exact Line Search Is One
Abstract
Powell asked whether the smoothness assumptions underlying classical superlinear convergence force a fixed power law between adjacent iterates of exact-line-search variable-metric methods. We answer this question negatively for BFGS: within the smooth strongly convex setting, the smallest possible adjacent-iterate Q-order is one, and this boundary is attained by a single nonterminating run. In every finite dimension at least two, and for any prescribed radius and Hessian tolerance, we construct an infinitely differentiable, globally strongly convex objective that equals the standard quadratic outside the corresponding ball and whose Hessian remains within the prescribed tolerance of the identity in operator norm. The objective has its unique minimizer at the origin and identity Hessian there. Exact-line-search BFGS, initialized with the identity matrix and started inside that ball, converges Q-superlinearly, yet no fixed power greater than one controls all sufficiently late adjacent errors.
Related
- A counterexample to a three-step convergence bound for BFGS with exact line search
- Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound
- Links of minimum degree and exact covering numbers
- Jordan-Block Degeneracy and Cubic-Order Bifurcating Periodic Orbits in Minimum-Energy Optimal Control of Hamiltonian Equilibria
- An Improved Riemannian Trust-Region Method Combining Line Search Techniques with Applications in Matrix Optimization
BibTeX
@misc{liu2026minimum,
title = {{The Minimum Q-Order of BFGS with Exact Line Search Is One}},
author = {Benqi Liu and Chenyi Li and Zaiwen Wen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00596},
eprint = {2609.00596},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00596},
}
RIS
TY - UNPB
TI - The Minimum Q-Order of BFGS with Exact Line Search Is One
AU - Benqi Liu
AU - Chenyi Li
AU - Zaiwen Wen
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00596
UR - https://arxiv.org/abs/2609.00596
AB - Powell asked whether the smoothness assumptions underlying classical superlinear convergence force a fixed power law between adjacent iterates of exact-line-search variable-metric methods. We answer this question negatively for BFGS: within the smooth strongly convex setting, the smallest possible adjacent-iterate Q-order is one, and this boundary is attained by a single nonterminating run. In every finite dimension at least two, and for any prescribed radius and Hessian tolerance, we construct an infinitely differentiable, globally strongly convex objective that equals the standard quadratic outside the corresponding ball and whose Hessian remains within the prescribed tolerance of the identity in operator norm. The objective has its unique minimizer at the origin and identity Hessian there. Exact-line-search BFGS, initialized with the identity matrix and started inside that ball, converges Q-superlinearly, yet no fixed power greater than one controls all sufficiently late adjacent errors.
ER -