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

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

Mingzheng Wang ^1, , M. Montaz Ali ^2, and Guihua Lin ^3,

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

Abstract
Related Papers

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.

Keywords: Stochastic nonlinear complementarity problem, super-network, two-stage stochastic mathematical programming, convergence., sample average approximation.

Mathematics Subject Classification: Primary: 90C33, 90C30, 90C1.

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

Tools

Metrics

Other articles
by authors

on AIMS
Mingzheng Wang M. Montaz Ali Guihua Lin
on Google Scholar
Mingzheng Wang M. Montaz Ali Guihua Lin

[Back to Top]