Three Projection Gradient Algorithms For Variational Inequalities

The theory of variational inequalities,proposed by Stampachia in the early 1960 s,witnessed the explosive growth of theoretical progress,algorithm development and applications in all disciplines of pure science and applied science.Due to the interaction between different branches of mathematics and engineering sciences,variational inequalities,as an important part of optimization theory and algorithms,provide a unified framework for many linear and nonlinear problems,and are widely used in economics,physics,optimization control,operations research,transportation and other aspects.Since there is no analytic solution to variational inequality,an important problem is how to construct an effective iterative algorithm to give approximate solution to the variational inequality and analyze the convergence of the given algorithm.Projection gradient algorithm has become one of the most important method in the study of variational inequality algorithm in recent years,because it does not require the derivability of function and is simple to calculate.The main idea of this method is to establish the equivalence between variational inequality and some fixed point problems by using the concept of projection.This alternative formulation has played an essential role in developing various projection-type methods for solving variational inequality.Recently,some scholars proposed to directly give the stepsize of these algorithms without using search in the projection.This innovation is widely used as a new efficient algorithm.Because the step-length of each iteration does not depend on the Lipschitz constant,the efficiency of the algorithm is improved.In this paper,based on the existing theories and algorithms,three new projection gradient algorithms are proposed for variational inequality problems,combined with the non-monotonic stepsize strategy.Our results can be seen as an improvement on the previously known results,and the specific work is as follows:Firstly,the projection gradient method for monotone variational inequality are improved and extended.According to the modified projection gradient algorithm proposed by Yang and Liu,each iteration step only needs to calculate one projection onto the feasible set and one value of the mapping.On this basis,the non-monotonic stepsize based on the local information of the operator and independent of Lipschitz constant is constructed,and the structure of the modified algorithm is extremely simple.It is proved that the sequence generated by the algorithm converges weakly to the solution of variational inequality when the mapping is monotone,and the R-linear convergence rate of the algorithm is established under the condition of the strong monotonicity or error bound.It is extended to solve genelized variational inequality problems.Under appropriate assumptions,the weak convergence and R-linear convergence rate of the raised algorithm are still valid,and the complexity of the method is almost equivalent to the classical gradient method.Through a large number of numerical experiments,it can be seen that the introduced method is quite effective compared with the iteration times and calculation time of the two recently proposed projection gradient methods.Secondly,the subgradient extragradient method for monotone variational inequality is improved.Using the characteristics of the modified subgradient extragradient algorithm proposed by Yang and Liu,that is,each iteration needs to calculate a projection to the feasible set and the values of two operators,and the remaining projection is in the half space,which has inherent explicit.In this paper,the method is modified and combined with the improved non-monotone stepsize strategy to solve the pseudomonotone variational inequality problem.The new algorithm converges weakly to the solution set of variational inequalities,and it is proved that the introduced algorithm has R-linear convergence rate when the mapping is strongly pseudomonotone.Numerical results show that,this method is better than the subgradient extragradient method proposed by Yang and Liu.