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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references