# American Institute of Mathematical Sciences

• Previous Article
Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis
• JIMO Home
• This Issue
• Next Article
Optimal control of electrorheological clutch described by nonlinear parabolic equation with nonlocal boundary conditions
April  2011, 7(2): 317-345. doi: 10.3934/jimo.2011.7.317

## Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks

 1 School of Management Science and Engineering, Dalian University of Technology, Dalian 116023, China 2 School of Computational and Applied Mathematics, University of the Witwatersrand, Private Bag-3, Wits-2050, Johannesburg, South Africa 3 School of Mathematical Science, Dalian University of Technology, Dalian 116024, China

Received  November 2009 Revised  January 2011 Published  April 2011

We consider a class of stochastic nonlinear complementarity problems. We propose a new reformulation of the stochastic complementarity problem, that is, a two-stage stochastic mathematical programming model reformulation. Based on this reformulation, we propose a smoothing-based sample average approximation method for stochastic complementarity problem and prove its convergence. As an application, a supply chain super-network equilibrium is modeled as a stochastic nonlinear complementarity problem and numerical results on the problem are reported.
Citation: 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
##### References:
 [1] F. Bastin, C. Cirllo and P. L. Toint, Convergence theory for nonconvex stochastic programming with an application to mixed logit, Mathematical Programming, 108 (2006), 207-234. doi: 10.1007/s10107-006-0708-6. [2] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research, 30 (2005), 1022-1038. doi: 10.1287/moor.1050.0160. [3] X. Chen, C. Zhang and M. Fukushima, Robust solution of stochastic matrix linear complementarity problems, Mathematical Programming, Ser. B, 117 (2009), 51-80. [4] F. H. Clarke, "Optimization and Nonsmooth Analysis," SIAM, 1990. [5] R. W. Cottle, J.-S. Pang and R. Stone, "The linear Complementary Problems," Academic Press, San Diego, CA, 1992. [6] J. Dong, D. Zhang and A. Nagurney, A supply chain network equilibrium model with random demands, European Journal of Operational Research, 156 (2004), 194-212. doi: 10.1016/S0377-2217(03)00023-7. [7] F. Facchinei and J-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Springer, New York, 2003. [8] H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ Matrix linear complementarity problems, SIAM Journal on Optimization, 18 (2007), 482-506. doi: 10.1137/050630805. [9] G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solutions of stochastic variational inequalities, Mathematical Programming, 84 (1999), 313-333. doi: 10.1007/s101070050024. [10] G. H. Lin, X. Chen and M. Fukushima, New restricted NCP functions and their applications to stochastic NCP and stochastic MPEC, Optimization, 56 (2007), 641-653. doi: 10.1080/02331930701617320. [11] G. H. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optimization Methods and Software, 21 (2006), 551-564. doi: 10.1080/10556780600627610. [12] F. W. Meng and H. Xu, A regularized sample average approximation method for stochastic mathematical programs with nonsmooth equality constraints, SIAM Journal on Optimization, 17 (2006), 891-919. doi: 10.1137/050638242. [13] A. Nagurney, "Network Economics: a Variational Inequality Approach," Kluwer Academic Publishers, Dordrecht, 1999. [14] A. Nagurney, J. Cruz, J. Dong and D. Zhang, Supply chain networks, electronic commence, and supply side and demand side risk, European Journal of Operational Research, 164 (2005), 120-142. doi: 10.1016/j.ejor.2003.11.007. [15] A. Nagurney and J. Dong, "Super-Networks: Decision-Making for the Information Age," Edward Elgar Publishers, Cheltenham, England, 2002. [16] S. M. Robinson, Analysis of sample-path optimization, Mathematics of Operations Research, 21 (1996), 513-528. doi: 10.1287/moor.21.3.513. [17] A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming," Handbooks in OR$&$MS, Vol. 10, North-Holland Publishing Company, Amsterdam, 2003. [18] T. Santoso, S. Ahmed and A. Shapiro, A stochastic programming approach for suppy chain network design under uncertainty, European Journal of Operational Research, 167 (2005), 96-115. doi: 10.1016/j.ejor.2004.01.046. [19] A. Shapiro, Stochastic mathematical programs with equilibrium constraints, Journal of Optimization Theory and Application, 128 (2006), 223-243. doi: 10.1007/s10957-005-7566-x. [20] A. Shapiro and H. Xu, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation, Optimization, 57 (2008), 395-418. doi: 10.1080/02331930801954177. [21] R. Storn and K. Price, Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11 (1997), 341-359. doi: 10.1023/A:1008202821328. [22] H. Xu and F. Meng, Convergence analysis of sample average approximation methods for a class of stochastic mathematical programs with equality constraints, Mathematics of Operations Research, 32 (2007), 648-668. doi: 10.1287/moor.1070.0260. [23] C. Zhang and X. Chen, Stochastic nonlinear complementary problem and application to traffic equilibrium under uncertainty, Journal of Optimization Theory and Applications, 137 (2008), 277-295. doi: 10.1007/s10957-008-9358-6.

show all references

##### References:
 [1] F. Bastin, C. Cirllo and P. L. Toint, Convergence theory for nonconvex stochastic programming with an application to mixed logit, Mathematical Programming, 108 (2006), 207-234. doi: 10.1007/s10107-006-0708-6. [2] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research, 30 (2005), 1022-1038. doi: 10.1287/moor.1050.0160. [3] X. Chen, C. Zhang and M. Fukushima, Robust solution of stochastic matrix linear complementarity problems, Mathematical Programming, Ser. B, 117 (2009), 51-80. [4] F. H. Clarke, "Optimization and Nonsmooth Analysis," SIAM, 1990. [5] R. W. Cottle, J.-S. Pang and R. Stone, "The linear Complementary Problems," Academic Press, San Diego, CA, 1992. [6] J. Dong, D. Zhang and A. Nagurney, A supply chain network equilibrium model with random demands, European Journal of Operational Research, 156 (2004), 194-212. doi: 10.1016/S0377-2217(03)00023-7. [7] F. Facchinei and J-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Springer, New York, 2003. [8] H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ Matrix linear complementarity problems, SIAM Journal on Optimization, 18 (2007), 482-506. doi: 10.1137/050630805. [9] G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solutions of stochastic variational inequalities, Mathematical Programming, 84 (1999), 313-333. doi: 10.1007/s101070050024. [10] G. H. Lin, X. Chen and M. Fukushima, New restricted NCP functions and their applications to stochastic NCP and stochastic MPEC, Optimization, 56 (2007), 641-653. doi: 10.1080/02331930701617320. [11] G. H. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optimization Methods and Software, 21 (2006), 551-564. doi: 10.1080/10556780600627610. [12] F. W. Meng and H. Xu, A regularized sample average approximation method for stochastic mathematical programs with nonsmooth equality constraints, SIAM Journal on Optimization, 17 (2006), 891-919. doi: 10.1137/050638242. [13] A. Nagurney, "Network Economics: a Variational Inequality Approach," Kluwer Academic Publishers, Dordrecht, 1999. [14] A. Nagurney, J. Cruz, J. Dong and D. Zhang, Supply chain networks, electronic commence, and supply side and demand side risk, European Journal of Operational Research, 164 (2005), 120-142. doi: 10.1016/j.ejor.2003.11.007. [15] A. Nagurney and J. Dong, "Super-Networks: Decision-Making for the Information Age," Edward Elgar Publishers, Cheltenham, England, 2002. [16] S. M. Robinson, Analysis of sample-path optimization, Mathematics of Operations Research, 21 (1996), 513-528. doi: 10.1287/moor.21.3.513. [17] A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming," Handbooks in OR$&$MS, Vol. 10, North-Holland Publishing Company, Amsterdam, 2003. [18] T. Santoso, S. Ahmed and A. Shapiro, A stochastic programming approach for suppy chain network design under uncertainty, European Journal of Operational Research, 167 (2005), 96-115. doi: 10.1016/j.ejor.2004.01.046. [19] A. Shapiro, Stochastic mathematical programs with equilibrium constraints, Journal of Optimization Theory and Application, 128 (2006), 223-243. doi: 10.1007/s10957-005-7566-x. [20] A. Shapiro and H. Xu, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation, Optimization, 57 (2008), 395-418. doi: 10.1080/02331930801954177. [21] R. Storn and K. Price, Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11 (1997), 341-359. doi: 10.1023/A:1008202821328. [22] H. Xu and F. Meng, Convergence analysis of sample average approximation methods for a class of stochastic mathematical programs with equality constraints, Mathematics of Operations Research, 32 (2007), 648-668. doi: 10.1287/moor.1070.0260. [23] C. Zhang and X. Chen, Stochastic nonlinear complementary problem and application to traffic equilibrium under uncertainty, Journal of Optimization Theory and Applications, 137 (2008), 277-295. doi: 10.1007/s10957-008-9358-6.
 [1] René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 [2] Zhiping Chen, Youpan Han. Continuity and stability of two-stage stochastic programs with quadratic continuous recourse. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 197-209. doi: 10.3934/naco.2015.5.197 [3] 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 [4] 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 [5] Rüdiger Schultz. Two-stage stochastic programs: Integer variables, dominance relations and PDE constraints. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 713-738. doi: 10.3934/naco.2012.2.713 [6] Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049 [7] Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2783-2804. doi: 10.3934/jimo.2020094 [8] Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 [9] Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1289-1314. doi: 10.3934/jimo.2020022 [10] Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial and Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99 [11] Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028 [12] Bin Li, Jie Sun, Honglei Xu, Min Zhang. A class of two-stage distributionally robust games. Journal of Industrial and Management Optimization, 2019, 15 (1) : 387-400. doi: 10.3934/jimo.2018048 [13] Chien Hsun Tseng. Applications of a nonlinear optimization solver and two-stage comprehensive Denoising techniques for optimum underwater wideband sonar echolocation system. Journal of Industrial and Management Optimization, 2013, 9 (1) : 205-225. doi: 10.3934/jimo.2013.9.205 [14] Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial and Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 [15] Ali Hadi, Saeid Mehrabian. A two-stage data envelopment analysis approach to solve extended transportation problem with non-homogenous costs. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022006 [16] Renzhi Qiu, Shanjian Tang. The Cauchy problem of Backward Stochastic Super-Parabolic Equations with Quadratic Growth. Probability, Uncertainty and Quantitative Risk, 2019, 4 (0) : 3-. doi: 10.1186/s41546-019-0037-3 [17] Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241 [18] Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145 [19] Martin Heida, Stefan Neukamm, Mario Varga. Stochastic two-scale convergence and Young measures. Networks and Heterogeneous Media, 2022, 17 (2) : 227-254. doi: 10.3934/nhm.2022004 [20] Jingzhi Li, Hongyu Liu, Qi Wang. Fast imaging of electromagnetic scatterers by a two-stage multilevel sampling method. Discrete and Continuous Dynamical Systems - S, 2015, 8 (3) : 547-561. doi: 10.3934/dcdss.2015.8.547

2020 Impact Factor: 1.801