Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Author: Gui-Hua Lin
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
Published electronically: January 21, 2009
MathSciNet review: 2501069
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. S.I. Birbil, G. Gürkan, and O. Listes, Solving stochastic mathematical programs with complementarity constraints using simulation, Mathematics of Operations Research, 31 (2006), 739-760. MR 2281227 (2007k:90073)
  • 2. F. Bastin, C. Cirillo and P.L. Toint, Convergence theory for nonconvex stochastic programming with an application to mixed logit, Mathematical Programming, 108 (2006), 207-234. MR 2238700 (2007c:90061)
  • 3. J.R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer, New York, 1997. MR 1460264 (99b:90001)
  • 4. B. Chen, Error bounds for $ R_0$-type and monotone nonlinear complementarity problems, Journal of Optimization Theory and Applications, 108 (2001), 297-316. MR 1824294 (2001m:90107)
  • 5. B. Chen and P.T. Harker, Smooth approximations to nonlinear complementarity problems, SIAM Journal on Optimization, 7 (1997), 403-420. MR 1443626 (98e:90192)
  • 6. X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research, 30 (2005), 1022-1038 MR 2185828 (2006h:90069)
  • 7. X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Mathematical Programming, 117 (2009), 51-80.
  • 8. Y. Chen and M. Florian, The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions, Optimization, 32 (1995), 193-209. MR 1336341 (96c:90100)
  • 9. R.W. Cottle, J.S. Pang, and R.E. Stone, The Linear Complementarity Problem, Academic Press, New York, 1992. MR 1150683 (93f:90001)
  • 10. F. Facchinei and J.S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003.
  • 11. H. Fang, X. Chen and M. Fukushima, Stochastic $ R_0$ matrix linear complementarity problems, SIAM Journal on Optimization, 18 (2007), 482-506. MR 2338448 (2008f:90112)
  • 12. G. Gürkan, A.Y. Özge and S.M. Robinson, Sample-path solution of stochastic variational inequalities, Mathematical Programming, 84 (1999), 313-333. MR 1690005 (2000b:90094)
  • 13. R. Hettich and K.O. Kortanek, Semi-infinite programming: Theory, methods, and applications, SIAM Review, 35 (1993), 380-429. MR 1234637 (94g:90152)
  • 14. G.H. Lin, X. Chen and M. Fukushima, New restricted NCP function and their applications to stochastic NCP and stochastic MPEC, Optimization, 56 (2007), 641-753. MR 2362712 (2008g:90068)
  • 15. 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.
  • 16. G.H. Lin and M. Fukushima, A class of stochastic mathematical programs with complementarity constraints: Reformulations and algorithms, Journal of Industrial and Management Optimization, 1 (2005), 99-122. MR 2127807 (2006d:90111)
  • 17. G.H. Lin and M. Fukushima, New reformulations for stochastic complementarity problems, Optimization Methods and Software, 21 (2006), 551-564. MR 2277498 (2007j:90036)
  • 18. G.H. Lin and M. Fukushima, Regularization method for stochastic mathematical programs with complementarity constraints, European Series of Applied and Industrial Mathematics (ESAIM): Control, Optimisation and Calculus of Variations, 11 (2005), 252-265. MR 2141889 (2005m:90073)
  • 19. G.H. Lin, H. Xu and M. Fukushima, Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints, Mathematical Methods of Operations Research, 67 (2008), 423-441. MR 2403716
  • 20. Z.Q. Luo, J.S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, United Kingdom, 1996. MR 1419501 (97j:90002)
  • 21. F. 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. MR 2257215 (2007i:90051)
  • 22. F. Meng and H. Xu, Exponential convergence of sample average approximation methods for a class of stochastic mathematical programs with complementarity constraints, Journal of Computational Mathematics, 24 (2006), 733-748. MR 2269956 (2007g:90068)
  • 23. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)
  • 24. J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
  • 25. A. Shapiro, Monte Carlo sampling approach to stochastic programming, European Series of Applied and Industrial Mathematics (ESAIM): Proceedings, 13 (2003), 65-73. MR 2160881 (2006d:90116)
  • 26. A. Shapiro, Stochastic programming with equilibrium constraints, Journal of Optimization Theory and Applications, 128 (2006), 223-243. MR 2201897 (2006j:90054)
  • 27. A. Shapiro and H. Xu, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation, Optimization, 57 (2008), 395-418. MR 2412074
  • 28. H. Xu, An implicit programming approach for a class of stochastic mathematical programs with linear complementarity constraints, SIAM Journal on Optimization, 16 (2006), 670-696. MR 2197552 (2006k:90086)
  • 29. 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. MR 2348240 (2008h:90068)
  • 30. C. Zhang and X. Chen, Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty, Journal of Optimization Theory and Applications, 137 (2008), 277-295. MR 2395102

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 90C33, 90C30, 90C15.

Retrieve articles in all journals with MSC (2000): 90C33, 90C30, 90C15.


Additional Information

Gui-Hua Lin
Affiliation: Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, China
Email: lin_g_h@yahoo.com.cn

DOI: https://doi.org/10.1090/S0025-5718-09-02206-6
Keywords: Stochastic nonlinear complementarity problem, recourse, Monte Carlo method, penalization, convergence
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.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society