On the Condition Number Upper Bound of the L-BFGS Inverse Hessian Approximation Matrix with a Two-Sided Geometric Envelope Safeguarding Mechanism
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.