Shrinking-cutting Projection Algorithms for Minty Quasiconvex Equilibrium Problems
摘要
We propose three algorithms for solving Minty (dual) quasiconvex equilibrium problems by using the fact that the solution-set of such a problem is just the intersection of the feasible domain and convex sets defined by the lower level sets of the bifunction involved. These algorithms overcome the difficulty arising from the fact that the sum of a quasiconvex function and a strongly convex function is, in general, neither strongly convex nor even quasiconvex. This prevents the application of the auxiliary problem principle, which is fruitfully used in solution methods for convex equilibrium and other related problems. The first algorithm is a shrinking procedure combined with a cutting hyperplane technique to reduce the search domain. A major drawback of this algorithm is that, at each iteration k, it requires computing the projection onto the intersection of the feasible domain and k-half-spaces, which increases the complexity of the algorithm significantly, especially when the number of iterations grows. The second and third algorithms are modified versions of the first one. Specifically, the second algorithm uses a suitable convex combination of projections onto the feasible domain and each half-space generated up to the current iteration. In contrast, the third algorithm projects onto the intersection of the feasible domain and only the half-space that has the maximum distance from the current iterate. Neither the monotonicity property nor a Lipschitz-type condition is required. The convergence of each algorithm is established under mild assumptions. Computational results on various randomly generated datasets demonstrate the behavior of each proposed algorithm.