American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  Google Scholar

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

[3]

X. Chen, C. Zhang and M. Fukushima, Robust solution of stochastic matrix linear complementarity problems, Mathematical Programming, Ser. B, 117 (2009), 51-80.  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, San Diego, CA, 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-212. 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, New York, 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-506. 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-333. 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-653. 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-564. 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-919. doi: 10.1137/050638242.  Google Scholar

[13]

A. Nagurney, "Network Economics: a Variational Inequality Approach," Kluwer Academic Publishers, Dordrecht, 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-142. 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, Cheltenham, England, 2002. Google Scholar

[16]

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

[17]

A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming," Handbooks in OR$&$MS, Vol. 10, North-Holland Publishing Company, Amsterdam, 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-115. 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-243. 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-418. 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-359. 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-668. 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-295. 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-234. 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-1038. 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, Ser. B, 117 (2009), 51-80.  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, San Diego, CA, 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-212. 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, New York, 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-506. 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-333. 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-653. 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-564. 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-919. doi: 10.1137/050638242.  Google Scholar

[13]

A. Nagurney, "Network Economics: a Variational Inequality Approach," Kluwer Academic Publishers, Dordrecht, 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-142. 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, Cheltenham, England, 2002. Google Scholar

[16]

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

[17]

A. Ruszcynski and A. Shapiro, Eds., "Stochastic Programming," Handbooks in OR$&$MS, Vol. 10, North-Holland Publishing Company, Amsterdam, 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-115. 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-243. 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-418. 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-359. 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-668. 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-295. 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]

Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049
[7]

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 & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[8]

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 & Management Optimization, 2021, 17 (5) : 2783-2804. doi: 10.3934/jimo.2020094
[9]

Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435
[15]

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

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

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

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

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

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences