一种新的求解拟单调变分不等式的压缩投影算法

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

运筹学学报 ›› 2023, Vol. 27 ›› Issue (1): 127-137.doi: 10.15960/j.cnki.issn.1007-6093.2023.01.009

一种新的求解拟单调变分不等式的压缩投影算法

叶明露¹^,*(), 邓欢¹

1. 西华师范大学数学与信息学院四川高等院校优化理论与应用重点实验室, 四川南充 637009

收稿日期:2022-09-28 出版日期:2023-03-15 发布日期:2023-03-16
通讯作者: 叶明露 E-mail:yml2002cn@aliyun.com
作者简介:叶明露, E-mail: yml2002cn@aliyun.com
基金资助:
国家自然科学基金面上项目(11871059);西华师范大学培育项目(20A024)

A new projection and contraction algorithm for solving quasimonotone variational inequalities

Minglu YE¹^,*(), Huan DENG¹

1. Sichuan Colleges and Universities Key Laboratory of Optimization Theory and Applications, School of Mathematics and Information, China West Normal University, Nanchong, 637009, Sichuan, China

Received:2022-09-28 Online:2023-03-15 Published:2023-03-16
Contact: Minglu YE E-mail:yml2002cn@aliyun.com

摘要/Abstract

摘要：

2020年Liu和Yang提出了求解Hilbert空间中拟单调且Lipschitz连续的变分不等式问题的投影算法，简称LYA。本文在欧氏空间中提出了一种新的求解拟单调变分不等式的压缩投影算法, 简称NPCA。新算法削弱了LYA中映射的Lipschitz连续性。在映射连续、拟单调且对偶变分不等式解集非空的条件下得到了NPCA所生成点列的聚点是解的结论。当变分不等式的解集还满足一定条件时，得到了NPCA的全局收敛性。数值实验结果表明NPCA所需的迭代步数少于LYA的迭代步数，NPCA在高维拟单调例子中所需的计算机耗时也更少。

关键词: 变分不等式, 拟单调, 压缩投影算法, 连续

Abstract:

In 2020, Liu and Yang proposed a projection algorithm (LYA for short) for solving quasi-monotone and Lipschitz continuous variational inequalities problem (VIP for short) in Hilbert space. In this paper, we present a new projection and contraction algorithm (NPCA for short) for solving quasi-monotone VIP in Euclidean space. The new algorithm weakens the Lipschitz continuity of the underlying mapping in LYA. NPCA clusters to the solution of VIP whenever the underlying mapping is continuous, quasi-monotone and the solution set of dual variational inequality is nonempty. The global convergence of NPCA needs an additional assumption about the solution set of VIP. Numerical experiments show that NPCA is more efficient than LYA from the total number of iterative point of view, and the CPU time point of view in high dimensional quasi-monotone VIP.

Key words: variational inequalities, quasi-monotone, projection and contraction algorithm, continuity

中图分类号:

O221.2

叶明露, 邓欢. 一种新的求解拟单调变分不等式的压缩投影算法[J]. 运筹学学报, 2023, 27(1): 127-137.

Minglu YE, Huan DENG. A new projection and contraction algorithm for solving quasimonotone variational inequalities[J]. Operations Research Transactions, 2023, 27(1): 127-137.

图/表 4

表1

表2

表3

表4

参考文献 20

1	Goldstein A A . Convex programming in Hilbert space[J]. Bulletin of the American Mathematical Society, 1964, 70 (5): 709- 710. doi: 10.1090/S0002-9904-1964-11178-2
2	Levitin E S , Polyak B T . Constrained minimization methods[J]. USSR Computational Mathematics and Mathematical Physics, 1966, 6 (5): 1- 50. doi: 10.1016/0041-5553(66)90114-5
3	Korpelevich G M . An extragradient method for finding saddle points and for other problems[J]. Matecon, 1976, 12 (4): 747- 756.
4	Khobotov E N . Modification of the extra-gradient method for solving variational inequalities and certain optimization problems[J]. USSR Computational Mathematics and Mathematical Physics, 1987, 27 (5): 120- 127. doi: 10.1016/0041-5553(87)90058-9
5	Iusem A N . An iterative algorithm for the variational inequality problem[J]. Computational and Applied Mathematics, 1994, 13, 103- 114.
6	Iusem A N , Svaiter B F . A variant of Korpelevich's method for variational inequalities with a new search strategy[J]. Optimization, 1997, 42 (4): 309- 321. doi: 10.1080/02331939708844365
7	Solodov M V , Svaiter B F . A new projection method for variational inequality problems[J]. SIAM Journal on Control and Optimization, 1999, 37 (3): 765- 776. doi: 10.1137/S0363012997317475
8	Tseng P . A modified forward-backward splitting method for maximal monotone mappings[J]. SIAM Journal on Control and Optimization, 2000, 38 (2): 431- 446. doi: 10.1137/S0363012998338806
9	Censor Y , Gibali A , Reich S . The subgradient extragradient method for solving variational inequalities in Hilbert space[J]. Journal of Optimization Theory and Applications, 2011, 148 (2): 318- 335. doi: 10.1007/s10957-010-9757-3
10	Vuong P T . On the weak convergence of the extragradient method for solving pseudo-monotone variational inequalities[J]. Journal of Optimization Theory and Applications, 2018, 176 (2): 399- 409. doi: 10.1007/s10957-017-1214-0
11	He B . A class of projection and contraction methods for monotone variational inequalities[J]. Applied Mathematics and Optimization, 1997, 35 (1): 69- 76. doi: 10.1007/s002459900037
12	Ye M , He Y . A double projection method for solving variational inequalities without monotonicity[J]. Computational Optimization and Applications, 2015, 60 (1): 141- 150. doi: 10.1007/s10589-014-9659-7
13	Lei M , He Y R . An extragradient method for solving variational inequalities without monotonicity[J]. Journal of Optimization Theory and Applications, 2021, 60 (188): 432- 446.
14	Ye M . An infeasible projection type algorithm for nonmonotone variational inequalities[J]. Numerical Algorithms, 2022, 89 (4): 1723- 1742. doi: 10.1007/s11075-021-01170-1
15	Liu H , Yang J . Weak convergence of iterative methods for solving quasimonotone variational inequalities[J]. Computational Optimization and Applications, 2020, 77 (2): 491- 508. doi: 10.1007/s10589-020-00217-8
16	Ye M . A half-space projection method for solving generalized Nash equilibrium problems[J]. Optimization, 2017, 66 (7): 1119- 1134. doi: 10.1080/02331934.2017.1326045
17	He Y . A new double projection algorithm for variational inequalities[J]. Journal of Computational and Applied Mathematics, 2006, 185 (1): 166- 173. doi: 10.1016/j.cam.2005.01.031
18	Facchinei F , Pang J S . Finite-Dimensional Variational Inequalities and Complementarity Problems[M]. New York: Springer, 2003.
19	Boyd S P , Vandenberghe L . Convex Optimization[M]. Cambridge: Cambridge University Press, 2004.
20	He B , Liao L . Improvements of some projection methods for monotone nonlinear variational inequalities[J]. Journal of Optimization Theory and Applications, 2002, 112 (1): 111- 128. doi: 10.1023/A:1013096613105

$ x^0 $	iter			CPU
$ x^0 $	NPCA	LYA1	LYA2	NPCA	LYA1	LYA2
$ -3 $	32	171	162	0.001 13	0.001 51	0.002 12
$ -2 $	29	162	1	0.001 19	0.001 65	0.000 501
0.5	25	151	151	0.001 16	0.001 69	0.001 72
0.7	28	156	155	0.001 2	0.001 95	0.001 93
0.9	28	161	159	0.001 13	0.001 45	0.001 72
1	1	162	160	0.000 586	0.001 55	0.001 6
4	29	174	172	0.001 17	0.001 68	0.001 72

$ x^0 $	iter			CPU
$ x^0 $	NPCA	LYA1	LYA2	NPCA	LYA1	LYA2
(0, 1)	10	18	20	0.001 21	0.002 63	0.001 13
(0, 0)	7	18	0	0.001 37	0.002 71	0.000 632
(1, 0)	10	18	19	0.001 43	0.001 97	0.001 08
(0.5, 0.5)	7	16	18	0.001 26	0.002 34	0.001 22
(0.2, 0.7)	7	17	19	0.001 22	0.002 22	0.001 3
(0.1, 0.6)	7	17	19	0.001 27	0.001 97	0.001 18
Random	9	17	19	0.001 32	0.002 16	0.001 25
Random	8	15	18	0.001 35	0.001 87	0.001 07

$ x^0 $	$ a $	iter			CPU
$ x^0 $	$ a $	NPCA	LYA1	LYA2	NPCA	LYA1	LYA2
(0, 0, 0, 0, 5)	5	39	155	154	0.295	0.541	0.484
(0, 0, 5, 0, 0)	5	39	155	154	0.295	0.55	0.487
(0, 2, 0, 2, 1)	5	42	150	159	0.273	0.525	0.497
(1, 1, 1, 1, 6)	10	28	309	295	0.101	1.02	0.912
(5, 0, 0, 0, 5)	10	45	313	293	0.156	1.03	0.916

$ n $	iter			CPU
$ n $	NPCA	LYA1	LYA2	NPCA	LYA1	LYA2
50	93	1 369	1 442	0.392	5.72	5.96
100	170	2 646	2 775	0.93	14.4	14.9
200	324	5 093	5 387	2.71	86	91.1
500	769	11 979	12 620	16.9	535	551
1 000	1 482	$ \backslash $	$ \backslash $	73.749 9	$ \backslash $	$ \backslash $

[1]	胡佳, 郭田德, 韩丛英. 小批量随机块坐标下降算法[J]. 运筹学学报, 2022, 26(1): 1-22.
[2]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[3]	李红武, 谢敏, 张榕. 一类非光滑凸优化问题的邻近梯度算法[J]. 运筹学学报, 2021, 25(1): 61-72.
[4]	王秀玲, 龚循华. 对称向量拟均衡问题有效解的存在性[J]. 运筹学学报, 2021, 25(1): 73-80.
[5]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[6]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[7]	孟旭东, 王三华, 龚循华. 含参广义集值向量均衡问题有效解映射下半连续的最优条件[J]. 运筹学学报, 2018, 22(3): 79-88.
[8]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[9]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[10]	隋允康, 李臻臻, 李宏, 陈国庆. 基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法[J]. 运筹学学报, 2017, 21(3): 35-44.
[11]	邢文训. 离散优化与连续优化的复杂性概念[J]. 运筹学学报, 2017, 21(2): 39-45.
[12]	杨琦, 蒋志刚, 冯恩民, 尹洪超, 修志龙. 以函数为参量的间歇发酵非线性动力系统及其辨识[J]. 运筹学学报, 2017, 21(2): 46-56.
[13]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.
[14]	罗国旺, 彭艳芳, 刘衍民, 黄建文. 参数弱向量平衡问题解集映射的连续性[J]. 运筹学学报, 2016, 20(1): 118-124.
[15]	何炳生. 修正乘子交替方向法求解三个可分离算子的凸优化[J]. 运筹学学报, 2015, 19(3): 57-70.

一种新的求解拟单调变分不等式的压缩投影算法

A new projection and contraction algorithm for solving quasimonotone variational inequalities

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 20

相关文章 15

编辑推荐

Metrics

本文评价