Mathematics of Computation

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

Author(s): Gui-Hua Lin.
Journal: Math. Comp. 78 (2009), 1671-1686.
MSC (2000): Primary 90C33; Secondary 90C30, 90C15.
Posted: January 21, 2009
Retrieve article in: PDF

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.

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

DOI: 10.1090/S0025-5718-09-02206-6
PII: S 0025-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
Posted: January 21, 2009
Additional Notes: This work was supported in part by NSFC Grant #10771025 and SRFDP Grant #20070141063.
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS