Researches On Extragradient-Type Algorithms For Solving Non-Monotone And Non-Lipschitzian Equilibrium Problems

Social activities in areas such as economic planning,traffic control,and engineering design can all be described as equilibrium problems.Equilibrium problem is of great generality.It includes the optimization problem,the variational inequality problem,the Nash equilibrium problem in non-cooperative game theory,the fixed point problem,the saddle point problem,the complementarity problem,and the minimax problem.When solving equilibrium problems,one needs to consider the convexity and monotonicity of the involved equilibrium bifunction and the property and structure of the feasible set.In addition,the convergence and effectiveness of the algorithms should also be taken into consideration.At present,the majority of existing algorithms for solving equilibrium problems require Lipschitz-type continuity and some kind of monotonicity of the involved equilibrium bifunction,such as strong monotonicity,monotonicity,strong pseudomonotonicity,and pseudomonotonicity.However,these algorithms are no longer effective when the equilibrium bifunction is non-monotone.In this case,the point is how to design algorithms and ensure their effectiveness and convergence for solving the non-monotone equilibrium problem.In light of this,we study the extragradient-type algorithms for solving non-monotone and nonLipschitzian equilibrium problems,aiming to obtain a better numerical behavior than existing ones.At first,we present two projection extragradient algorithms for solving nonmonotone and non-Lipschitzian equilibrium problems.More precisely,we combine cutting hyperplane technique with the technique of constructing shrinking convex sets,employ Armijo-linesearch and the projection with embedded subgradient,and prove that the sequences generated by them converge weakly and strongly to a solution of the equilibrium problem,respectively.When proving the convergence,we do not require any monotonicity and Lipschitz-type property of the involved equilibrium bifunction but the assumption that the solution set of the Minty equilibrium problem associated with the equilibrium problem is nonempty.Compared with the projection without subgradient,the aforementioned projection with embedded subgradient achieves a better distance decrease between the current point and the solution set of the equilibrium problem than existing algorithms for solving non-monotone equilibrium problems.This is illustrated by its advantages in the number of iterations and the running time.Secondly,considering non-monotone and non-Lipschitzian equilibrium problems over the fixed point sets,we employ Armijo-linesearch,combine cutting hyperplane technique with the technique of constructing shrinking convex sets for solving non-monotone equilibrium problems,and propose one extragradient-type algorithm for solving these problems.Under the assumption that the equilibrium bifunction is non-monotone and non-Lipschitzian,we prove that the sequence generated by the proposed extragradient-type algorithm weakly converges to a solution of the equilibrium problem.Different from the no-nmonotone equilibrium problem,the convergence of this extragradient-type algorithm is guaranteed by the condition that a subset of the solution set of the Minty equilibrium problem over the fixed point set is not empty.Numerical results show the effectiveness of this extragradient-type algorithm.Furthermore,in view of the great significance of the inertial effect for the speed of convergence in the iterative algorithms,this paper develops the aforementioned projection extragradient algorithms and obtains four inertial extragradient algorithms.Among them,the first two inertial extragradient algorithms project the combination of the current point and the inertial effect onto the feasible set,while the latter two algorithms avoid this projection.The numerical results show that the developed weak convergence algorithms are superior to the algorithm without the inertial effect,and they have advantages in the number of iterations and running time,respectively.Finally,a linesearch projection extragradient-type algorithm is presented for solving non-monotone and non-Lipschitzian equilibrium problems.Different from the above mentioned three kinds of algorithms,we prove the boundedness of the generated sequence by embedding the initial point into the projection plane,instead of relying on Fejer monotonicity.Compared with other algorithms,this presented algorithm shows its own advantages in numerical behavior.