1 Introduction
The equilibrium problem has been considered as an important and general framework for describing various problems arising in different areas of mathematics, including optimization problems, mathematical economic problems and Nash equilibrium problems. As far as we know, this formulation has been followed for a long time by several studies on equilibrium problems considered under different headings such as quasi-equilibrium problem, mixed equilibrium problem, ordered equilibrium problem, vector equilibrium problem and so on [
1‐
4]. It should be noted that one of the interests of this common formulation is that many techniques developed for a particular case may be extended, with suitable adaptations, to the equilibrium problem, and then they can be applied to other particular cases [
5‐
16]. In this paper, we mainly deal with existence of solutions and approximate solutions of the quasi-equilibrium problem.
Let
\(X\subset\mathbb{R}^{n}\) be a nonempty closed convex set,
K be a point-to-set mapping from
X onto itself such that, for any
\(x\in X\),
\(K(x)\) is a nonempty closed convex set of
X, and let
\(f:X\times X \to R\) be a function such that, for any
\(x\in X\),
\(f(x,x)=0\) and
\(f(x,\cdot )\) is convex on
X. The quasi-equilibrium problem
\(\operatorname{QEP}(K,f)\) is to find a vector
\(x^{*}\in K(x^{*})\) such that
$$ f\bigl(x^{*},y\bigr)\ge0,\quad\forall y\in K\bigl(x^{*}\bigr). $$
(1.1)
Throughout this paper, we denote the solution set by
\(K^{*}\).
Certainly, when
\(f(x,y)=\langle F(x),y-x\rangle\) with
F being a vector-valued mapping from
X to
\(\mathbb{R}^{n}\), then the quasi-equilibrium problem reduces to the generalized variational inequality or quasi-variational inequality problem [
17‐
20] which is to find vector
\(x^{*}\in K(x^{*})\) such that
$$ \bigl\langle F\bigl(x^{*}\bigr),y-x^{*}\bigr\rangle \ge0, \quad \forall y \in K\bigl(x^{*}\bigr). $$
(1.2)
To move on, we recall the classical equilibrium problem, and classical Nash equilibrium problem (NEP) [
21]. Assume the function
\(f_{i}:\mathbb{R}^{n}\to R\) is continuous, and suppose
\(K_{i}\) is a nonempty closed set in
\(R^{n_{i}}\) for
\(i=1,2,\ldots, N\) with
\(n=\sum_{i=1}^{N}n_{i}\). Suppose that there are
N players such that each player controls the variables
\(x_{i}\in R^{n_{i}}\). Denote
\(x=(x_{1},\ldots, x_{N})\), and
\(x_{-i}=(x_{1},\ldots, x_{i-1}, x_{i+1},\ldots, x_{N})\). Player
i needs to take an
\(x_{i}\in K_{i}\subset R^{n_{i}}\) that solves the following optimization problem:
$$\min_{x_{i}\in K_{i}}f_{i}(x_{i}, x_{-i}) $$
based on the other players’ strategies
\(x_{-i}\). If these
N players do not cooperate, then each players’ strategy set may vary with other players’ strategies, that is, the
ith player’s strategy set varies with the other players’ strategies
\(x_{-i}\). In this case, we need to use
\(K_{i}(x_{-i})\) instead of
\(K_{i}\) to indicate the
ith player’s strategy set, and the
ith player needs to choose a strategy
\(x^{*}_{i} \in K_{i}(x_{-i})\) that solves the following optimization problem:
$$\min_{x_{i}\in K_{i}(x_{-i})} f_{i}(x_{i}, x_{-i}). $$
In [
22], the non-cooperative game model is called generalized Nash equilibrium problem (GNEP), which can be formulated as the quasi-equilibrium problem where the involved functions are nondifferentiable [
23].
For the problem GNEP, when the functions
\(f_{i}(\cdot, x_{-i})\) are convex and differentiable, then the problem can be equivalently formulated as the quasi-variational inequalities (
1.2) by setting
$$F(x)=\bigl(\nabla_{x_{i}}f_{i}(x)\bigr)_{i=1}^{N} $$
and
\(K(x)=\prod_{i=1}^{N}K_{i}(x_{-i})\). When the function
\(f_{i}(\cdot, x_{-i})\) is convex and nondifferentiable, then the GNEP reduces to the quasi-equilibrium problem (
1.1) [
24] via the Nikaido Isoda funtion
$$f(x,y)=\sum_{i=1}^{N}\bigl[f_{i}(y_{i},x_{-i})-f_{i}(x_{i},x_{-i}) \bigr]. $$
On the other hand, the quasi-equilibrium problem (QEP) has received much attention of researchers in mathematics, economics, engineering, operations research, etc. [
17,
22]; for more information see [
19,
25,
26]. There are many solution methods for solving QEP. Recently, [
27] considered an optimization reformulation approach with the regularized gap function. Different from the variational inequalities problem, the regularized gap function is in general not differentiable, but only directional differentiable. Furthermore, supplementary conditions must be imposed to guarantee that any stationary point of these functions is a global minimum, since the gap functions is nonconvex [
28]. It should be noted that such conditions are known for variational inequality problem but not for QEP. So, [
23] proposed several projection and extragradient methods rather than methods based on gap functions, which generalized the double-projection methods for variational inequality problem to equilibrium problems with a moving constraint set
\(K(x)\).
It is well known that the extragradient projection method is an efficient solution method for variational inequalities due to its low memory and low cost of computing [
29,
30]. Based on those advantages, it was extended to solve QEP recently [
20,
23,
31] and this opened a new approach for solving the problem. An important feature of this method is that it has the contraction property in the sense that the generated sequence has contraction property with respect to the solution set of the problem [
29],
i.e.
$$\bigl\Vert x^{k+1}-x^{*} \bigr\Vert \leq \bigl\Vert x^{k}-x^{*} \bigr\Vert ,\quad\forall k\geq0, x^{*}\in K^{*}. $$
The numerical experiments given in [
20,
23,
31] show that the extragradient projection method is a practical solution method for the QEP.
It should be noted that not all the extragradient projection methods have the contraction property [
32]. In that case, it may not slow down the convergence rate significantly. Although the extragradient projection method has no contraction property, it still has a good numerical performance [
32]. Now, a question can be posed naturally, can this method be applied to solve the QEP? And if so, how about its performance? This constitutes the main motivation of this paper.
Inspired by the work [
23,
32], we propose a new type of extragradient projection method for the QEP in this paper. Different from the extragradient projection method proposed in [
23], the generated sequence by the newly designed method possesses an expansion property with respect to the initial point,
i.e.,
$$\bigl\Vert x^{k+1}-x^{k} \bigr\Vert ^{2}+ \bigl\Vert x^{k}-x^{0} \bigr\Vert ^{2}\leq \bigl\Vert x^{k+1}-x^{0} \bigr\Vert ^{2}. $$
The existence results for (
1.1) are established under pseudomonotonicity condition of the equilibrium function and the continuity of the underlying multi-valued mapping. Furthermore, we show that the generated sequence converges to the nearest point in the solution set to the initial point. Numerical experiments show the efficiency of the method.
The remainder of this paper is organized as follows. In Section
2, we recall some concepts and related conclusions to be used in the sequel. The newly designed method and its global convergence are developed in Section
3. Some preliminary computational results and experiments are presented in Section
4.
3 Algorithm and convergence
In this section, we mainly develop a new type of extragradient projection method for solving QEP. The basic idea of the algorithm is as follows. At each step of the algorithm, we obtain a solution \(y^{k}\) by solving a convex subproblem. If \(x^{k}=y^{k}\), then stop with \(x^{k}\) being a solution of the QEP; otherwise, find a trial point \(z^{k}\) by a back-tracking search at \(x^{k}\) along the direction \(x^{k}-y^{k}\), and the new iterate is obtained by projecting \(x^{0}\) onto the intersection of \(K(x^{k})\) of two halfspaces which are, respectively, associated with \(z^{k}\) and \(x^{k}\). Repeat the process until \(x^{k}=y^{k}\). The detailed description of our designed algorithm is as follows.
Indeed, for every \(x^{k}\in K(x^{k})\), since \(y^{k}\in K(x^{k})\), \(z^{k}\in K(x^{k})\), so we have \(K(x^{k})\cap H_{k}^{1}\neq\emptyset\) and \(K(x^{k})\cap H_{k}^{2}\neq\emptyset\). To establish the convergence of the algorithm, we first discuss the relationship of the halfspace \(H_{k}^{1}\) with \(x^{k}\) and the solution set \(K^{*}\).
The justification of the termination criterion can be seen from Proposition 2 in [
23], and the feasibility of the stepsize rule (
3.1),
i.e., the existence of point
\(m_{k}\) can be guaranteed from Proposition 7 in [
23].
Next, to show that the algorithm is well defined, we will show that the nonempty set \(K^{*}\) is always contained in \(H_{k}^{1}\cap H_{k}^{2} \cap X\) for the projection step.
In the following, we show the expansion property of the algorithm with respect to the initial point.
To prove the boundedness of the generated sequence \(\{x^{k}\}\), we assume that the algorithm generates an infinite sequence for simple.
Since
\(\{x^{k}\}\) is bounded, it has an accumulation point. Without loss of generality, assume that the subsequence
\(\{x^{k_{j}}\}\) converges to
x̄. Then the sequences
\(\{y^{k_{j}}\}\),
\(\{z^{k_{j}}\}\) and
\(\{g^{k_{j}}\}\) are bounded from the Proposition 10 in [
23], where
\(g^{k_{j}} \in\partial f(z^{k_{j}},x^{k_{j}})\).
Before given the next result, the following lemma is needed (for details see [
23]).
Based on the analysis above, we can establish the main results of this section that the generated sequence
\(\{x^{k}\}\) globally converge to a solution of the problem (
1.1).
4 Numerical experiment
In this section, we will make some numerical experiments and give a numerical comparison with the method proposed in [
23] to test the efficiency of the proposed method. The MATLAB codes are run on a PIV 2.0 GHz personal computer under MATLAB version 7.0.1.24704(R14). In the following, ‘Iter.’ denotes the number of iteration, and ‘CPU’ denotes the running time in seconds. The tolerance
ε means the iterative procedure terminates when
\(\Vert x^{k}-y^{k} \Vert\leq\varepsilon\).
This problem was tested in [
36] with initial point
\(x^{0}=(1, 3, 1, 1, 2)^{T}\). They obtained the appropriate solution after 21 iterates with the tolerance
\(\varepsilon=10^{-3}\).
By the algorithm proposed in this paper, the numerical results obtained for this example are listed in Table
1 with
\(c=\gamma=0.5\),
\(\varepsilon=10^{-3}\) and
\(X=K(x)\), and with different initial points.
Table 1
Numerical results for Example
4.1
Iter. | 5 | 13 | 9 | 7 | 8 |
CPU | 0.2060 | 0.5340 | 0.3590 | 0.2190 | 0.3430 |
Now, we consider a quasi-variational inequality problems and we solve it by using Algorithm
3.1 with the equilibrium function
\(f(x, y)= \langle F(x), y-x\rangle\).
This problem was tested in [
23]. The numerical results of Algorithm
3.1, abbreviated as Alg. 31, for this example are shown in Table
2 with different initial points.
Table 2
Numerical results for Example
4.2
Iter. | 53 | 2 | 2 | 8 | 51 | 48 |
CPU(s) | 0.7030 | 0.0160 | 0.0310 | 0.2030 | 0.8440 | 0.7810 |
For this example, we choose
\(X=K(x)\) and take
\(c=\gamma=0.5\). During the experiments, we set the stopping criterion
\(\varepsilon =10^{-6}\). The numerical comparison of our proposed method with the algorithms,
i.e., Alg.1, Alg.1a, Alg.1b, proposed in [
23] are given in Tables
3 and
4.
Table 3
Iterations from Alg.31, Alg.1, Alg.1a and Alg.1b respectively
(10,0) | 2 | 3 | 2 | 2 |
(10,10) | 53 | 255 | 120 | 120 |
Table 4
The CPU time from Alg.31, Alg.1, Alg.1a and Alg.1b respectively
(10,0) | 0.02 | 0.26 | 0.20 | 0.15 |
(10,10) | 0.70 | 8.43 | 3.70 | 2.57 |
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.