## Combined Monte Carlo sampling and penalty method for Stochastic nonlinear complementarity problems

HTML articles powered by AMS MathViewer

- by Gui-Hua Lin PDF
- Math. Comp.
**78**(2009), 1671-1686 Request permission

## Abstract:

In this paper, we consider a new formulation with recourse for a class of stochastic nonlinear complementarity problems. We show that the new formulation is equivalent to a smooth semi-infinite program that no longer contains recourse variables. We then propose a combined Monte Carlo sampling and penalty method for solving the problem in which the underlying sample space is assumed to be compact. Furthermore, we suggest a compact approximation approach for the case where the sample space is unbounded. Two preliminary numerical examples are included as well.## References

- Ş. İlker Birbil, Gül Gürkan, and Ovidiu Listeş,
*Solving stochastic mathematical programs with complementarity constraints using simulation*, Math. Oper. Res.**31**(2006), no. 4, 739–760. MR**2281227**, DOI 10.1287/moor.1060.0215 - Fabian Bastin, Cinzia Cirillo, and Philippe L. Toint,
*Convergence theory for nonconvex stochastic programming with an application to mixed logit*, Math. Program.**108**(2006), no. 2-3, Ser. B, 207–234. MR**2238700**, DOI 10.1007/s10107-006-0708-6 - John R. Birge and François Louveaux,
*Introduction to stochastic programming*, Springer Series in Operations Research, Springer-Verlag, New York, 1997. MR**1460264** - B. Chen,
*Error bounds for $R_0$-type and monotone nonlinear complementarity problems*, J. Optim. Theory Appl.**108**(2001), no. 2, 297–316. MR**1824294**, DOI 10.1023/A:1026434200384 - Bintong Chen and Patrick T. Harker,
*Smooth approximations to nonlinear complementarity problems*, SIAM J. Optim.**7**(1997), no. 2, 403–420. MR**1443626**, DOI 10.1137/S1052623495280615 - Xiaojun Chen and Masao Fukushima,
*Expected residual minimization method for stochastic linear complementarity problems*, Math. Oper. Res.**30**(2005), no. 4, 1022–1038. MR**2185828**, DOI 10.1287/moor.1050.0160 - X. Chen, C. Zhang and M. Fukushima,
*Robust solution of monotone stochastic linear complementarity problems*, Mathematical Programming,**117**(2009), 51–80. - Y. Chen and M. Florian,
*The nonlinear bilevel programming problem: formulations, regularity and optimality conditions*, Optimization**32**(1995), no. 3, 193–209. MR**1336341**, DOI 10.1080/02331939508844048 - Richard W. Cottle, Jong-Shi Pang, and Richard E. Stone,
*The linear complementarity problem*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1992. MR**1150683** - F. Facchinei and J.S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003.
- Haitao Fang, Xiaojun Chen, and Masao Fukushima,
*Stochastic $R_0$ matrix linear complementarity problems*, SIAM J. Optim.**18**(2007), no. 2, 482–506. MR**2338448**, DOI 10.1137/050630805 - Gül Gürkan, A. Yonca Özge, and Stephen M. Robinson,
*Sample-path solution of stochastic variational inequalities*, Math. Program.**84**(1999), no. 2, Ser. A, 313–333. MR**1690005**, DOI 10.1007/s101070050024 - R. Hettich and K. O. Kortanek,
*Semi-infinite programming: theory, methods, and applications*, SIAM Rev.**35**(1993), no. 3, 380–429. MR**1234637**, DOI 10.1137/1035089 - G.-H. Lin, X. Chen, and M. Fukushima,
*New restricted NCP functions and their applications to stochastic NCP and stochastic MPEC*, Optimization**56**(2007), no. 5-6, 641–953. MR**2362712**, DOI 10.1080/02331930701617320 - G.H. Lin, X. Chen and M. Fukushima,
*Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization*, Mathematical Programming,**116**(2009), 343–368. - Gui-Hua Lin and Masao Fukushima,
*A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms*, J. Ind. Manag. Optim.**1**(2005), no. 1, 99–122. MR**2127807**, DOI 10.3934/jimo.2005.1.99 - Gui-Hua Lin and Masao Fukushima,
*New reformulations for stochastic nonlinear complementarity problems*, Optim. Methods Softw.**21**(2006), no. 4, 551–564. MR**2277498**, DOI 10.1080/10556780600627610 - Gui-Hua Lin and Masao Fukushima,
*Regularization method for stochastic mathematical programs with complementarity constraints*, ESAIM Control Optim. Calc. Var.**11**(2005), no. 2, 252–265. MR**2141889**, DOI 10.1051/cocv:2005005 - Gui-Hua Lin, Huifu Xu, and Masao Fukushima,
*Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints*, Math. Methods Oper. Res.**67**(2008), no. 3, 423–441. MR**2403716**, DOI 10.1007/s00186-007-0201-x - Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph,
*Mathematical programs with equilibrium constraints*, Cambridge University Press, Cambridge, 1996. MR**1419501**, DOI 10.1017/CBO9780511983658 - Fanwen Meng and Huifu Xu,
*A regularized sample average approximation method for stochastic mathematical programs with nonsmooth equality constraints*, SIAM J. Optim.**17**(2006), no. 3, 891–919. MR**2257215**, DOI 10.1137/050638242 - Fan-wen Meng and Hui-fu Xu,
*Exponential convergence of sample average approximation methods for a class of stochastic mathematical programs with complementarity constraints*, J. Comput. Math.**24**(2006), no. 6, 733–748. MR**2269956** - Harald Niederreiter,
*Random number generation and quasi-Monte Carlo methods*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR**1172997**, DOI 10.1137/1.9781611970081 - J. M. Ortega and W. C. Rheinboldt,
*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810** - A. Shapiro,
*Monte Carlo sampling approach to stochastic programming*, Proceedings of 2003 MODE-SMAI Conference, ESAIM Proc., vol. 13, EDP Sci., Les Ulis, 2003, pp. 65–73. MR**2160881** - A. Shapiro,
*Stochastic programming with equilibrium constraints*, J. Optim. Theory Appl.**128**(2006), no. 1, 223–243. MR**2201897**, DOI 10.1007/s10957-005-7566-x - Alexander Shapiro and Huifu Xu,
*Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation*, Optimization**57**(2008), no. 3, 395–418. MR**2412074**, DOI 10.1080/02331930801954177 - Huifu Xu,
*An implicit programming approach for a class of stochastic mathematical programs with complementarity constraints*, SIAM J. Optim.**16**(2006), no. 3, 670–696. MR**2197552**, DOI 10.1137/040608544 - Huifu Xu and Fanwen Meng,
*Convergence analysis of sample average approximation methods for a class of stochastic mathematical programs with equality constraints*, Math. Oper. Res.**32**(2007), no. 3, 648–668. MR**2348240**, DOI 10.1287/moor.1070.0260 - C. Zhang and X. Chen,
*Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty*, J. Optim. Theory Appl.**137**(2008), no. 2, 277–295. MR**2395102**, DOI 10.1007/s10957-008-9358-6

## Additional Information

**Gui-Hua Lin**- Affiliation: Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, China
- Email: lin_g_h@yahoo.com.cn
- Received by editor(s): May 14, 2007
- Received by editor(s) in revised form: January 26, 2008, and July 13, 2008
- Published electronically: January 21, 2009
- Additional Notes: This work was supported in part by NSFC Grant #10771025 and SRFDP Grant #20070141063.
- © Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**78**(2009), 1671-1686 - MSC (2000): Primary 90C33; Secondary 90C30, 90C15
- DOI: https://doi.org/10.1090/S0025-5718-09-02206-6
- MathSciNet review: 2501069