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 and 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.

[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.

[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.

[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.

[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.

[6]

S. Dafermos, Traffic equilibrium and variational inequalities, Transport. Sci., 14 (1980), 42-54. doi: 10.1287/trsc.14.1.42.

[7]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-varlag, New York, 2003.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[18]

J.-M. Peng, Equivalence of variational inequality problems to unconstrained optimization, Math. Program., 78 (1997), 347-355. doi: 10.1007/BF02614360.

[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.

[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.

[21]

A. Ruszczyński and A. Shapiro, eds., Stochastic Programming, Handbooks in Operations Research and Management Science, 10, Elsevier Science B.V., Amsterdam, 2003.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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.

[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.

[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.

[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.

[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.

[6]

S. Dafermos, Traffic equilibrium and variational inequalities, Transport. Sci., 14 (1980), 42-54. doi: 10.1287/trsc.14.1.42.

[7]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-varlag, New York, 2003.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[18]

J.-M. Peng, Equivalence of variational inequality problems to unconstrained optimization, Math. Program., 78 (1997), 347-355. doi: 10.1007/BF02614360.

[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.

[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.

[21]

A. Ruszczyński and A. Shapiro, eds., Stochastic Programming, Handbooks in Operations Research and Management Science, 10, Elsevier Science B.V., Amsterdam, 2003.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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 and 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 and 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 and 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 and Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645

[5]

Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022017

[6]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1

[7]

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 and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

[8]

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 and Control Theory, 2014, 3 (4) : 557-578. doi: 10.3934/eect.2014.3.557

[9]

Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial and Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045

[10]

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 and Management Optimization, 2019, 15 (4) : 1653-1675. doi: 10.3934/jimo.2018116

[11]

Masao Fukushima. A class of gap functions for quasi-variational inequality problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 165-171. doi: 10.3934/jimo.2007.3.165

[12]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[13]

Qiang Du, Manlin Li. On the stochastic immersed boundary method with an implicit interface formulation. Discrete and Continuous Dynamical Systems - B, 2011, 15 (2) : 373-389. doi: 10.3934/dcdsb.2011.15.373

[14]

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 and Optimization, 2021  doi: 10.3934/naco.2021046

[15]

S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial and Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155

[16]

Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2599-2610. doi: 10.3934/jimo.2021083

[17]

Ugo Bessi. The stochastic value function in metric measure spaces. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076

[18]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381

[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]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (116)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]