• Previous Article
    Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization
  • JIMO Home
  • This Issue
  • Next Article
    A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem
July  2022, 18(4): 2599-2610. doi: 10.3934/jimo.2021083

Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities

College of Mathematics and Statistics, Chongqing University, Chongqing 401331, China

* Corresponding author: Shengjie Li

Received  November 2020 Revised  March 2021 Published  July 2022 Early access  April 2021

This paper focuses on the quantitative stability analysis of the expected residual minimization (ERM) formulation for a class of stochastic linear variational inequalities. Firstly, the existence of solutions of the ERM formulation and its perturbed problem is discussed. Then, the quantitative stability of the ERM formulation is derived under suitable probability metrics. Finally, the sample average approximation (SAA) problem of the ERM formulation is studied, and the rates of convergence of optimal solution sets are obtained under different assumptions.

Citation: Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2599-2610. doi: 10.3934/jimo.2021083
References:
[1]

R. P. AgdeppaN. Yamashita and M. Fukushima, Convex expected residual models for stochastic affine variational inequality problems and its application to the traffic equilibrium problem, Pac. J. Optim., 6 (2010), 3-19. 

[2]

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

[3]

X. ChenR. J.-B. Wets and Y. Zhang, Stochastic variational inequalities: Residual minimization smoothing sample average approximations, SIAM J. Optim., 22 (2012), 649-673.  doi: 10.1137/110825248.

[4]

F. Facchinei and J. -S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.

[5]

H. FangX. Chen and M. Fukushima, Stochastic $R_{0}$ matrix linear complementarity problems, SIAM J. Optim., 18 (2007), 482-506.  doi: 10.1137/050630805.

[6]

J. Jiang and Z. Chen, Quantitative stability of multistage stochastic programs via calm modifications, Oper. Res. Lett., 46 (2018), 543-547.  doi: 10.1016/j.orl.2018.08.007.

[7]

J. Jiang and Z. Chen, Quantitative stability analysis of two-stage stochastic linear programs with full random recourse, Numer. Func. Anal. Optim., 40 (2019), 1847-1876.  doi: 10.1080/01630563.2019.1639729.

[8]

J. JiangX. Chen and Z. Chen, Quantitative analysis for a class of two-stage stochastic linear variational inequality problems, Comput. Optim. Appl., 76 (2020), 431-460.  doi: 10.1007/s10589-020-00185-z.

[9]

J. Jiang, Z. Chen and X. M. Yang, Rates of convergence of sample average approximation under heavy tailed distributions, To preprint on Optimization Online.

[10]

Z. Lin and Z. Bai, Probability Inequalities, Springer Science & Business Media, 2011. doi: 10.1007/978-3-642-05261-3.

[11]

J. Liu and S. Li, Unconstrained optimization reformulation for stochastic nonlinear complementarity problems, Appl. Anal., (2019). doi: 10.1080/00036811.2019.1636969.

[12]

F. Lu and S.-J. Li, Method of weighted expected residual for solving stochastic variational inequality problems, Appl. Math. Comput., 269 (2015), 651-663.  doi: 10.1016/j.amc.2015.07.115.

[13]

M. J. Luo and G. H. Lin, Expected residual minimization method for stochastic variation inequality problems, J. Optim. Theory Appl., 140 (2009), 103-116.  doi: 10.1007/s10957-008-9439-6.

[14]

M. J. Luo and G. H. Lin, Convergence results of the ERM method for nonlinear stochastic variation inequality problems, J. Optim. Theory. Appl., 142 (2009), 569-581.  doi: 10.1007/s10957-009-9534-3.

[15]

L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Quart J. Math. Oxford, 11 (1960), 50-59.  doi: 10.1093/qmath/11.1.50.

[16]

S. T. Rachev, L. B. Klebanov, S. V. Stoyanov and F. J. Fobozzi, The Methods of Distances in the Theory of Probility and Statistics, Springer, New York, 2013. doi: 10.1007/978-1-4614-4869-3.

[17]

S. T. Rachev and W. Römisch, Quantitative stability in stochastic programming: The method of probability metrics, Math. Oper. Res., 27 (2002), 792-818.  doi: 10.1287/moor.27.4.792.304.

[18]

W. Römisch, Stability of stochastic programming problems, Stochastic programming, 10 (2003), 483-554.  doi: 10.1016/S0927-0507(03)10008-4.

[19]

A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2014. doi: 10.1137/1.9780898718751.

[20]

A. Shapiro and H. Xu, Stochastic mathematical programs with with equilibrium constraints, modelling and sample average approximation, Optimization, 57 (2008), 395-418.  doi: 10.1080/02331930801954177.

[21]

H. Xu, Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming, J. Math. Anal. Appl., 368 (2010), 692-710.  doi: 10.1016/j.jmaa.2010.03.021.

[22]

H. Xu, Sample average approximation methods for a class of stochastic variational inequality problems, Asia-Pac. J. Oper. Res., 27 (2010), 103-119.  doi: 10.1142/S0217595910002569.

[23]

Y. Zhang and X. Chen, Regularizations for stochastic linear variational inequalities, J. Optim. Theory Appl., 163 (2014), 460-481.  doi: 10.1007/s10957-013-0514-2.

[24]

Y. ZhaoJ. ZhangX. Yang and G.-H. Lin, Expected residual minimization formulation for a class of stochastic vector variational inequalities, J. Optim. Theory Appl., 175 (2017), 545-566.  doi: 10.1007/s10957-016-0939-5.

show all references

References:
[1]

R. P. AgdeppaN. Yamashita and M. Fukushima, Convex expected residual models for stochastic affine variational inequality problems and its application to the traffic equilibrium problem, Pac. J. Optim., 6 (2010), 3-19. 

[2]

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

[3]

X. ChenR. J.-B. Wets and Y. Zhang, Stochastic variational inequalities: Residual minimization smoothing sample average approximations, SIAM J. Optim., 22 (2012), 649-673.  doi: 10.1137/110825248.

[4]

F. Facchinei and J. -S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.

[5]

H. FangX. Chen and M. Fukushima, Stochastic $R_{0}$ matrix linear complementarity problems, SIAM J. Optim., 18 (2007), 482-506.  doi: 10.1137/050630805.

[6]

J. Jiang and Z. Chen, Quantitative stability of multistage stochastic programs via calm modifications, Oper. Res. Lett., 46 (2018), 543-547.  doi: 10.1016/j.orl.2018.08.007.

[7]

J. Jiang and Z. Chen, Quantitative stability analysis of two-stage stochastic linear programs with full random recourse, Numer. Func. Anal. Optim., 40 (2019), 1847-1876.  doi: 10.1080/01630563.2019.1639729.

[8]

J. JiangX. Chen and Z. Chen, Quantitative analysis for a class of two-stage stochastic linear variational inequality problems, Comput. Optim. Appl., 76 (2020), 431-460.  doi: 10.1007/s10589-020-00185-z.

[9]

J. Jiang, Z. Chen and X. M. Yang, Rates of convergence of sample average approximation under heavy tailed distributions, To preprint on Optimization Online.

[10]

Z. Lin and Z. Bai, Probability Inequalities, Springer Science & Business Media, 2011. doi: 10.1007/978-3-642-05261-3.

[11]

J. Liu and S. Li, Unconstrained optimization reformulation for stochastic nonlinear complementarity problems, Appl. Anal., (2019). doi: 10.1080/00036811.2019.1636969.

[12]

F. Lu and S.-J. Li, Method of weighted expected residual for solving stochastic variational inequality problems, Appl. Math. Comput., 269 (2015), 651-663.  doi: 10.1016/j.amc.2015.07.115.

[13]

M. J. Luo and G. H. Lin, Expected residual minimization method for stochastic variation inequality problems, J. Optim. Theory Appl., 140 (2009), 103-116.  doi: 10.1007/s10957-008-9439-6.

[14]

M. J. Luo and G. H. Lin, Convergence results of the ERM method for nonlinear stochastic variation inequality problems, J. Optim. Theory. Appl., 142 (2009), 569-581.  doi: 10.1007/s10957-009-9534-3.

[15]

L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Quart J. Math. Oxford, 11 (1960), 50-59.  doi: 10.1093/qmath/11.1.50.

[16]

S. T. Rachev, L. B. Klebanov, S. V. Stoyanov and F. J. Fobozzi, The Methods of Distances in the Theory of Probility and Statistics, Springer, New York, 2013. doi: 10.1007/978-1-4614-4869-3.

[17]

S. T. Rachev and W. Römisch, Quantitative stability in stochastic programming: The method of probability metrics, Math. Oper. Res., 27 (2002), 792-818.  doi: 10.1287/moor.27.4.792.304.

[18]

W. Römisch, Stability of stochastic programming problems, Stochastic programming, 10 (2003), 483-554.  doi: 10.1016/S0927-0507(03)10008-4.

[19]

A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2014. doi: 10.1137/1.9780898718751.

[20]

A. Shapiro and H. Xu, Stochastic mathematical programs with with equilibrium constraints, modelling and sample average approximation, Optimization, 57 (2008), 395-418.  doi: 10.1080/02331930801954177.

[21]

H. Xu, Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming, J. Math. Anal. Appl., 368 (2010), 692-710.  doi: 10.1016/j.jmaa.2010.03.021.

[22]

H. Xu, Sample average approximation methods for a class of stochastic variational inequality problems, Asia-Pac. J. Oper. Res., 27 (2010), 103-119.  doi: 10.1142/S0217595910002569.

[23]

Y. Zhang and X. Chen, Regularizations for stochastic linear variational inequalities, J. Optim. Theory Appl., 163 (2014), 460-481.  doi: 10.1007/s10957-013-0514-2.

[24]

Y. ZhaoJ. ZhangX. Yang and G.-H. Lin, Expected residual minimization formulation for a class of stochastic vector variational inequalities, J. Optim. Theory Appl., 175 (2017), 545-566.  doi: 10.1007/s10957-016-0939-5.

[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]

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

[3]

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

[4]

Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35

[5]

S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial and Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155

[6]

Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645

[7]

Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022017

[8]

Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028

[9]

Liping Pang, Fanyun Meng, Jinhe Wang. Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1653-1675. doi: 10.3934/jimo.2018116

[10]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

[11]

Yulan Lu, Minghui Song, Mingzhu Liu. Convergence rate and stability of the split-step theta method for stochastic differential equations with piecewise continuous arguments. Discrete and Continuous Dynamical Systems - B, 2019, 24 (2) : 695-717. doi: 10.3934/dcdsb.2018203

[12]

Martin Brokate, Pavel Krejčí. Optimal control of ODE systems involving a rate independent variational inequality. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 331-348. doi: 10.3934/dcdsb.2013.18.331

[13]

Jun Fan, Dao-Hong Xiang. Quantitative convergence analysis of kernel based large-margin unified machines. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4069-4083. doi: 10.3934/cpaa.2020180

[14]

María Teresa V. Martínez-Palacios, Adrián Hernández-Del-Valle, Ambrosio Ortiz-Ramírez. On the pricing of Asian options with geometric average of American type with stochastic interest rate: A stochastic optimal control approach. Journal of Dynamics and Games, 2019, 6 (1) : 53-64. doi: 10.3934/jdg.2019004

[15]

Shengji Li, Chunmei Liao, Minghua Li. Stability analysis of parametric variational systems. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 317-331. doi: 10.3934/naco.2011.1.317

[16]

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

[17]

Dingqian Sun, Gechun Liang, Shanjian Tang. Quantitative stability and numerical analysis of Markovian quadratic BSDEs with reflection. Probability, Uncertainty and Quantitative Risk, 2022, 7 (1) : 13-30. doi: 10.3934/puqr.2022002

[18]

Graeme D. Chalmers, Desmond J. Higham. Convergence and stability analysis for implicit simulations of stochastic differential equations with random jump magnitudes. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 47-64. doi: 10.3934/dcdsb.2008.9.47

[19]

George Avalos, Thomas J. Clark. A mixed variational formulation for the wellposedness and numerical approximation of a PDE model arising in a 3-D fluid-structure interaction. Evolution Equations and Control Theory, 2014, 3 (4) : 557-578. doi: 10.3934/eect.2014.3.557

[20]

T. A. Shaposhnikova, M. N. Zubova. Homogenization problem for a parabolic variational inequality with constraints on subsets situated on the boundary of the domain. Networks and Heterogeneous Media, 2008, 3 (3) : 675-689. doi: 10.3934/nhm.2008.3.675

2021 Impact Factor: 1.411

Article outline

[Back to Top]