连续非单调变分不等式的一种惯性投影算法

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

摘要/Abstract

摘要：

一种求解非单调变分不等式问题的投影算法(IPA) 由Ye (2022) 提出。IPA无需变分不等式的映射具有任何的单调性, 仅在映射连续且对偶变分不等式解集非空的条件下得到了算法的全局收敛性。本文提出了惯性的IPA算法, 并在相同的假设下证明了新算法的全局收敛性。数值实验表明, 惯性方法能加速IPA。

关键词: 变分不等式, 投影算法, 非单调, 惯性方法

Abstract:

An infeasible projection algorithm (IPA) for solving nonmonotone variational inequality problems was proposed by Ye (2022). Without needing any monotonicity condition of the underlying mapping, the global convergence of the sequence generated by IPA is established whenever the underlying mapping is continuous and the solution set of the dual variational inequality is nonempty. In this paper, we present an inertial IPA for solving nonmonotone variational inequalities. The global convergence of this new algorithm is proved under the same assumptions in IPA. Numerical experiments show that the inertial technique can accelerate IPA.

Key words: variational inequalities, projection algorithm, nonmonotone, inertial technique

中图分类号:

O221.2

叶明露, 黄明. 连续非单调变分不等式的一种惯性投影算法[J]. 运筹学学报（中英文）, 2024, 28(2): 81-92.

Minglu YE, Ming HUANG. An inertial projection algorithm for nonmonotone continuous variational inequalities[J]. Operations Research Transactions, 2024, 28(2): 81-92.

图/表 2

参考文献 27

1	Karamardian S . Complementarity problems over cones with monotone and pseudomonotone maps[J]. Journal of Optimization Theory and Applications, 1976, 18 (4): 445- 454. doi: 10.1007/BF00932654
2	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
3	Levitin E S , Polyak B T . Constrained minimization problems[J]. USSR Computational Mathematical Physics, 1966, 6 (5): 1- 50. doi: 10.1016/0041-5553(66)90114-5
4	Korpelevich G M . An extragradient method for finding saddle points and for other problems[J]. Matecon, 1976, 12 (4): 747- 756.
5	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
6	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
7	Ye M L , He Y R . A double projection method for solving variational inequalities without monotonocity[J]. Computation Optimization and Applications, 2015, 60 (1): 141- 150. doi: 10.1007/s10589-014-9659-7
8	Burachik R S , Millan R D . A projection algorithm for non-monotone variational inequalities[J]. Set-valued and Variational Analysis, 2020, 28 (1): 149- 166. doi: 10.1007/s11228-019-00517-0
9	Strodiot J J , Vuong P T , Nguyen T T . A class of shrinking projection extragradient methods for solving non-monotone equilibrium problems in Hilbert spaces[J]. Journal of Global Optimization, 2016, 64 (1): 159- 178. doi: 10.1007/s10898-015-0365-5
10	Van Dinh B , Kim D S . Projection algorithms for solving nonmonotone equilibrium problems in Hilbert space[J]. Journal of Computational and Applied Mathematics, 2016, 302, 106- 117. doi: 10.1016/j.cam.2016.01.054
11	Deng L , Hu R , Fang Y . Projection extragradient algorithms for solving nonmonotone and non-Lipschitzian equilibrium problems in Hilbert spaces[J]. Numerical Algorithms, 2021, 86, 191- 221. doi: 10.1007/s11075-020-00885-x
12	Liu H , Yang J . Weak convergence of iterative methods for solving quasimonotone variational inequalities[J]. Computation Optimization and Applications, 2020, 77 (2): 491- 508. doi: 10.1007/s10589-020-00217-8
13	Ye M L . An infeasible projection type algorithm for nonmonotone variational inequalities[J]. Numerical Algorithms, 2022, 89 (4): 1723- 1742. doi: 10.1007/s11075-021-01170-1
14	Polyak B T . Some methods of speeding up the convergence of iteration methods[J]. USSR Computational Mathematical Physics, 1964, 4 (5): 1- 17. doi: 10.1016/0041-5553(64)90137-5
15	Wen B , Chen X , Pong T K . A proximal difference of convex algorithm with extrapolation[J]. Computation Optimization and Applications, 2018, 69, 297- 324. doi: 10.1007/s10589-017-9954-1
16	Pock T , Sabach S . Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems[J]. SIAM Journal on Imaging Sciences, 2016, 9, 1756- 1787. doi: 10.1137/16M1064064
17	Thong D V , Van Hieu D , Rassias T M . Self adaptive inertial subgradient extragradient algorithms for solving pseudomonotone variational inequality problems[J]. Optimization Letters, 2020, 14, 115- 144. doi: 10.1007/s11590-019-01511-z
18	Thong D V , Vinh N T , Cho Y J . New strong convergence theorem of the inertial projection and contraction method for variational inequality problems[J]. Numerical Algorithms, 2020, 84 (1): 285- 305. doi: 10.1007/s11075-019-00755-1
19	Shehu Y , Iyiola O S . Projection methods with alternating inertial steps for variational inequalities: Weak and linear convergence[J]. Applied Numerical Mathematics, 2020, 157, 315- 337. doi: 10.1016/j.apnum.2020.06.009
20	Ye M L , Pong T K . A subgradient-based approach for finding the maximum feasible subsystem with respect to a set[J]. SIAM Journal on Optimization, 2020, 30 (2): 1274- 1299. doi: 10.1137/18M1186320
21	He Y . Solvability of the minty variational inequality[J]. Journal of Optimization Theory and Applications, 2017, 174 (3): 686- 692. doi: 10.1007/s10957-017-1124-1
22	Zarantonello E H . Projections on Convex sets in Hilbert Space and Spectral Theory, Contributions to Nonlinear Functional Analysis[M]. New York: Academic Press, 1971.
23	He Y R . A new double projection algorithm for variational inequalities[J]. Journal of Computational and Applied Mathematics, 2006, 185 (1): 163- 173.
24	Boyd S , Vandenberghe L . Convex Optimization[M]. Cambridge: Cambridge University Press, 2004.
25	Ye M L . An improved projection method for solving generelized varistional inequality problems[J]. Optimization, 2018, 67 (9): 1523- 1533. doi: 10.1080/02331934.2018.1478971
26	Gafni E M , Bertsekas D P . Two-metric projection problems and descent methods for asymmetric variational inequality problems[J]. Mathematical Programming, 1984, 53, 99- 110.
27	Polyak B T . Introduction to Optimization[M]. New York: Optimization Software, 1987.

$ n $	iter		np		CPU		disxS
$ n $	IPA1	IPA2	IPA1	IPA2	IPA1	IPA2	IPA1	IPA2
50	24	6	26	21	0.00	0.01	$ 3\times 10^{-5} $	$ 6\times 10^{-5} $
100	49	11	51	39	0.01	0.01	$ 5\times 10^{-5} $	$ 1\times 10^{-4} $
500	76	17	79	57	0.01	0.01	$ 8\times 10^{-5} $	$ 3\times 10^{-4} $
1 000	104	23	108	77	0.02	0.01	$ 1\times 10^{-4} $	$ 6\times 10^{-4} $
3 000	132	31	137	114	0.04	0.01	$ 1\times 10^{-4} $	$ 1\times 10^{-3} $

$ n $	iter		np		CPU		disxS
$ n $	IPA1	IPA2	IPA1	IPA2	IPA1	IPA2	IPA1	IPA2
1 000	19	4	39	7	0.01	0.00	$ 7\times 10^{-6} $	$ 1\times 10^{-15} $
2 000	38	8	79	14	0.02	0.01	$ 1\times 10^{-5} $	$ 7\times 10^{-15} $
3 000	57	12	119	21	0.03	0.01	$ 2\times 10^{-5} $	$ 1\times 10^{-14} $

[1]	王茂然, 蔡邢菊, 吴中明, 韩德仁. 多模式交通均衡问题的一阶分裂算法[J]. 运筹学学报, 2023, 27(2): 63-78.
[2]	叶明露, 邓欢. 一种新的求解拟单调变分不等式的压缩投影算法[J]. 运筹学学报, 2023, 27(1): 127-137.
[3]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[4]	周雪玲, 李梅霞, 车海涛. 多集分裂等式问题的逐次松弛投影算法[J]. 运筹学学报, 2021, 25(2): 93-103.
[5]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[6]	王秀玲, 龚循华. 对称向量拟均衡问题有效解的存在性[J]. 运筹学学报, 2021, 25(1): 73-80.
[7]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[8]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[9]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[10]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[11]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[12]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[13]	屈彪, 张文伟, 于丽超. 线性方程组l_1范数问题的松弛投影算法及其应用[J]. 运筹学学报, 2017, 21(2): 57-65.
[14]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[15]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.