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.

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

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

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

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

[6]

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

[7]

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

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

[9]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Math. Program., 53 (1992), 99. 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. 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. 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. 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.

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

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

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

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

[18]

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

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

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

[21]

A. Ruszczyński and A. Shapiro, eds., Stochastic Programming,, Handbooks in Operations Research and Management Science, (2003).

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

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

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

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

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

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

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

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

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.

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

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

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

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

[6]

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

[7]

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

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

[9]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Math. Program., 53 (1992), 99. 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. 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. 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. 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.

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

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

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

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

[18]

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

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

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

[21]

A. Ruszczyński and A. Shapiro, eds., Stochastic Programming,, Handbooks in Operations Research and Management Science, (2003).

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

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

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

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

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

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

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

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

[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, 2017, 13 (5) : 1-23. 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 (7)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]