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.

**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 -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 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**

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.