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

Lin, Gui-Hua

doi:10.1090/S0025-5718-09-02206-6

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