Incremental constraint projection methods for variational inequalities (Q2340334)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Incremental constraint projection methods for variational inequalities |
scientific article |
Statements
Incremental constraint projection methods for variational inequalities (English)
0 references
16 April 2015
0 references
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.
0 references
random projection
0 references
alternate/cyclic projection
0 references
variational inequalities
0 references
stochastic gradient
0 references
incremental method
0 references
sampling
0 references
stochastic approximation
0 references
error constant
0 references
cycling projection algorithm
0 references
linear regularity
0 references
strongly monotone operator
0 references
large-scale data
0 references
convergence
0 references
large number of sets
0 references
constraint distributed structures
0 references
0 references