Incremental constraint projection methods for variational inequalities (Q2340334)

The authors propose new algorithms for strongly monotone variational inequalities with structure that lends itself to constraint and function sampling. The convergence properties of various types of sampling over cyclic sampling is analyzed. The variational inequalities (VI) problem is to find \(x^* \in X\) such that (1) \(F(x^*)'\), \((x-x^*) \geq 0 \forall x \in X\), where \(F:\mathbb R^n \rightarrow \mathbb R^n\) is a mapping and \(X\) is a closed and convex set in \(\mathbb R^n\). The authors are interested in a VI of the form (1) in which the constraint set \(X\) is the intersection of many sets, i.e. \(X=\cap_{i \in M} X_i\), with each \(X_i\) being a closed and convex subset of \(\mathbb R^n\), and \(M\) being the set of constraint indexes. The classical projection method for a solution of a VI has the form (2) \(x_{k+1} = \Pi [x_k - \alpha_k F(x_k)]\), where \(\Pi\) denotes the Euclidean orthogonal projection onto \(X\), and \(\{\alpha_k\}\) is a sequence of constant or diminishing positive scalars. Since \(X\) is closed and convex, the projection exists and is unique. A major difficulty when using this method in practice is the computation of the projection at each iteration, which can be time-consuming. In the case where the constraint set \(X\) is the intersection of a large number of simpler sets \(X_i\), it is possible to exploit this structure and improve the method by projecting onto a single set \(X_i\) at each iteration. A modification of the algorithm (2): \[ x_{k+1} = \Pi_{w_k} [x_k - \alpha_k F(x_k)] \] is suggested, too.