• 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 & 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. doi: 10.1007/s10107-006-0708-6. Google Scholar

[2]

X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Mathematics of Operations Research, 30 (2005), 1022. doi: 10.1287/moor.1050.0160. Google Scholar

[3]

X. Chen, C. Zhang and M. Fukushima, Robust solution of stochastic matrix linear complementarity problems,, Mathematical Programming, 117 (2009), 51. Google Scholar

[4]

F. H. Clarke, "Optimization and Nonsmooth Analysis,", SIAM, (1990). Google Scholar

[5]

R. W. Cottle, J.-S. Pang and R. Stone, "The linear Complementary Problems,", Academic Press, (1992). Google Scholar

[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. doi: 10.1016/S0377-2217(03)00023-7. Google Scholar

[7]

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

[8]

H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ Matrix linear complementarity problems,, SIAM Journal on Optimization, 18 (2007), 482. doi: 10.1137/050630805. Google Scholar

[9]

G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solutions of stochastic variational inequalities,, Mathematical Programming, 84 (1999), 313. doi: 10.1007/s101070050024. Google Scholar

[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. doi: 10.1080/02331930701617320. Google Scholar

[11]

G. H. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems,, Optimization Methods and Software, 21 (2006), 551. doi: 10.1080/10556780600627610. Google Scholar

[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. doi: 10.1137/050638242. Google Scholar

[13]

A. Nagurney, "Network Economics: a Variational Inequality Approach,", Kluwer Academic Publishers, (1999). Google Scholar

[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. doi: 10.1016/j.ejor.2003.11.007. Google Scholar

[15]

A. Nagurney and J. Dong, "Super-Networks: Decision-Making for the Information Age,", Edward Elgar Publishers, (2002). Google Scholar

[16]

S. M. Robinson, Analysis of sample-path optimization,, Mathematics of Operations Research, 21 (1996), 513. doi: 10.1287/moor.21.3.513. Google Scholar

[17]

A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming,", Handbooks in OR$&$MS, (2003). Google Scholar

[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. doi: 10.1016/j.ejor.2004.01.046. Google Scholar

[19]

A. Shapiro, Stochastic mathematical programs with equilibrium constraints,, Journal of Optimization Theory and Application, 128 (2006), 223. doi: 10.1007/s10957-005-7566-x. Google Scholar

[20]

A. Shapiro and H. Xu, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation,, Optimization, 57 (2008), 395. doi: 10.1080/02331930801954177. Google Scholar

[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. doi: 10.1023/A:1008202821328. Google Scholar

[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. doi: 10.1287/moor.1070.0260. Google Scholar

[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. doi: 10.1007/s10957-008-9358-6. Google Scholar

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. doi: 10.1007/s10107-006-0708-6. Google Scholar

[2]

X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Mathematics of Operations Research, 30 (2005), 1022. doi: 10.1287/moor.1050.0160. Google Scholar

[3]

X. Chen, C. Zhang and M. Fukushima, Robust solution of stochastic matrix linear complementarity problems,, Mathematical Programming, 117 (2009), 51. Google Scholar

[4]

F. H. Clarke, "Optimization and Nonsmooth Analysis,", SIAM, (1990). Google Scholar

[5]

R. W. Cottle, J.-S. Pang and R. Stone, "The linear Complementary Problems,", Academic Press, (1992). Google Scholar

[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. doi: 10.1016/S0377-2217(03)00023-7. Google Scholar

[7]

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

[8]

H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ Matrix linear complementarity problems,, SIAM Journal on Optimization, 18 (2007), 482. doi: 10.1137/050630805. Google Scholar

[9]

G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solutions of stochastic variational inequalities,, Mathematical Programming, 84 (1999), 313. doi: 10.1007/s101070050024. Google Scholar

[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. doi: 10.1080/02331930701617320. Google Scholar

[11]

G. H. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems,, Optimization Methods and Software, 21 (2006), 551. doi: 10.1080/10556780600627610. Google Scholar

[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. doi: 10.1137/050638242. Google Scholar

[13]

A. Nagurney, "Network Economics: a Variational Inequality Approach,", Kluwer Academic Publishers, (1999). Google Scholar

[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. doi: 10.1016/j.ejor.2003.11.007. Google Scholar

[15]

A. Nagurney and J. Dong, "Super-Networks: Decision-Making for the Information Age,", Edward Elgar Publishers, (2002). Google Scholar

[16]

S. M. Robinson, Analysis of sample-path optimization,, Mathematics of Operations Research, 21 (1996), 513. doi: 10.1287/moor.21.3.513. Google Scholar

[17]

A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming,", Handbooks in OR$&$MS, (2003). Google Scholar

[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. doi: 10.1016/j.ejor.2004.01.046. Google Scholar

[19]

A. Shapiro, Stochastic mathematical programs with equilibrium constraints,, Journal of Optimization Theory and Application, 128 (2006), 223. doi: 10.1007/s10957-005-7566-x. Google Scholar

[20]

A. Shapiro and H. Xu, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation,, Optimization, 57 (2008), 395. doi: 10.1080/02331930801954177. Google Scholar

[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. doi: 10.1023/A:1008202821328. Google Scholar

[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. doi: 10.1287/moor.1070.0260. Google Scholar

[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. doi: 10.1007/s10957-008-9358-6. Google Scholar

[1]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & 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 & 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 & 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 & 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 & Optimization, 2012, 2 (4) : 713-738. doi: 10.3934/naco.2012.2.713

[6]

Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99

[7]

Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028

[8]

Bin Li, Jie Sun, Honglei Xu, Min Zhang. A class of two-stage distributionally robust games. Journal of Industrial & Management Optimization, 2019, 15 (1) : 387-400. doi: 10.3934/jimo.2018048

[9]

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 & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435

[10]

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 & Management Optimization, 2013, 9 (1) : 205-225. doi: 10.3934/jimo.2013.9.205

[11]

Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145

[12]

Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241

[13]

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

[14]

Jingzhi Li, Hongyu Liu, Qi Wang. Fast imaging of electromagnetic scatterers by a two-stage multilevel sampling method. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 547-561. doi: 10.3934/dcdss.2015.8.547

[15]

Urszula Foryś, Beata Zduniak. Two-stage model of carcinogenic mutations with the influence of delays. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2501-2519. doi: 10.3934/dcdsb.2014.19.2501

[16]

Liping Zhang. A nonlinear complementarity model for supply chain network equilibrium. Journal of Industrial & Management Optimization, 2007, 3 (4) : 727-737. doi: 10.3934/jimo.2007.3.727

[17]

David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161.

[18]

Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

[19]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287

[20]

Esther S. Daus, Shi Jin, Liu Liu. Spectral convergence of the stochastic galerkin approximation to the boltzmann equation with multiple scales and large random perturbation in the collision kernel. Kinetic & Related Models, 2019, 12 (4) : 909-922. doi: 10.3934/krm.2019034

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (15)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]