A new solution method for equilibrium problems

Giancarlo Bigi, Marco Castellani and Massimo Pappalardo


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