×

zbMATH — the first resource for mathematics

Two-stage stochastic variational inequalities: an ERM-solution procedure. (English) Zbl 1386.90157
Summary: We propose a two-stage stochastic variational inequality model to deal with random variables in variational inequalities, and formulate this model as a two-stage stochastic programming with recourse by using an expected residual minimization solution procedure. The solvability, differentiability and convexity of the two-stage stochastic programming and the convergence of its sample average approximation are established. Examples of this model are given, including the optimality conditions for stochastic programs, a Walras equilibrium problem and Wardrop flow equilibrium. We also formulate stochastic traffic assignments on arcs flow as a two-stage stochastic variational inequality based on Wardrop flow equilibrium and present numerical results of the Douglas-Rachford splitting method for the corresponding two-stage stochastic programming with recourse.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C15 Stochastic programming
Software:
PATH Solver
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agdeppa, R; Yamashita, N; Fukushima, M, Convex expected residual models for stochastic affine variational inequality problems and its application to the traffic equilibrium problem, Pac. J. Optim., 6, 3-19, (2010) · Zbl 1193.65107
[2] Attouch, H; Wets, R, Epigraphical processes: laws of large numbers for random lsc functions, Sémin. d’Anal. Convexe, 13, 1-29, (1990) · Zbl 0744.60021
[3] Bauschke, H., Combettes, P.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011) · Zbl 1218.47001
[4] Beckmann, M., McGuire, C., Winsten, C.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
[5] Cruz, JYB; Iusem, A, Convergence of direct methods for paramonotone variational inequalities, Comput. Optim. Appl., 46, 247-263, (2010) · Zbl 1220.90129
[6] Birge, J., Louveaux, F.: Introduction to Stochastic Programming. Springer, London (1997) · Zbl 0892.90142
[7] Brown, D; DeMarzo, X; Eaves, BC, Computing equilibria when asset markets are incomplete, Econometrica, 64, 1-27, (1996) · Zbl 0861.90018
[8] Chen, X; Fukushima, M, Expected residual minimization method for stochastic linear complementarity problems, Math. Oper. Res., 30, 1022-1038, (2005) · Zbl 1162.90527
[9] Chen, X; Sun, H; Wets, R, Regularized mathematical programs with stochastic equilibrium constraints: estimating structural demand models, SIAM J. Optim., 25, 53-75, (2015) · Zbl 1358.90138
[10] Chen, X; Wets, R; Zhang, Y, Stochastic variational inequalities: residual minimization smoothing, SIAM J. Optim., 22, 649-673, (2012) · Zbl 1263.90098
[11] Chen, X; Ye, Y, On homotopy-smoothing methods for box constrained variational inequalities, SIAM J. Control Optim., 37, 589-616, (1999) · Zbl 0973.65051
[12] Chen, X; Zhang, C; Fukushima, M, Robust solution of monotone stochastic linear complementarity problems, Math. Program., 117, 51-80, (2009) · Zbl 1165.90012
[13] Cominetti, R, Equilibrium routing under uncertainty, Math. Program., 151, 117-151, (2015) · Zbl 1329.90027
[14] Correa, J.R., Stier-Moses, N.E.: Wardrop Equilibria. Wiley Online Library (2011) · Zbl 0377.90073
[15] Dang, C; Ye, Y; Zhu, Z, An interior-point path-following algorithm for computing a Leontief economy equilibrium, Computat. Optim. Appl., 50, 213-236, (2011) · Zbl 1236.90129
[16] Demarzo, P; Eaves, BC, Computing equilibria of GEI by relocalization on a Grassmann manifold, J. Math. Econ., 26, 479-497, (1996) · Zbl 0876.90026
[17] Deride, J., Jofré, A., Wets, R.: Solving deterministic and stochastic equilibrium problems via augmented Walrasian. Comput. Econ. (2017) · Zbl 1315.65058
[18] Dirkse, S., Ferris, M., Munson, T.: http://pages.cs.wisc.edu/ferris/path.html, 2015—the PATH solver. Technical report, University of Wisconsin (2015) · Zbl 0343.90039
[19] 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) · Zbl 0070.35401
[20] Eckstein, J; Bertsekas, D, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[21] Fachinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin (2003)
[22] Fang, H; Chen, X; Fukushima, M, Stochastic R\(_0\) matrix linear complementarity problems, SIAM J. Optim., 18, 482-506, (2007) · Zbl 1151.90052
[23] Ferris, M; Pang, J-S, Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713, (1997) · Zbl 0891.90158
[24] Ferris, M; Wets, R, MOPEC: a computationally amiable formulation of multi-agent optimization problems with global equilibrium constraints, Department of Mathematics, University of California-Davis, 63, 309-345, (2017)
[25] Fukushima, M, A relaxed projection method for variational inequalities, Math. Program., 35, 58-70, (1986) · Zbl 0598.49024
[26] Fukushima, M, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. Program., 53, 99-110, (1992) · Zbl 0756.90081
[27] Gürkan, G., Özge, A., Robinson, S.: Sample-path solution of stochastic variational inequalities with applications to option pricing. In: Charnes, J., Morrice, D., Brunner, D., Swain, J. (eds) Proceedings of the 1966 Winter Simulation Conference, pp. 337-344. INFORMS (1966) · Zbl 1190.90112
[28] Gürkan, G; Özge, A; Robinson, S, Sample-path solution of stochastic variational inequalities, Math. Program., 84, 313-333, (1999) · Zbl 0972.90079
[29] He, B; Yuan, X, On the O\((1/n)\) convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., 50, 700-709, (2012) · Zbl 1245.90084
[30] Iusem, A., Jofré, A., Thompson, P.: Approximate projection methods for monotone stochastic variational inequalities. Technical report IMPA, Rio de Janeiro (2015) · Zbl 1346.90584
[31] Iusem, A; Svaiter, B, A variant of kopelevich’s method for variational inequalities with a new search strategy, Optimization, 42, 309-321, (1997) · Zbl 0891.90135
[32] Jiang, H; Xu, H, Stochastic approximation approaches to stochastic variational inequalities, IEEE Trans. Autom. Control, 53, 1462-1475, (2008) · Zbl 1367.90072
[33] Jofré, A; Rockafellar, RT; Wets, R, Variational inequalities and economic equilibrium, Math. Oper. Res., 32, 32-50, (2007) · Zbl 1276.91070
[34] Jofré, A., Rockafellar, R.T., Wets, R.: General economic equilibirum with financial market and retainability. Economic Theory63, 309-345 (2017) · Zbl 1405.91742
[35] Juditsky, A; Nemirovski, A; Tauvel, C, Solving variational inequalities with stochastic mirror-prox algorithm, Stoch. Syst., 1, 17-58, (2011) · Zbl 1291.49006
[36] Kall, P., Wallace, S.: Stochastic Programming. Wiley, London (1995) · Zbl 0812.90122
[37] Korf, L; Wets, R, Random lsc functions: an ergodic theorem, Math. Oper. Res., 26, 421-445, (2001) · Zbl 1082.90552
[38] Lamm, M., Lu, S., Budhiraja, A: Individual confidence intervals for solutions to expected value formulations of stochastic variational inequalities. Math. Program. doi:10.1007/s10107-016-1046-y · Zbl 1386.90159
[39] Li, G; Pong, TK, Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems, Math. Program., 159, 371-401, (2016) · Zbl 1346.90584
[40] Lu, S, Confidence regions for stochastic variational inequalities, Optimization, 63, 1431-1443, (2012) · Zbl 1295.90093
[41] Lu, S, Symmetric confidence regions and confidence intervals for normal map formulations of stochastic variational inequalities, SIAM J. Optim., 24, 1458-1484, (2014) · Zbl 1304.49022
[42] Luo, M; Lin, G, Expected residual minimization method for stochastic variational inequality problems, J. Optim. Theory Appl., 140, 103-116, (2009) · Zbl 1190.90112
[43] Luo, Z., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996) · Zbl 1139.90003
[44] Marcotte, P. Patriksson, P.: Transportation, Handbooks in Operations Research and Management Science, vol. 14 of Handbooks in Operations Research and Management Science, Chapter Traffic Equilibrium, pp. 623-713. Elsevier (2007) · Zbl 1245.90084
[45] Norkin, V; Wets, R, On strong graphical law of large numbers for random semicontinuous mappings, Vestn. St.-Petersbg. Univ., 10, 102-110, (2013)
[46] Norkin, V., Wets, R., Xu, H.: Graphical Convergence of Sample Average Random Set-Valued Mappings. Mathematics, University of California, Davis (2010)
[47] Pang, J-S; Su, C-L; Lee, Y, A constructive approach to estimating pure characteristics demand models with pricing, Oper. Res., 63, 639-659, (2015) · Zbl 1377.91118
[48] Pennanen, T, Epi-convergent discretizations of multistage stochastic programs, Math. Oper. Res., 30, 245-256, (2005) · Zbl 1082.90078
[49] Pennanen, T; Koivu, M, Epi-convergent discretization of stochastic programs via integration quadratures, Numer. Math., 100, 141-163, (2005) · Zbl 1063.65047
[50] Philpott, A; Ferris, M; Wets, R, Equilibrium, uncertainty and risk in hydro-thermal electricity systems, Math. Program., 157, 483-513, (2016) · Zbl 1350.90034
[51] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[52] Rockafellar, RT; Wets, R, Stochastic convex programming: Kuhn-Tucker conditions, J. Math. Econ., 2, 349-370, (1975) · Zbl 0343.90039
[53] Rockafellar, RT; Wets, R, Nonanticipativity and \({\cal{L}}^1\)-martingales in stochastic optimization problems, Math. Program. Study, 6, 170-187, (1976) · Zbl 0377.90073
[54] Rockafellar, RT; Wets, R, Stochastic convex programming: basic duality, Pac. J. Math., 62, 173-195, (1976) · Zbl 0339.90048
[55] Rockafellar, RT; Wets, R, Stochastic convex programming: relatively complete recourse and induced feasibility, SIAM J. Control Optim., 14, 574-589, (1976) · Zbl 0346.90058
[56] Rockafellar, RT; Wets, R, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16, 119-147, (1991) · Zbl 0729.90067
[57] Rockafellar, RT; Wets, R, A dual strategy for the implementation of the aggregation principle in decision making under uncertainty, Appl. Stoch. Models Data Anal., 8, 245-255, (1992) · Zbl 0800.90002
[58] Rockafellar, R.T., Wets, R.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001
[59] Rockafellar, R.T., Wets, R.: Stochastic variational inequalities: single-stage to multistage. Math. Program. doi:10.1007/s10107-016-0995-5 · Zbl 1378.49010
[60] Shanbhag, UV; Infanger, G; Glynn, P, A complementarity framework for forward contracting under uncertainty, Oper. Res., 59, 810-834, (2011) · Zbl 1235.91074
[61] Shapiro, A.: Lectures on Stochastic Programming, Chapter 5: Statistical Inference, pp. 155-252. SIAM, Philadelphia (2009) · Zbl 1183.90005
[62] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming-Modeling and Theory. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2009) · Zbl 1183.90005
[63] Shapiro, A; Xu, H, Uniform laws of large numbers for set-valued mappings and subdifferentials of random functions, J. Math. Anal. Appl., 325, 1390-1399, (2007) · Zbl 1109.60030
[64] Sun, D; Toh, K-C; Yang, L, A convergent 3-block semi-proximal alternating irection method of multipliers for conic programming with 4-type of constraints, SIAM J. Optim., 25, 882-915, (2015) · Zbl 1328.90083
[65] Slyke, R; Wets, R, L-shaped linear programs with application to optimal control and stochastic programming, SIAM J. Appl. Math., 17, 638-663, (1969) · Zbl 0197.45602
[66] Wang, M; Bertsekas, D, Incremental constraint projection methods for variational inequalities, Math. Program., 150, 321-363, (2015) · Zbl 1315.65058
[67] Xie, Y; Shanbhag, UV, On robust solutions to uncertain linear complementarity problems and their variants, SIAM J. Optim., 26, 2120-2159, (2016) · Zbl 1366.90151
[68] Yang, H, Sensitivity analysis for the elastic-demand network equilibrium problem with applications, Transp. Res. B, 31, 55-70, (1997)
[69] Yin, Y; Madanat, S; Lu, X-Y, Robust improvement schemes for road networks under demand uncertainty, Eur. J. Oper. Res., 198, 470-479, (2009) · Zbl 1163.90378
[70] Zhang, C; Chen, X; Sumalee, A, Robust wardrop’s user equilibrium assignment under stochastic demand and supply: expected residual minimization approach, Transp. Res. B, 45, 534-552, (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.