A new solution method for equilibrium problems
Giancarlo Bigi, Marco Castellani and Massimo Pappalardo
Summary
Concepts of equilibrium appear frequently in many practical
problems arising, for instance, in physics, engineering, game theory
and economics. The so-called equilibrium problem (shortly EP) is a model
whose formulation includes optimization, variational inequalities,
Nash equilibria and complementarity problems as particular cases.
A common approach to solve (EP) is based on its
reformulation as an optimization problem through appropriate "gap"
functions. This approach has been originally conceived for
variational inequalities and extended to
the framework of more general equilibrium problems afterwards.
Reformulations based on both constrained and
unconstrained optimization can be developed according to the kind of
gap function that is considered. In any case, solution methods for
optimization problems generally converge to a stationary point,
which is not necessarily a global optimum unless strong assumptions
are made. Therefore the assumptions, which guarantee that all the
stationary points of the gap function are actually solutions of (EP),
are a key point of the reformulations which have been considered up to now.
In order to devise a solution method which does not
require the above "stationarity property", we rely on a parametric
family of auxiliary equilibrium problems; these problems are built
exploiting a well-known regularization technique which allows to
have differentiable gap functions whose gradients are also easily
computable. Auxiliary problems have been largely used for variational
inequalities and recently applied to equilibrium.
While a unique auxiliary problem has been generally used, therefore
fixing the parameter α the approach we consider relies on the
possibility to modify it: whenever the search of a descent direction
for the gap function of the α-auxiliary equilibrium problem is
unsuccessful, the parameter is decreased and a new search performed.
This procedure allows to overcome the need of the stationarity property
through an additional assumption on the equilibrium bifunction, which
guarantees to achieve a descent direction when decreasing the parameter
(see Theorem 3.3). In the case of variational inequalities this assumption
reduces to the monotonicity of the operator and the algorithm reduces
to the one introduced by Zhu and Marcotte (JOTA 80 (1994)).
The original paper is available at http://dx.doi.org/10.1080/10556780902855620.
My Home Page