Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Strictly Convex Quadratic Problems

Forum topic · 小凯 · 2026-07-25

Summary

This paper (arXiv:2507.19314) by Dawei Li, Xiaotian Jiang, and Mingyi Hong answers a central open question about the Barzilai-Borwein (BB) method: whether it converges superlinearly for almost every strictly convex quadratic problem and initialization. The authors give a negative answer. For every finite dimension n >= 4, they construct a nonempty open (hence positive-Lebesgue-measure) family of strictly convex quadratic problems and initial points for which the long Barzilai-Borwein method (BB1) converges but cannot converge root-superlinearly. With explicit constants rho_min = 10^-6 and rho_max = 0.61, every spectral component of the gradient is bounded above and below by geometric sequences. Consequently, the gradient norm and error in energy norm satisfy two-sided geometric estimates, while the objective gap satisfies squared-rate estimates; all three quantities are bounded below by geometric sequences, ruling out superlinear convergence. The construction relies on a computer-assisted proof of a non-resonant attracting seven-period for the four-dimensional projected BB dynamics.

Overview

This paper (arXiv:2507.19314) by Dawei Li, Xiaotian Jiang, and Mingyi Hong addresses a fundamental open question in continuous optimization: does the Barzilai-Borwein (BB) method converge superlinearly for almost every strictly convex quadratic problem and initialization?

Main Result

The authors provide a negative answer to this question. Specifically, for every finite dimension n >= 4, they construct a nonempty open — and therefore positive-Lebesgue-measure — family of strictly convex quadratic problems and initial points for which the long Barzilai-Borwein method (BB1) converges but cannot converge root-superlinearly.

Quantitative Estimates

With explicit constants rho_min = 10^-6 and rho_max = 0.61:

Every spectral component of the gradient is bounded above and below by corresponding geometric sequences.
The gradient norm and the error in energy norm satisfy two-sided geometric estimates at the same rate.
The objective gap satisfies squared-rate estimates.
All three quantities are bounded below by geometric sequences, which excludes superlinear convergence.

Proof Technique

The construction is highly nontrivial and is based on a computer-assisted proof of a non-resonant attracting seven-period in the four-dimensional projected BB dynamics.

Significance

BB methods are widely used in practice, yet their convergence dynamics remain poorly understood. This result shows that superlinear convergence is not a generic property even in the simplest setting of strictly convex quadratics, as failures occur on open sets of problems.

Paper: arXiv:2507.19314