An Outer Gradient Algorithm For Solving Stochastic Variational Inequalities

Variational inequality is an important tool to solve nonlinear problems,which has been widely used in equilibrium problems in the economic field,engineering optimization and urban transportation network problems.A host of effective algorithms have been proposed for such problem.Since the data of many problems are often affected by uncertainty or randomness in real world applications,the original models are mostly stochastic optimization or equilibrium problems.So they can be transformed into stochastic variational inequalities.Therefore,the study of stochastic variational inequalities has important economic benefits and practical significance for optimal management,transportation and engineering applications,and it has been one of the hot topics in recent years.Extra-gradient method(EGM)is one of the effective methods to variational inequalities,which has been extended to solve stochastic variational inequalities,i.e.,stochastic extra-gradient method(SEGM).There are also many modified extragradient methods that have been extended to stochastic forms,such as Tseng's forward-backward-forward(FBF)method.Inspired by the deterministic method,we propose two modified stochastic extra-gradient methods,and compare them with SEGM and SFBF in numerical experiments.We consider to solve the pseudo-monotone stochastic variational inequality problem,and make the following contributions in this paper.First,we present a modified stochastic extra-gradient method with constant step-size(MSEGMC)and prove the convergence of it.With the strong pseudo-monotone operator and the exponentially growing sample sequences,we establish the R-linear convergence rate in terms of the mean natural residual and the oracle complexity O((?))of the MSEGMC.Second,we propose a modified stochastic extra-gradient method with adaptive step-size(MSEGMA).In addition,the update of step-size doesn't depend on the Lipschitz constant.We also prove the MSEGMA almost sure convergence to a solution of the original problem.Finally,we use some numerical experiments to carry out the verification on the effectiveness of these two algorithms.