A Double Projection Algorithm for Solving Non-Monotone Variational Inequalities
-
摘要:
投影算法是求解变分不等式问题的主要方法之一。目前，有关投影算法的研究通常需要假设映射是单调且Lipschitz连续的，然而在实际问题中，往往不满足这些假设条件。该文利用线搜索方法，提出了一种新的求解非单调变分不等式问题的二次投影算法。在一致连续假设下，证明了算法产生的迭代序列强收敛到变分不等式问题的解。数值实验结果表明了该文所提算法的有效性和优越性。
Abstract:The projection algorithm is one of the main methods to solve variational inequality problems. At present, the research on projection algorithms usually requires the assumptions that the mapping is monotone and Lipschitz continuous, but in practical problems, these assumptions are often unsatisfied. A new double projection algorithm for solving non-monotone variational inequality problems was proposed with the line search method. Under the assumption that the mapping is uniformly continuous, the sequence generated by the algorithm was proved to strongly converge to the solution of the variational inequality. The numerical experiments illustrate the effectiveness and superiority of the proposed algorithm.
-
表 1
$ \varepsilon _{\rm{err}} = 10^{-4}$ 时不同算法关于维数的比较Table 1. For
$ \varepsilon _{\rm{err}} = 10^{-4},$ comparison of different algorithms about dimensions
下载: 导出CSV
表 2
$\varepsilon_ {\rm{err}} = 10^{-4}$ 时不同算法关于初始点的比较Table 2. For
$ \varepsilon_{\rm{err}} = 10^{-4},$ comparison of different algorithms about the initial point$ m = 100$ $ x_{1} = {\rm{rand}}(100,1)$ $x_{1} = 2\times{\rm{rand} }(100,1)$ $x_{1} = 5\times{\rm{rand} }(100,1)$ iter Ni CPU time t/s iter Ni CPU time t/s iter Ni CPU time t/s alg. 1 93 0.6047 119 0.7330 195 1.0379 alg. 3.3 in ref. [14] $ 10^{5}$ 758.4269 $ 10^{5}$ 757.2559 $ 10^{5}$ 748.3109 alg. 4 in ref. [15] 489 5.4683 699 7.6306 924 9.3821
下载: 导出CSV
表 3
$ m = 100$ 时不同算法关于允许误差的比较Table 3. For
$ m = 100,$ comparison of different algorithms about allowable errors$ x_{1} = (1,1,\cdots ,1)$ $\varepsilon_{ {\rm{err} } }=10^{-3}$ $ \varepsilon_{ {\rm{err} } }=10^{-5}$ $ \varepsilon_{ {\rm{err} } }=10^{-8}$ iter Ni CPU time t/s iter Ni CPU time t/s iter Ni CPU time t/s alg. 1 59 0.0142 145 0.0215 166 1.1689 alg. 3.3 in ref. [14] 54460 407.0808 $ 10^{5}$ 764.3791 $ 10^{5}$ 751.3783 alg. 4 in ref. [15] 622 7.1918 1133 13.1318 1418 16.5836
下载: 导出CSV
-
[1] KINDERLEHRER D, STAMPACCHIA G. An Introduction to Variational Inequalities and Their Applications[M]. New York: Academic Press, 1980. [2] FACHINEL F, PANG J S. Finite-Dimensional Variational Inequalities and Complementarity Problems[M]. New York: Springer, 2003. [3] HE Y R. 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 [4] XU H K. Iterative algorithms for nonlinear operators[J]. Journal of the London Mathematical Society, 2002, 66(1): 240-256. doi: 10.1112/S0024610702003332 [5] HE X, HUANG N J, LI X S. Modified projection methods for solving multi-valued variational inequality without monotonicity[J]. Networks and Spatial Economics, 2022, 22: 361-377. doi: 10.1007/s11067-019-09485-2 [6] 贺月红, 龙宪军. 求解伪单调变分不等式问题的惯性收缩投影算法[J]. 数学物理学报, 2021, 41A(6): 1897-1911 doi: 10.3969/j.issn.1003-3998.2021.06.026HE Yuehong, LONG Xianjun. A inertial contraction and projection algorithm for pseudomonotone variational inequalities problems[J]. Acta Mathematica Scientia, 2021, 41A(6): 1897-1911.(in Chinese) doi: 10.3969/j.issn.1003-3998.2021.06.026 [7] 万升联. 解变分不等式的一种二次投影算法[J]. 数学物理学报, 2021, 41A(1): 237-244 doi: 10.3969/j.issn.1003-3998.2021.01.019WAN Shenglian. A double projection algorithm for solving variational inequalities[J]. Acta Mathematica Scientia, 2021, 41A(1): 237-244.(in Chinese) doi: 10.3969/j.issn.1003-3998.2021.01.019 [8] 杨军. 非单调变分不等式黄金分割算法研究[J]. 应用数学和力学, 2021, 42(7): 764-770YANG Jun. A golden ratio algorithm for solving nonmonotone variational inequalities[J]. Applied Mathematics and Mechanics, 2021, 42(7): 764-770.(in Chinese) [9] YE M L, HE Y R. 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 [10] HE B S. A class of projection and contraction methods for monotone variational inequalities[J]. Applied Mathematics and Optimization, 1997, 35: 69-76. doi: 10.1007/s002459900037 [11] GOLDSTEIN A. Convex programming in Hilbert space[J]. Bulltin of the American Mathematical Society, 1964, 70(5): 709-710. doi: 10.1090/S0002-9904-1964-11178-2 [12] KORPELEVICH G M. The extragradient method for finding saddle points and other problems[J]. Ekonomika I Matematicheskie Metody, 1976, 12: 747-756. [13] 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 [14] VUONG P T, SHEHU Y. Convergence of an extragradient-type method for variational inequality with applications to optimal control problems[J]. Numerical Algorithms, 2019, 81(1): 269-291. doi: 10.1007/s11075-018-0547-6 [15] REICH S, THONG D V, DONG Q L, et al. New algorithms and convergence theorems for solving variational inequalities with non-Lipschitz mappings[J]. Numerical Algorithms, 2021, 87(2): 527-549. doi: 10.1007/s11075-020-00977-8 [16] HE Y R. 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 -
渝公网安备50010802005915号