A counterexample to a three-step convergence bound for BFGS with exact line search
Abstract
We disprove a three-step error estimate for the Broyden--Fletcher--Goldfarb--Shanno {(BFGS)} method with exact line searches. We construct a globally strongly convex function F∈ C∞(ℝ3) and a single nonterminating trajectory xk→0 for which limsupk→∞|xk+3|/(|xk+2||xk|)=+∞. The Hessian of F lies between 1/2 I and 3/2 I everywhere, and F(x)−1/2|x|2 is compactly supported with all derivatives vanishing at $0$. The proof first constructs point-gradient pairs satisfying the exact BFGS step identities. A five-step cycle produces a large three-step quotient and restores an invariant plane for the actual updated matrix, allowing the cycle to be repeated with arbitrarily small gradient errors. Disjoint smooth corrections to a quadratic then realize all the pairs by one objective. Strong convexity identifies the prescribed points with the unique exact line-search minimizers. Thus smoothness and strong convexity do not imply the proposed product estimate, even for an objective that agrees with a quadratic to every order at its minimizer.
Related
- A Counterexample to Yau's Conjectured Asymptotic Scalar-Curvature Integral Bound
- A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
- The Exact Boundary of Linear Optimality in Witsenhausen's Counterexample
- A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound
- A Counterexample to the Exact Eight-Point Angular-Energy Conjecture
BibTeX
@misc{xu2026counterexample,
title = {{A counterexample to a three-step convergence bound for BFGS with exact line search}},
author = {Jiawei Xu and Jiang Hu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02719},
eprint = {2611.02719},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02719},
}
RIS
TY - UNPB
TI - A counterexample to a three-step convergence bound for BFGS with exact line search
AU - Jiawei Xu
AU - Jiang Hu
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02719
UR - https://arxiv.org/abs/2611.02719
AB - We disprove a three-step error estimate for the Broyden--Fletcher--Goldfarb--Shanno {(BFGS)} method with exact line searches. We construct a globally strongly convex function F∈ C^∞(ℝ^3) and a single nonterminating trajectory x_k→0 for which limsup_k→∞|x_k+3|/(|x_k+2||x_k|)=+∞. The Hessian of F lies between 1/2 I and 3/2 I everywhere, and F(x)−1/2|x|^2 is compactly supported with all derivatives vanishing at $0$. The proof first constructs point-gradient pairs satisfying the exact BFGS step identities. A five-step cycle produces a large three-step quotient and restores an invariant plane for the actual updated matrix, allowing the cycle to be repeated with arbitrarily small gradient errors. Disjoint smooth corrections to a quadratic then realize all the pairs by one objective. Strong convexity identifies the prescribed points with the unique exact line-search minimizers. Thus smoothness and strong convexity do not imply the proposed product estimate, even for an objective that agrees with a quadratic to every order at its minimizer.
ER -