Two-Stage Stochastic Variational Inequalities: Theory, Algorithms and Applications

doi:10.1007/s40305-019-00267-8

Abstract

Abstract: The stochastic variational inequality (SVI) provides a unified form of optimality conditions of stochastic optimization and stochastic games which have wide applications in science, engineering, economics and finance. In the recent two decades, one-stage SVI has been studied extensively and widely used in modeling equilibrium problems under uncertainty. Moreover, the recently proposed two-stage SVI and multistage SVI can be applied to the case when the decision makers want to make decisions at different stages in a stochastic environment. The two-stage SVI is a foundation of multistage SVI, which is to find a pair of “here-and-now” solution and “wait-and-see” solution. This paper provides a survey of recent developments in analysis, algorithms and applications of the two-stage SVI.

Key words: Two-stage stochastic variational inequality, Two-stage stochastic complementary problem, Two-stage stochastic games

CLC Number:

90C15
90C33

Hai-Lin Sun, Xiao-Jun Chen. Two-Stage Stochastic Variational Inequalities: Theory, Algorithms and Applications[J]. Journal of the Operations Research Society of China, 2021, 9(1): 1-32.

TrendMD

References

[1] Cottle, R.W., Pang, J.S., Stone, R.E.:The Linear Complementarity Problem. Academic Press, New York (1992)
[2] Facchinei, F., Pang, J.S.:Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
[3] Lin, G.H., Fukushima, M.:Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints:a survey. Pac. J. Optim. 6, 455-482(2010)
[4] Shanbhag, U.:Stochastic variational inequality problems:applications, analysis, and algorithms. In:INFORMS Tutorials in Operations Research. pp. 71-107(2013)
[5] Chen, X., Wets, R.J.-B.:Special Issue:Stochastic Equilibrium and Variational Inequalities. Math. Program. 165(2017)
[6] Chen, X., Fukushima, M.:Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 1022-1038(2005)
[7] Chen, X., Zhang, C., Fukushima, M.:Robust solution of monotone stochastic linear complementarity problems. Math. Program. 117, 51-80(2009)
[8] Ling, C., Qi, L., Zhou, G., Caccetta, L.:The SC1 property of an expected residual function arising from stochastic complementarity problems. Oper. Res. Lett. 36, 456-460(2008)
[9] Luo, M.J., Lin, G.H.:Expected residual minimization method for stochastic variational inequality problems. J. Optim. Theory Appl. 140, 103-116(2009)
[10] Zhang, C., Chen, X.:Smoothing projected gradient method and its application to stochastic linear complementarity problems. SIAM J. Optim. 20, 627-649(2009)
[11] Chen, X., Wets, R.J.-B., Zhang, Y.:Stochastic variational inequalities:residual minimization smoothing sample average approximations. SIAM J. Optim. 22, 649-673(2012)
[12] King, A.J., Rockafellar, R.T.:Asymptotic theory for solutions in statistical estimation and stochastic programming. Math. Oper. Res. 18, 148-162(1993)
[13] Jiang, H., Xu, H.:Stochastic approximation approaches to the stochastic variational inequality problem. IEEE Trans. Autom. Control 53, 1462-1475(2008)
[14] Ravat, U., Shanbhag, U.V.:On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games. SIAM J. Optim. 21, 1168-1199(2011)
[15] Gürkan, G., Özge, A.Y., Robinson, S.M.:Sample-path solution of stochastic variational inequalities. Math. Program. 84, 313-333(1999)
[16] Fukushima, M.:Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99-110(1992)
[17] Rockafellar, R.T., Uryasev, S.:Optimization of conditional value-at-risk. J. Risk 2, 21-41(2000)
[18] Tibshirani, R., Saunders, M., Rosset, S., Zhu, Ji:Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. B 67, 91-108(2005)
[19] Ralph, D., Xu, H.:Convergence of stationary points of sample average two stage stochastic programs:a generalized equation approach. Math. Oper. Res. 36, 568-592(2011)
[20] Chen, X., Pong, T.K., Wets, R.J.-B.:Two-stage stochastic variational inequalities:an ERM-solution procedure. Math. Program. 165, 71-111(2017)
[21] Luo, Z., Pang, J.S., Ralph, D.:Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
[22] Rockafellar, R.T., Wets, R.J.-B.:Stochastic variational inequalities:single-stage to multistage. Math. Program. 165, 331-360(2017)
[23] Rockafellar, R.T., Sun, J.:Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging. Math. Program. 174, 453-471(2018)
[24] Rockafellar R. T., Sun, J.:Solving lagrangian variational inequalities with applications to stochastic programming, Manuscripts (2018)
[25] Van Slyke, R., Wets, R.:L-shaped linear programs with application to optimal control and stochastic programming. SIAM J. Appl. Math. 17, 638-663(1969)
[26] Rockafellar, R.T., Wets, R.:Variational Analysis. Springer, Berlin (1998)
[27] Douglas, J., Rachford, H.:On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 82, 421-439(1956)
[28] Li, G., Pong, T.K.:Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Program. 159, 371-401(2016)
[29] Rockafellar, R.T., Wets, R.J.-B.:Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16, 235-290(1991)
[30] Chen, X., Sun, H., Xu, H.:Discrete approximation of two-stage stochastic and distributionally robust linear complementarity problems. Math. Program. 177, 255-289(2019)
[31] Chen, X., Shapiro, A., Sun, H.:Convergence analysis of sample average approximation of two-stage stochastic generalized equations. SIAM J. Optim. 29, 135-161(2019)
[32] Clarke, F.H.:Optimization and Nonsmooth Analysis. Wiley, New York (1983)
[33] Shapiro, A., Dentcheva, D., Ruszczyński, A.:Lectures on Stochastic Programming:Modeling and Theory. MPS/SIAM Series on Optimization, vol. 9. Society for Industrial and Applied Mathematics, Philadelphia (2009)
[34] Shapiro, A., Xu, H.:Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation. Optimization 57, 395-418(2008)
[35] Xu,H.:Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming. J. Math. Anal. Appl. 368, 692-710(2010)
[36] Izmailov, A.F.:Strongly regular nonsmooth generalized equations. Math. Program. 147, 581-590(2014)
[37] Genc, T.S., Reynolds, S.S., Sen, S.:Dynamic oligopolistic games under uncertainty:a stochastic programming approach. J. Econ. Dyn. Control 31, 55-80(2007)
[38] Ehrenmann, A., Smeers, Y.:Generation capacity expansion in a risky environment:a stochastic equilibrium analysis. Oper. Res. 59, 1332-1346(2011)
[39] Gürkan, G., Ozdemir, O., Smeers, Y.:Generation capacity investments in electricity markets:perfect competition. CentER Discussion Paper, Tilburg:Econometrics, vol. 045(2013)
[40] Gürkan, G., Pang, J.S.:Approximations of Nash equilibria. Math. Program. 117, 223-253(2009)
[41] Kannan, A., Shanbhag, U.V., Kim, H.M.:Addressing supply-side risk in uncertain power markets:stochastic Nashmodels,scalable algorithms and error analysis.Optim.MethodsSoftw. 28,1095-1138(2013)
[42] Kannan, A., Shanbhag, U.V., Kim, H.M.:Strategic behavior in power markets under uncertainty. Energy Syst. 2, 115-141(2011)
[43] Yao, J., Adler, I., Oren, S.S.:Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network. Oper. Res. 56, 34-47(2008)
[44] Gabriel, S.A., Fuller, J.D.:A Benders decomposition method for solving stochastic complementarity problems with an application in energy. Comput. Econ. 35, 301-329(2010)
[45] Schiro,D.A.,Hobbs,B.F.,Pang,J.S.:Perfectly competitive capacity expansion games with risk-averse participants. Comput. Optim. Appl. 65, 511-539(2015)
[46] Jiang, J., Shi, Y., Wang, X., Chen, X.:Regularized two-stage stochastic variational inequalities for Cournot-Nash equilibrium under uncertainty. J. Comp. Math. arXiv:1907.07317(2019)
[47] Ferris, M., Pang, J.S.:Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669-713(1997)
[48] Pang, J.S., Sen, S., Shanbhag, U.V.:Two-stage non-cooperative games with risk-averse players. Math. Program. 165, 119-147(2017)