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

@misc{soe2026graal,
  title = {{GRAAL for variational inequalities revisited: sharp parameter range and adaptive step sizes}},
  author = {Santanu Soe and Matthew K. Tam and V. Vetrivel},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.34975},
  eprint = {2610.34975},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34975},
}

TY  - UNPB
TI  - GRAAL for variational inequalities revisited: sharp parameter range and adaptive step sizes
AU  - Santanu Soe
AU  - Matthew K. Tam
AU  - V. Vetrivel
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2610.34975
UR  - https://arxiv.org/abs/2610.34975
AB  - 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 c to 1<c≤φ, where φ=(1+√5)/2 is the golden ratio. Through a new Lyapunov analysis, we show that this range of c can be extended to 1<c<3. Further, a two-dimensional linear counterexample shows that this parameter range is sharp. In particular, for every c≥3 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) 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.
ER  -