Numerical Methods for Variational Inequalities and Saddle Point Problems with Relative Inexact Information

In this work, we consider the variational inequality problem with Lipschitz-continuous and strongly monotone operators and the access available only to relative inexact information of these operators. To solve such a problem, we consider projection and extra-gradient methods with relative error values of the operator at the current points in each iteration. Theoretical estimates for the quality of the solution (the last iterated point) were obtained in the case when the problem is constrained. When the problem is unconstrained (i.e., the feasible set coincides with the whole space) we proved the linear convergence rate to both methods under consideration with tight conditions on the relative error parameter for which we conserve the linear convergence rate. We also consider saddle point problems with the two-sided Polyak–Lojasiewicz condition and propose a gradient descent-ascent type method for them which converges at a linear rate. Some numerical experiments, for both variational inequalities and saddle point problems, were conducted to demonstrate the effectiveness of the proposed algorithms and to confirm the theoretical results in the paper.