D-gap functions and descent techniques for solving equilibrium problems
Giancarlo Bigi and Mauro Passacantando
Summary
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