Incremental constraint projection methods for monotone stochastic variational inequalities
| Autor: | Alfredo N. Iusem, Alejandro Jofré, Philip Thompson |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
021103 operations research
Intersection (set theory) General Mathematics Feasible region MathematicsofComputing_NUMERICALANALYSIS 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology Management Science and Operations Research Stochastic approximation 01 natural sciences Projection (linear algebra) Computer Science Applications Constraint (information theory) Monotone polygon Optimization and Control (math.OC) Variational inequality Projection method FOS: Mathematics Applied mathematics 0101 mathematics Mathematics - Optimization and Control Mathematics |
| DOI: | 10.48550/arxiv.1703.00272 |
| Popis: | We consider stochastic variational inequalities with monotone operators defined as the expected value of a random operator. We assume the feasible set is the intersection of a large family of convex sets. We propose a method that combines stochastic approximation with incremental constraint projections meaning that at each iteration, a step similar to some variant of a deterministic projection method is taken after the random operator is sampled and a component of the intersection defining the feasible set is chosen at random. Such sequential scheme is well suited for applications involving large data sets, online optimization and distributed learning. First, we assume that the variational inequality is weak-sharp. We provide asymptotic convergence, feasibility rate of $O(1/k)$ in terms of the mean squared distance to the feasible set and solvability rate of $O(1/\sqrt{k})$ (up to first order logarithmic terms) in terms of the mean distance to the solution set for a bounded or unbounded feasible set. Then, we assume just monotonicity of the operator and introduce an explicit iterative Tykhonov regularization to the method. We consider Cartesian variational inequalities so as to encompass the distributed solution of stochastic Nash games or multi-agent optimization problems under a limited coordination. We provide asymptotic convergence, feasibility rate of $O(1/k)$ in terms of the mean squared distance to the feasible set and, in the case of a compact set, we provide a near-optimal solvability convergence rate of $O\left(\frac{k^\delta\ln k}{\sqrt{k}}\right)$ in terms of the mean dual gap-function of the SVI for arbitrarily small $\delta>0$. Comment: 37 pages. Submitted to Mathematics of Operations Research (submitted June 2015, first revision submitted September 2016, under second revision). See also preprint.impa.br/visualizar?id=6170 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|