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