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

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

[2]

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

[3]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[4]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[5]

Baba Issa Camara, Houda Mokrani, Evans K. Afenya. Mathematical modeling of glioma therapy using oncolytic viruses. Mathematical Biosciences & Engineering, 2013, 10 (3) : 565-578. doi: 10.3934/mbe.2013.10.565

[6]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[7]

A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909

[8]

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

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

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597

[11]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[12]

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

[13]

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

[14]

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

[15]

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

[16]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044

[17]

Shangzhi Li, Shangjiang Guo. Permanence and extinction of a stochastic SIS epidemic model with three independent Brownian motions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2693-2719. doi: 10.3934/dcdsb.2020201

[18]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192

[19]

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

[20]

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

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (67)
  • HTML views (374)
  • Cited by (0)

Other articles
by authors

[Back to Top]