An Infeasible Stochastic Approximation and Projection Algorithm for Stochastic Variational Inequalities

Xiao-Juan Zhang (), Xue-Wu Du (), Zhen-Ping Yang () and Gui-Hua Lin ()
Additional contact information
Xiao-Juan Zhang: Chongqing University of Posts and Telecommunications
Xue-Wu Du: Chongqing Normal University
Zhen-Ping Yang: Shanghai University
Gui-Hua Lin: Shanghai University

Journal of Optimization Theory and Applications, 2019, vol. 183, issue 3, No 13, 1053-1076

Abstract: Abstract In this paper, we consider a stochastic variational inequality, in which the mapping involved is an expectation of a given random function. Inspired by the work of He (Appl Math Optim 35:69–76, 1997) and the extragradient method proposed by Iusem et al. (SIAM J Optim 29:175–206, 2019), we propose an infeasible projection algorithm with line search scheme, which can be viewed as a modification of the above-mentioned method of Iusem et al. In particular, in the correction step, we replace the projection by computing search direction and stepsize, that is, we need only one projection at each iteration, while the method of Iusem et al. requires two projections at each iteration. Moreover, we use dynamic sampled scheme with line search to cope with the absence of Lipschitz constant and choose the stepsize to be bounded away from zero and the direction to be a descent direction. In the process of stochastic approximation, we iteratively reduce the variance of a stochastic error. Under appropriate assumptions, we derive some properties related to convergence, convergence rate, and oracle complexity. In particular, compared with the method of Iusem et al., our method uses less projections and has the same iteration complexity, which, however, has a higher oracle complexity for a given tolerance in a finite dimensional space. Finally, we report some numerical experiments to show its efficiency.

Keywords: Stochastic variational inequality; Infeasible projection algorithm; Stochastic approximation; Convergence rate; Oracle complexity; 65K15; 90C33; 90C15 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-019-01578-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:183:y:2019:i:3:d:10.1007_s10957-019-01578-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-019-01578-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().