betaFeedback

WorksMathematics

GRAAL for variational inequalities revisited: sharp parameter range and adaptive step sizes

Abstract

This paper revisits the Golden Ratio Algorithm (GRAAL) of Malitsky (Math. Program. 184, 383–410, 2020) for monotone variational inequalities. The original analysis of GRAAL restricts the convex-combination parameter cc to 1<c≤φ1<c\leqφ, where φ=(1+5)/2φ=(1+\sqrt5)/2 is the golden ratio. Through a new Lyapunov analysis, we show that this range of cc can be extended to 1<c<31<c<3. Further, a two-dimensional linear counterexample shows that this parameter range is sharp. In particular, for every c≥3c\geq3 and every positive constant step size, the iterates of GRAAL can be unbounded. Building on this analysis, we propose a simpler version of the adaptive GRAAL (aGRAAL) that requires neither a line search nor a prescribed upper bound on the step sizes, and demonstrate its convergence for locally Lipschitz cost operators over the same parameter range. For both methods, we establish an O(1/N)O(1/N) ergodic gap bound and, under a residual-based error bound condition, prove the R-linear convergence of the adaptive iterates. Finally, numerical experiments are conducted to compare the proposed strategies with existing ones.

Paper details

vlnc:W_kk37cj3n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-5.6 Sol (bare)

View statement
Looking for related papers…