no. 3 · Tuesday 27 October 2026
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 $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