No Access

Variance-Based Modified Backward-Forward Algorithm with Line Search for Stochastic Variational Inequality Problems and Its Applications

Zhen-Ping Yang

School of Management, Shanghai University, Shanghai 200444, P. R. China

E-mail Address: yangzhenping1026@163.com

Search for more papers by this author

Yuliang Wang

Department of Mathematics, Hong Kong Baptist University, Hong Kong 999077, P. R. China

HKBU Institute of Research and Continuing Education, Shenzhen 518000, P. R. China

E-mail Address: jadelightking@qq.com

Search for more papers by this author

, and

Gui-Hua Lin

School of Management, Shanghai University, Shanghai 200444, P. R. China

E-mail Address: guihualin@shu.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0217595920500116Cited by:10 (Source: Crossref)

Abstract

We propose a variance-based modified backward-forward algorithm with a stochastic approximation version of Armijo’s line search, which is robust with respect to an unknown Lipschitz constant, for solving a class of stochastic variational inequality problems. A salient feature of the proposed algorithm is to compute only one projection and two independent queries of a stochastic oracle at each iteration. We analyze the proposed algorithm for its asymptotic convergence, sublinear convergence rate in terms of the mean natural residual function, and optimal oracle complexity under moderate conditions. We also discuss the linear convergence rate with finite computational budget for the proposed algorithm without strong monotonicity. Preliminary numerical experiments indicate that the proposed algorithm is competitive with some existing algorithms. Furthermore, we consider an application in dealing with an equilibrium problem in stochastic natural gas trading market.

Keywords:

References

Adeosun, TA, OA Olatunde, JO Aderohunmu and TO Ogunjare (2009). Development of unsteady-state Weymouth equations for gas volumetric flow rate in horizontal and inclined pipes. Journal of Natural Gas Science and Engineering, 1, 113–117. Web of Science, Google Scholar
Bot, RI, ER Csetnek and PT Vuong (2018). The forward-backward-forward method from discrete and continuous perspective for pseudo-monotone variational inequalities in Hilbert spaces. https://arxiv.org/abs/1808.08084. Google Scholar
Burkholder, DL, BJ Davis and RF Gundy (1972). Integral inequalities for convex functions of operators on martingales. Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, 223–240. Google Scholar
Cai, XJ, GY Gu and BS He (2014). On the $O (1 / t)$ convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators. Computational Optimization and Applications, 57(2), 339–363. Web of Science, Google Scholar
Chen, YM, GH Lan and YY Ouyang (2017). Accelerated schemes for a class of variational inequalities. Mathematical Programming, 165(1), 113–149. Web of Science, Google Scholar
Cui, SS and UV Shanbhag (2016). On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems. IEEE Conference on Decision and Control, 4510–4515. Google Scholar
Demiguel, V and HF Xu (2009). A stochastic multiple leader Stackelberg model: Analysis, computation, and application. Operations Research, 57(5), 1220–1235. Web of Science, Google Scholar
Devine, MT, SA Gabriel and S Moryadee (2016). A rolling horizon approach for stochastic mixed complementarity problems with endogenous learning: Application to natural gas markets. Computers & Operations Research, 68, 1–15. Web of Science, Google Scholar
Facchinei, F and JS Pang (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems, I and II. Springer, New York Press. Google Scholar
Gabriel, SA, S Kiet and JF Zhuang (2005). A mixed complementarity-based equilibrium model of natural gas markets. Operations Research, 53(5), 799–818. Web of Science, Google Scholar
Gabriel, SA, JF Zhuang and R Egging (2009). Solving stochastic complementarity problems in energy market modeling using scenario reduction. European Journal of Operational Research, 197, 1028–1040. Web of Science, Google Scholar
Gürkan, G, A Özge and SM Robonson (1999). Sample-path solution of stochastic variational inequalities. Mathematical Programming, 84, 313–333. Web of Science, Google Scholar
Iusem, AN, A Jofré, RI Oliveira and P Thompsn (2017). Extragradient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2), 1143–1153. Web of Science, Google Scholar
Iusem, AN, A Jofré, RI Oliveira and P Thompsn (2019). Variance-based extragradient methods with line search for stochastic variational inequalities. SIAM Journal on Optimization, 29(1), 175–206. Web of Science, Google Scholar
Iusem, AN, A Jofré and Thompsn P (2019). Incremental constraint projection methods for monotone stochastic variational inequalities. Mathematics of Operations Research, 44(1), 236–263. Web of Science, Google Scholar
Jadamba, B and F Raciti (2015). Variational inequality approach to stochastic Nash equilibrium problems with an application to Cournot oligopoly. Journal of Optimization Theory and Applications, 165, 1050–1070. Web of Science, Google Scholar
Jalilzadeh, A and UV Shanbhag (2016). eg-VSSA: An extragradient variable sample-size stochastic approximation scheme: Error analysis and complexity trade-offs. Proceedings of the 2016 Winter Simulation Conference, 690–701. Google Scholar
Jiang, HY and HF Xu (2008). Stochastic approximation approaches to the stochastic variational inequality problem. IEEE Transactions on Automatic Control, 53(6), 1462–1475. Web of Science, Google Scholar
Kannan, A and UV Shanbhag (2014). The pseudomonotone stochastic variational inequality problem: Analytical statements and stochastic extragradient schemes. Presented at the American Control Conference, Portland, pp. 2930–2935. Google Scholar
Kannan, A and UV Shanbhag (2019). Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74, 779–820. Web of Science, Google Scholar
Koshal, J, A Nedić and UV Shanbhag (2013). Regularized iterative stochastic approximation methods for stochastic variational inequality problems. IEEE Transactions on Automatic Control, 58(3), 594–609. Web of Science, Google Scholar
Lei, JL and UV Shanbhag (2018). Linearly convergent variable sample-size schemes for stochastic Nash games: Best-response schemes and distributed gradient-response schemes. IEEE Conference on Decision and Control, 3547–3552. Google Scholar
Lin, GH and M Fukushima (2010). Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: A survey. Pacific Journal of Optimization, 6, 455–482. Web of Science, Google Scholar
Lin, GH, MJ Luo, DL Zhang and J Zhang (2017). Stochastic second-order-cone complementarity problems: Expected residual minimization formulation and its applications. Mathematical Programming, 165(1), 197–233. Web of Science, Google Scholar
Mertikopoulos, P and ZY Zhou (2019). Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173(1–2), 465–507. Web of Science, Google Scholar
Ravat, U and UV Shanbhag (2011). On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games. SIAM Journal on Optimization, 21(3), 1168–1199. Web of Science, Google Scholar
Robbins, H and S Monro (1951). A stochastic approximation method. The Annals of Mathematical Statistics, 22, 400–407. Web of Science, Google Scholar
Polyak, B (1987). Introduction to Optimisation New York: Optimization Software Press. Google Scholar
Shanbhag, UV (2013). Stochastic variational inequality problems: Applications, analysis, and algorithms. INFORMS Tutorials in Operations Research, 71–107. Google Scholar
Shanbhag, UV and J Blanchet (2015). Budget-constrained stochastic approximation. Proceedings of the 2015 Winter Simulation Conference, 368–379. Google Scholar
Shapiro, A, D Dentcheva and A Ruszczynski (2009). Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia Press. Google Scholar
Solodov, MV and BF Svaiter (1999). A new projection method for variational inequality problems. SIAM Journal on Control Optimization, 37(3), 765–776. Web of Science, Google Scholar
Tseng, P (2000). A modified forward-backward splitting method for maximal monotone mapping. SIAM Journal on Control and Optimization, 38(2), 431–446. Web of Science, Google Scholar
Wang, M and DP Bertsekas (2015). Incremental constraint projection methods for variational inequalities. Mathematical Programming, 150(2), 321–363. Web of Science, Google Scholar
Wang, MZ, GH Lin, YL Gao and MM Ali (2011). Sample average approximation method for a class of stochastic variational inequality problems. Journal of Systems Science and Complexity, 24, 1143–1153. Web of Science, Google Scholar
Wu, S, RZ Ríos-Mercado, EA Botd and LR Scott (2000). Model relaxations for the fuel cost minimization of steady-state gas pipeline networks. Mathematical and Computer Modelling, 31, 197–220. Web of Science, Google Scholar
Xiao, L and T Zhang (2014). A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4), 2057–2075. Web of Science, Google Scholar
Xu, HF (2010). Sample average approximation methods for a class of stochastic variational inequality problems. Asia-Pacific Journal of Operational Research, 27(1), 103–119. Link, Web of Science, Google Scholar
Yang, ZP, J Zhang, X Zhu and GH Lin (2019). Infeasible interior-point algorithms based on sampling average approximations for a class of stochastic complementarity problems and their applications. Journal of Computational and Applied Mathematics, 352, 382–400. Web of Science, Google Scholar
Yousefian, F, A Nedić and UV Shanbhag (2017). On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems. Mathematical Programming, 165, 391–431. Web of Science, Google Scholar
Yousefian, F, A Nedić and UV Shanbhag (2018). On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: Randomized block coordinate and optimal averaging schemes. Set-Valued and Variational Analysis, 26(4), 789–819. Web of Science, Google Scholar
Yousefian, F, A Nedić and UV Shanbhag (2014). Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems. IEEE Conference on Decision and Control, 5831–5836. Google Scholar
Yousefian, F, A Nedić and UV Shanbhag (2016). Self-tuned stochastic approximation schemes for non-Lipschitzian stochastic multi-user optimization and Nash games. IEEE Transactions on Automatic Control, 61(7), 1753–1766. Web of Science, Google Scholar
Zhang, XJ, XW Du, ZP Yang and GH Lin (2019). An infeasible stochastic approximation and projection algorithm for stochastic variational inequalities. Journal of Optimization Theory and Applications, 183, 1053–1076. Web of Science, Google Scholar
Zhuang, J and SA Gabriel (2008). A complementarity model for solving stochastic natural gas market equilibria. Energy Economics, 30, 113–147. Web of Science, Google Scholar