• Previous Article
    Optimal control of electrorheological clutch described by nonlinear parabolic equation with nonlocal boundary conditions
  • JIMO Home
  • This Issue
  • Next Article
    Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis
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.

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

[3]

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

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

[7]

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

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

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

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

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

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

[13]

A. Nagurney, "Network Economics: a Variational Inequality Approach,", Kluwer Academic Publishers, (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. 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, (2002).

[16]

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

[17]

A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming,", Handbooks in OR$&$MS, (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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1287/moor.1050.0160.

[3]

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

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

[7]

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

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

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

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

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

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

[13]

A. Nagurney, "Network Economics: a Variational Inequality Approach,", Kluwer Academic Publishers, (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. 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, (2002).

[16]

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

[17]

A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming,", Handbooks in OR$&$MS, (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. 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. 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. 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. 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. 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. 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 & 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, 2018, 13 (5) : 1-14. doi: 10.3934/jimo.2018048

[9]

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

[10]

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

[11]

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

[12]

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

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

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

[17]

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

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

G. Buffoni, S. Pasquali, G. Gilioli. A stochastic model for the dynamics of a stage structured population. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 517-525. doi: 10.3934/dcdsb.2004.4.517

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]