Search papers, labs, and topics across Lattice.
This paper critically examines the convergence behavior of the Barzilai-Borwein (BB) method in the context of strictly convex quadratic problems, revealing that it fails to achieve superlinear convergence for a significant class of cases in dimensions \( n \geq 4 \). By constructing a family of quadratic problems with positive Lebesgue measure, the authors demonstrate that while BB converges, it does so at a rate that is fundamentally limited by geometric sequences, thus ruling out superlinear convergence. The findings challenge the prevailing assumption of BB's superior performance in optimization, providing explicit bounds on the convergence rates that are essential for understanding its limitations.
Superlinear convergence of the Barzilai-Borwein method is a myth for a wide class of quadratic problems in dimensions four and higher.
Barzilai--Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. In particular, a central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. We provide a negative answer to this question. Specifically, for every finite dimension $n\geq4$, we 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. More precisely, with the explicit constants $蟻_{\min}=10^{-6},蟻_{\max}=0.61$, every spectral component of the gradient is bounded above and below by the corresponding geometric sequence. Consequently, the gradient norm and the energy norm of the error satisfy two-sided geometric estimates with the same rates, while the objective gap satisfies the corresponding estimates with squared rates. In particular, all three quantities are bounded below by geometric sequences, ruling out superlinear convergence. The construction is highly nontrivial, based on a computer-assisted proof of a nonresonant, attracting seven-cycle of the projectivized BB dynamics in dimension four.
