Incremental constraint projection methods for variational inequalities
alternate/cyclic projectionconstraint distributed structuresconvergencecycling projection algorithmerror constantincremental methodlarge number of setslarge-scale datalinear regularityrandom projectionsamplingstochastic approximationstochastic gradientstrongly monotone operatorvariational inequalities
Variational inequalities (49J40) Stochastic approximation (62L20) Numerical methods for variational inequalities and related problems (65K15) Online algorithms; streaming algorithms (68W27) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
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.
- Random and cyclic projection algorithms for variational inequalities
- Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
- A new incremental constraint projection method for solving monotone variational inequalities
- Stochastic projection gradient algorithm for stochastic variational inequalities
- Inertial-type incremental constraint projection method for solving variational inequalities without Lipschitz continuity
- Approximate policy iteration: a survey and some new methods
- Common solutions to variational inequalities
- Dynamic programming and optimal control. Vol. 2
- scientific article; zbMATH DE number 5348356 (Why is no real title available?)
- scientific article; zbMATH DE number 1009689 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- Incremental proximal methods for large scale convex optimization
- Projection methods for variational inequalities with application to the traffic assignment problem
- Projections onto super-half-spaces for monotone variational inequality problems in finite-dimensional space
- Relaxed Alternating Projection Methods
- Temporal Difference Methods for General Projected Equations
- Two-stage stochastic variational inequalities: an ERM-solution procedure
- Inexact proximal stochastic gradient method for convex composite optimization
- On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
- On the analysis of variance-reduced and randomized projection variants of single projection schemes for monotone stochastic variational inequality problems
- Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities
- A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
- Inertial projection and contraction algorithms with larger step sizes for solving quasimonotone variational inequalities
- Inertial-type incremental constraint projection method for solving variational inequalities without Lipschitz continuity
- Linear convergence of cyclic SAGA
- Two fast variance-reduced proximal gradient algorithms for SMVIPs -- stochastic mixed variational inequality problems with suitable applications to stochastic network games and traffic assignment problems
- Stochastic first-order methods with random constraint projection
- Ergodic convergence of a stochastic proximal point algorithm
- Equilibrium in multi-criteria transportation networks
- A Projection-Based Algorithm for Consistent and Inconsistent Constraints
- String-averaging incremental stochastic subgradient algorithms
- scientific article; zbMATH DE number 6178178 (Why is no real title available?)
- Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
- Random and cyclic projection algorithms for variational inequalities
- Variance-based modified backward-forward algorithm with line search for stochastic variational inequality problems and its applications
- A method with convergence rates for optimization problems with variational inequality constraints
- Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
- A new incremental constraint projection method for solving monotone variational inequalities
- Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
- Hybrid SGD algorithms to solve stochastic composite optimization problems with application in sparse portfolio selection problems
- Data perturbations in stochastic generalized equations: statistical robustness in static and sample average approximated models
- Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities
- Scenario decomposable subgradient projection method for two-stage stochastic programming with convex risk measures
- Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
- Random and cyclic projection algorithms for strongly pseudomonotone variational inequalities
- New penalized stochastic gradient methods for linearly constrained strongly convex optimization
- Stochastic approximation based confidence regions for stochastic variational inequalities
- An improved random projection-type algorithm for solving multiple-sets split feasibility problems with application to medical radiotherapy
- Proximal algorithms and temporal difference methods for solving fixed point problems
- Dynamical behavior of a stochastic forward-backward algorithm using random monotone operators
- Adaptive-batch stochastic gradient descent for constrained optimization based on relaxed barrier functions
- Robust stochastic gradient descent for linearly constrained problems via adaptive barrier amplification
- Tailed-average SGD: a Polyak-Ruppert modification for optimal-rate constrained optimization
- Stochastic functions learning from distribution-driven data: generalization bound and algorithms
- Practical early stopping for adaptive barrier SGD: balancing stochastic speed with validation accuracy
This page was built for publication: Incremental constraint projection methods for variational inequalities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340334)
