Skip to content
DraconiticResearch
Search Sources API
189,280 studies31 sourcesUpdated 26 min ago
PreprintarXiv licencearXiv

Lyapunov Functions and R-Linear Convergence for Quadratic Barzilai-Borwein Dynamics

  • Shutai Yang
  • Ya-xiang Yuan
Open at sourcePDFDOICite

Abstract

The Barzilai--Borwein (BB) method is R-linearly convergent on strongly convex quadratics, although neither the objective value nor the gradient norm is generally monotone. We construct an explicit current-point Lyapunov function for the quadratic dynamics after the warm-up step, assuming that both endpoints of the initial active spectrum survive this step. If a<b are these endpoints and Pa,Pb are the corresponding spectral projectors, then f̅(x) :=lVert Pa∇ f(x)rVert2b/(a+b) lVert Pb∇ f(x)rVert2a/(a+b) satisfies, for BB1, BB2, and every fixed positive weighted delayed Rayleigh rule, f̅(xk+1) =((b−a)/(b+a))2 e−2Da,b(τk)f̅(xk), Da,b(τk)≥0, where τk=1/αk is the reciprocal step. The function is obtained by denormalizing the endpoint coboundary certificate in the sharp-rate analysis of Yang and Yuan. We prove that the endpoint exponents are the unique minimax choice among endpoint monomials and illustrate the Lyapunov law on a nonmonotone BB1 trajectory. Using this law, we also give a proof of R-linear convergence of the method in finite dimensions.

Related

  1. R-Linear Convergence of Barzilai-Borwein Methods on Strictly Convex Quadratics via Closed-Cone Homogeneous Dynamics
    Shutai Yang, Ya-xiang Yuan
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingOptimisation & controlarXiv
  2. Convergence of Large-Stepsize SGD for the Cross-entropy Loss via Stochastic Lyapunov Stability
    Konstantinos Emmanouilidis, Lachlan MacDonald, Salma Tarmoun +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlStatisticsarXiv
  3. Linear Lyapunov Functions for Nonlinear Compartmental Systems
    Sondre Wiersdalen, Mike Pereira, Annika Lang +3
    IEEE Transactions on Automatic ControlPeer-reviewedCC BY 4.0Full textAnalysis & PDEsHAL
  4. Fixed-Time ISS for Interconnected Discrete-Time Systems, Part I: Extinction-Based Lyapunov Functions
    Sumadhu Rubaiyat, Jorge I. Poveda
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Lyapunov functions for the Langevin equation with dissipative damping
    Barkat Mian, Hung D. Nguyen
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{yang2026lyapunov,
  title = {{Lyapunov Functions and $R$-Linear Convergence for Quadratic Barzilai-Borwein Dynamics}},
  author = {Shutai Yang and Ya-xiang Yuan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.12084},
  eprint = {2609.12084},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.12084},
}
RIS
TY  - UNPB
TI  - Lyapunov Functions and R-Linear Convergence for Quadratic Barzilai-Borwein Dynamics
AU  - Shutai Yang
AU  - Ya-xiang Yuan
PY  - 2026
DA  - 2026/09/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.12084
UR  - https://arxiv.org/abs/2609.12084
AB  - The Barzilai--Borwein (BB) method is R-linearly convergent on strongly convex quadratics, although neither the objective value nor the gradient norm is generally monotone. We construct an explicit current-point Lyapunov function for the quadratic dynamics after the warm-up step, assuming that both endpoints of the initial active spectrum survive this step. If a<b are these endpoints and P_a,P_b are the corresponding spectral projectors, then f̅(x) :=lVert P_a∇ f(x)rVert^2b/(a+b) lVert P_b∇ f(x)rVert^2a/(a+b) satisfies, for BB1, BB2, and every fixed positive weighted delayed Rayleigh rule, f̅(x_k+1) =((b−a)/(b+a))^2 e^−2D_a,b(τ_k)f̅(x_k), D_a,b(τ_k)≥0, where τ_k=1/α_k is the reciprocal step. The function is obtained by denormalizing the endpoint coboundary certificate in the sharp-rate analysis of Yang and Yuan. We prove that the endpoint exponents are the unique minimax choice among endpoint monomials and illustrate the Lyapunov law on a nonmonotone BB1 trajectory. Using this law, we also give a proof of R-linear convergence of the method in finite dimensions.
ER  -