为L-BFGS设计了动态控制条件数的稳定机制,提升非凸优化的鲁棒性。
On the Condition Number Upper Bound of the L-BFGS Inverse Hessian Approximation Matrix with a Two-Sided Geometric Envelope Safeguarding Mechanism

- 通过双侧几何包络动态约束逆海森矩阵条件数
- 理论证明条件数有统一上界,且保持原有计算复杂度
- 适合高维非凸优化场景,尤其改善病态问题收敛性
有限记忆拟牛顿法(L-BFGS)因其线性内存和计算开销成为大规模优化的核心方法。然而,在病态或非凸场景下,隐式逆海森矩阵近似可能引发条件数爆炸,导致数值不稳定和收敛性能下降。为此,本文提出两面式L-BFGS,通过双侧几何包络动态约束逆海森算子的条件数。该方法保留累积曲率信息,并维持标准的 $O(mn)$ 内存和每轮迭代时间复杂度。我们证明该几何包络可对算法生成的每一逆海森近似提供统一的条件数上界。通过追踪从缩放单位矩阵出发、经过 $m$ 次连续拟牛顿更新后极端特征值的代数演化,该上界显式表达为记忆深度、问题维度和包络超参数的函数。此外,我们在标准光滑性和强沃尔夫线搜索假设下,证明了两面式L-BFGS在非凸情形下仍保持渐近全局收敛性,与采用李-福岛谨慎更新规则的L-BFGS变体具有相同的理论保证。高维优化实验表明,所提方法能保持逆海森矩阵的良好条件性,显著提升病态基准测试下的鲁棒性和收敛表现。
原文摘要 · Abstract (English)
The limited-memory BFGS (L-BFGS) algorithm is a cornerstone of large-scale optimization due to its linear memory and computational costs. However, in ill-conditioned or non-convex landscapes, the implicit inverse Hessian approximation can suffer from an exploding condition number, leading to numerical instability and degraded convergence. To address this, we propose Two-Sided L-BFGS, a safeguarded variant that dynamically constrains the condition number of the inverse Hessian operator via a two-sided geometric envelope. Moreover, we show that Two-Sided L-BFGS preserves accumulated curvature information and maintains standard $O(mn)$ memory and per-iteration time complexities. We prove that this geometric envelope yields a uniform bound on the condition number of every inverse Hessian approximation generated by the algorithm. By tracking the algebraic evolution of the extreme eigenvalues through $m$ consecutive quasi-Newton updates starting from a scaled identity matrix, the resulting bound is expressed explicitly as a function of the memory depth, problem dimension, and envelope hyperparameters. Moreover, we show that Two-Sided L-BFGS preserves asymptotic global convergence in non-convex regimes under standard smoothness and strong Wolfe line-search assumptions, matching the theoretical guarantees of L-BFGS variants utilizing the Li-Fukushima cautious update rule. Numerical experiments on high-dimensional optimization problems demonstrate that the proposed method maintains well-conditioned inverse Hessian approximations and improves robustness and convergence behavior on ill-conditioned benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。