# American Institute of Mathematical Sciences

July  2014, 10(3): 977-987. doi: 10.3934/jimo.2014.10.977

## A sample average approximation method based on a D-gap function for stochastic variational inequality problems

 1 School of Science, Wuhan University of Technology, Wuhan Hubei, 430070, China, China, China

Received  January 2013 Revised  August 2013 Published  November 2013

Sample average approximation method is one of the well-behaved methods in the stochastic optimization. This paper presents a sample average approximation method based on a D-gap function for stochastic variational inequality problems. An unconstrained optimization reformulation is proposed for the expected-value formulation of stochastic variational inequality problems based on the D-gap function. An implementable sample average approximation method for the reformulation is established and it is proven that the optimal values and the optimal solutions of the approximation problems converge to their true counterpart with probability one as the sample size increases under some moderate assumptions. Finally, the preliminary numerical results for some test examples are reported, which show that the proposed method is promising.
Citation: Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977
##### References:
 [1] R. P. Agdeppa, N. Yamashita and M. Fukushima, Convex expected residual models for stochastic affine variational inequality problems and its applications to the traffic equilibrium problem, Pac. J. Optim., 6 (2010), 3-19.  Google Scholar [2] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Math. Oper. Res., 30 (2005), 1022-1038. doi: 10.1287/moor.1050.0160.  Google Scholar [3] X. Chen, R. B.-J. Wets and Y. Zhang, Stochastic variational inequalities: Residual minimization smoothing sample average approximations, SIAM J. Optimiz., 22 (2012), 649-673. doi: 10.1137/110825248.  Google Scholar [4] X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Math. Program., 117 (2009), 51-80. doi: 10.1007/s10107-007-0163-z.  Google Scholar [5] F. Y. Chen, H Yan and L Yao, A newsvendor pricing game, IEEE T. Syst. Man Cy. A, 34 (2004), 450-456. doi: 10.1109/TSMCA.2004.826290.  Google Scholar [6] S. Dafermos, Traffic equilibrium and variational inequalities, Transport. Sci., 14 (1980), 42-54. doi: 10.1287/trsc.14.1.42.  Google Scholar [7] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-varlag, New York, 2003. Google Scholar [8] H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems, SIAM J. Optimiz., 18 (2007), 482-506. doi: 10.1137/050630805.  Google Scholar [9] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. Program., 53 (1992), 99-110. doi: 10.1007/BF01585696.  Google Scholar [10] M. Fukushima, N. Yamashita and K. Taji, Unconstrained optimization reformulations of variational inequality problems, J. Optimiz. Theory App., 92 (1997), 439-456. doi: 10.1023/A:1022660704427.  Google Scholar [11] G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solution of stochastic variational inequalities, Math. Program., 84 (1999), 313-333. doi: 10.1007/s101070050024.  Google Scholar [12] H. Jiang and H. F. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE T. Automat. Contr., 53 (2008), 1462-1475. doi: 10.1109/TAC.2008.925853.  Google Scholar [13] G.-H. Lin and M. Fukushima, Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: A survey, Pac. J. Optim., 6 (2010), 455-482.  Google Scholar [14] M. J. Luo and G. H. Lin, Expected residual minimization method for stochastic variational inequality problems, J. Optimiz. Theory App., 140 (2009), 103-116. doi: 10.1007/s10957-008-9439-6.  Google Scholar [15] S. Mahajan and G. van Ryzin, Inventory competition under dynamic consumer choice, Oper. Res., 49 (2001), 646-657. doi: 10.1287/opre.49.5.646.10603.  Google Scholar [16] F. W. Meng and H. Xu, A regularized sample average approximation method for stochastic mathematical programs with nonsmooth equality constraints, SIAM J. Optimiz., 17 (2006), 891-919. doi: 10.1137/050638242.  Google Scholar [17] M. H. Ngo and V. Krishnamurthy, Game theoretic cross-layer transmission policies in multipacket reception wireless networks, IEEE T. Signal Proces., 55 (2007), 1911-1926. doi: 10.1109/TSP.2006.889403.  Google Scholar [18] J.-M. Peng, Equivalence of variational inequality problems to unconstrained optimization, Math. Program., 78 (1997), 347-355. doi: 10.1007/BF02614360.  Google Scholar [19] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar [20] R. Y. Rubinstein and A. Shapiro, Discrete Event Systems. Sensitivity Analysis and Stochastic Optimization by the Score Function Method, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1993.  Google Scholar [21] A. Ruszczyński and A. Shapiro, eds., Stochastic Programming, Handbooks in Operations Research and Management Science, 10, Elsevier Science B.V., Amsterdam, 2003.  Google Scholar [22] A. Shapiro and H. F. Xu, Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation, Optimization, 57 (2008), 395-418. doi: 10.1080/02331930801954177.  Google Scholar [23] B. Verweij, S. Ahmed, A. J. Kleywegt, G. Nemhauser and A. Shapiro, The sample average approximation method applied to stochastic routing problems: A omputational study, Comput. Optim. Appl., 24 (2003), 289-333. doi: 10.1023/A:1021814225969.  Google Scholar [24] M. Wang and M. M. Ali, Stochastic nonlinear complementarity problems: Stochastic programming reformulation and penalty-based approximation method, J. Optimiz. Theory App., 144 (2010), 597-614. doi: 10.1007/s10957-009-9606-4.  Google Scholar [25] M. Wang, M. M. Ali and G. Lin, Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks, J. Ind. Manag. Optim., 7 (2011), 317-345. Google Scholar [26] M. Wang, G. Lin, Y. Gao and M. Ali, Sample average approximation method for a class of stochastic variational inequality problems, J. Syst. Sci. Complex., 24 (2011), 1143-1153. doi: 10.1007/s11424-011-0948-2.  Google Scholar [27] H. Xu, Sample average approximation method for a class of stochastic variational inequality problems, Asia-Pac. J. Oper. Res., 27 (2010), 103-119. doi: 10.1142/S0217595910002569.  Google Scholar [28] H. Xu and F. Meng, Convergence analysis of sample average approximation methods for a class of stochastic mathematical programs with equality constraints, Math. Oper. Res., 32 (2007), 648-668. doi: 10.1287/moor.1070.0260.  Google Scholar [29] C. Zhang and X. Chen, Smoothing projected gradient method and its application to stochastic linear complementarity problems, SIAM J. Optimiz., 20 (2009), 627-649. doi: 10.1137/070702187.  Google Scholar

show all references

##### References:
 [1] R. P. Agdeppa, N. Yamashita and M. Fukushima, Convex expected residual models for stochastic affine variational inequality problems and its applications to the traffic equilibrium problem, Pac. J. Optim., 6 (2010), 3-19.  Google Scholar [2] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Math. Oper. Res., 30 (2005), 1022-1038. doi: 10.1287/moor.1050.0160.  Google Scholar [3] X. Chen, R. B.-J. Wets and Y. Zhang, Stochastic variational inequalities: Residual minimization smoothing sample average approximations, SIAM J. Optimiz., 22 (2012), 649-673. doi: 10.1137/110825248.  Google Scholar [4] X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Math. Program., 117 (2009), 51-80. doi: 10.1007/s10107-007-0163-z.  Google Scholar [5] F. Y. Chen, H Yan and L Yao, A newsvendor pricing game, IEEE T. Syst. Man Cy. A, 34 (2004), 450-456. doi: 10.1109/TSMCA.2004.826290.  Google Scholar [6] S. Dafermos, Traffic equilibrium and variational inequalities, Transport. Sci., 14 (1980), 42-54. doi: 10.1287/trsc.14.1.42.  Google Scholar [7] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-varlag, New York, 2003. Google Scholar [8] H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems, SIAM J. Optimiz., 18 (2007), 482-506. doi: 10.1137/050630805.  Google Scholar [9] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. Program., 53 (1992), 99-110. doi: 10.1007/BF01585696.  Google Scholar [10] M. Fukushima, N. Yamashita and K. Taji, Unconstrained optimization reformulations of variational inequality problems, J. Optimiz. Theory App., 92 (1997), 439-456. doi: 10.1023/A:1022660704427.  Google Scholar [11] G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solution of stochastic variational inequalities, Math. Program., 84 (1999), 313-333. doi: 10.1007/s101070050024.  Google Scholar [12] H. Jiang and H. F. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE T. Automat. Contr., 53 (2008), 1462-1475. doi: 10.1109/TAC.2008.925853.  Google Scholar [13] G.-H. Lin and M. Fukushima, Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: A survey, Pac. J. Optim., 6 (2010), 455-482.  Google Scholar [14] M. J. Luo and G. H. Lin, Expected residual minimization method for stochastic variational inequality problems, J. Optimiz. Theory App., 140 (2009), 103-116. doi: 10.1007/s10957-008-9439-6.  Google Scholar [15] S. Mahajan and G. van Ryzin, Inventory competition under dynamic consumer choice, Oper. Res., 49 (2001), 646-657. doi: 10.1287/opre.49.5.646.10603.  Google Scholar [16] F. W. Meng and H. Xu, A regularized sample average approximation method for stochastic mathematical programs with nonsmooth equality constraints, SIAM J. Optimiz., 17 (2006), 891-919. doi: 10.1137/050638242.  Google Scholar [17] M. H. Ngo and V. Krishnamurthy, Game theoretic cross-layer transmission policies in multipacket reception wireless networks, IEEE T. Signal Proces., 55 (2007), 1911-1926. doi: 10.1109/TSP.2006.889403.  Google Scholar [18] J.-M. Peng, Equivalence of variational inequality problems to unconstrained optimization, Math. Program., 78 (1997), 347-355. doi: 10.1007/BF02614360.  Google Scholar [19] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar [20] R. Y. Rubinstein and A. Shapiro, Discrete Event Systems. Sensitivity Analysis and Stochastic Optimization by the Score Function Method, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1993.  Google Scholar [21] A. Ruszczyński and A. Shapiro, eds., Stochastic Programming, Handbooks in Operations Research and Management Science, 10, Elsevier Science B.V., Amsterdam, 2003.  Google Scholar [22] A. Shapiro and H. F. Xu, Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation, Optimization, 57 (2008), 395-418. doi: 10.1080/02331930801954177.  Google Scholar [23] B. Verweij, S. Ahmed, A. J. Kleywegt, G. Nemhauser and A. Shapiro, The sample average approximation method applied to stochastic routing problems: A omputational study, Comput. Optim. Appl., 24 (2003), 289-333. doi: 10.1023/A:1021814225969.  Google Scholar [24] M. Wang and M. M. Ali, Stochastic nonlinear complementarity problems: Stochastic programming reformulation and penalty-based approximation method, J. Optimiz. Theory App., 144 (2010), 597-614. doi: 10.1007/s10957-009-9606-4.  Google Scholar [25] M. Wang, M. M. Ali and G. Lin, Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks, J. Ind. Manag. Optim., 7 (2011), 317-345. Google Scholar [26] M. Wang, G. Lin, Y. Gao and M. Ali, Sample average approximation method for a class of stochastic variational inequality problems, J. Syst. Sci. Complex., 24 (2011), 1143-1153. doi: 10.1007/s11424-011-0948-2.  Google Scholar [27] H. Xu, Sample average approximation method for a class of stochastic variational inequality problems, Asia-Pac. J. Oper. Res., 27 (2010), 103-119. doi: 10.1142/S0217595910002569.  Google Scholar [28] H. Xu and F. Meng, Convergence analysis of sample average approximation methods for a class of stochastic mathematical programs with equality constraints, Math. Oper. Res., 32 (2007), 648-668. doi: 10.1287/moor.1070.0260.  Google Scholar [29] C. Zhang and X. Chen, Smoothing projected gradient method and its application to stochastic linear complementarity problems, SIAM J. Optimiz., 20 (2009), 627-649. doi: 10.1137/070702187.  Google Scholar
 [1] Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial & Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333 [2] Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial & Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317 [3] Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35 [4] Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645 [5] Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1 [6] Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485 [7] George Avalos, Thomas J. Clark. A mixed variational formulation for the wellposedness and numerical approximation of a PDE model arising in a 3-D fluid-structure interaction. Evolution Equations & Control Theory, 2014, 3 (4) : 557-578. doi: 10.3934/eect.2014.3.557 [8] Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial & Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045 [9] Liping Pang, Fanyun Meng, Jinhe Wang. Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1653-1675. doi: 10.3934/jimo.2018116 [10] Masao Fukushima. A class of gap functions for quasi-variational inequality problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 165-171. doi: 10.3934/jimo.2007.3.165 [11] Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 [12] Qiang Du, Manlin Li. On the stochastic immersed boundary method with an implicit interface formulation. Discrete & Continuous Dynamical Systems - B, 2011, 15 (2) : 373-389. doi: 10.3934/dcdsb.2011.15.373 [13] Francis Akutsah, Akindele Adebayo Mebawondu, Hammed Anuoluwapo Abass, Ojen Kumar Narain. A self adaptive method for solving a class of bilevel variational inequalities with split variational inequality and composed fixed point problem constraints in Hilbert spaces. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021046 [14] S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155 [15] Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021083 [16] Ugo Bessi. The stochastic value function in metric measure spaces. Discrete & Continuous Dynamical Systems, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076 [17] Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381 [18] Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895 [19] Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017 [20] Li Wang, Yang Li, Liwei Zhang. A differential equation method for solving box constrained variational inequality problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 183-198. doi: 10.3934/jimo.2011.7.183

2020 Impact Factor: 1.801