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

Suxiang He; Pan Zhang; Xiao Hu; Rong Hu

doi:10.3934/jimo.2014.10.977

Article Contents

2014, Volume 10, Issue 3: 977-987. Doi: 10.3934/jimo.2014.10.977

This issue Previous Article A majorized penalty approach to inverse linear second order cone programming problems Next Article

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

Received: January 2013

Revised: August 2013

Published: July 2014

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Stochastic variational inequality problem,
expected-value formulation,
D-gap function,
sample average approximation method,
convergence.

Mathematics Subject Classification: 90C15, 90C33.

Citation:

Related Papers

Cited by

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.