Gap functions and penalization for solving equilibrium problems with nonlinear constraints

Giancarlo Bigi and Mauro Passacantando

Summary

Several methods to solve equilibrium problems have been proposed, often extending those originally conceived for optimization problems or variational inequalities to the framework of more general equilibrium problems. Well-known solution methods are the so-called descent methods, which are based on the reformulation of the equilibrium problem as a global optimization problem through appropriate gap functions. Most approaches need to minimize a convex function over the feasible region in order to evaluate the gap function, and the evaluation could be computationally expensive when the feasible region is described by nonlinear convex inequalities. Therefore, we introduce a family of gap functions which rely on a polyhedral approximation of the feasbile region rather than on the feasible region itself, and we evelop a method based on the minimization of convex functions over polyhedra. In Section 2 these gap functions are introduced, considering the equilibrium bifunction along with an additional regularizing bifunction, and some properties about their continuity and generalized directional differentiability are given. Moreover, we prove that monotonicity type assumptions on the equilibrium guarantee that each stationary point of a gap function is actually a solution of the equilibrium problem. This result extends to equilibrium problems a similar one developed for variational inequalities. Section 3 provides a solution method which does not require the above 'stationarity property', relying on a concavity type assumption on the equilibrium bifunction. Moreover, unlike most of the available algorithm, we consider a search direction which could be unfeasible, so that the introduction of an exact penalty function is required. The direction is indeed a descent one if either the regularization or the penalization parameter is small enough. Therefore, the algorithm exploits fixed values for the two parameters as long as they provide a descent direction and it decreases both of them otherwise. Section 4 provides the results of some numerical tests, which have been performed applying the algorithm to a problem of production competition over a network under the Nash-Cournot equilibrium framework.

The original paper is available at http://dx.doi.org/10.1007/s10589-012-9481-z. A Technical Report version is available here.

My Home Page