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

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

Abstract

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

CLC Number:

O221.2

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

Figures/Tables 4

References 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]	Jia HU, Tiande GUO, Congying HAN. Mini-batch stochastic block coordinate descent algorithm [J]. Operations Research Transactions, 2022, 26(1): 1-22.
[2]	FENG Junkai, ZHANG Haibin, QIN Yuan, ZHANG Kaili. An inexact parallel alternating direction method for structured variational inequalities [J]. Operations Research Transactions, 2018, 22(2): 18-30.
[3]	LUO Guowang, PENG Yanfang, LIU Yanmin, HUANG Jianwen. Continuity of the solution set map to parametric weak vector equilibrium problems [J]. Operations Research Transactions, 2016, 20(1): 118-124.
[4]	XIA Shun-You, XU De-Ping. The Stability of the Solutions of Optimization Problem for Set-Valued Maps With Upper Semi-continuity Under Graphic Approximate [J]. Operations Research Transactions, 2012, 16(1): 115-120.

A new projection and contraction algorithm for solving quasimonotone variational inequalities

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 20

Related Articles 4

Recommended Articles

Metrics

Comments