×

Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. (English) Zbl 1320.65103

Summary: In this paper, we consider the class of stochastic generalized Nash equilibrium problems (SGNEP). Such problems have a wide range of applications and have attracted significant attention recently. First, using the first order optimality condition of SGNEP and the nonlinear complementary function, we present an expected residual minimization (ERM) model for the case when the involved functions are not continuously differentiable. Then, we introduce a smoothing function, depending on a smoothing parameter, to yield a smooth approximate ERM model. We further show that the solutions of this smooth ERM model converge to the solutions of the original ERM model as the smoothing parameter tends to zero. Since the ERM formulation contains an expectation, we further propose a sample average approximate problem for the ERM model. Moreover, we show that the global optimal solutions of these approximate problems converge to the global optimal solutions of the ERM problem with probability one. Here, convergence can be achieved in two ways. One is to fix the smoothing parameter, the other is to let the smoothing parameter tend to zero as the sample increases.

MSC:

65K10 Numerical optimization and variational techniques
49J55 Existence of optimal solutions to problems involving randomness
49M25 Discrete approximations in optimal control

References:

[1] J. R. Birge, <em>Quasi-Monte Carlo Approaches to Option Pricing</em>,, Technical Report 94-19, 94 (1994)
[2] F. H. Clarke, <em>Optimization and Nonsmooth Analysis</em>,, Wiley (1983) · Zbl 0582.49001
[3] X. Chen, Expected residual minimization method for stochastic linear complementarity problems,, Mathematics of Operations Research, 30, 1022 (2005) · Zbl 1162.90527 · doi:10.1287/moor.1050.0160
[4] X. Chen, Robust solution of monotone stochastic linear complementarity problems,, Mathematical Programming, 117, 51 (2009) · Zbl 1165.90012 · doi:10.1007/s10107-007-0163-z
[5] D. De Wolf, A stochastic version of a Stackelberg-Nash-Cournot equilibrium model,, Management Science, 43, 190 (1997) · Zbl 0889.90046
[6] A. Fischer, A special Newton-type optimization method,, Optimization, 24, 269 (1992) · Zbl 0814.65063 · doi:10.1080/02331939208843795
[7] F. Facchinei, Generalized Nash equilibrium problems,, A Quarterly Journal of Operations Research, 5, 173 (2007) · Zbl 1211.91162 · doi:10.1007/s10288-007-0054-4
[8] F. Facchinei, <em>Finite-Dimensional Variational Inequalities and Complementarity Problems</em>,, Springer-Verlag (2003) · Zbl 1062.90002 · doi:10.1007/b97544
[9] H. Fang, Stochastic \(R_0\) matrix linear complementarity problems,, SIAM Journal on Optimization, 18, 482 (2007) · Zbl 1151.90052 · doi:10.1137/050630805
[10] G. Gürkan, Sample-path solution of stochastic variational inequalities,, Mathematical Programming, 84, 313 (1999) · Zbl 0972.90079 · doi:10.1007/s101070050024
[11] J. Gao, Stochastic Nash equilibrium with a numerical solution method,, Computer Science, 3496, 811 (2005) · Zbl 1082.68621 · doi:10.1007/11427391_130
[12] J. B. Krawczyk, Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems,, Computational Management Science, 4, 183 (2007) · Zbl 1134.91303 · doi:10.1007/s10287-006-0033-9
[13] C. Ling, The \(SC^1\) property of an expected residual function arising from stochastic complementarity problems,, Operations Research Letters, 36, 456 (2008) · Zbl 1155.90461 · doi:10.1016/j.orl.2008.01.010
[14] G. H. Lin, New restricted NCP function and their applications to stochastic NCP and stochastic MPEC,, Optimization, 56, 641 (2007) · Zbl 1172.90455 · doi:10.1080/02331930701617320
[15] G. H. Lin, New reformulations for stochastic nonlinear complementarity problems,, Optimization Methods and Software, 21, 551 (2006) · Zbl 1113.90110 · doi:10.1080/10556780600627610
[16] P. Y. Li, Sampling average approximation method for a class of stochastic Nash equilibrium problems,, Optimization Methods and Software, 28, 785 (2013) · Zbl 1278.65069 · doi:10.1080/10556788.2012.750321
[17] H. Mukaidani, Stochastic Nash equilibrium seeking for games with general nonlinear payoffs,, SIAM Journal on Control and Optimization, 49, 1659 (2011) · Zbl 1239.60047 · doi:10.1137/100811738
[18] H. Niederreiter, <em>Random Number Generation and Quasi-Monte Carlo Methods</em>,, Philadelphia (1992) · Zbl 0761.65002 · doi:10.1137/1.9781611970081
[19] J. F. Nash, Non-Cooperative games,, Annals of Mathematics, 54, 286 (1951) · Zbl 0045.08202 · doi:10.2307/1969529
[20] R. T. Rockafellar, <em>Variational Analysis</em>,, Springer-Verlag (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[21] A. Shapiro, Monte Carlo sampling approch to stochastic programming,, European Series of Applied and Industrial Mathematics: Proceeding, 13, 65 (2003) · Zbl 1053.90103
[22] A. Shapiro, Monte carlo sampling methods, stochastic programming,, Handbooks in Operations Research and Management Science, 10, 353 (2003) · Zbl 1115.90001 · doi:10.1016/S0927-0507(03)10006-0
[23] A. Shapiro, Stochasic mathematical programs with equiblbrium constraints, modelling and sample average approximation,, Optimization, 57, 395 (2008) · Zbl 1145.90047 · doi:10.1080/02331930801954177
[24] P. Tseng, Growth behavior of a class of merit functions for the nonlinear complementarity problem,, Journal of Optimization Theory and Applications, 89, 17 (1996) · Zbl 0866.90127 · doi:10.1007/BF02192639
[25] H. F. Xu, Stochastic Nash equilibrium problems: Sample average approximation and applications,, Computational Optimization and Applications, 55, 597 (2013) · Zbl 1281.91046 · doi:10.1007/s10589-013-9538-7
[26] H. F. Xu, Smooth sample average appproximation of stationary points in nonsmooth stochastic optimization and applications,, Mathematical Programming Series A, 119, 371 (2009) · Zbl 1168.90009 · doi:10.1007/s10107-008-0214-0
[27] Y. H. Yuan, A smoothing Newton method based on sample average approximation for a class of stochastic generalized Nash equilibrium problems,, Pacific Journal of Optimization · Zbl 1241.91010
[28] C. Zhang, Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty,, Journal of Optimization Theory and Applications, 137, 277 (2008) · Zbl 1163.90034 · doi:10.1007/s10957-008-9358-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.