A Parameter-Free Adaptive Reflected Gradient Method for Monotone Variational Inequalities

Abstract

We analyze a one-evaluation-per-iteration method for $\mathrm{VI}(C,B)$ with monotone $L$-Lipschitz $B$: $x_{k+1}=P_C(x_k-\lambda B(u_k))$, $u_k=x_k+\theta_k(x_k-x_{k-1})+\beta_k(x_k-u_{k-1})$, $\theta_k+\beta_k=1$. For constant step and summable filter ($\sum_k\beta_k<\infty$) we prove weak convergence via a Lyapunov function with exact rational dissipation budgets, including Malitsky's reflected gradient method. It is robust to summable operator errors; if $C$ is bounded, the constant-step range reaches $\lambda<(\sqrt2-1)/L$. For unbounded $C$ this reduces to an a priori boundedness statement, certified to $\lambda L=0.387$ by dissipation trading; for affine $B$ on polyhedral $C$, $\dist(x_n,S)\to0$ with $\sum_n\dist^2(x_n,S)<\infty$, strong convergence for bounded $C$, and $R$-linear rates after face identification. The main result is a safeguarded adaptive step-size rule needing no $L$ and no extra evaluations, proved weakly convergent unconditionally: a data-driven Lyapunov weight removes $L$ from the dissipation budgets. For affine $B$ with $C=\mathcal H$, sharpness of $\lambda L=1/\sqrt3$ via a rotation lower bound; the same constant is sharp for unconstrained nonlinear $B$, with convergence for square-summable operator values. Unconditional convergence below $1/(\sqrt3\,L)$ reduces to a marginal-pole absolute-stability statement; the projected case remains open. Under strong monotonicity we prove $R$-linear convergence with explicit contraction, and certify $\Omega(L)$ speedups over constant steps. Numerics confirm the gains.