• Previous Article
    Adjustable robust optimization in enabling optimal day-ahead economic dispatch of CCHP-MG considering uncertainties of wind-solar power and electric vehicle
  • JIMO Home
  • This Issue
  • Next Article
    Optimality results for a specific fractional problem
doi: 10.3934/jimo.2020050

Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints

1. 

School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

2. 

City Institute, Dalian University of Technology, Dalian 116600, China

3. 

Key Laboratory of Operations Research and Control of Universities in Fujian, College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China

4. 

School of Mathematics, Liaoning Normal University, Dalian 116029, China

* Corresponding author: Bo Wang

Received  May 2019 Revised  October 2019 Published  March 2020

Fund Project: The second author's research is supported in part by the National Natural Science Foundation of China under Project No. 11701091, and Fujian Education and Research Program for Young Teachers under Project No. JAT170096. The third author's research is supported by the National Natural Science Foundation of China under Project No. 11671183 and No. 11671184, Program for Liaoning Excellent Talents in University under Project No. LR2017049, Scientific Research Fund of Liaoning Provincial Education Department under Project No. L201783638, Liaoning BaiQianWan Talents Program, and Project of Liaoning Provincial Natural Science Foundation of China No. 2019MS-217

A stochastic mathematical program model with second-order cone complementarity constraints (SSOCMPCC) is introduced in this paper. It can be considered as a non-trivial extension of stochastic mathematical program with complementarity constraints, and could arise from a hard-to-handle class of bilivel second-order cone programming and inverse stochastic second-order cone programming. By introducing the Chen-Harker-Kanzow-Smale (CHKS) type function to replace the projection operator onto the second-order cone, a smoothing sample average approximation (SAA) method is proposed for solving the SSOCMPCC problem. It can be shown that with proper assumptions, as the sample size goes to infinity, any cluster point of global solutions of the smoothing SAA problem is a global solution of SSOCMPCC almost surely, and any cluster point of stationary points of the former problem is a C-stationary point of the latter problem almost surely. C-stationarity can be strengthened to M-stationarity with additional assumptions. Finally, we report a simple illustrative numerical test to demonstrate our theoretical results.

Citation: Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020050
References:
[1]

Ş. İ. BirbilG. Gürkan and O. Listeş, Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res., 31 (2006), 739-760.  doi: 10.1287/moor.1060.0215.  Google Scholar

[2]

B. T. Chen and P. T. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM J. Matrix Anal. Appl., 14 (1993), 1168-1190.  doi: 10.1137/0614081.  Google Scholar

[3]

X. J. ChenH. L. Sun and R. J.-B. Wets, Regularized mathematical programs with stochastic equilibrium constraints: Estimating structural demand models, SIAM J. Optim., 25 (2015), 53-75.  doi: 10.1137/130930157.  Google Scholar

[4]

S. ChristiansenM. Patriksson and L. Wynter, Stochastic bilevel programming in structural optimization, Struct. Multidiscip. Optim., 21 (2001), 361-371.  doi: 10.1007/s001580100115.  Google Scholar

[5]

F. H. Clarke, Optimization and Nonsmooth Analysis, Second edition, Classics in Applied Mathematics, 5. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. doi: 10.1137/1.9781611971309.  Google Scholar

[6]

H. Y. Jiang and H. F. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Trans. Autom. Control, 53 (2008), 1462-1475.  doi: 10.1109/TAC.2008.925853.  Google Scholar

[7]

C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17 (1996), 851-868.  doi: 10.1137/S0895479894273134.  Google Scholar

[8]

A. J. King and R. T. Rockafellar, Sensitivity analysis for nonsmooth generalized equations, Math. Program., 55 (1992), 193-212.  doi: 10.1007/BF01581199.  Google Scholar

[9]

G.-H. LinM.-J. Luo and J. Zhang, Smoothing and SAA method for stochastic programming problems with non-smooth objective and constraints, J. Global Optim., 66 (2016), 487-510.  doi: 10.1007/s10898-016-0413-9.  Google Scholar

[10]

G.-H. LinM.-J. LuoD. L. Zhang and J. Zhang, Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications, Math. Program., 165 (2017), 197-233.  doi: 10.1007/s10107-017-1121-z.  Google Scholar

[11]

G.-H. LinH. F. Xu and M. Fukushima, Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints, Math. Method Oper. Res., 67 (2008), 423-441.  doi: 10.1007/s00186-007-0201-x.  Google Scholar

[12]

Y. C. Liu and G.-H. Lin, Convergence analysis of a regularized sample average approximation method for stochastic mathematical programs with complementarity constraints, Asia Pac. J. Oper. Res., 28 (2011), 755-771.  doi: 10.1142/S0217595911003338.  Google Scholar

[13]

Y. C. LiuH. F. Xu and J. J. Ye, Penalized sample average approximation methods for stochastic mathematical programs with complementarity constraints, Math. Oper. Res., 36 (2011), 670-694.  doi: 10.1287/moor.1110.0513.  Google Scholar

[14]

R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren der mathematischen Wissenschaften, 317. Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[15]

A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming, Society for Industrial and Applied Mathematics, 2009. doi: 10.1137/1.9780898718751.  Google Scholar

[16]

S. Smale, Algorithms for solving equations, Proceedings of the International Congress of Mathematicians, Amer. Math. Soc., Providence, RI, 1, 2 (1986), 172-195.   Google Scholar

[17]

H. L. SunC.-L. Su and X. J. Chen, SAA-regularized methods for multiproduct price optimization under the pure characteristics demand model, Math. Program., 165 (2017), 361-389.  doi: 10.1007/s10107-017-1119-6.  Google Scholar

[18]

G. X. WangJ. ZhangB. Zeng and G.-H. Lin, Expected residual minimization formulation for a class of stochastic linear second-order cone complementarity problems, Eur. J. Oper. Res., 265 (2018), 437-447.  doi: 10.1016/j.ejor.2017.09.008.  Google Scholar

[19]

H. F. 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.  Google Scholar

[20]

H. F. Xu and D. L. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications, Math. Program. Ser. A, 119 (2009), 371-401.  doi: 10.1007/s10107-008-0214-0.  Google Scholar

[21]

J. J. Ye, The exact penalty principle, Nonlinear Anal., 75 (2012), 1642-1654.  doi: 10.1016/j.na.2011.03.025.  Google Scholar

[22]

J. J. Ye and J. C. Zhou, First-order optimality conditions for mathematical programs with second-order cone complementarity constraints,, SIAM J. Optim., 26 (2016), 2820-2846.  doi: 10.1137/16M1055554.  Google Scholar

[23]

J. J. Ye and J. C. Zhou, Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems, Math. Program. Ser. A, 171 (2018), 361-395.  doi: 10.1007/s10107-017-1193-9.  Google Scholar

[24]

J. ZhangL.-W. Zhang and S. Lin, A class of smoothing SAA methods for a stochastic mathematical program with complementarity constraints, J. Math. Anal. Appl., 387 (2012), 201-220.  doi: 10.1016/j.jmaa.2011.08.073.  Google Scholar

[25]

Y. ZhangY. JiangL. W. Zhang and J. Z. Zhang, A perturbation approach for an inverse linear second-order cone programming, J. Ind. Manag. Optim., 9 (2013), 171-189.  doi: 10.3934/jimo.2013.9.171.  Google Scholar

[26]

Y. ZhangL. W. Zhang and J. Wu, Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints, Set-Valued Var. Anal., 19 (2011), 609-646.  doi: 10.1007/s11228-011-0190-z.  Google Scholar

show all references

References:
[1]

Ş. İ. BirbilG. Gürkan and O. Listeş, Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res., 31 (2006), 739-760.  doi: 10.1287/moor.1060.0215.  Google Scholar

[2]

B. T. Chen and P. T. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM J. Matrix Anal. Appl., 14 (1993), 1168-1190.  doi: 10.1137/0614081.  Google Scholar

[3]

X. J. ChenH. L. Sun and R. J.-B. Wets, Regularized mathematical programs with stochastic equilibrium constraints: Estimating structural demand models, SIAM J. Optim., 25 (2015), 53-75.  doi: 10.1137/130930157.  Google Scholar

[4]

S. ChristiansenM. Patriksson and L. Wynter, Stochastic bilevel programming in structural optimization, Struct. Multidiscip. Optim., 21 (2001), 361-371.  doi: 10.1007/s001580100115.  Google Scholar

[5]

F. H. Clarke, Optimization and Nonsmooth Analysis, Second edition, Classics in Applied Mathematics, 5. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. doi: 10.1137/1.9781611971309.  Google Scholar

[6]

H. Y. Jiang and H. F. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Trans. Autom. Control, 53 (2008), 1462-1475.  doi: 10.1109/TAC.2008.925853.  Google Scholar

[7]

C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17 (1996), 851-868.  doi: 10.1137/S0895479894273134.  Google Scholar

[8]

A. J. King and R. T. Rockafellar, Sensitivity analysis for nonsmooth generalized equations, Math. Program., 55 (1992), 193-212.  doi: 10.1007/BF01581199.  Google Scholar

[9]

G.-H. LinM.-J. Luo and J. Zhang, Smoothing and SAA method for stochastic programming problems with non-smooth objective and constraints, J. Global Optim., 66 (2016), 487-510.  doi: 10.1007/s10898-016-0413-9.  Google Scholar

[10]

G.-H. LinM.-J. LuoD. L. Zhang and J. Zhang, Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications, Math. Program., 165 (2017), 197-233.  doi: 10.1007/s10107-017-1121-z.  Google Scholar

[11]

G.-H. LinH. F. Xu and M. Fukushima, Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints, Math. Method Oper. Res., 67 (2008), 423-441.  doi: 10.1007/s00186-007-0201-x.  Google Scholar

[12]

Y. C. Liu and G.-H. Lin, Convergence analysis of a regularized sample average approximation method for stochastic mathematical programs with complementarity constraints, Asia Pac. J. Oper. Res., 28 (2011), 755-771.  doi: 10.1142/S0217595911003338.  Google Scholar

[13]

Y. C. LiuH. F. Xu and J. J. Ye, Penalized sample average approximation methods for stochastic mathematical programs with complementarity constraints, Math. Oper. Res., 36 (2011), 670-694.  doi: 10.1287/moor.1110.0513.  Google Scholar

[14]

R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren der mathematischen Wissenschaften, 317. Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[15]

A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming, Society for Industrial and Applied Mathematics, 2009. doi: 10.1137/1.9780898718751.  Google Scholar

[16]

S. Smale, Algorithms for solving equations, Proceedings of the International Congress of Mathematicians, Amer. Math. Soc., Providence, RI, 1, 2 (1986), 172-195.   Google Scholar

[17]

H. L. SunC.-L. Su and X. J. Chen, SAA-regularized methods for multiproduct price optimization under the pure characteristics demand model, Math. Program., 165 (2017), 361-389.  doi: 10.1007/s10107-017-1119-6.  Google Scholar

[18]

G. X. WangJ. ZhangB. Zeng and G.-H. Lin, Expected residual minimization formulation for a class of stochastic linear second-order cone complementarity problems, Eur. J. Oper. Res., 265 (2018), 437-447.  doi: 10.1016/j.ejor.2017.09.008.  Google Scholar

[19]

H. F. 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.  Google Scholar

[20]

H. F. Xu and D. L. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications, Math. Program. Ser. A, 119 (2009), 371-401.  doi: 10.1007/s10107-008-0214-0.  Google Scholar

[21]

J. J. Ye, The exact penalty principle, Nonlinear Anal., 75 (2012), 1642-1654.  doi: 10.1016/j.na.2011.03.025.  Google Scholar

[22]

J. J. Ye and J. C. Zhou, First-order optimality conditions for mathematical programs with second-order cone complementarity constraints,, SIAM J. Optim., 26 (2016), 2820-2846.  doi: 10.1137/16M1055554.  Google Scholar

[23]

J. J. Ye and J. C. Zhou, Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems, Math. Program. Ser. A, 171 (2018), 361-395.  doi: 10.1007/s10107-017-1193-9.  Google Scholar

[24]

J. ZhangL.-W. Zhang and S. Lin, A class of smoothing SAA methods for a stochastic mathematical program with complementarity constraints, J. Math. Anal. Appl., 387 (2012), 201-220.  doi: 10.1016/j.jmaa.2011.08.073.  Google Scholar

[25]

Y. ZhangY. JiangL. W. Zhang and J. Z. Zhang, A perturbation approach for an inverse linear second-order cone programming, J. Ind. Manag. Optim., 9 (2013), 171-189.  doi: 10.3934/jimo.2013.9.171.  Google Scholar

[26]

Y. ZhangL. W. Zhang and J. Wu, Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints, Set-Valued Var. Anal., 19 (2011), 609-646.  doi: 10.1007/s11228-011-0190-z.  Google Scholar

Table 1.  Numerical result for Problem (22)
N $ \bar{f} $ $ \bar{\varepsilon}_u $ $ \bar{\varepsilon}_v $ infea time(s)
1000 1.53 8.88E-02 4.07E-02 5.43E-06 0.02
10000 1.49 5.14E-02 2.82E-02 3.97E-05 0.02
100000 1.54 5.74E-02 6.77E-02 4.74E-03 0.02
1000000 1.44 3.74E-04 5.22E-04 6.23E-06 0.13
10000000 1.44 1.82E-04 1.89E-04 7.35E-06 1.23
N $ \bar{f} $ $ \bar{\varepsilon}_u $ $ \bar{\varepsilon}_v $ infea time(s)
1000 1.53 8.88E-02 4.07E-02 5.43E-06 0.02
10000 1.49 5.14E-02 2.82E-02 3.97E-05 0.02
100000 1.54 5.74E-02 6.77E-02 4.74E-03 0.02
1000000 1.44 3.74E-04 5.22E-04 6.23E-06 0.13
10000000 1.44 1.82E-04 1.89E-04 7.35E-06 1.23
[1]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[2]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[3]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[4]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[5]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[6]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[7]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[8]

Wenqiang Zhao, Yijin Zhang. High-order Wong-Zakai approximations for non-autonomous stochastic $ p $-Laplacian equations on $ \mathbb{R}^N $. Communications on Pure & Applied Analysis, 2021, 20 (1) : 243-280. doi: 10.3934/cpaa.2020265

[9]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[10]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[11]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[12]

Martin Kalousek, Joshua Kortum, Anja Schlömerkemper. Mathematical analysis of weak and strong solutions to an evolutionary model for magnetoviscoelasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 17-39. doi: 10.3934/dcdss.2020331

[13]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110

[14]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323

[15]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[16]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[17]

Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278

[18]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[19]

Xuhui Peng, Rangrang Zhang. Approximations of stochastic 3D tamed Navier-Stokes equations. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5337-5365. doi: 10.3934/cpaa.2020241

[20]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]