English

运筹学学报 >

2023 , Vol. 27 >Issue 1: 127 - 137

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.01.009

 

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

展开
  • 1. 西华师范大学 数学与信息学院 四川高等院校优化理论与应用重点实验室, 四川南充 637009
叶明露, E-mail: yml2002cn@aliyun.com

收稿日期: 2022-09-28

  网络出版日期: 2023-03-16

基金资助

国家自然科学基金面上项目(11871059);西华师范大学培育项目(20A024)

收起

A new projection and contraction algorithm for solving quasimonotone variational inequalities

Expand
  • 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 date: 2022-09-28

  Online published: 2023-03-16

Fold

摘要

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

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

本文引用格式

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

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

参考文献

1 Goldstein A A . Convex programming in Hilbert space[J]. Bulletin of the American Mathematical Society, 1964, 70 (5): 709- 710.
2 Levitin E S , Polyak B T . Constrained minimization methods[J]. USSR Computational Mathematics and Mathematical Physics, 1966, 6 (5): 1- 50.
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.
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.
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.
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.
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.
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.
11 He B . A class of projection and contraction methods for monotone variational inequalities[J]. Applied Mathematics and Optimization, 1997, 35 (1): 69- 76.
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.
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.
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.
16 Ye M . A half-space projection method for solving generalized Nash equilibrium problems[J]. Optimization, 2017, 66 (7): 1119- 1134.
17 He Y . A new double projection algorithm for variational inequalities[J]. Journal of Computational and Applied Mathematics, 2006, 185 (1): 166- 173.
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.
Options
文章导航

/

〈 〉