Twelve monotonicity conditions arising from algorithms for equilibrium problems
Giancarlo Bigi and Mauro Passacantando
Summary
Many mathematical models (including optimization, multiobjective optimization, variational inequalities, fixed point and complementarity problems, Nash equilibria in noncooperative games and inverse optimization) can be formulated in the same format, namely the (abstract) equilibrium problem (shortly EP). This general format clearly stems from variational inequalities, and solution methods for (EP) generally extend those originally designed for optimization or variational inequalities exploiting the underlying common structure.
Algorithms for (EP) can be roughly divided into a few classes: fixed point, extragradient, convex feasibility and descent methods, which generally require the solution of a sequence of (convex) optimization problems, and proximal pointand Tikhonov-Browder regularization methods, which generally require the solution of a sequence of equilibrium problems with better properties than the given one. Almost all these methods share a common feature: convergence is guaranteed under suitable monotonicity assumptions on the equilibrium bifunction. This is not really surprising as the monotonicity of the operator is a crucial assumption in the algorithms for variational inequalities. Indeed, in equilibrium problems monotonicity plays a role which is similar to convexity in optimization. For instance, stationarity points of gap and D-gap functions for (EP) are actually global minima if appropriate monotonicity conditions
hold.
Several definitions of monotonicity for bifunctions have been introduced. Anyway, to the best of our knowledge, a thorough study of their relations has never been carried out. Therefore, the paper aims at analysing all the relationships between those monotonicity conditions which are relevant in the algorithms for (EP). Twelve different conditions have been identified and they are briefly recalled in Section 2, while Section 3 provides a full picture of the relationships between them. Finally, the analysis is further detailed in Section 4 for two particular cases: variational inequalities and the so-called linear equilibrium problems, which include also Nash equilibrium problems with quadratic payoffs.
The original paper is available at http://dx.doi.org/10.1080/10556788.2014.900552.
A Technical Report version is available
here.
My Home Page