# 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.   Google Scholar [2] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Math. Oper. Res., 30 (2005), 1022.  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.  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.  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.  doi: 10.1109/TSMCA.2004.826290.  Google Scholar [6] S. Dafermos, Traffic equilibrium and variational inequalities,, Transport. Sci., 14 (1980), 42.  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, (2003).   Google Scholar [8] H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems,, SIAM J. Optimiz., 18 (2007), 482.  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.  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.  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.  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.  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.   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.  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.  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.  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.  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.  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], (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, (1993).   Google Scholar [21] A. Ruszczyński and A. Shapiro, eds., Stochastic Programming,, Handbooks in Operations Research and Management Science, (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.  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.  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.  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.   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.  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.  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.  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.  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.   Google Scholar [2] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Math. Oper. Res., 30 (2005), 1022.  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.  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.  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.  doi: 10.1109/TSMCA.2004.826290.  Google Scholar [6] S. Dafermos, Traffic equilibrium and variational inequalities,, Transport. Sci., 14 (1980), 42.  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, (2003).   Google Scholar [8] H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems,, SIAM J. Optimiz., 18 (2007), 482.  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.  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.  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.  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.  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.   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.  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.  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.  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.  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.  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], (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, (1993).   Google Scholar [21] A. Ruszczyński and A. Shapiro, eds., Stochastic Programming,, Handbooks in Operations Research and Management Science, (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.  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.  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.  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.   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.  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.  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.  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.  doi: 10.1137/070702187.  Google Scholar
 [1] Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 [2] Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151 [3] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [4] Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213 [5] Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$\alpha$ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113 [6] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [7] Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233 [8] Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827 [9] Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709 [10] M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072 [11] Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065 [12] Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 [13] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [14] Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018 [15] Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 [16] Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053 [17] Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29 [18] Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133 [19] Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463 [20] Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

2019 Impact Factor: 1.366