Gap functions for quasi-equilibrium problems
Giancarlo Bigi and Mauro Passacantando
Summary
In this paper we focus on the so-called abstract quasi-equilibrium problem (shortly QEP). QEPs are modelled upon quasi-variational inequalities (shortly QVIs). Also generalized Nash equilibrium problems (shortly GNEPs) can be reformulated through (QEP) with the Nikaido-Isoda aggregate bifunction. It is also worth noting that (QEP) is a natural generalization of the abstract equilibrium problem (shortly EP), i.e., the case in which the set-valued map C defining the feasible region is constant. As EP subsumes optimization, multiobjective optimization, variational inequalities, fixed point and complementarity problems, Nash equilibria in noncooperative games and inverse optimization in a unique mathematical model, further “quasi” type models could be analysed through the QEP format beyond QVIs and GNEPs.
Unlikely QVI and GNEP, the QEP format did not receive much attention. The goal of the paper is to reformulate (QEP) as an optimization problem through a suitable gap function and develop an ad-hoc descent algorithm, supposing that the set-valued map C can be described by constraining bifunctions.
Gap functions have been originally conceived for variational inequalities and later extended to EPs, QVIs, jointly convex GNEPs via the Nikaido-Isoda binfunction and generic GNEPs via QVI reformulations Though descent type methods based on gap functions have been extensively developed for EPs, the analysis of gap functions for QVIs is focused on smoothness properties and error bounds while no algorithm is developed. A descent method has been developed for jointly convex GNEPs: anyway, restricting to the computation of normalized equilibria makes the problem actually fall within the EP (and not the QEP) framework.
Indeed, the reformulation of (QEP) as an optimization problem brings some difficult issues in devising descent methods which are not met in the EP case: the gap function is not necessarily differentiable even though the equilibrium and the constraining bifunctions are differentiable; the feasible region is given by the fixed points of the set-valued constraining map C and is therefore more difficult to handle; the so-called stationarity property, which guarantees all the stationary points of the gap function to be actually global minimizers and therefore solutions of (QEP), requires monotonicity assumptions both on the equilibrium and constraining bifunctions. These issues are dealt with in the talk. After the gap function has been introduced and the reformulation of (QEP) as an optimization problem shown, the smoothness properties of the gap function are analysed; in particular, an upper estimate of its Clarke directional derivative is given, which provides a key tool in devising the descent method. Furthermore, classes of constraints which allow guaranteing the stationarity property are identified. The convergence of the descent method is proved under standard assumptions, and finally error bounds are given, which guarantee that the sequence generated by the algorithm is bounded.
The original paper is available at http://dx.doi.org/10.1007/s10898-016-0458-9.
A Technical Report version is available
here.
My Home Page