|
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
MathSciNet review:
2501069
Retrieve article in:
PDF
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:
-
- 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
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:
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.
|
