January  2016, 12(1): 1-15. doi: 10.3934/jimo.2016.12.1

Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems

1. 

School of Mathematics, Liaoning University, Liaoning 110031, China

2. 

School of Management, Shanghai University, Shanghai 200444, China

Received  January 2014 Revised  October 2014 Published  April 2015

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.
Citation: Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1
References:
[1]

J. R. Birge, Quasi-Monte Carlo Approaches to Option Pricing, Technical Report 94-19, Department of Industrial and Operations Engineering, University of Michigan, 1994.

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.

[3]

X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research, 30 (2005), 1022-1038. doi: 10.1287/moor.1050.0160.

[4]

X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Mathematical Programming, 117 (2009), 51-80. doi: 10.1007/s10107-007-0163-z.

[5]

D. De Wolf and Y. Smeers, A stochastic version of a Stackelberg-Nash-Cournot equilibrium model, Management Science, 43 (1997), 190-197.

[6]

A. Fischer, A special Newton-type optimization method, Optimization, 24 (1992), 269-284. doi: 10.1080/02331939208843795.

[7]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, A Quarterly Journal of Operations Research, 5 (2007), 173-210. doi: 10.1007/s10288-007-0054-4.

[8]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. doi: 10.1007/b97544.

[9]

H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems, SIAM Journal on Optimization, 18 (2007), 482-506. doi: 10.1137/050630805.

[10]

G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solution of stochastic variational inequalities, Mathematical Programming, 84 (1999), 313-333. doi: 10.1007/s101070050024.

[11]

J. Gao and Y. Liu, Stochastic Nash equilibrium with a numerical solution method, Computer Science, 3496 (2005), 811-816. doi: 10.1007/11427391_130.

[12]

J. B. Krawczyk, Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems, Computational Management Science, 4 (2007), 183-204. doi: 10.1007/s10287-006-0033-9.

[13]

C. Ling, L. Qi, G. Zhou and L. Caccetta, The $SC^1$ property of an expected residual function arising from stochastic complementarity problems, Operations Research Letters, 36 (2008), 456-460. doi: 10.1016/j.orl.2008.01.010.

[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-953. doi: 10.1080/02331930701617320.

[15]

G. H. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optimization Methods and Software, 21 (2006), 551-564. doi: 10.1080/10556780600627610.

[16]

P. Y. Li, Z. F. He and G. H. Lin, Sampling average approximation method for a class of stochastic Nash equilibrium problems, Optimization Methods and Software, 28 (2013), 785-795. 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 (2011), 1659-1679. doi: 10.1137/100811738.

[18]

H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, Philadelphia, SIAM, 1992. doi: 10.1137/1.9781611970081.

[19]

J. F. Nash, Non-Cooperative games, Annals of Mathematics, 54 (1951), 286-295. doi: 10.2307/1969529.

[20]

R. T. Rockafellar and R. J. B.wets, Variational Analysis, Springer-Verlag, Berlin Heidelberg, 1998. 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 (2003), 65-73.

[22]

A. Shapiro, Monte carlo sampling methods, stochastic programming, Handbooks in Operations Research and Management Science, 10 (2003), 353-425. doi: 10.1016/S0927-0507(03)10006-0.

[23]

A. Shapiro and H. F. Xu, Stochasic mathematical programs with equiblbrium constraints, modelling and sample average approximation, Optimization, 57 (2008), 395-418. 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 (1996), 17-37. doi: 10.1007/BF02192639.

[25]

H. F. Xu and D. L. Zhang, Stochastic Nash equilibrium problems: Sample average approximation and applications, Computational Optimization and Applications, 55 (2013), 597-645. doi: 10.1007/s10589-013-9538-7.

[26]

H. F. Xu and D. L. Zhang, Smooth sample average appproximation of stationary points in nonsmooth stochastic optimization and applications, Mathematical Programming Series A, 119 (2009), 371-401. doi: 10.1007/s10107-008-0214-0.

[27]

Y. H. Yuan, L. W. Zhang and Y. Wu, A smoothing Newton method based on sample average approximation for a class of stochastic generalized Nash equilibrium problems,, Pacific Journal of Optimization, (). 

[28]

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. doi: 10.1007/s10957-008-9358-6.

show all references

References:
[1]

J. R. Birge, Quasi-Monte Carlo Approaches to Option Pricing, Technical Report 94-19, Department of Industrial and Operations Engineering, University of Michigan, 1994.

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.

[3]

X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research, 30 (2005), 1022-1038. doi: 10.1287/moor.1050.0160.

[4]

X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Mathematical Programming, 117 (2009), 51-80. doi: 10.1007/s10107-007-0163-z.

[5]

D. De Wolf and Y. Smeers, A stochastic version of a Stackelberg-Nash-Cournot equilibrium model, Management Science, 43 (1997), 190-197.

[6]

A. Fischer, A special Newton-type optimization method, Optimization, 24 (1992), 269-284. doi: 10.1080/02331939208843795.

[7]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, A Quarterly Journal of Operations Research, 5 (2007), 173-210. doi: 10.1007/s10288-007-0054-4.

[8]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003. doi: 10.1007/b97544.

[9]

H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems, SIAM Journal on Optimization, 18 (2007), 482-506. doi: 10.1137/050630805.

[10]

G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solution of stochastic variational inequalities, Mathematical Programming, 84 (1999), 313-333. doi: 10.1007/s101070050024.

[11]

J. Gao and Y. Liu, Stochastic Nash equilibrium with a numerical solution method, Computer Science, 3496 (2005), 811-816. doi: 10.1007/11427391_130.

[12]

J. B. Krawczyk, Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems, Computational Management Science, 4 (2007), 183-204. doi: 10.1007/s10287-006-0033-9.

[13]

C. Ling, L. Qi, G. Zhou and L. Caccetta, The $SC^1$ property of an expected residual function arising from stochastic complementarity problems, Operations Research Letters, 36 (2008), 456-460. doi: 10.1016/j.orl.2008.01.010.

[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-953. doi: 10.1080/02331930701617320.

[15]

G. H. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optimization Methods and Software, 21 (2006), 551-564. doi: 10.1080/10556780600627610.

[16]

P. Y. Li, Z. F. He and G. H. Lin, Sampling average approximation method for a class of stochastic Nash equilibrium problems, Optimization Methods and Software, 28 (2013), 785-795. 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 (2011), 1659-1679. doi: 10.1137/100811738.

[18]

H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, Philadelphia, SIAM, 1992. doi: 10.1137/1.9781611970081.

[19]

J. F. Nash, Non-Cooperative games, Annals of Mathematics, 54 (1951), 286-295. doi: 10.2307/1969529.

[20]

R. T. Rockafellar and R. J. B.wets, Variational Analysis, Springer-Verlag, Berlin Heidelberg, 1998. 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 (2003), 65-73.

[22]

A. Shapiro, Monte carlo sampling methods, stochastic programming, Handbooks in Operations Research and Management Science, 10 (2003), 353-425. doi: 10.1016/S0927-0507(03)10006-0.

[23]

A. Shapiro and H. F. Xu, Stochasic mathematical programs with equiblbrium constraints, modelling and sample average approximation, Optimization, 57 (2008), 395-418. 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 (1996), 17-37. doi: 10.1007/BF02192639.

[25]

H. F. Xu and D. L. Zhang, Stochastic Nash equilibrium problems: Sample average approximation and applications, Computational Optimization and Applications, 55 (2013), 597-645. doi: 10.1007/s10589-013-9538-7.

[26]

H. F. Xu and D. L. Zhang, Smooth sample average appproximation of stationary points in nonsmooth stochastic optimization and applications, Mathematical Programming Series A, 119 (2009), 371-401. doi: 10.1007/s10107-008-0214-0.

[27]

Y. H. Yuan, L. W. Zhang and Y. Wu, A smoothing Newton method based on sample average approximation for a class of stochastic generalized Nash equilibrium problems,, Pacific Journal of Optimization, (). 

[28]

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. doi: 10.1007/s10957-008-9358-6.

[1]

Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977

[2]

Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial and Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317

[3]

Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091

[4]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51

[5]

Ouayl Chadli, Gayatri Pany, Ram N. Mohapatra. Existence and iterative approximation method for solving mixed equilibrium problem under generalized monotonicity in Banach spaces. Numerical Algebra, Control and Optimization, 2020, 10 (1) : 75-92. doi: 10.3934/naco.2019034

[6]

Narcisse Batangouna, Morgan Pierre. Convergence of exponential attractors for a time splitting approximation of the Caginalp phase-field system. Communications on Pure and Applied Analysis, 2018, 17 (1) : 1-19. doi: 10.3934/cpaa.2018001

[7]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[8]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123

[9]

Esther S. Daus, Shi Jin, Liu Liu. Spectral convergence of the stochastic galerkin approximation to the boltzmann equation with multiple scales and large random perturbation in the collision kernel. Kinetic and Related Models, 2019, 12 (4) : 909-922. doi: 10.3934/krm.2019034

[10]

Patrick Henning, Mario Ohlberger. A-posteriori error estimate for a heterogeneous multiscale approximation of advection-diffusion problems with large expected drift. Discrete and Continuous Dynamical Systems - S, 2016, 9 (5) : 1393-1420. doi: 10.3934/dcdss.2016056

[11]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1

[12]

Nikolai Dokuchaev. On strong causal binomial approximation for stochastic processes. Discrete and Continuous Dynamical Systems - B, 2014, 19 (6) : 1549-1562. doi: 10.3934/dcdsb.2014.19.1549

[13]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017

[14]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control and Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010

[15]

Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049

[16]

Do Sang Kim, Nguyen Ngoc Hai, Bui Van Dinh. Weak convergence theorems for symmetric generalized hybrid mappings and equilibrium problems. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 63-78. doi: 10.3934/naco.2021051

[17]

Xuemei Li, Rafael de la Llave. Convergence of differentiable functions on closed sets and remarks on the proofs of the "Converse Approximation Lemmas''. Discrete and Continuous Dynamical Systems - S, 2010, 3 (4) : 623-641. doi: 10.3934/dcdss.2010.3.623

[18]

Roberta Bianchini, Roberto Natalini. Convergence of a vector-BGK approximation for the incompressible Navier-Stokes equations. Kinetic and Related Models, 2019, 12 (1) : 133-158. doi: 10.3934/krm.2019006

[19]

Antonio De Rosa, Domenico Angelo La Manna. A non local approximation of the Gaussian perimeter: Gamma convergence and Isoperimetric properties. Communications on Pure and Applied Analysis, 2021, 20 (5) : 2101-2116. doi: 10.3934/cpaa.2021059

[20]

Ta Cong Son, Nguyen Tien Dung, Nguyen Van Tan, Tran Manh Cuong, Hoang Thi Phuong Thao, Pham Dinh Tung. Weak convergence of delay SDEs with applications to Carathéodory approximation. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021249

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (119)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]