Optimization tools for solving equilibrium problems with nonsmoth data
Giancarlo Bigi, Massimo Pappalardo and Mauro Passacantando
Summary
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