D-gap functions and descent techniques for solving equilibrium problems

Giancarlo Bigi and Mauro Passacantando


The equilibrium problem (EP) is a convenient mathematical format which provides a rather general setting including several mathematical models such as optimization, multiobjective optimization, variational inequalities, fixed point and complementarity problems, Nash equilibria in noncooperative games and inverse optimization. Many methods for computing equilibria have been developed, which can be divided into several classes: fixed point and extragradient methods, descent methods, proximal point and Tikhonov-Browder regularization methods.
In this paper we focus on the approach based on descent procedures. In general, descent methods rely on the reformulation of the equilibrium problem as an optimization problem through suitable merit functions. The so-called gap functions yield reformulations as constrained optimization problems, while the difference of two appropriate gap functions (D-gap function) leads to reformulations as unconstrained optimization problems.
In the framework of the equilibrium problem(EP) solution methods relying on D-gap functions have been developed in a few papers. These methods need strong assumptions, in fact their convergence requires the strict or uniform strong monotonicity of gradient mappings of the equilibrium bifunction: this assumption implies that all the stationary points of a D-gap function coincide with its global minima and hence with the solutions of (EP). Furthermore, the parameters of some algorithms have to be set according to thresholds which depend on the constants of strong monotonicity and Lipschitz continuity of the above gradient mappings. As these values have to be known in advance, it is hard to implement these methods in a general framework.
To overcome these drawbacks, we develop a new solution method for (EP) exploiting a whole family of D-gap functions in order to preserve a sufficient decrease condition at each iteration of the algorithm: this allows to deal with stationarity issues. In fact, the convergence of the method requires just the monotonicity of the gradient mappings: as a consequence, there may be stationary points of any given D-gap function which are not global minima and therefore do not solve (EP). Furthermore, the method does not require Lipschitz continuity assumptions and hence no a priori knowledge of constants/thresholds is needed. Thus, the paper aims at providing a method which can be both easily implemented and applied to a wider class of equilibrium problems.
The paper is organized as follows. Section 2 provides basic results which play a key role in devising the method. In particular, bounds on the values of the D-gap functions are proved. Section 3 describes the solution method, addressing also possible improvements in the choice of the parameters. Since the convergence result requires the boundedness of the feasible region, conditions which allow to drop it are also addressed. Finally, Section 4 provides preliminary numerical tests to analyse the sensitivity of the algorithm with respect to its parameters and some numerical comparisons with other similar algorithms.

The original paper is available at http://dx.doi.org/10.1007/s10898-014-0223-x.

A Technical Report version is available here (meaningful differences hold with the final paper).

My Home Page