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]

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]

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

[12]

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

[13]

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

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

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

[16]

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

[17]

Walter Allegretto, Yanping Lin, Shuqing Ma. On the box method for a non-local parabolic variational inequality. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 71-88. doi: 10.3934/dcdsb.2001.1.71

[18]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[19]

Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1381-1396. doi: 10.3934/jimo.2018012

[20]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]