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 & 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, (1994), 94.   Google Scholar

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis,, Wiley, (1983).   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Springer-Verlag, (2003).  doi: 10.1007/b97544.  Google Scholar

[9]

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

[10]

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

[11]

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

[12]

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

[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.  doi: 10.1016/j.orl.2008.01.010.  Google Scholar

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

[15]

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

[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.  doi: 10.1080/10556788.2012.750321.  Google Scholar

[17]

H. Mukaidani, Stochastic Nash equilibrium seeking for games with general nonlinear payoffs,, SIAM Journal on Control and Optimization, 49 (2011), 1659.  doi: 10.1137/100811738.  Google Scholar

[18]

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

[19]

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

[20]

R. T. Rockafellar and R. J. B.wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[21]

A. Shapiro, Monte Carlo sampling approch to stochastic programming,, European Series of Applied and Industrial Mathematics: Proceeding, 13 (2003), 65.   Google Scholar

[22]

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

[23]

A. Shapiro and H. F. Xu, Stochasic mathematical programs with equiblbrium constraints, modelling and sample average approximation,, Optimization, 57 (2008), 395.  doi: 10.1080/02331930801954177.  Google Scholar

[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.  doi: 10.1007/BF02192639.  Google Scholar

[25]

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

[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.  doi: 10.1007/s10107-008-0214-0.  Google Scholar

[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, ().   Google Scholar

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

show all references

References:
[1]

J. R. Birge, Quasi-Monte Carlo Approaches to Option Pricing,, Technical Report 94-19, (1994), 94.   Google Scholar

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis,, Wiley, (1983).   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Springer-Verlag, (2003).  doi: 10.1007/b97544.  Google Scholar

[9]

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

[10]

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

[11]

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

[12]

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

[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.  doi: 10.1016/j.orl.2008.01.010.  Google Scholar

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

[15]

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

[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.  doi: 10.1080/10556788.2012.750321.  Google Scholar

[17]

H. Mukaidani, Stochastic Nash equilibrium seeking for games with general nonlinear payoffs,, SIAM Journal on Control and Optimization, 49 (2011), 1659.  doi: 10.1137/100811738.  Google Scholar

[18]

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

[19]

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

[20]

R. T. Rockafellar and R. J. B.wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[21]

A. Shapiro, Monte Carlo sampling approch to stochastic programming,, European Series of Applied and Industrial Mathematics: Proceeding, 13 (2003), 65.   Google Scholar

[22]

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

[23]

A. Shapiro and H. F. Xu, Stochasic mathematical programs with equiblbrium constraints, modelling and sample average approximation,, Optimization, 57 (2008), 395.  doi: 10.1080/02331930801954177.  Google Scholar

[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.  doi: 10.1007/BF02192639.  Google Scholar

[25]

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

[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.  doi: 10.1007/s10107-008-0214-0.  Google Scholar

[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, ().   Google Scholar

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

[1]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006

[2]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[4]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[5]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[6]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25

[7]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053

[8]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[9]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[10]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027

[11]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[12]

Seung-Yeal Ha, Dongnam Ko, Chanho Min, Xiongtao Zhang. Emergent collective behaviors of stochastic kuramoto oscillators. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1059-1081. doi: 10.3934/dcdsb.2019208

[13]

María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088

[14]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[15]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210

[16]

Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175

[17]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004

[18]

Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$ \alpha $ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113

[19]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]