解变分不等式的一种二次投影算法

摘要/Abstract

摘要：

该文研究一种新的解变分不等式的二次投影算法.通过构造一类新的严格分离当前迭代和变分不等式解集的超平面，进而建立了解决伪单调变分不等式投影算法的一种新的框架.通过改进已有结果的证明方法，证明了该算法生成的无穷序列是全局收敛的，并且在局部误差和Lipschitz条件下给出了收敛率分析.

关键词: 变分不等式, 二次投影算法, 超平面, 伪单调, 收敛性

Abstract:

In this paper, a new double projection algorithm for solving variational inequalities is proposed. By constructing a new class of hyperplanes that strictly separate the current iteration and variational inequality solution sets and improving proof of existing results, We prove that the infinite sequence generated by the algorithm is globally convergent, and establish the convergence rate analysis under local error and Lipschitz conditions.

Key words: Variational inequalities, Double projection algorithm, Hyperplanes, Pseudomonotone, Convergence

中图分类号:

万升联. 解变分不等式的一种二次投影算法[J]. 数学物理学报, 2021, 41(1): 237-244.

Shenglian Wan. A Double Projection Algorithm for Solving Variational Inequalities[J]. Acta mathematica scientia,Series A, 2021, 41(1): 237-244.

图/表 2

参考文献 16

1	Karamardian S . Complementarity problems over cones with monotone and pseudomonotone maps. J Optim Theory Appl, 1976, 18 (4): 445- 454 doi: 10.1007/BF00932654
2	Dafermos S . Traffic equilibrium and variational inequalities. Transportation Science, 1980, 14 (1): 42- 54 doi: 10.1287/trsc.14.1.42
3	Harker P T , Pang J S . Finite-dimensional variational inequality and nonlinear complementarity problems:A survey of theory, algorithms and applications. Mathe Program, 1990, 48 (2): 161- 220
4	Popov L D . A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical Notes, 1980, 28 (5): 845- 848 doi: 10.1007/BF01141092
5	Malitsky Y V , Semenov V V . An extragradient algorithm for monotone variational inequalities. Cybernetics and Systems Analysis, 2014, 50 (2): 271- 277 doi: 10.1007/s10559-014-9614-8
6	He B S . A class of projection and contraction methods for monotone variational inequalities. Appl Math Optim, 1997, 35 (1): 69- 76 doi: 10.1007/s002459900037
7	Yan X H , Han D R , Sun W Y . A self-adaptive projection method with improved step-size for solving variational inequalities. Comput Math Appl, 2008, 55 (4): 819- 832 doi: 10.1016/j.camwa.2007.05.008
8	Bnouhachem A , Xu M H , Fu X L , et al. Modified extragradient methods for solving variational inequalities. Comput Math Appl, 2009, 57 (2): 230- 239 doi: 10.1016/j.camwa.2008.10.065
9	Xiu N H , Zhang J Z . Some recent advances in projection-type methods for variational inequalities. J Comput Appl Math, 2003, 152 (1/2): 559- 585
10	Korpelevich G M . An extragradient method for finding saddle points and for other problems. Matecon, 1976, 17: 747- 765
11	Solodov M V , Svaiter B F . A new projection method for variational inequality problems. SIAM J Control Optim, 1999, 37 (3): 765- 776 doi: 10.1137/S0363012997317475
12	He Y R . A new double projection algorithm for variational inequalities. J Comput Appl Math, 2006, 185 (1): 166- 173 doi: 10.1016/j.cam.2005.01.031
13	叶明露. 变分不等式的一类二次投影算法. 应用数学学报, 2012, 35 (3): 529- 535 doi: 10.3969/j.issn.0254-3079.2012.03.012
	Ye M L . The framework of a double projection algorithm for variational inequalities. Acta Math Appl Sinica, 2012, 35 (3): 529- 535 doi: 10.3969/j.issn.0254-3079.2012.03.012
14	Wang Y J , Xiu N H , Wang C Y . Unified framework of extragradient-type methods for pseudomonotone variational inequalities. J Optim Theory Appl, 2001, 111 (3): 641- 656 doi: 10.1023/A:1012606212823
15	Polyak B T. Introduction to Optimization. New York: Optimization Software Inc, 1987(Translated from Russian, with a foreword by Dimitri P. Bertsekas)
16	Sun D . A new step-size skill for solving a class of nonlinear projection equations. J Comput Math, 1995, (4): 357- 368

	算法3.1.1	算法3.1.2	算法2.2
n	iter(nf) time	iter(nf) time	iter(nf) time
n = 10	14(64) 0.561604	14(65) 0.546004	22(87) 0.748805
n = 50	17(79) 0.639604	17(83) 0.608404	20(85) 0.670804
n = 100	19(89) 1.48201	17(81) 1.37281	21(85) 1.62241
n = 200	18(86) 2.35562	18(85) 2.46482	22(89) 2.13721
n = 500	19(87) 9.21966	18(87) 9.15726	23(93) 8.04965

	算法3.1.1	算法3.1.2	算法2.2
n	iter(nf) time	iter(nf) time	iter(nf) time
n = 10	17(76) 0.421203	16(72) 0.499203	18(69) 0.499203
n = 50	19(90) 0.483603	19(95) 0.483603	20(78) 0.624004
n = 100	20(95) 1.201210	19(93) 1.232410	21(82) 1.23241
n = 200	20(96) 2.090410	20(98) 1.996810	21(89) 2.12161
n = 500	20(95) 9.762660	20(95) 10.43650	21(98) 6.70804

[1]	王娟,原子霞. 具有对数敏感度和混合边界的一维趋化模型解的整体存在性和收敛性[J]. 数学物理学报, 2020, 40(6): 1646-1669.
[2]	葛志昊,李瑞华. Bogoliubov-Tolmachev-Shirkov模型临界温度和能隙解的数值方法[J]. 数学物理学报, 2020, 40(6): 1699-1711.
[3]	李伟,黄鹏展. 流体相互作用模型的粘性分离有限元方法[J]. 数学物理学报, 2020, 40(5): 1362-1380.
[4]	杨柳,邓醉茶. 退化抛物型方程的一个初值反演问题[J]. 数学物理学报, 2020, 40(4): 891-903.
[5]	马国栋. 一般约束极大极小优化问题一个强收敛的广义梯度投影算法[J]. 数学物理学报, 2020, 40(3): 641-649.
[6]	蔡钢. Hilbert空间中关于变分不等式问题和不动点问题的粘性隐式中点算法[J]. 数学物理学报, 2020, 40(2): 395-407.
[7]	何泽荣,张智强,裘哲勇. 一类非线性年龄等级结构种群模型的数值解法[J]. 数学物理学报, 2020, 40(2): 515-526.
[8]	胡雨贤. 求解变分不等式的一种双投影算法[J]. 数学物理学报, 2019, 39(6): 1492-1498.
[9]	梁聪刚,杨晓侠,石东洋. 抛物积分微分方程的Wilson元收敛性分析[J]. 数学物理学报, 2019, 39(5): 1158-1169.
[10]	章茜,蔡光辉. WOD随机变量序列的完全收敛性和矩完全收敛性[J]. 数学物理学报, 2019, 39(5): 1183-1191.
[11]	丘小玲,贾文生. 有限理性下变分不等式的逼近定理[J]. 数学物理学报, 2019, 39(4): 730-737.
[12]	章志华,陈平炎. $φ$-混合序列加权和的完全收敛性[J]. 数学物理学报, 2018, 38(6): 1095-1102.
[13]	罗雪萍, 崔梦天. 自反巴拿赫空间中方向扰动的广义混合变分不等式的可解性[J]. 数学物理学报, 2018, 38(6): 1144-1152.
[14]	赵雅迪, 吴立飞, 杨晓忠, 孙淑珍. 时间分数阶慢扩散方程的一类有效差分方法[J]. 数学物理学报, 2018, 38(6): 1122-1134.
[15]	朱志锋,张绍义. 用概率距离研究非时齐马氏链的收敛性[J]. 数学物理学报, 2018, 38(5): 963-969.