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

Li Chu; Bo Wang; Jie Zhang; Hong-Wei Zhang

doi:10.3934/jimo.2020050

Article Contents

2021, Volume 17, Issue 4: 1863-1886. Doi: 10.3934/jimo.2020050

This issue Previous Article A stochastic model and social optimization of a blockchain system based on a general limited batch service queue Next Article Optimal mean-variance reinsurance in a financial market with stochastic rate of return

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
^* Corresponding author: Bo Wang

Received: April 30, 2019

Revised: September 30, 2019

Early access: March 2020

Published: July 2021

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

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C46, 90C26.

Citation:

FullText(HTML)

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Ş. İ. Birbil, G. 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.
[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.
[3]	X. J. Chen, H. 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.
[4]	S. Christiansen, M. Patriksson and L. Wynter, Stochastic bilevel programming in structural optimization, Struct. Multidiscip. Optim., 21 (2001), 361-371. doi: 10.1007/s001580100115.
[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.
[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.
[7]	C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17 (1996), 851-868. doi: 10.1137/S0895479894273134.
[8]	A. J. King and R. T. Rockafellar, Sensitivity analysis for nonsmooth generalized equations, Math. Program., 55 (1992), 193-212. doi: 10.1007/BF01581199.
[9]	G.-H. Lin, M.-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.
[10]	G.-H. Lin, M.-J. Luo, D. 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.
[11]	G.-H. Lin, H. 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.
[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.
[13]	Y. C. Liu, H. 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.
[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.
[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.
[16]	S. Smale, Algorithms for solving equations, Proceedings of the International Congress of Mathematicians, Amer. Math. Soc., Providence, RI, 1, 2 (1986), 172-195.
[17]	H. L. Sun, C.-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.
[18]	G. X. Wang, J. Zhang, B. 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.
[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.
[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.
[21]	J. J. Ye, The exact penalty principle, Nonlinear Anal., 75 (2012), 1642-1654. doi: 10.1016/j.na.2011.03.025.
[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.
[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.
[24]	J. Zhang, L.-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.
[25]	Y. Zhang, Y. Jiang, L. 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.
[26]	Y. Zhang, L. 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.