×

zbMATH — the first resource for mathematics

Individual confidence intervals for solutions to expected value formulations of stochastic variational inequalities. (English) Zbl 1386.90159
Summary: Stochastic variational inequalities (SVIs) provide a means for modeling various optimization and equilibrium problems where data are subject to uncertainty. Often the SVI cannot be solved directly and requires a numerical approximation. This paper considers the use of a sample average approximation and proposes three methods for computing confidence intervals for components of the true solution. The first two methods use an “indirect approach” that requires initially computing asymptotically exact confidence intervals for the solution to the normal map formulation of the SVI. The third method directly constructs confidence intervals for the true SVI solution; intervals produced with this method meet a minimum specified level of confidence in the same situations for which the first two methods are applicable. We justify the three methods theoretically with weak convergence results, discuss how to implement these methods, and test their performance using three numerical examples.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C15 Stochastic programming
65K10 Numerical optimization and variational techniques
62F25 Parametric tolerance and confidence regions
Software:
MCPLIB; mvtnorm
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agdeppa, RP; 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] Anitescu, M., Petra, C.: Higher-order confidence intervals for stochastic programming using bootstrapping. Tech. Rep. ANL/MCS-P1964-1011, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL (2011) · Zbl 0746.46039
[3] Attouch, H., Cominetti, R., Teboulle, M. (eds.): Special Issue on Nonlinear Convex Optimization and Variational Inequalities. Springer (2009). Mathematical Programming 116, Numbers 1-2
[4] Chen, X; Fukushima, M, Expected residual minimization method for stochastic linear complementarity problems, Math. Oper. Res., 30, 1022-1038, (2005) · Zbl 1162.90527
[5] Chen, X., Pong, T.K., Wets, R.J.B.: Two-stage stochastic variational inequalities: an ERM-solution procedure. Preprint (2015) · Zbl 1386.90157
[6] Chen, X; Wets, RJB; Zhang, Y, Stochastic variational inequalities: residual minimization smoothing sample average approximations, SIAM J. Optim., 22, 649-673, (2012) · Zbl 1263.90098
[7] Chen, X; Zhang, C; Fukushima, M, Robust solution of monotone stochastic linear complementarity problems, Math. Program., 117, 51-80, (2009) · Zbl 1165.90012
[8] Chen, Y., Lan, G., Yuyuan, O.: Accelerated schemes for a class of variational inequalities. Submitted (2014) · Zbl 1386.90102
[9] Demir, M.C.: Asymptotics and confidence regions for stochastic variational inequalities. Ph.D. thesis, University of Wisconsin, Madison (2000) · Zbl 0716.90090
[10] Dirkse, SP; Ferris, MC, Mcplib: A collection of nonlinear mixed complementarity problems, Opt. Methods Softw., 5, 319-345, (1995)
[11] Dupacova, J., Wets, R.: Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems. Ann. Stat. 16(4), 1517-1549 (1988) · Zbl 0667.62018
[12] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003) · Zbl 1062.90002
[13] Fang, H; Chen, X; Fukushima, M, Stochastic R\(_0\) matrix linear complementarity problems, SIAM J. Optim., 18, 482-506, (2007) · Zbl 1151.90052
[14] Ferris, M.C., Pang, J.S.: Complementarity and Variational Problems: State of the Art. SIAM, Philadelphia (1997) · Zbl 0891.90158
[15] Ferris, MC; Pang, JS, Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713, (1997) · Zbl 0891.90158
[16] Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gümüs, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization, vol. 33. Springer, New York (1999) · Zbl 0943.90001
[17] Genz, A., Bretz, F.: Computation of Multivariate Normal and t Probabilities. Lecture Notes in Statistics. Springer, Heidelberg (2009) · Zbl 1204.62088
[18] Genz, A., Bretz, F., Miwa, T., Mi, X., Leisch, F., Scheipl, F., Hothorn, T.: mvtnorm: Multivariate Normal and t Distributions (2013). http://CRAN.R-project.org/package=mvtnorm.R package version 0.9-9996
[19] Giannessi, F., Maugeri, A. (eds.): Variational Inequalities and Network Equilibrium Problems. Plenum Press, New York (1995) · Zbl 0844.90069
[20] Giannessi, F., Maugeri, A., Pardalos, P.M. (eds.): Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models, Nonconvex Optimization and Its Applications, vol. 58. Springer, New York · Zbl 0979.00025
[21] Gürkan, G; Pang, JS, Approximations of Nash equilibria, Math. Program., 117, 223-253, (2009) · Zbl 1216.91003
[22] Gürkan, G; Yonca Özge, A; Robinson, SM, Sample-path solution of stochastic variational inequalities, Math. Program., 84, 313-333, (1999) · Zbl 0972.90079
[23] Hansen, T; Koopmans, TC, On the definition and computation of a capital stock invariant under optimization, J. Econ. Theory, 5, 487-523, (1972) · Zbl 0266.90018
[24] Harker, PT; Pang, JS, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms, and applications, Math. Program., 48, 161-220, (1990) · Zbl 0734.90098
[25] Huber, P.: The behavior of maximum likelihood estimates under nonstandard conditions. In: LeCam, L., Neyman, J. (eds.) Proceedings of the 5th Berkeley Symposium on Mathematical Statistics, pp. 221-233. University of California Press, Berkeley, (1967) · Zbl 0212.21504
[26] Jiang, H; Huifu, X, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Trans. Autom. Control, 53, 1462-1475, (2008) · Zbl 1367.90072
[27] Juditsky, A; Nemirovski, A; Tauvel, C, Solving variational inequalities with stochastic mirror-prox algorithm, Stoch. Syst., 1, 17-58, (2011) · Zbl 1291.49006
[28] King, AJ; Rockafellar, RT, Asymptotic theory for solutions in statistical estimation and stochastic programming, Math. Oper. Res., 18, 148-162, (1993) · Zbl 0798.90115
[29] Koshal, J; Nedic̀, A; Shanbhag, UV, Regularized iterative stochastic approximation methods for stochastic variational inequality problems, IEEE Trans. Autom. Control, 58, 594-609, (2013) · Zbl 1369.49012
[30] Lu, S.: A new method to build confidence regions for solutions of stochastic variational inequalities. Optimization (2012). Published online before print at http://www.tandfonline.com. doi:10.1080/02331934.2012.727556 · Zbl 0734.90098
[31] Lu, S.: Symmetric confidence regions and confidence intervals for normal map formulations of stochastic variational inequalities. SIAM J. Opt. 24(3), 1458-1484 (2014) · Zbl 1304.49022
[32] Lu, S; Budhiraja, A, Confidence regions for stochastic variational inequalities, Math. Oper. Res., 38, 545-568, (2013) · Zbl 1291.90262
[33] Lu, S., Liu, Y., Yin, L., Zhang, K.: Confidence intervals and retions for the lasso using stochastic variational inequality techniques in optimization. J. Roy. Stat. Soc. Ser. B (2016). doi:10.1111/rssb.12184 · Zbl 1367.90072
[34] Lu, S; Robinson, SM, Normal fans of polyhedral convex sets: structures and connections, Set-valued Anal., 16, 281-305, (2008) · Zbl 1144.52008
[35] Luo, M; Lin, G, Expected residual minimization method for stochastic variational inequality problems, J. Opt. Theory Appl., 140, 103-116, (2009) · Zbl 1190.90112
[36] Nemirovski, A; Juditsky, A; Lan, G; Shapiro, A, Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19, 1574-1609, (2009) · Zbl 1189.90109
[37] Pang, J, Newton’s method for b-differentiable equations, Math. Oper. Res., 15, 311-341, (1990) · Zbl 0716.90090
[38] Pang, J.S., Ralph, D. (eds.): Special Issue on Nonlinear Programming, Variational Inequalities, and Stochastic Programming. Springer (2009). Mathematical Programming 117, Numbers 1-2 · Zbl 1186.90083
[39] Polyak, BT, New stochastic approximation type procedures, Avtomatica i Telemekhanika, 7, 98-107, (1990)
[40] Polyak, BT; Juditsky, AB, Acceleration of stochastic approximation by averaging, SIAM J. Control Opt., 30, 838-855, (1992) · Zbl 0762.62022
[41] Ralph, D, On branching numbers of normal manifolds, Nonlinear Anal. Theory Methods Appl., 22, 1041-1050, (1994) · Zbl 0830.57014
[42] Ravat, U., Shanbhag, U.V.: On the existence of soulutions to quasi-variational inequality and complementarity problems. Preprint (2015) · Zbl 1375.90231
[43] Robbins, H; Monro, S, A stochastic approximation method, Ann. Math. Stat., 22, 400-407, (1951) · Zbl 0054.05901
[44] Robinson, SM, An implicit-function theorem for a class of nonsmooth functions, Math. Oper. Res., 16, 292-309, (1991) · Zbl 0746.46039
[45] Robinson, SM, Normal maps induced by linear transformations, Math. Oper. Res., 17, 691-714, (1992) · Zbl 0777.90063
[46] Robinson, SM; Giannessi, F (ed.); Maugeri, A (ed.), Sensitivity analysis of variational inequalities by normal-map techniques, 257-269, (1995), New York · Zbl 0861.49009
[47] Rockafellar, R.T., Wets, R.: Variational Analysis, A Series of Comprehensive Studies in Mathematics, vol. 317. Springer-Verlag, Berlin (2009)
[48] Rockafellar, R.T., Wets, R.J.B.: Stochastic variational inequalities: Single-stage to multistage. Math. Program. (2016). doi:10.1007/s10107-016-0995-5 · Zbl 1378.49010
[49] Scholtes, S, A proof of the branching number bound for normal manifolds, Linear Algebra Appl., 246, 83-95, (1996) · Zbl 0868.52003
[50] Scholtes, S.: Introduction to Piecewise Differentiable Equations. Springer, New York (2012) · Zbl 1453.49002
[51] Shapiro, A., Dentcheva, D., Ruszczyński, A.P.: Lectures on Stochastic Programming: Modeling and Theory. Society for Industrial and Applied Mathematics and Mathematical Programming Society, Philadelphia, PA (2009) · Zbl 0762.62022
[52] Shapiro, A; Xu, H, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation, Optimization, 57, 395-418, (2008) · Zbl 1145.90047
[53] Stefanski, LA; Boos, DD, The calculus of M-estimation, Am. Stat., 56, 29-38, (2002)
[54] Vogel, S, Universal confidence sets for solutions of optimization problems, SIAM J. Optim., 19, 1467-1488, (2008) · Zbl 1198.90310
[55] Wald, A, Note on the consitency of the maximum likelihood estimate, Ann. Math. Stat., 20, 595-601, (1949) · Zbl 0034.22902
[56] Xu, H, Sample average approximation methods for a class of stochastic variational inequality problems, Asia-Pac. J. Oper. Res., 27, 103-119, (2010) · Zbl 1186.90083
[57] Yin, L., Lu, S., Liu, Y.: Confidence intervals for sparse penalized regression with random designs. Submitted for publication (2015) · Zbl 0830.57014
[58] Zhang, C; Chen, X; Sumlee, A, Robust wardrop’s user equilibrium assignment under stochastic demand and supply, 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.