Optimization tools for solving equilibrium problems with nonsmoth data

Giancarlo Bigi, Massimo Pappalardo and Mauro Passacantando


In this paper, we consider the so-called equilibrium problem with nonsmooth data in a finite-dimensional setting, following its mathematical format by Muu-Oettli (Nonlinear Analysis, 1992) and Blum-Oettli (The Mathematics Student, 1994). This format was shaped on the well-known Ky Fanť˘˛¨s minimax inequality and has attracted increasing attention ever since its introduction. Indeed, it provides a rather general model that includes scalar and vector optimization, inverse optimization, variational inequalities, fixed point, complementarity, saddle points and noncooperative games as particular cases.
Many classes of methods for solving the equilibrium problem have been developed: fixed point and extragradient methods, descent methods, proximal point and Tikhonovť˘˛ˇBrowder regularization methods. In this paper, we focus on algorithms that are based on descent procedures.
Descent techniques exploit the reformulation of the equilibrium problem as an optimization problem through suitable merit functions, which are generally referred to as gap functions. Many descent-type algorithms have been developed exploiting both gap functions and D-gap functions under the assumption that the equilibrium bifunction is continuously differentiable. This assumption guarantees the differentiability of the gap function; moreover, convergence results require some kind of monotonicity assumption on the gradients of the equilibrium bifunction. Entering nonsmoothness brings in some difficulties: The differentiability of the gap function is generally lost, and monotonicity conditions have to be addressed through generalized derivatives.
When the nonsmooth equilibrium problem takes the shape of a variational inequality, i.e., the equilibrium bifunction is affine in the second argument, with a Lipschitz operator, the analysis of nonsmooth gap functions leads to error bounds and to devise solution methods under the strong monotonicity of the operator. The algorithms require the explicit knowledge of the modulus of strong monotonicity or the Lipschitz constant.
In the general case, some algorithms have been developed just for those particular problems in which the nonsmooth terms of the bifunction are additively separable. Anyhow, the connections between directional derivatives, monotonicity and descent properties given in Castellani-Pappalardo (Taiwainese J Mathematics, 2009) pave the way to a general framework for descenttype methods. In this paper, we deepen their analysis of using the generalized directional derivatives of the equilibrium bifunction, and we exploit them to devise descent algorithms for the general case.
The paper is structured in the following way. Section 2 recalls the gap function approach, analyzes how the local Lipschitz continuity of the equilibrium bifunction is inherited by the gap function and provides an upper estimate of its generalized directional derivative. Section 3 introduces monotonicity conditions on f through generalized directional derivatives and explores their connections with stationarity and descent properties of the gap function. Section 4 exploits the results of the previous sections to devise two different solution methods and to prove their convergence. Finally, Sect. 5 reports the results of some preliminary numerical tests.

The original paper is available at http://dx.doi.org/10.1007/10.1007/s10957-016-0974-2.

A Technical Report version is available here (meaningful differences hold with the final paper).

My Home Page