Preprint A760/2015
Approximate projection methods for monotone stochastic variational inequalities
Alfredo Noel Iusem | Alejandro Jofré | Philip Thompson
Keywords: stochastic variational inequalities | projection method | stochastic approximation

We consider stochastic variational inequalities with monotone operators. The operator F defining the variational inequality depends both on a variable in the finite dimensional Euclidean space and on a random variable. We are interested in finding solutions for the deterministic variational inequality problem whose operator T is defined as the expected value of F, but we do not assume that T is explicitly available; rather we propose a Stochastic Approximation procedure, meaning that at each iteration, a step similar to some variant of the deterministic projection method is taken after sampling the random variable, choosing thus a specific realization of the operator. We consider two variants of the method where the exact orthogonal projection step is replaced by an approximate one. The first variant is a projection method with approximate projections, where the variational inequality satisfies an error bound on the solution set, called weak sharpness. We prove that the generated sequence is bounded and its distance to the solution set converges to zero almost surely. In particular, every cluster point of the sequence is, almost surely, a solution. For the case in which the feasible set is compact, we establish a convergence rate and an estimate on the number of iterations required so that any solution of an auxiliary linear program solves the variational inequality. The second variant is an iterative Tykhonov regularization method with approximate projections where, instead of solving a sequence of regularized variational inequality problems, the regularization parameter is updated in each iteration and a single projection step associated with the regularized problem is taken. In this second method, we allow a Cartesian structure on the variational inequality so as to encompass, for example, equilibrium conditions of monotone stochastic Nash games with a limited coordination between the players' stepsize and regularization sequences. Requiring just monotonicity, we prove that the generated sequence converges to the least-norm solution of the variational inequality almost surely.