New kinds of self-adaptive subgradient extragradient projection methods for solving pseudomonotone variational inequalities

Abstract

Gibali [J. Nonlinear Anal. Optim., 2015, 6(1): 41‒51] presented a self-adaptive subgradient extragradient projection method for solving variational inequalities without Lipschitz continuity, where its next iterative point was obtained by projecting a vector onto a specific half-space. In this paper, we present new kinds of self-adaptive subgradient extragradient projection methods by using a new descent direction. With the help of the techniques in the method of He and Liao [J. Optim. Theory Appl, 2002, 112(1): 111‒128], we get a longer step-size for these kinds of algorithms, which proves the global convergence of the generated sequence. Numerical results show that these kinds of extragradient subgradient projection methods are less dependent on the choice of the initial point, the dimension of the variational inequalities, and the tolerance of accuracy than the known methods. Moreover, the new methods proposed in this paper outperform (with respect to the number of iterations and cpu-time) the method presented by Gibali.

Keywords

Variational inequalities / subgradient extragradient projection method / half-space / pseudomonotone / non-Lipschitz continuous

1 Introduction

In this paper, the variational inequality model \mathrm{V}\mathrm{I}(F,C) considered in this paper refers to: find a point x^{\ast }\in C such that

(1.1)⟨F\left(x^{\ast }\right),x-x^{\ast }⟩\ge 0,\mathrm{\forall }x\in C,

where C\subset {\mathbb{R}}^n is a non-empty closed convex set, F:{\mathbb{R}}^n\to {\mathbb{R}}^n is a continuous map, ⟨\cdot ,\cdot ⟩ and \parallel \cdot \parallel are the inner product and the norm in the corresponding space respectively. Denote S as the solution set of the variational inequality \mathrm{V}\mathrm{I}(F,C), d(x,C) the distance from the point x to the set C, and P_C\left(x\right) the projection of the point x onto C. Since C is a closed convex set, P_C\left(x\right) exists uniquely and there is \parallel x-P_C\left(x\right)\parallel =d\left(x,C\right).

The variational inequality model has been applied in the research of economics, financial management, network planning, transportation, and game theory. See [1, 3, 16-17]. The projection algorithm is an easy-to-implement algorithm for solving variational inequality problems. Regarding the projection algorithm, readers can refer to articles [6, 12, 14-15, 19-20, 22], review literature [18, 23-24], monograph [4], and relevant references.

Censor et al. [2] proposed a projection algorithm for solving the case where F was Lipschitz continuous. When calculating the new iterative point, this algorithm replaces the projection calculation onto the non-empty closed convex set C with the projection onto a specific half-space. Since this half-space is constructed by using the characteristics of the sub-differential, this algorithm is called the subgradient extragradient algorithm. Meanwhile, as the projection onto the half-space can be directly calculated, this algorithm eliminates one projection calculation compared with the extragradient projection algorithm [12].

However, considering that it may be not easy to calculate the Lipschitz coefficient of the map F, and to weaken the Lipschitz continuity of the map F, Iusem and Svaiter [11] introduced an algorithm for solving pseudomonotone variational inequalities using line search. This line search does not require the calculation of projections, and the algorithm only needs to project twice in one iteration process. However, the step-size of this line search may tend to zero. Wang et al. [22] propose a better step-size rule for this line search. Similar line-search methods can also be found in [10] and [20].

To solve this kind of variational inequality problem, Han and Lo [6] adopt a different line search method (this line search process requires calculating the projection onto the feasible set C, and the number of projections is uncertain). The advantage of this line search is that, under the assumption that F is Lipschitz continuous, it can be proved that the lower bound of the step-size is strictly greater than 0 (see [6, Lemma 3.1]). [6] utilizes this characteristic to construct a self-adaptive projection algorithm. The next iterative point of this algorithm is obtained by projecting onto the closed convex set C. Similar self-adaptive algorithms can also be found in [3], etc. In addition, He and Liao [9] introduce a method to optimize the step-size of this type of algorithm.

Gibali [5] proposes a self-adaptive subgradient extragradient projection algorithm for solving pseudomonotone non-Lipschitz continuous variational inequalities. The algorithm is as follows:

\{\begin{array}{l}(\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{h})\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}{y}^k=P_C\left(x^k-{\beta }_{k}F\left(x^k\right)\right),\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}{\beta }_k={\beta }_{k-1}{\beta }^{m_k},\\ m_k\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{n}\mathrm{o}\mathrm{n}-\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{r}\mathrm{m},\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\\ {\beta }_k\left(x^k-y^k,F\left(x^k\right)-F\left(y^k\right)\right)\le \left(1-\epsilon \right)\parallel x^k-y^k{\parallel }^2\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{s};\\ T_k:=\left\{w\in {\mathbb{R}}^n|⟨x^k-{\beta }_{k}F\left(x^k\right)-y^k,w-y^k⟩\le 0\right\};\\ x^{k+1}=P_{T_k}\left(x^k-{\beta }_k{d}_2\left(x^k,{\beta }_k\right)\right).\end{array}

The descent direction of this algorithm is d_2\left(x^k,{\beta }_k\right)=F\left(y^k\right), and under the assumptions that

(A) The solution set S is non-empty;

(B) F is pseudomonotone on the non-empty closed convex set C;

(C) F is Lipschitz continuous on {\mathbb{R}}^n.

The global convergence of this algorithm is proved. [13] constructs a subgradient extragradient projection algorithm for solving pseudomonotone variational inequalities by using this descent direction.

In this paper, with the help of the line search method in [6], a class of self-adaptive subgradient extragradient projection algorithms for solving non-Lipschitz continuous variational inequalities is proposed. The main differences between this algorithm and the existing algorithms are as follows:

1) The descent directions of the algorithms in [5] and [13] are both d_2\left(x^k,{\beta }_k\right)=F\left(y^k\right). This paper considers not only Algorithm 2.1 with the descent direction of d_1(x^k,{\beta }_k)=x^k-y^k-{\beta }_k\left(F\right(x^k)-F(y^k\left)\right), but also a class of Algorithm 3.1 using the non-negative combination of d_1\left(x^k,{\beta }_k\right) and d_2\left(x^k,{\beta }_k\right) as the descent direction. See Note 3.1(b) and Note 4.1(b).

2) For these types of algorithms, the step-size is optimized by using the techniques in [9].

3) Under certain conditions, Algorithm 3.1 can degenerate into the algorithm in [13], thus generalizing the existing algorithms. Additionally, under the same assumptions as in [5], it is proven that the infinite sequence of points generated by these types of algorithms can converge to the solution of the variational inequality. Numerical experiments show that these types of algorithms are less affected by the dimension of the variational inequality problem, the precision, and the selection of the initial point. Moreover, in terms of the number of iterations, the number of projections, and the time spent on operations, the new algorithm outperforms the algorithm in Gibali [5]. See Note 4.1.

2 Preliminaries

First, we introduce the definition, some of its properties, and some basic conclusions of the projection operator. For any non-empty closed set \mathrm{\Omega }\subset {\mathbb{R}}^n, denote P_{\mathrm{\Omega }}\left(x\right):=\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{m}\mathrm{i}\mathrm{n}}_{y\in \Omega }\{\parallel x-y\parallel \} as the projection of the point x onto Ω, where \parallel \cdot \parallel is {\ell }_2 norm in {\mathbb{R}}^n.

Lemma 2.1 [4, 24]　 Let \Omega \subset {\mathbb{R}}^n be a non-empty closed convex set, then the following conclusions hold:

(i) ⟨P_{\mathrm{\Omega }}\left(x\right)-x,y-P_{\mathrm{\Omega }}\left(x\right)⟩\ge 0,\mathrm{\forall }x\in {\mathbb{R}}^n,\mathrm{\forall }y\in \mathrm{\Omega };

(ii) \parallel P_{\mathrm{\Omega }}\left(x\right)-P_{\mathrm{\Omega }}\left(y\right)\parallel \le \parallel x-y\parallel ,\mathrm{\forall }x,y\in {\mathbb{R}}^n;

(iii) \parallel P_{\mathrm{\Omega }}\left(x\right)-x{\parallel }^2\le \parallel x-y{\parallel }^2-\parallel P_{\mathrm{\Omega }}\left(x\right)-y{\parallel }^2,\mathrm{\forall }x\in {\mathbb{R}}^n,\mathrm{\forall }y\in \mathrm{\Omega }.

To give the necessary and sufficient condition for the solution of the variational inequality \mathrm{V}\mathrm{I}(F,C), denote the natural residual mapping as

(2.1)e\left(x,\lambda \right)=x-P_C\left(x-\lambda F\left(x\right)\right),\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\lambda >0.

Lemma 2.2 [4]　 Let λ > 0, then x^{\ast }\in S if and only if \parallel e\left(x^{\ast },\lambda \right)\parallel =0.

Lemma 2.3 [4]　 Let \mathrm{\forall }x\in {\mathbb{R}}^n, then for any 0 < λ₁ < λ₂, there is

(2.2)\parallel e\left(x,{\lambda }_1\right)\parallel \le \parallel e\left(x,{\lambda }_2\right)\parallel ,\frac{\parallel e\left(x,{\lambda }_1\right)\parallel }{{\lambda }_1}\ge \frac{\parallel e\left(x,{\lambda }_2\right)\parallel }{{\lambda }_2}.

Lemma 2.4 [4]　 If x\notin S, then for a fixed ν > 0, there exists \tilde{\beta }>0, such that for any \beta \in \left(0,\tilde{\beta }\right), the following equation holds:

\beta \parallel F\left(x\right)-F\left(x-e\left(x,\beta \right)\right)\parallel \le \nu \parallel e\left(x,\beta \right)\parallel .

It is noted that P_H\left(z\right)=\mathrm{a}\mathrm{r}\mathrm{g}{\mathrm{m}\mathrm{i}\mathrm{n}}_{y\in H}\frac{1}{2}\parallel z-y{\parallel }^2, and by applying the KKT condition to this constrained optimization problem the following lemma can be obtained.

Lemma 2.5　 Let H:=\{x\in {\mathbb{R}}^n\mid h\left(x\right)\le 0\} be a half-space, where u\in {\mathbb{R}}^n, b\in \mathbb{R} and h\left(x\right):=⟨u,x⟩-b. If z\notin H and u\ne 0, then P_H\left(z\right)=z-\frac{⟨u,z⟩-b}{\parallel u{\parallel }^2}u.

Definition 2.1　A mapping F:{\mathbb{R}}^n\to {\mathbb{R}}^n is said to be pseudomonotone on C. If \mathrm{\forall }x,y\in C, there is

⟨F\left(x\right),y-x⟩\ge 0\Rightarrow ⟨F\left(y\right),y-x⟩\ge 0.

The following shows the assumptions proposed in this paper.

Assumption H (A) S is non-empty;

(B) F is continuous on {\mathbb{R}}^n;

(C) F is pseudomonotone on C.

From assumptions (A) and (C), there is

(2.3)⟨F\left(y\right),y-x^{\ast }⟩\ge 0,\mathrm{\forall }y\in C,\mathrm{\forall }{x}^{\ast }\in S.

Let y=P_C\left(x-\lambda F\left(x\right)\right). It is noted that S\subset C, then according to Lemma 2.1(i), there is

(2.4)⟨x-\lambda F\left(x\right)-y,y-x^{\ast }⟩\ge 0,\mathrm{\forall }{x}^{\ast }\in S,\mathrm{\forall }x\in {\mathbb{R}}^n,\mathrm{\forall }\lambda \in \mathbb{R}.

Moreover, based on (2.3) and (2.4), there is

(2.5)⟨x-y-\lambda \left(F\right(x)-F(y\left)\right),y-x^{\ast }⟩\ge 0,\mathrm{\forall }{x}^{\ast }\in S,\mathrm{\forall }x\in {\mathbb{R}}^n,\mathrm{\forall }\lambda >0.

3 Self-adaptative subgradient extragradient algorithm

The following first shows the algorithm proposed in this paper.

Algorithm 3.1　Select an initial point x^0\in {\mathbb{R}}^n and parameters \nu ,l\in \left(0,1\right), \gamma \in \left(0,2\right), r = 1. Take k := 0.

Step 1: Compute y^k:=P_C(x^k-{\beta }_{k}F(x^k\left)\right), {\beta }_k:=r{l}^{m_k}, where m_k is the smallest non-negative integer m for which the following equation holds:

(3.1){\beta }_k\parallel F\left(x^k\right)-F(x^k-e(x^k,{\beta }_k\left)\right)\parallel \le \nu \parallel e(x^k,{\beta }_k)\parallel .

Step 2: Compute e(x^k,{\beta }_k)=x^k-y^k. If e\left(x^k,{\beta }_k\right)=0, stop; otherwise, go to the next step.

Step 3: Compute

x^{k+1}=P_{T_k}(x^k-{\alpha }_k{d}_1(x^k,{\beta }_k\left)\right),

where T_k is a half-space:

T_k:=\{w\in {\mathbb{R}}^n:⟨x^k-{\beta }_{k}F\left(x^k\right)-y^k,w-y^k⟩\le 0\},

{\alpha }_k=\gamma \frac{⟨e(x^k,{\beta }_k),d_1(x^k,{\beta }_k)⟩}{\parallel d_1(x^k,{\beta }_k){\parallel }^2},d_1(x^k,{\beta }_k)=x^k-y^k-{\beta }_k\left(F\right(x^k)-F(y^k\left)\right).

Step 4: If

{\beta }_k\parallel F\left(x^k\right)-F(x^k-{\beta }_{k}F(x^k\left)\right)\parallel \le 0.4\parallel e(x^k,{\beta }_k)\parallel ,

r=\frac{{\beta }_k}{0.7}; or, r = β_k. Let k:=k+1, go back to Step 1.

The following notes are used to illustrate the main differences between this algorithm and existing algorithms, as well as the specific calculation methods of the new iterative points.

Note 3.1　(a) The next iterative point of the algorithm is obtained by projecting onto the half-space T_k. Since the projection onto a half-space can be calculated directly (for the specific calculation, see Note 3.2), this algorithm requires one less projection calculation in each iteration compared to Algorithm 3.1 in [6]. This can reduce the computing time of the computer when the projection onto the feasible set C is difficult to calculate.

(b) This algorithm adopts a new descent direction d_1\left(x^k,{\beta }_k\right)=x^k-y^k-{\beta }_k\left(F\left(x^k\right)-F\left(y^k\right)\right), which is different from the descent direction d_2\left(x^k,{\beta }_k\right)=F\left(y^k\right) in [5] and [13].

(c) This algorithm optimizes the step-size by using the method in [9], thus obtaining a relatively longer step-size.

Note 3.2　Assume z^k=x^k-{\alpha }_k{d}_1(x^k,{\beta }_k), u^k=x^k-{\beta }_{k}F\left(x^k\right)-y^k. Then x^{k+1} is calculated as follows:

(a) If ⟨x^k-{\beta }_{\mathrm{k}}F\left(x^{\mathrm{k}}\right)-y^{\mathrm{k}},z^{\mathrm{k}}-y^{\mathrm{k}}⟩\le 0, then z^{\mathrm{k}}\in T_{\mathrm{k}}, and there is

x^{k+1}=z^k,

(b) or ⟨x^k-{\beta }_{k}F\left(x^k\right)-y^k,z^k-y^k⟩>0 and \parallel u^k\parallel \ne 0. At this point, it can be assumed that u=u^k, b=⟨u^k,y^k⟩, and according to Lemma 2.5, there is

x^{k+1}=z^k-\frac{⟨z^k-y^k,u^k⟩}{\parallel u^k{\parallel }^2}{u}^k.

The following lemmas are used to illustrate that Algorithm 3.1 is feasible.

Lemma 3.1　 If condition (B) in assumption H holds, then for any fixed positive numbers r > 0 and x_k\in {\mathbb{R}}^n, there exists a smallest non-negative integer m such that the following equation holds:

(3.2)r{l}^m\parallel F\left(x^k\right)-F(x^k-e(x^k,r{l}^m\left)\right)\parallel \le \nu \parallel e(x^k,r{l}^m)\parallel .

Proof　Assume that Eq. (3.2) cannot be achieved within a finite number of steps. Then, for any positive integer m, there is

(3.3)\parallel F\left(x^k\right)-F(x^k-e(x^k,r{l}^m\left)\right)\parallel >\nu \frac{\parallel e(x^k,r{l}^m)\parallel }{r{l}^m}.

If \parallel e\left(x^k,1\right)\parallel =0, then x^k\in S. Consequently, \parallel e\left(x^k,{\beta }_k\right)\parallel =0, and in this case, (3.2) is naturally true. Therefore, it can be assumed that\parallel e\left(x^k,1\right)\parallel >0. Note l\in \left(0,1\right), and there are the following discussions:

(i) If x_k\in C makes m\to \mathrm{\infty }, there is r{l}^m\to 0. From the continuity of P_C(\cdot ) and the assumption that F is a continuous mapping, it is obtained that e(x^k,r{l}^m)\to 0(m\to \mathrm{\infty }). Furthermore, there is

\parallel F\left(x^k\right)-F(x^k-e(x^k,r{l}^m\left)\right)\parallel \to 0.

On the other hand, for a sufficiently large m, there is r{l}^m\le 1, and according to (2.2), there is

\nu \frac{\parallel e\left(x^k,r{l}^m\right)\parallel }{r{l}^m}\ge \nu \frac{\parallel e\left(x^k,1\right)\parallel }{1}>0.

This contradicts (2.3).

(ii) If x_k\notin C, at this time e(x^k,r{l}^m)\to x^k-P_C\left(x^k\right)\ne 0(m\to \mathrm{\infty }). Here, according to (3.3), there is r{l}^m\parallel F\left(x^k\right)-F\left(x^k-e\left(x^k,r{l}^m\right)\right)\parallel >\nu \parallel e\left(x^k,r{l}^m\right)\parallel. According to the continuity of F, it is known that the left-hand side of this inequality r{l}^m\parallel F\left(x^k\right)-F(x^k-e(x^k,r{l}^m\left)\right)\parallel \to 0(m\to \mathrm{\infty }). But the right-hand side of this inequality is \nu \parallel e(x^k,r{l}^m)\parallel \to \nu \parallel x^k-P_C\left(x^k\right)\parallel >0(m\to \mathrm{\infty }). Thus, a contradiction is obtained.

First, in Algorithm 3.1, for any z\in C, according to the definition y^k=P_C\left(x^k-{\beta }_{k}F\left(x^k\right)\right) and Lemma 2.1(i), there is ⟨x^k-{\beta }_{k}F\left(x^k\right)-y^k,z-y^k⟩\le 0, so C\subset T_k.

Second, as known from Lemma 2.2, if \parallel e\left(x^k,{\beta }_k\right)\parallel =0, then x^k is a solution of \mathrm{V}\mathrm{I}(F,C), and the algorithm stops at this time. Therefore, if \left\{x^k\right\} is an infinite sequence generated in Algorithm 3.1, it can assumed that \parallel e\left(x^k,{\beta }_k\right)\parallel >0.

Lemma 3.2 [9]　 The infinite sequence \left\{x^k\right\} generated by Algorithm 3.1 satisfies the following inequalities:

(i) ⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩>\frac{1}{2}\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2;

(ii) ⟨e(x^k,{\beta }_k),d_1(x^k,{\beta }_k)⟩\ge (1-\nu )\parallel e(x^k,{\beta }_k){\parallel }^2.

Proof　Based on the definition of d_1\left(x^k,{\beta }_k\right), \nu \in \left(0,1\right), and together with (3.1), there is

\begin{array}{rl}& ⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩\\ & =\parallel e\left(x^k,{\beta }_k\right){\parallel }^2-{\beta }_k⟨e\left(x^k,{\beta }_k\right),F\left(x^k\right)-F\left(x^k-e\left(x^k,{\beta }_k\right)\right)⟩\\ & >\frac{1}{2}\parallel e\left(x^k,{\beta }_k\right){\parallel }^2-{\beta }_k⟨e\left(x^k,{\beta }_k\right),F\left(x^k\right)-F\left(x^k-e\left(x^k,{\beta }_k\right)\right)⟩\\ & +\frac{1}{2}{\nu }^2\parallel e\left(x^k,{\beta }_k\right){\parallel }^2\\ & >\frac{1}{2}\parallel e\left(x^k,{\beta }_k\right){\parallel }^2-{\beta }_k⟨e\left(x^k,{\beta }_k\right),F\left(x^k\right)-F\left(x^k-e\left(x^k,{\beta }_k\right)\right)⟩\\ & +\frac{1}{2}{{\beta }_k}^2\parallel F\left(x^k\right)-F\left(x^k-e\left(x^k,{\beta }_k\right)\right){\parallel }^2\\ & =\frac{1}{2}\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2.\end{array}

Q.E.D. for (i).

By the Cauchy-Schwarz inequality and (3.1), there is

\begin{array}{rl}& ⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩\\ & =\parallel e\left(x^k,{\beta }_k\right){\parallel }^2-{\beta }_k⟨e\left(x^k,{\beta }_k\right),F\left(x^k\right)-F\left(x^k-e\left(x^k,{\beta }_k\right)\right)⟩\\ & \ge \parallel e\left(x^k,{\beta }_k\right){\parallel }^2-{\beta }_k\parallel F\left(x^k\right)-F\left(x^k-e\left(x^k,{\beta }_k\right)\right)\parallel \parallel e\left(x^k,{\beta }_k\right)\parallel \\ & \ge \parallel e\left(x^k,{\beta }_k\right){\parallel }^2-\nu \parallel e\left(x^k,{\beta }_k\right){\parallel }^2\\ & =\left(1-\nu \right)\parallel e\left(x^k,{\beta }_k\right){\parallel }^2.\end{array}

Q.E.D. for (ii). □

In addition, it can also be found from Lemma 2.2(ii) that \parallel d_1\left(x^{\mathrm{k}},{\beta }_{\mathrm{k}}\right)\parallel >0.

4 Convergence of algorithms

Lemma 4.1　 If Assumption H holds and \left\{x^k\right\} is an infinite sequence generated by Algorithm 3.1, then for any fixed x^{\ast }\in S,

(4.1)\parallel x^{k+1}-x^{\ast }{\parallel }^2\le \parallel x^k-x^{\ast }{\parallel }^2-\frac{1}{2}\gamma \left(2-\gamma \right)\left(1-\nu \right)\parallel e\left(x^k,{\beta }_k\right){\parallel }^2.

Proof　By Lemma 2.1(iii), combined with S\subset C\subset T_k, and for any fixed x^{\ast }\in S, there is

\begin{array}{rl}\parallel x^{k+1}-x^{\ast }{\parallel }^2& \le \parallel x^k-{\alpha }_k{d}_1\left(x^k,{\beta }_k\right)-x^{\ast }{\parallel }^2-\parallel x^k-{\alpha }_k{d}_1\left(x^k,{\beta }_k\right)-x^{k+1}{\parallel }^2\\ & =\parallel x^k-x^{\ast }{\parallel }^2-2{\alpha }_k⟨x^k-x^{\ast },d_1\left(x^k,{\beta }_k\right)⟩+{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2\\ & -\left(\parallel x^k-x^{k+1}{\parallel }^2-2{\alpha }_k⟨x^k-x^{k+1},d_1\left(x^k,{\beta }_k\right)⟩+{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2\right)\\ & =\parallel x^k-x^{\ast }{\parallel }^2-2{\alpha }_k⟨x^{k+1}-x^{\ast },d_1\left(x^k,{\beta }_k\right)⟩-\parallel x^k-x^{k+1}{\parallel }^2.\end{array}

Let \vartheta \left(x_k\right)=\parallel x^k-x^{\ast }{\parallel }^2-\parallel x^{k+1}-x^{\ast }{\parallel }^2. There is

(4.2)\begin{array}{rl}\vartheta \left(x_k\right)& \ge \parallel x^k-x^{k+1}{\parallel }^2+2{\alpha }_k⟨x^{k+1}-x^{\ast },d_1\left(x^k,{\beta }_k\right)⟩\\ & =\parallel x^k-x^{k+1}{\parallel }^2+2{\alpha }_k⟨x^{k+1}-y^k+y^k-x^{\ast },d_1\left(x^k,{\beta }_k\right)⟩\\ & =\parallel x^k-x^{k+1}{\parallel }^2+2{\alpha }_k⟨x^{k+1}-y^k,d_1\left(x^k,{\beta }_k\right)⟩+2{\alpha }_k⟨y^k-x^{\ast },d_1\left(x^k,{\beta }_k\right)⟩\\ & \ge \parallel x^k-x^{k+1}{\parallel }^2+2{\alpha }_k⟨x^{k+1}-y^k,d_1\left(x^k,{\beta }_k\right)⟩.\end{array}

The second inequality can be obtained from Eq. (2.5) and {\alpha }_k\ge 0 (in fact, it is known from the selection of α_k that {\alpha }_k>\frac{1}{2}\gamma).

It is noted that

(4.3)2{\alpha }_k⟨x^{k+1}-y^k,d_1\left(x^k,{\beta }_k\right)⟩=2{\alpha }_k⟨x^{k+1}-x^k,d_1\left(x^k,{\beta }_k\right)⟩+2{\alpha }_k⟨x^k-y^k,d_1\left(x^k,{\beta }_k\right)⟩

and

(4.4)\begin{array}{rl}\parallel x^k-x^{k+1}{\parallel }^2& =\parallel x^k-x^{k+1}-{\alpha }_k{d}_1\left(x^k,{\beta }_k\right)+{\alpha }_k{d}_1\left(x^k,{\beta }_k\right){\parallel }^2\\ & \ge 2⟨x^k-x^{k+1}-{\alpha }_k{d}_1\left(x^k,{\beta }_k\right),{\alpha }_k{d}_1\left(x^k,{\beta }_k\right)⟩+{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2\\ & =-{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2+2{\alpha }_k⟨x^k-x^{k+1},d_1\left(x^k,{\beta }_k\right)⟩.\end{array}

According to (4.2)‒(4.4), there is

(4.5)\begin{array}{rl}\vartheta \left(x_k\right)& \ge -{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2+2{\alpha }_k⟨x^k-x^{k+1},d_1\left(x^k,{\beta }_k\right)⟩\\ & +2{\alpha }_k⟨x^{k+1}-x^k,d_1\left(x^k,{\beta }_k\right)⟩+2{\alpha }_k⟨x^k-y^k,d_1\left(x^k,{\beta }_k\right)⟩\\ & =-{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2+2{\alpha }_k⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩.\end{array}

To obtain a relatively long step-size, it is noted that the right-hand side of inequality (4.5) is a quadratic function of α_k, which reaches its maximum value at {\alpha }_k^{\ast }=\frac{⟨e(x^k,{\beta }_k),d_1(x^k,{\beta }_k)⟩}{\parallel d_1(x^k,{\beta }_k){\parallel }^2}. Similar to the method in [9], a relaxation factor γ is introduced in this paper, where \gamma \in \left(0,2\right). Let {\alpha }_k=\gamma {\alpha }_k^{\ast } in (4.5), and combined with Lemma 3.2(i) and 3.2(ii). We can obtain

\vartheta \left(x_k\right)\ge \frac{1}{2}\gamma \left(2-\gamma \right)\left(1-\nu \right)\parallel e\left(x^k,{\beta }_k\right){\parallel }^2.

Hence,

\parallel x^{k+1}-x^{\ast }{\parallel }^2\le \parallel x^k-x^{\ast }{\parallel }^2-\frac{1}{2}\gamma \left(2-\gamma \right)\left(1-\nu \right)\parallel e\left(x^k,{\beta }_k\right){\parallel }^2.

Based on the above, Q.E.D. □

Theorem 4.1　 Assume that Assumption H holds and \left\{x^k\right\} is an infinite sequence generated by Algorithm 3.1, then the sequence \left\{x^k\right\} converges to the solution of the variational inequality (1.1).

Proof　Arbitrarily take a fixed x^{\ast }\in S. According to (3.1) and the values of the parameters in the algorithm \gamma \in \left(0,2\right) and \nu \in \left(0,1\right), it is known that \left\{\Vert x^k-x^{\ast }\Vert \right\} is a strictly monotonically decreasing sequence with a lower bound, so it converges. Thus, the sequence \left\{x^k\right\} is bounded and

0\le \frac{1}{2}\gamma \left(2-\gamma \right)\left(1-\nu \right)\parallel e\left(x^k,{\beta }_k\right){\parallel }^2\le \parallel x^k-x^{\ast }{\parallel }^2-\parallel x^{k+1}-x^{\ast }{\parallel }^2\to 0,k\to \mathrm{\infty }.

Based on the definition of y^k in Step 1 of Algorithm 3.1, there is

(4.6)\underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\parallel e\left(x^k,{\beta }_k\right)\parallel =\underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\parallel x^k-y^k\parallel =0.

Let \overline{x} be any cluster point of the sequence \left\{x^k\right\}. Then there exists an index set I\subset \{1,2,\dots \} such that x^i\to \overline{x}(i\in I,i\to \mathrm{\infty }). First, it requires to prove that there exists an index set J\subset I such that the following equation holds:

(4.7)\underset{j\in J,j\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\parallel e\left(x^j,1\right)\parallel =0.

To this end, the following cases are discussed:

(a) If {\beta }_0:=\mathrm{i}\mathrm{n}\mathrm{f}\{{\beta }_i\mid i\in I\}>0, then for any i\in I, there is {\beta }_0\le {\beta }_i. Further, for any i\in I, there is

0\le \parallel e\left(x^i,1\right)\parallel \le \frac{\parallel e\left(x^i,{\beta }_i\right)\parallel }{\mathrm{m}\mathrm{i}\mathrm{n}\{{\beta }_i,1\}}\le \frac{\parallel e\left(x^i,{\beta }_i\right)\parallel }{\mathrm{m}\mathrm{i}\mathrm{n}\{{\beta }_0,1\}}\to 0, i\to \mathrm{\infty },

where the second inequality can be deduced from Lemma 2.3 (\parallel e(x^i,1)\parallel =\frac{\parallel e(x^i,1)\parallel }{1}\le \frac{\parallel e(x^i,min\{{\beta }_i,1\left\}\right)\parallel }{min\{{\beta }_i,1\}}\le \frac{\parallel e(x^i,{\beta }_i)\parallel }{min\{{\beta }_i,1\}}), and from (4.6), it is known that the limit is zero. If I=J, (4.7) holds.

(b) If {\beta }_0:=\mathrm{i}\mathrm{n}\mathrm{f}\{{\beta }_i\mid i\in I\}=0, then there exists J\subset I such that {\beta }_j\to 0(j\to \mathrm{\infty }). Noting the definition of β_k in (4.1), for large enough j\in J (such that ), there is

(4.8)\begin{array}{rl}\parallel F\left(x^j\right)-F\left(x^j-e\left(x^j,l^{-1}{\beta }_j\right)\right)\parallel & >\nu \frac{\parallel e\left(x^j,l^{-1}{\beta }_j\right)\parallel }{l^{-1}{\beta }_j}\ge \nu \frac{\parallel e\left(x^j,1\right)\parallel }{1}\\ & =\nu \parallel e\left(x^j,1\right)\parallel ,\end{array}

where the second inequality is derived from (2.2) and . In addition, based on the definition of the residual function in (2.1), the definition y^j=P_C(x^j-{\beta }_{j}F(x^j\left)\right) in Step 1, and the non-expansiveness of the projection operator, there is

\begin{array}{rl}\parallel x^j-(x^j-e(x^j,l^{-1}{\beta }_j\left)\right)\parallel & =\parallel x^j-P_C(x^j-l^{-1}{\beta }_{j}F(x^j\left)\right)\parallel \\ & \le \parallel x^j-y^j\parallel +\parallel y^j-P_C(x^j-l^{-1}{\beta }_{j}F(x^j\left)\right)\parallel \\ & \le \parallel x^j-y^j\parallel +\parallel x^j-{\beta }_{j}F\left(x^j\right)-(x^j-l^{-1}{\beta }_{j}F(x^j\left)\right)\parallel \\ & =\parallel x^j-y^j\parallel +{\beta }_j|1-l^{-1}|\parallel F\left(x^j\right)\parallel \to 0,j\in J,j\to \mathrm{\infty },\end{array}

and it is known that the limit is zero from (4.6). Assume {\beta }_j\to 0\left(j\to \mathrm{\infty }\right), and there is the boundedness of the sequence \left\{x^k\right\} and the continuity of F on {\mathbb{R}}^n (so the sequence \{\parallel F\left(x^j\right)\parallel \} is bounded). From this, combined with (4.8) and the continuity of F on {\mathbb{R}}^n, it is shown that (4.7) holds.

Based on the above, (4.7) holds. □

Next, it requires to prove the main conclusions of this paper.

Since \left\{x^k\right\} is a bounded sequence, let \overline{x} be one of its cluster points. Due to the continuity of the mapping \parallel e\left(\cdot ,1\right)\parallel and (4.7), it is known that e\left(\overline{x},1\right)=0. Then, by Lemma 2.2, \overline{x}\in S. In Eq. (4.1), replace x* with \overline{x} and thus obtain that \{\parallel x^k-\overline{x}\parallel \} is a convergent sequence. Since \overline{x} is a cluster point of \left\{x^k\right\}, \{\parallel x^k-\overline{x}\parallel \} must converge to 0. Therefore, \left\{x^k\right\} converges to \overline{x}\in S. Thus, the proof of the theorem is completed.

According to [7], a new search direction is considered.

d\left(x^k,{\beta }_k\right)=t_1{d}_1\left(x^k,{\beta }_k\right)+t_2{d}_2\left(x^k,{\beta }_k\right),

where d_1(x^k,{\beta }_k)=x^k-y^k-{\beta }_k\left(F\right(x^k)-F(y^k\left)\right), d_2(x^k,{\beta }_k)={\beta }_{k}F\left(y^k\right), t_1,t_2\in [0,\mathrm{\infty }) and t_1^2+t_2^2\ne 0.

The following presents algorithm based on the direction d\left(x^k,{\beta }_k\right)=t_1{d}_1\left(x^k,{\beta }_k\right)+t_2{d}_2\left(x^k,{\beta }_k\right).

Algorithm 4.1　Select an initial point x^0\in {\mathbb{R}}^n and parameters \nu ,l\in \left(0,1\right), \gamma \in \left(0,2\right), r = 1. Take k := 0.

Step 1: Compute y^k=P_C(x^k-{\beta }_{k}F(x^k\left)\right), {\beta }_k:=r{l}^{m_k}. Here, m_k is the smallest non-negative integer m such that the following equation holds:

{\beta }_k\parallel F\left(x^k\right)-F\left(x^k-e\left(x^k,{\beta }_k\right)\right)\parallel \le \nu \parallel e\left(x^k,{\beta }_k\right)\parallel .

Step 2: Compute e\left(x^k,{\beta }_k\right)=x^k-y^k. If e\left(x^k,{\beta }_k\right)=0, stop; otherwise, proceed to the next step.

Step 3: Compute

x^{k+1}=P_{T_k}\left(x^k-{\alpha }_{k}d\left(x^k,{\beta }_k\right)\right),

where

\begin{array}{rl}& T_k=\{w\in {\mathbb{R}}^n:⟨x^k-{\beta }_{k}F(x^k)-y^k,w-y^k⟩\le 0\},\\ & {\alpha }_k=\gamma \frac{⟨e(x^k,{\beta }_k),d_1(x^k,{\beta }_k)⟩}{(t_1+t_2)\parallel d_1(x^k,{\beta }_k){\parallel }^2},\\ & d(x^k,{\beta }_k)=t_1{d}_1(x^k,{\beta }_k)+t_2{d}_2(x^k,{\beta }_k),\\ & d_1(x^k,{\beta }_k)=x^k-y^k-{\beta }_k\left(F\right(x^k)-F(y^k\left)\right),\\ & d_2(x^k,{\beta }_k)={\beta }_{k}F\left(y^k\right),t_1^2+t_2^2\ne 0,t_1,t_2\in [0,\mathrm{\infty }).\end{array}

Step 4: If

{\beta }_k\parallel F\left(x^k\right)-F\left(x^k-{\beta }_{k}F\left(x^k\right)\right)\parallel \le 0.4\parallel e\left(x^k,{\beta }_k\right)\parallel ,

r=\frac{{\beta }_k}{0.7}, or r={\beta }_k, let k:=k+1. Go back to Step 1.

The following notes are used to illustrate the relationship between Algorithm 4.1 and existing algorithms.

Note 4.1　(a) When t_1=1,t_2=0, Algorithm 4.1 degenerates into Algorithm 3.1. Therefore, Algorithm 4.1 can be regarded as a generalization of Algorithm 3.1.

(b) When t₁ = 0, t₂ = 1, and γ = 1, then the next iterative point of Algorithm 4.1 is as follows.

x^{k+1}=P_{T_k}\left(x^k-\frac{⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩}{\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2}{d}_2\left(x^k,{\beta }_k\right)\right).

At this point, Algorithm 4.1 degenerates into Algorithm 1 in [13]. Consequently, Algorithm 4.1 can also be regarded as a generalization of Algorithm 1 in [13].

Lemma 4.2　 If Assumption H holds and \left\{x^k\right\} is an infinite sequence generated by Algorithm 4.1, then for any fixed x^{\ast }\in S, the following conclusion holds:

(4.9)\parallel x^{k+1}-x^{\ast }{\parallel }^2\le \parallel x^k-x^{\ast }{\parallel }^2-\frac{1}{2}\gamma \left(2-\gamma \right)\left(1-\nu \right)\parallel e\left(x^k,{\beta }_k\right){\parallel }^2.

Proof　By Lemma 2.1(iii) and combining S\subset C\subset T_k, for arbitrarily taken x^{\ast }\in S, there is

\begin{array}{rl}\parallel x^{k+1}-x^{\ast }{\parallel }^2& \le \parallel x^k-{\alpha }_{k}d(x^k,{\beta }_k)-x^{\ast }{\parallel }^2-\parallel x^k-{\alpha }_{k}d(x^k,{\beta }_k)-x^{k+1}{\parallel }^2\\ & =\parallel x^k-x^{\ast }{\parallel }^2-2{\alpha }_k⟨x^k-x^{\ast },d(x^k,{\beta }_k)⟩+{\alpha }_k^2\parallel d(x^k,{\beta }_k){\parallel }^2\\ & -(\parallel x^k-x^{k+1}{\parallel }^2-2{\alpha }_k⟨x^k-x^{k+1},d(x^k,{\beta }_k)⟩+{\alpha }_k^2\parallel d(x^k,{\beta }_k\left){\parallel }^2\right)\\ & =\parallel x^k-x^{\ast }{\parallel }^2-2{\alpha }_k⟨x^{k+1}-x^{\ast },d(x^k,{\beta }_k)⟩-\parallel x^k-x^{k+1}{\parallel }^2.\end{array}

Let \vartheta \left(x_k\right)=\parallel x^k-x^{\ast }{\parallel }^2-\parallel x^{k+1}-x^{\ast }{\parallel }^2. There is

(4.10)\begin{array}{rl}\vartheta \left(x_k\right)& \ge \parallel x^k-x^{k+1}{\parallel }^2+2{\alpha }_k⟨x^{k+1}-x^{\ast },d\left(x^k,{\beta }_k\right)⟩\\ & =\parallel x^k-x^{k+1}{\parallel }^2+2{\alpha }_k⟨x^{k+1}-y^k,d\left(x^k,{\beta }_k\right)⟩+2{\alpha }_k⟨y^k-x^{\ast },d\left(x^k,{\beta }_k\right)⟩\\ & \ge \parallel x^k-x^{k+1}{\parallel }^2+2{\alpha }_k⟨x^{k+1}-y^k,d\left(x^k,{\beta }_k\right)⟩,\end{array}

where the second inequality can be obtained from (2.3), (2.5), and α_k ≥ 0.

(4.11)\begin{array}{rl}& 2{\alpha }_k⟨x^{k+1}-y^k,d\left(x^k,{\beta }_k\right)⟩\\ & =2{\alpha }_k⟨x^{k+1}-y^k,t_1\left(x^k-y^k\right)-t_1{\beta }_{k}F\left(x^k\right)+\left(t_1+t_2\right){\beta }_{k}F\left(y^k\right)⟩\\ & \ge 2{\alpha }_k⟨x^{k+1}-y^k,t_1\left(x^k-y^k\right)-t_1{\beta }_{k}F\left(x^k\right)+\left(t_1+t_2\right){\beta }_{k}F\left(y^k\right)⟩\\ & +2{\alpha }_k⟨x^{k+1}-y^k,t_2\left(x^k-{\beta }_{k}F\left(x^k\right)-y^k\right)⟩\\ & =2{\alpha }_k\left(t_1+t_2\right)⟨x^{k+1}-y^k,x^k-y^k-{\beta }_k\left(F\left(x^k\right)-F\left(y^k\right)\right)⟩\\ & =2{\alpha }_k\left(t_1+t_2\right)⟨x^{k+1}-y^k,d_1\left(x^k,{\beta }_k\right)⟩,\end{array}

where the second inequality is derived from x^{k+1}\in T_k,{\alpha }_k>0, and t₂ > 0.

(4.12)\begin{array}{rl}\parallel x^k-x^{k+1}{\parallel }^2& =\parallel x^k-x^{k+1}-{\alpha }_k\left(t_1+t_2\right)d_1\left(x^k,{\beta }_k\right)+{\alpha }_k\left(t_1+t_2\right)d_1\left(x^k,{\beta }_k\right){\parallel }^2\\ & \ge 2⟨x^k-x^{k+1}-\left(t_1+t_2\right){\alpha }_k{d}_1\left(x^k,{\beta }_k\right),\left(t_1+t_2\right){\alpha }_k{d}_1\left(x^k,{\beta }_k\right)⟩\\ & +{\left(t_1+t_2\right)}^2{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2\\ & =-{\left(t_1+t_2\right)}^2{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2+2\left(t_1+t_2\right){\alpha }_k⟨x^k-x^{k+1},d_1\left(x^k,{\beta }_k\right)⟩.\end{array}

According to (4.10)‒(4.12), there is

(4.13)\begin{array}{rl}\vartheta \left(x_k\right)& \ge -{\left(t_1+t_2\right)}^2{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2+2\left(t_1+t_2\right){\alpha }_k⟨x^k-y^k,d_1\left(x^k,{\beta }_k\right)⟩\\ & =-{\left(t_1+t_2\right)}^2{\alpha }_k^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2+2\left(t_1+t_2\right){\alpha }_k⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩.\end{array}

The right-hand side of the inequality (4.13) is a quadratic function with respect to α_k, which reaches its maximum value at {\alpha }_k^{\ast }=\frac{⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩}{\left(t_1+t_2\right)\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2}. Substitute{\alpha }_k^{\ast } into the equation (4.13), and there is

\begin{array}{rl}\vartheta \left(x_k\right)& \ge -{\left(t_1+t_2\right)}^2{\left({\alpha }_k^{\ast }\right)}^2\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2+2\left(t_1+t_2\right){\alpha }_k^{\ast }⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩\\ & ={\alpha }_k^{\ast }⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩.\end{array}

Let {\alpha }_k=\gamma \frac{⟨e\left(x^k,{\beta }_k\right),d_1\left(x^k,{\beta }_k\right)⟩}{\left(t_1+t_2\right)\parallel d_1\left(x^k,{\beta }_k\right){\parallel }^2}, and Eq. (4.9) can be obtained through similar discussions as in Lemma 4.1.

Similarly, the following conclusions can be reached.

Theorem 4.2　 If Assumption H holds and \left\{x^k\right\} is an infinite sequence generated by Algorithm 4.1, then the sequence \left\{x^k\right\} converges to a solution of the variational inequality (1.1).

5 Computer verification of the algorithm

This section presents the computer verification results of Algorithm 3.1 and Algorithm 4.1 in the following four simple examples, and makes a comparison with Algorithm 3.1 in [5] (referred to as the Gibali algorithm for short) and Algorithm 2.2 in [20] (referred to as the S‒S algorithm for short). All these results are obtained by running MATLAB on a laptop with an Intel(R) Core(TM) i5-3210M CPU (dual core, main frequency 2.50 GHz) and 2.0 GB RAM. The parameter selection for Algorithm 3.1 and Algorithm 4.1 is as follows: v =0.98, r = 1, l = 0.5, γ= 1.9, t₁ = 1, t₂ = 1. The parameters selected for the Gibali algorithm are the same as those in [5], namely {\alpha }_{-1}=0.7, ε = 0.2, β = 0.5. The parameters selected for the S-S algorithm are the same as those in [20], namely σ = 0.3, γ = 0.5, {\eta }_{-1}=1, θ = 4. The termination condition of the algorithms is \parallel x_n-y_n\parallel \le \epsilon. Respectively take \epsilon ={10}^{-4} and \epsilon ={10}^{-8} as the stopping criteria for the algorithms. Denote the running time in CPU (unit: s), the number of iteration steps as iter, the total number of projection times as np, and the total number of function value estimation times as nf. Denote the initial point as x⁰.

Example 5.1　This example is used in [14] to test the algorithms for continuous monotone variational inequality problems. The feasible set and the mapping are respectively C=\{x\in {\mathbb{R}}_{+}^n:x_1+x_2+x_3+x_4=4\} and

F(x_1,x_2,x_3,x_4)=\left[\begin{array}{c}3x_1^2+2x_1{x}_2+2x_2^2+x_3+3x_4-6\\ 2x_1^2+x_1+x_2^2+10x_3+2x_4-2\\ 3x_1^2+x_1{x}_2+2x_2^2+2x_3+9x_4-9\\ x_1^2+3x_2^2+2x_3+3x_4-3\end{array}\right].

Example 5.2　This example is used in [21] to test the algorithms for the Nonlinear Complementarity Problem (NCP). Define C={\mathbb{R}}_{+}^n,F\left(x\right)=F_1\left(x\right)+F_2\left(x\right), where

\begin{array}{rl}& F_1\left(x\right)=\left(f_1\right(x),f_2(x),\dots ,f_n(x\left)\right),\\ & F_2\left(x\right)=Mx+q,\\ & f_i\left(x\right)=x_{i-1}^2+x_i^2+x_{i-1}{x}_i+x_i{x}_{i+1},i=1,2,\dots ,n,\\ & x_0=x_n=0.\end{array}

The matrix M is an n × n square matrix, and q=\left(-1,-1,\dots ,-1\right),

M=\left(\begin{array}{ccccc}4& -2& & & \\ 1& 4& -2& & \\ & 1& 4& -2& \\ & & \ddots & \ddots & ⋮\\ & & & 1& 4\end{array}\right).

The initial point x^0=\left(0,0,\dots ,0\right).

Example 5.3　This example is used in [9] to test the algorithms for the Nonlinear Complementarity Problem, where

F\left(x\right)=Mx+D\left(x\right)+q,

where M=A^{\mathrm{T}}A+B, A is an n×n square matrix randomly generated from the interval (−5, 5), B is an anti-symmetric matrix generated in the same way, the vector q is uniformly generated from the interval (−500, 0), and D_i\left(x\right)=d_i\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{a}\mathrm{n}\left(x_i\right), where d_i is a random variable on the interval (0,1). The initial point x^0=\left(1,1,\dots ,1\right).

Example 5.4　Nonlinear variational inequality problem. In this example, three cases are tested for the above four algorithms. The Mathiesen case is tested in reference [20]. Harker [8] defined and tested the 5-dimensional Harnash5 and 10-dimensional Harnash10. For the Mathiesen case, the initial point is taken as x^0=\left(0.3,0.4,0.3\right), and x^0=\left(1,1,\dots ,1\right) for the other cases in this example.

Note 5.1　Judging from the results of the numerical experiments, we have the following conclusions:

(A) Algorithm 4.1, Algorithm 3.1, the Gibali algorithm, and the S‒S algorithm can all work out the solutions of the variational inequality problems. However, the subgradient extragradient projection algorithm is less affected by the dimension of the variational inequality problem, the precision, and the selection of the initial point, as shown in Tables 1 and 3. It is believed that this is mainly because the next iterative point of the subgradient extragradient projection algorithm is obtained by projecting onto a half-space and it does not require the condition x^k\in C. In contrast, the convergence analysis of the S‒S algorithm requires the condition x^k\in C. Thus, when there is an error in the computer’s calculation of the next iterative point: x^k+1=P_{C\cap H_k}\left(x^k\right)+{\epsilon }_k (ε_k is the error vector), it is not necessarily guaranteed that x^k+1\in C at this time. This may have an impact on the convergence of the algorithm. Therefore, this algorithm does not perform well when the stopping criterion is 10⁻⁸.

(B) Under the circumstances of low dimension and stopping criteria, the S‒S algorithm outperforms the Gibali algorithm [5], demonstrating an advantage in the number of iteration steps. See Tables 1, 2, and 4.

(C) In terms of the number of iterations, the number of function value estimations, and the number of projections, both Algorithm 3.1 and Algorithm 4.1 outperform the algorithm in [5], as shown in Tables 1‒4.

(D) Algorithm 4.1 outperforms Algorithm 3.1.

References

[1] BertsekasD.P.. and Gafni, E.M., Projection methods for variational inequalities with application to the traffic assignment problem, In: Nondifferential and Variational Techniques in Optimization (Sorensen, D.C. and Wets, R.J.-B. eds.), Math. Programming Stud., No. 17, Amsterdam: North-Holland, 1982, 139–159

[2] Censor Y., Gibali, A. , Reich, S. . Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space. Optimization 2012; 61(9): 1119–1132

[3] Chen A., Lo, H.K. , Yang, H. . A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs. European J. Oper. Res. 2001; 135(1): 27–41

[4] FacchineiF. , Pang, J.-S., Finite-dimensional Variational Inequalities and Complementarity Problems, Vol. I, Springer Series in Operations Research, New York: Springer-Verlag, 2003

[5] Gibali A. . A new non-Lipschitzian projection method for solving variational inequalities in Euclidean spaces. J. Nonlinear Anal. Optim. 2015; 6(1): 41–51

[6] Han D.R. , Lo, H.K. . Two new self-adaptive projection methods for variational inequality problems. Comput. Math. Appl. 2002; 43(12): 1529–1537

[7] Han D.R., Zhang, H.C., Qian, G. , Xu, L.L. . An improved two-step method for solving generalized Nash equilibrium problems. European J. Oper. Res. 2012; 216(3): 613–623

[8] Harker P.T. . Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities. Math. Programming Ser. A 1988; 41(1): 29–59

[9] He B.S. , Liao, L.Z. . Improvements of some projection methods for monotone nonlinear variational inequalities. J. Optim. Theory Appl. 2002; 112(1): 111–128

[10] He Y.R. . A new double projection algorithm for variational inequalities. J. Comput. Appl. Math. 2006; 185(1): 166–173

[11] Iusem A.N. , Svaiter, B.F. . A variant of Korpelevich’s method for variational inequalities with a new search strategy. Optimization 1997; 42(4): 309–321

[12] Khobotov E.N. . Modification of the extra-gradient method for solving variational inequalities and certain optimization problems. USSR Comput. Math. Math. Phys. 1987; 27(5): 120–127

[13] Li H., Yang, L. , Li, J. . A subgradient exgradient projection method for pseudomonotone variational inequalities. J. China West Norm. Univ. (Nat. Sci.) 2016; 37(2): 189–194

[14] Malitsky . Projected reflected gradient methods for monotone variational inequalities. SIAM. J. Optim. 2015; 25(1): 502–520

[15] Malitsky . An extragradient algorithm for monotone variational inequalities. Cybernet. Systems Anal. 2014; 50(2): 271–277

[16] NagurneyA., Network Economics: A Variational Inequality Approach, Revised Second Edition, Advances in Computational Economics, Vol. 10, Dordrecht: Springer Science+Business Media, 1999

[17] Nagurney A. , Ramanujam, P. . Transportation network policy modeling with goal targets and generalized penalty functions. Transport. Sci. 1996; 30(1): 3–13

[18] Noor M.A., Some recent advances in variational inequalities, II. . other concepts. New Zealand J. Math. 1997; 26(2): 229–255

[19] Sibony M. . Methodes itératives pour les équations et inequations aux dérivées partielles non linéaires de type monotone. Calcolo 1970; 7: 65–183

[20] Solodov M.V. , Svaiter B.F. . A new projection method for variational inequality problems. SIAM J. Control Optim. 1999; 37(3): 765–776

[21] Sun D.F. . A projection and contraction method for the nonlinear complementarity problem and its extensions. Math. Numer. Sinica 1994; 16(2): 183–194

[22] Wang Y.J., Xiu, N.H. , Wang, C.Y. . A new version of extragradient method for variational inequality problems. Comput. Math. Appl. 2001; 42(6/7): 969–979

[23] Wang Y.J., Xiu, N.H. , Wang, C.Y. . Unified framework of extragradient-type methods for pseudomonotone variational inequalities. J. Optim. Theory Appl. 2001; 111(3): 641–656

[24] Xiu N.H. , Zhang, J.Z. . Some recent advances in projection-type methods for variational inequalities. J. Comput. Appl. Math. 2003; 152(1/2): 559–585

RIGHTS & PERMISSIONS

Higher Education Press 2025