随机二阶锥二次规划逆问题的SAA方法

doi:10.15960/j.cnki.issn.1007-6093.2022.02.003

运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 31-44.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.003

随机二阶锥二次规划逆问题的SAA方法

王博¹, 初丽²^,*(), 张立卫³, 张宏伟³

1. 福州大学数学与统计学院, 运筹学与控制论高校重点实验室, 福建福州 350116
2. 福建工程学院计算机科学与数学学院, 福建福州 350118
3. 大连理工大学数学科学学院, 辽宁大连 116024

收稿日期:2020-06-23 出版日期:2022-06-15 发布日期:2022-05-27
通讯作者: 初丽 E-mail:sophiatruly@126.com
作者简介:初丽 E-mail: sophiatruly@126.com
基金资助:
国家自然科学基金青年项目(11701091)

An SAA approach for a class of second-order cone stochastic inverse quadratic programming problem

Bo WANG¹, Li CHU²^,*(), Liwei ZHANG³, Hongwei ZHANG³

1. Key Laboratory of Operations Research and Control of Universities in Fujian, School of Mathematics and Statistics, Fuzhou University, Fuzhou 350116, Fujian, China
2. College of Computer Science and Mathematics, Fujian University of Technology, Fuzhou 350118, Fujian, China
3. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, Liaoning, China

Received:2020-06-23 Online:2022-06-15 Published:2022-05-27
Contact: Li CHU E-mail:sophiatruly@126.com

摘要/Abstract

摘要：

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。

关键词: 随机抽样, 互补约束, 二阶锥优化

Abstract:

In this paper, we consider a class of stochastic inverse quadratic second-order cone programming problem. This stochastic model contains complementarity constraints, and is more proper to model some class of real world problems. By employing the techniques of stochastic sampling and smoothing, we construct auxiliary approximate sub-problems to solve the original model. In addition, we proved that if the solutions of the approximate sub-problems converge, then with probability one the limit is the C-stationary point of the original problem. If strict complementarity condition and the second order necessary condition hold, then with probability one the limit is an M-stationary point. A simple numerical test verified the applicability of our approach.

Key words: stochastic sampling, complementarity constraint, second-order cone programming

中图分类号:

王博, 初丽, 张立卫, 张宏伟. 随机二阶锥二次规划逆问题的SAA方法[J]. 运筹学学报, 2022, 26(2): 31-44.

Bo WANG, Li CHU, Liwei ZHANG, Hongwei ZHANG. An SAA approach for a class of second-order cone stochastic inverse quadratic programming problem[J]. Operations Research Transactions, 2022, 26(2): 31-44.

图/表 1

参考文献 11

1	Ahuja R K , Orlin J B . Combinatorial algorithms for inverse network flow problems[J]. Networks, 2002, 40 (4): 181- 187. doi: 10.1002/net.10048
2	Heuberger C . Inverse combinatorial optimization: A survey on problems, methods, and results[J]. Journal of Combinatorial Optimization, 2004, 8 (3): 329- 361. doi: 10.1023/B:JOCO.0000038914.26975.9b
3	Jalilzadeh A, Hamedani E Y. Inverse quadratic transportation problem[J/OL]. (2014-09-21)[2020-05-20]. https://arxiv.org/abs/1409.6030v1.
4	Wang S , Liu Y , Jiang Y . A majorized penalty approach to inverse linear second order cone programming problems[J]. Journal of Industrial and Management Optimization, 2013, 10 (3): 965- 976.
5	Zhang Y , Zhang L , Wu J , et al. A perturbation approach for an inverse quadratic programming problem over second-order cones[J]. Mathematics of Computation, 2014, 84 (291): 209- 236. doi: 10.1090/S0025-5718-2014-02848-2
6	Zhang J , Zhang L . An augmented lagrangian method for a class of inverse quadratic programming problems[J]. Applied Mathematics and Optimization, 2009, 61 (1): 57.
7	Zhang J , Zhang L , Xiao X . A perturbation approach for an inverse quadratic programming problem[J]. Mathematical Methods of Operations Research, 2010, 72 (3): 379- 404. doi: 10.1007/s00186-010-0323-4
8	Xu H , Ye J J . Approximating stationary points of stochastic mathematical programs with equilibrium constraints via sample averaging[J]. Set-Valued and Variational Analysis, 2011, 19 (2): 283- 309. doi: 10.1007/s11228-010-0160-x
9	Shapiro A, Dentcheva D, Ruszczyński A. Lectures on Stochastic Programming[M]. Society for Industrial and Applied Mathematics, 2009.
10	Rockafellar R T , Wets R J B . Variational Analysis[M]. Berlin: Springer-Verlag, 1998.
11	Zhang Y , Zhang L , Wu J . Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints[J]. Set-Valued and Variational Analysis, 2011, 19 (4): 609. doi: 10.1007/s11228-011-0190-z

N	ErrSOC	ErrCom	ErrSol	运行时间/s
50	0	8.10×10^-2	1.96×10^-1	1.01
100	0	8.65×10^-2	2.90×10^-1	1.12
200	0	9.92×10^-2	8.49×10^-2	2.47
500	0	8.63×10^-2	6.51×10^-2	5.60
1 000	0	8.97×10^-2	4.31×10^-2	8.46
5 000	0	8.37×10^-2	1.42×10^-2	73.16
10 000	0	8.39×10^-2	2.10×10^-2	47.11
20 000	0	8.34×10^-2	1.81×10^-2	261.29
50 000	0	8.15×10^-2	8.89×10^-3	110.73

[1]	陈林, 杨新民. 一类带概率互补约束的随机优化问题的最优性条件[J]. 运筹学学报, 2017, 21(2): 24-30.
[2]	刘水霞, 陈国庆. 求解互补约束优化问题的乘子松弛法[J]. 运筹学学报, 2014, 18(4): 119-130.
[3]	张弘捷，白延琴，方淳亮. 鲁棒信用风险优化的线性锥优化模型[J]. 运筹学学报, 2013, 17(1): 86-97.
[4]	刘水霞, 陈国庆. 互补约束优化问题的乘子序列部分罚函数算法[J]. 运筹学学报, 2011, 15(4): 55-64.

随机二阶锥二次规划逆问题的SAA方法

An SAA approach for a class of second-order cone stochastic inverse quadratic programming problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 11

相关文章 4

编辑推荐

Metrics

本文评价