Research On Projection Algorithms For Variational Inequalities

Variational inequality is an important part of nonlinear analysis and optimization theory.It is a subject widely emerged in different fields such as economics,physics,optimization control,operations research and transportation.Since there is no analytic solution to variational inequality,an important problem is how to construct an effective iterative algorithm to compute variational inequality.Several variational inequality algorithms have been proposed in recent decades.As the projection algorithms do not need the derivability of the mapping,the algorithms become one of the most important methods to study variational inequality in recent years.It is known that the classical projection algorithms of variational inequalities need to know the Lipschitz constant of the mapping or at least to know some estimation of it.Generally,it is difficult to estimate the Lipschitz constant of the mapping.Even if the Lipschitz constant can be estimated,the value of the step size of the projection algorithms are small,leading to slow convergence.The usual way is to use an Armijo-like adaptive method to get the step size,but Armijo search requires multiple calculations of the value of projection and mapping at different points,so the efficiency of the algorithms are low.In this paper,based on the existing theories and algorithms of variational inequalities,some new adaptive methods of variational inequalities are proposed.The main contributions are listed as follows:1.The gradient methods for variational inequalities are modified.(1)Using contraction mapping and viscosity method,Tseng's gradient method is modified with a simple step size.The modified algorithm has a simple form and the algorithm does not need to know the Lipschitz constant of the mapping.A strong convergence theorem for the algorithm is proved without any requirement of additional projections.The numerical results show that the proposed algorithm is effective.(2)Inspired by Malitsky's algorithm,a new projection gradient algorithm is also proposed.Our method requires only one projection onto the feasible set and one value of the mapping per iteration.Under monotonicity assumption of the mapping,it is proved that the algorithm is convergent weakly to a solution of variational inequality.Under strong monotonicity assumption of the mapping,the proposed algorithm has R-linear convergence rate.Numerical results show that the proposed algorithm is very effective.2.We modify the subgradient extragradient methods with new step sizes.(1)The classical subgradient extragradient method is modified with a new step size.It is proved that the modified algorithm is convergent weakly to the solution of variational inequality.Using the Halpern method,strong convergence of the subgradient extragradient algorithm is given.It is shown that the step sizes is better than Armijo-like step sizes.(2)A new step size of Popov's subgradient extragradient method is constructed and we answer the open problems raised by Malitsky when he proposed this method.It is proved that the proposed algorithm is convergent weakly to the solution set of variational inequalities.We also prove the proposed algorithm has R-linear convergence rate under strong monotonicity assumption of the mapping.The proposed algorithm is extended to Bregman projection.(3)The subgradient extragradient method is extended to solve the pseudo-monotone equilibrium problem and fixed problem.The step size is given directly according to the given information.Combined with Halpern method,it is proved that the proposed method converges strongly to the equilibrium problem and fixed problem.The effectiveness of the proposed algorithm is illustrated by an example of Nash-Cournot equilibrium problem.3.The projection algorithms of pseudo-monotone variational inequality are modified by inertial method,the projection gradient algorithms for quasimonotone and non-monotone variational inequalities are also considersied.(1)For Tseng's gradient projection algorithm,using the inertial method and the new step sizes,two inertial projection algorithms are proposed.The two inertial projection algorithms converge weakly and strongly to the solution set of pseudo-monotone variational inequalities,respectively.(2)We modify the golden gradient algorithm proposed by Malitsky and present simple algorithms for variational inequalities and equilibrium problem.Under pseudomonotone assumption of the mapping and bifunction,weak convergence theorems are established.Numerical experiments show the effectiveness of the algorithms.(3)The projection gradient algorithms for quasimonotone and non-monotone variational inequalities are presented.Under appropriate conditions,the weak convergence of the proposed algorithms are proved.Numerical experiments show the effectiveness of the algorithms.The algorithms are further modified by projection technique,and the strong convergence of the algorithms are proved.