Paperlane

no. 3 · Tuesday 27 October 2026

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

Santanu Soe, Matthew K. Tam and V. Vetrivel

math.OC · 29 pp

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 $c$ to $1<c\leq\varphi$, where $\varphi=(1+\sqrt5)/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\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)$ 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.

comments
29 pages and 20 figures
fields
Optimization and Control
pdf ↗ page arXiv:2610.34975 ↗