×

zbMATH — the first resource for mathematics

Generalized conditioning based approaches to computing confidence intervals for solutions to stochastic variational inequalities. (English) Zbl 07047585
Summary: Stochastic variational inequalities (SVI) provide a unified framework for the study of a general class of nonlinear optimization and Nash-type equilibrium problems with uncertain model data. Often the true solution to an SVI cannot be found directly and must be approximated. This paper considers the use of a sample average approximation (SAA), and proposes a new method to compute confidence intervals for individual components of the true SVI solution based on the asymptotic distribution of SAA solutions. We estimate the asymptotic distribution based on one SAA solution instead of generating multiple SAA solutions, and can handle inequality constraints without requiring the strict complementarity condition in the standard nonlinear programming setting. The method in this paper uses the confidence regions to guide the selection of a single piece of a piecewise linear function that governs the asymptotic distribution of SAA solutions, and does not rely on convergence rates of the SAA solutions in probability. It also provides options to control the computation procedure and investigate effects of certain key estimates on the intervals.

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:
mvtnorm; SUTIL
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. Technical Report ANL/MCS-P1964-1011, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL (2011)
[3] Attouch, H.; Cominetti, R.; Teboulle, M., Forward: Special issue on nonlinear convex optimization and variational inequalities, Math. Program., 116, 1-3, (2009)
[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 (2015) (preprint) · 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] Dentcheva, D.; Römisch, W., Differential stability of two-stage stochastic programs, SIAM J. Optim., 11, 87-112, (2000) · Zbl 0999.90042
[9] Dontchev, AL; Rockafellar, RT, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, SIAM J. Optim., 6, 1087-1105, (1996) · Zbl 0899.49004
[10] Dupacova, J.; Wets, R., Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems, Ann. Stat., 16, 1517-1549, (1988) · Zbl 0667.62018
[11] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003) · Zbl 1062.90001
[12] Fang, H.; Chen, X.; Fukushima, M., Stochastic R\(_0\) matrix linear complementarity problems, SIAM J. Optim., 18, 482-506, (2007) · Zbl 1151.90052
[13] Ferris, M.C., Pang, J.S.: Complementarity and Variational Problems: State of the Art. SIAM, Philadelphia (1997) · Zbl 0863.00054
[14] Ferris, MC; Pang, JS, Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713, (1997) · Zbl 0891.90158
[15] Genz, A., Bretz, F.: Computation of Multivariate Normal and t Probabilities. Lecture Notes in Statistics. Springer, Heidelberg (2009) · Zbl 1204.62088
[16] 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
[17] Giannessi, F., Maugeri, A. (eds.): Variational Inequalities and Network Equilibrium Problems. Plenum Press, New York (1995) · Zbl 0847.49008
[18] Giannessi, F., Maugeri, A., Pardalos, P.M. (eds.): Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models. Nonconvex optimization and its applications, vol. 58. Kluwer Academic Publishers, Dordrecht (2001) · Zbl 0992.49001
[19] Gürkan, G.; Pang, JS, Approximations of Nash equilibria, Math. Program., 117, 223-253, (2009) · Zbl 1216.91003
[20] Gürkan, G.; Yonca Özge, A.; Robinson, SM, Sample-path solution of stochastic variational inequalities, Math. Program., 84, 313-333, (1999) · Zbl 0972.90079
[21] 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
[22] Haurie, A., Zaccour, G., Legrand, J., Smeers, Y.: A stochastic dynamic nash-cournot model for the European gas market. Technical Report G-87-24, École des hautes études commerciales, Montréal, Québec, Canada (1987)
[23] Huber, P.: The behavior of maximum likelihood estimates under nonstandard conditions. In: LeCam L., Neyman J. (eds.) Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics, pp. 221-233. University of California Press, Berkeley, CA (1967)
[24] Jiang, H.; Xu, H., Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Trans. Autom. Control, 53, 1462-1475, (2008) · Zbl 1367.90072
[25] King, AJ; Rockafellar, RT, Asymptotic theory for solutions in statistical estimation and stochastic programming, Math. Oper. Res., 18, 148-162, (1993) · Zbl 0798.90115
[26] Lamm, M.; Lu, S.; Budhiraja, A., Individual confidence intervals for true solutions to expected value formulations stochastic variational inequalities, Math. Prog. Ser. B, 165, 151-196, (2017) · Zbl 1386.90159
[27] Lan, G.; Nemirovski, A.; Shapiro, A., Validation analysis of mirror descent stochastic approximation method, Math. Program., 134, 425-458, (2012) · Zbl 1273.90154
[28] Linderoth, J.; Shapiro, A.; Wright, S., The empirical behavior of sampling methods for stochastic programming, Ann. Oper. Res., 142, 215-241, (2006) · Zbl 1122.90391
[29] Lu, S., A new method to build confidence regions for solutions of stochastic variational inequalities, Optimization, 63, 1431-1443, (2014) · Zbl 1295.90093
[30] 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
[31] Lu, S.; Budhiraja, A., Confidence regions for stochastic variational inequalities, Math. Oper. Res., 38, 545-568, (2013) · Zbl 1291.90262
[32] Lu, S.; Liu, Y.; Yin, L.; Zhang, K., Confidence intervals and retions for the lasso by using stochastic variational inequality techniques in optimization, J. R. Stat. Soc. Ser. B, 79, 589-611, (2017)
[33] Luo, M.; Lin, G., Expected residual minimization method for stochastic variational inequality problems, J. Optim. Theory Appl., 140, 103-116, (2009) · Zbl 1190.90112
[34] Pang, J., Newton’s method for B-differentiable equations, Math. Oper. Res., 15, 311-341, (1990) · Zbl 0716.90090
[35] Pang, JS; Ralph, D., Forward: Special issue on nonlinear programming, variational inequalities, and stochastic programming, Math. Program., 117, 1-4, (2009)
[36] Phelps, C.; Royset, JO; Gong, Q., Optimal control of uncertain systems using sample average approximations, SIAM J. Control Optim., 54, 1-29, (2016) · Zbl 1334.49078
[37] Ralph, D., On branching numbers of normal manifolds, Nonlinear Anal. Theory Methods Appl., 22, 1041-1050, (1994) · Zbl 0830.57014
[38] Robinson, SM, Strongly regular generalized equations, Math. Oper. Res., 5, 43-62, (1980) · Zbl 0437.90094
[39] Robinson, SM, An implicit-function theorem for a class of nonsmooth functions, Math. Oper. Res., 16, 292-309, (1991) · Zbl 0746.46039
[40] Robinson, SM, Normal maps induced by linear transformations, Math. Oper. Res., 17, 691-714, (1992) · Zbl 0777.90063
[41] 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
[42] Rockafellar, RT; Wets, RJB, Stochastic variational inequalities: single-stage to multistage, Math. Program. Ser. B, 165, 331-360, (2017) · Zbl 1378.49010
[43] Römisch, W.; Ruszczyński, A. (ed.); Shapiro, A. (ed.), Stability of stochastic programming problems, No. 10, 483-554, (2003), Amsterdam
[44] Scholtes, S.: Introduction to Piecewise Differentiable Equations. Springer, New York (2012) · Zbl 1453.49002
[45] Shapiro, A., Asymptotic behavior of optimal solutions in stochastic programming, Math. Oper. Res., 18, 829-845, (1993) · Zbl 0804.90101
[46] 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)
[47] Shapiro, A.; Homem-de Mello, T., On the rate of convergence of optimal solutions of monte carlo approximations of stochastic programs, SIAM J. Optim., 11, 70-86, (2000) · Zbl 0999.90023
[48] Shapiro, A.; Xu, H., Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation, Optimization, 57, 395-418, (2008) · Zbl 1145.90047
[49] Stefanski, LA; Boos, DD, The calculus of M-estimation, Am. Stat., 56, 29-38, (2002)
[50] Vogel, S., Universal confidence sets for solutions of optimization problems, SIAM J. Optim., 19, 1467-1488, (2008) · Zbl 1198.90310
[51] Wald, A., Note on the consitency of the maximum likelihood estimate, Ann. Math. Stat., 20, 595-601, (1949) · Zbl 0034.22902
[52] 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
[53] Yin, L., Lu, S., Liu, Y.: Confidence intervals for sparse penalized regression with random designs (2015) (submitted for publication)
[54] 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.