Incremental constraint projection methods for monotone stochastic variational inequalities

Resumo

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 convergene, feasibility rate of O(1/k) in terms of the mean squared distance to the feasible set and solvability rate of
 O(1/√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.

Ficha do documento

Tipo

Artigo científico

Ano

2017

Instituição

Fundação Getulio Vargas

Fonte

Repositório da FGV

Idioma

Português

Acesso

Não informado

Identificador

oai:repositorio.fgv.br:10438/33764

Palavras-chave

Stochastic variational inequalitiesEstocásticaDesigualdades variacionaisMatemáticaDesigualdades variacionais (Matemática)Processo estocástico