BB优化法在高维二次问题上无法实现超线性收敛
Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$
- 构造四维以上二次问题的开集，证明BB法不超线性收敛
- 梯度与误差范数呈几何下降，下界为几何序列
- 适用于研究优化算法收敛性理论的研究者
Barzilai-Borwein（BB）方法在连续优化中表现出强劲的实际性能，但其收敛机制仍不明确。一个核心未解问题是：对几乎所有严格凸二次问题和任意初值，BB是否能实现超线性收敛？本文给出否定回答。具体而言，对每个有限维数 $n\geq4$，我们构造了一个非空开集（即正勒贝格测度）的严格凸二次问题与初始点，使得长期BB1方法收敛，但无法实现根超线性收敛。更精确地，存在显式常数 $ρ_{\min}=10^{-6}, ρ_{\max}=0.61$，使得梯度的每个谱分量被对应的几何序列上下界定。因此，梯度范数与误差能量范数满足相同速率的双侧几何估计，而目标差距则对应平方速率的估计。特别地，三类量均被几何序列下界控制，排除了超线性收敛的可能性。该构造极为复杂，基于计算机辅助证明，在四维情况下投影化BB动力系统的非共振吸引七周期的存在性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。