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

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

Abstract

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

CLC Number:

O221.2

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

Figures/Tables 2

References 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]	Maoran WANG, Xingju CAI, Zhongming WU, Deren HAN. First-order splitting algorithm for multi-model traffic equilibrium problems [J]. Operations Research Transactions, 2023, 27(2): 63-78.
[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.
[3]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[4]	Xueling ZHOU, Meixia LI, Haitao CHE. Successive relaxed projection algorithm for multiple-sets split equality problem [J]. Operations Research Transactions, 2021, 25(2): 93-103.
[5]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[6]	CHEN Xiangping. Spectral HS projection algorithm for solving nonlinear monotone equations [J]. Operations Research Transactions, 2018, 22(3): 15-27.
[7]	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.
[8]	QU Biao, ZHANG Wenwei, YU Lichao. The relaxed projection methods for solving the l_1-norm problem of linear equations and their applications [J]. Operations Research Transactions, 2017, 21(2): 57-65.
[9]	HANG Dan, YAN Shijian. Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters [J]. Operations Research Transactions, 2016, 20(4): 85-92.
[10]	LIU Yuanwen, OU Yigui. A hybrid method for a system of nonlinear equations with bound constraints [J]. Operations Research Transactions, 2015, 19(1): 45-56.
[11]	LIU Yuanyuan, OU Yigui. An ODE-based hybrid method based on the nonmonotone technique [J]. Operations Research Transactions, 2013, 17(3): 11-22.
[12]	ZHAO Qi, ZHANG Yan. A Nonmonotoe Filter Method For Minimax Problems [J]. Operations Research Transactions, 2012, 16(2): 91-104.
[13]	WANG Hua. A Nonmonotone Feasible SQP Method for Nonlinear Complementarity Problem [J]. Operations Research Transactions, 2011, 15(2): 85-94.

An inertial projection algorithm for nonmonotone continuous variational inequalities

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 27

Related Articles 13

Recommended Articles

Metrics

Comments