Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
Authors:
- 24 August 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 58 (3) , 594-609
Abstract
We consider a Cartesian stochastic variational inequality problem with a monotone map. Monotone stochastic variational inequalities arise naturally, for instance, as the equilibrium conditions of monotone stochastic Nash games over continuous strategy sets or multiuser stochastic optimization problems. We introduce two classes of stochastic approximation methods, each of which requires exactly one projection step at every iteration, and provide convergence analysis for each of them. Of these, the first is a stochastic iterative Tikhonov regularization method which necessitates the update of the regularization parameter after every iteration. The second method is a stochastic iterative proximal-point method, where the centering term is updated after every iteration. The Cartesian structure lends itself to constructing distributed multi-agent extensions and conditions are provided for recovering global convergence in limited coordination variants where agents are allowed to choose their steplength sequences, regularization and centering parameters independently, while meeting a suitable coordination requirement. We apply the proposed class of techniques and their limited coordination versions to a stochastic networked rate allocation problem.Keywords
This publication has 34 references indexed in Scilit:
- Games with coupled propagated constraints in optical networks with multi-link topologiesAutomatica, 2009
- On generalized Nash games and variational inequalitiesOperations Research Letters, 2007
- An extension of duality to a game-theoretic frameworkAutomatica, 2007
- Dual extrapolation and its applications to solving variational inequalities and related problemsMathematical Programming, 2006
- A Noncooperative Game Approach to OSNR Optimization in Optical NetworksIEEE Transactions on Automatic Control, 2006
- Monte Carlo bounding techniques for determining solution quality in stochastic programsOperations Research Letters, 1999
- Optimization flow control. I. Basic algorithm and convergenceIEEE/ACM Transactions on Networking, 1999
- Rate control for communication networks: shadow prices, proportional fairness and stabilityJournal of the Operational Research Society, 1998
- Stochastic approximation with two time scalesSystems & Control Letters, 1997
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951