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 to , where is the golden ratio. Through a new Lyapunov analysis, we show that this range of can be extended to . Further, a two-dimensional linear counterexample shows that this parameter range is sharp. In particular, for every 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 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.