Incremental constraint projection methods for variational inequalities

被引:40
作者
Wang, Mengdi [1 ]
Bertsekas, Dimitri P. [2 ]
机构
[1] Princeton Univ, Dept Operat Res & Financial Engn, Princeton, NJ 08544 USA
[2] MIT, Dept Elect Engn & Comp Sci, LIDS, Cambridge, MA 02139 USA
关键词
Random projection; Alternate/cyclic projection; Variational inequalities; Stochastic gradient; Incremental method; Sampling; Stochastic approximation; LINEAR-PROGRAMMING APPROACH; APPROXIMATION METHODS; COMMON SOLUTIONS; CONVERGENCE; ALGORITHMS;
D O I
10.1007/s10107-014-0769-x
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We consider the solution of strongly monotone variational inequalities of the form , for all . We focus on special structures that lend themselves to sampling, such as when is the intersection of a large number of sets, and/or is an expected value or is the sum of a large number of component functions. We propose new methods that combine elements of incremental constraint projection and stochastic gradient. These methods are suitable for problems involving large-scale data, as well as problems with certain online or distributed structures. We analyze the convergence and the rate of convergence of these methods with various types of sampling schemes, and we establish a substantial rate of convergence advantage for random sampling over cyclic sampling.
引用
收藏
页码:321 / 363
页数:43
相关论文
共 54 条
[1]  
[Anonymous], NONLINEAR PROGRAMING
[2]  
[Anonymous], 1976, MATECON
[3]  
[Anonymous], J CONTROL THEORY APP
[4]  
[Anonymous], 2013, LIDSP2907 MIT
[5]  
[Anonymous], ACTA SCI MATH
[6]  
[Anonymous], APPL MATH COMPUT
[7]  
[Anonymous], 1996, Neuro-Dynamic Programming
[8]  
[Anonymous], 1998, Reinforcement Learning: An Introduction
[9]  
[Anonymous], HDB OR MS
[10]  
[Anonymous], LIDSP1938 MIT