|Table of Contents|

Convergence Rate Analysis of Prediction Correction Methods for a Class of Variational Inequalities with Linear Constraints(PDF)

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:
2024年03期
Page:
1-7
Research Field:
数学
Publishing date:

Info

Title:
Convergence Rate Analysis of Prediction Correction Methods for a Class of Variational Inequalities with Linear Constraints
Author(s):
Ge Zhili1; Tan Zhicong1; Xu Yingying2; Zhang Xin3
(1.School of Mathematics and Information Science,Nanjing Normal University of Special Education,Nanjing 210048,China)
(2.School of Information Science and Engineering,Southeast University,Nanjing 211189,China)
(3.School of Arts and Science,Suqian University,Suqian 223800,China)
Keywords:
linear constraints; variational inequalities; global linear convergence; prediction correction method
PACS:
O221.4
DOI:
10.3969/j.issn.1001-4616.2024.03.001
Abstract:
This paper considers a class of variational inequalities with linear constraints:finding x*∈Ω,such that F(x*)T(x-x*)≥0,x∈Ω,where Ω={x∈Rn|Ax≤b,x∈K},A∈Rm×n,b∈Rm,K is a simple nonempty closed convex subset of Rn,F is a continuous unknown mapping from Rn to Rn,and satisfies the strong monotonicity. We study a new prediction correction method for this class of problems. Based on the previous convergence results,we further analyze the linear convergence by using the error bound condition. Finally,two numerical results in traffic equilibrium problems with linear constraints demonstrate the effectiveness of the algorithm.

References:

[1]DAFERMOS S. Traffic equilibrium and variational inequalities[J]. Transportation science,1980,14(1):42-54.
[2]BERTSEKAS D P,GAFNI E M. Projection methods for variational inequalities with application to the traffic assignment problem[J]. Mathematical programming study,1982,17(16):139-159.
[3]NAGURNEY A. Network Economics:a variational inequality approach[M]. New York:Kluwer Academic Publishers,1993.
[4]FACCHINEI F,PANG J S. Finite-dimensional variational inequalities and complementarity problems[M]. Berlin:Springer Verlag,2003.
[5]HAN D R,SUN W Y. A new modified Goldstein-Levitin-Polyak projection method for variational inequality problems[J]. Computers and mathematics with applications,2004,47(12):1817-1825.
[6]HAN D R,HE B S. A new accuracy criterion for approximate proximal point algorithms[J]. Journal of mathematical analysis and applications,2001,263(2):343-354.
[7]HAN D R,XU W,YANG H. An operator splitting method for variational inequalities with partially unknown mappings[J]. Numerische mathematik,2008,111(2):207-237.
[8]WARDROP J G. Discussion:Some theoretical aspects of road traffic research[J]. Proceedings of the institution of civil engineers,part II,1952,1:325-378.
[9]YANG H,XU W,HE B S. Road pricing for congestion control with unknown demand and cost functions[J]. Transportation research part C:emerging technologies,2010,18(2):157-175.
[10]HAN D R,XU W,YANG H. Solving a class of variational inequalities with inexact oracle operators[J]. Mathematical methods of operations research,2010,71(3):427-452.
[11]GE Z L,HAN D R,NI Q,et al. An operator splitting method for monotone variational inequalities with a new perturbation strategy[J]. Optimization letters,2018,12(1):103-122.
[12]DONG X M,CAI X J,HAN D R,et al. Solving a class of variational inequality problems with a new inexact strategy[J]. Asia-pacific journal of operational research,2020,37(1):20.
[13]KOU X P,LI S J. On non-ergodic convergence rate of the operator splitting method for a class of variational inequalities[J]. Optimization letters,2017,11(1):71-80.
[14]葛志利,蔡邢菊,张欣. 算子分裂法求解一类变分不等式问题的收敛率分析[J]. 南京师大学报(自然科学版),2020,43(1):5-12.
[15]HE B S,YUAN X M. On the O(1/n)Convergence rate of the Douglas-Rachford alternating direction method[J]. SIAM journal on numerical analysis,2012,50(2):700-709.
[16]HE B S,YUAN X M. On the convergence rate of Douglas-Rachford operator splitting method[J]. Mathematical programming,2015,153(2):715-722.
[17]TSENG P. Error bounds and superlinear convergence analysis of some newton-type methods in optimization[M]. Boston,MA:Springer,2000.
[18]DENG W,YIN W T. On the global and linear convergence of the generalized alternating direction method of multipliers[J]. Journal of scientific computing,2016,66(3):889-916.
[19]PENG J W,ZHANG X Q. Linear convergence rate of the generalized alternating direction method of multipliers for a class of convex minimization problems[J]. Journal of nonlinear and convex analysis,2022,23(8):1559-1575.
[20]JIA Z H,GAO X,CAI X J,et al. Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems[J]. Journal of optimization theory and applications,2021,188(1):1-25.

Memo

Memo:
-
Last Update: 2024-09-15