# The Strong Convergence of Prediction-Correction and Relaxed Hybrid Steepest-Descent Method for Variational Inequalities

Authors: Haiwen Xu
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We establish the strong convergence of prediction-correction and relaxed hybrid steepest-descent method (PRH method) for variational inequalities under some suitable conditions that simplify the proof. And it is to be noted that the proof is different from the previous results and also
is not similar to the previous results. More importantly, we design a set of practical numerical experiments. The results demonstrate that the PRH method under some descent directions is more slightly efficient than that of the modified and relaxed hybrid steepest-descent method, and the PRH Method under some new conditions is more efficient than that under some old conditions.


---

## Body

## 1. Introduction

LetH be a real Hilbert space with inner product  〈·,·〉 and norm ∥·∥, let K be a nonempty closed convex subset of H, and let F:H→H be an operator. Then the variational inequality problem VI(F,K) [1] is to find x*∈K such that
(1)x*∈K,〈x-x*,F(x*)〉≥0,∀x∈K.The literature contains many methods for solving variational inequality problems; see [2–25] and references therein. According to the relationship between the variational inequality problems and a fixed point problem, we can obtain
(2)x*isthesolutionofVI(F,K)⟺x*=PK[x*-βF(x*)],β>0,
where the projection operator PK is the projection from H onto K, that is,
(3)PK(x)=argminy∈K∥x-y∥,∀x∈H.
In this paper, F:H→H is an operator with F:κ-Lipschtz and η-strongly monotone; that is, F satisfies the following conditions:
(4)∥F(x)-F(y)∥≤κ∥x-y∥,〈F(x)-F(y),x-y〉≥η∥x-y∥2,∀x,y∈K.
If β is small enough, then PK is a contraction. Naturally, the convergence of Picard iterates generated by the right-hand side of (2) is obtained by Banach’s fixed point theorem. Such a method is called the projection method or more results about the projection method see [6, 8, 20] and so forth.In fact, the projectionPK in the contraction methods may not be easy to compute, and a great effort is to compute the projection PK in each iteration. Yamada and Deutsch have provided a hybrid steepest-descent method for solving the VI(F,K) [2, 3] in order to reduce the difficulty and complexity of computing the projection PK. Subsequently, the convergence of hybrid steepest-descent methods was given out by Xu and Kim [4] and Zeng et al. [5]. Naturally, by analyzing several three-step iterative methods in each iteration by the fixed pointed equation, we can obtain the Noor iterations. Recently, Ding et al. [7] proposed a three-step relaxed hybrid steepest-descent method for variational inequalities, and the simple proof of three-step relaxed hybrid steepest-descent methods under different conditions was introduced by Yao et al. [24]. The literature [14, 16] described a modified and relaxed hybrid steepest-descent (MRHSD) method and the different convergence of the MRHSD method under the different conditions. A set of practical numerical experiments in the literature [16] demonstrated that the MRHSD method has different efficiency under different conditions. Subsequently, the prediction-correction and relaxed hybrid steepest-descent method (PRH method) [15] makes more use of the history information and less decreases the loss of information than the methods [7, 14]. The PRH method introduced more descent directions than the MRHSD method [14, 16], and computing these descent directions only needs the history information.In this paper, we will prove the strong convergence of PRH method under different and suitable restrictions imposed on parameters (Condition12), which differs from that of [15]. Moreover, the proof of strong convergence is different from the previous proof in [15], which is not similar to that in [7] in Step 2. And more importantly, numerical experiments verify that the PRH method under Condition 12 is more efficient than that under Condition 10, and the PRH method under some descent directions is more slightly efficient than that of the MRHSD method [14, 16]. Furthermore, it is easy to obtain these descent directions.The remainder of the paper is organized as follows. In Section2, we review several lemmas and preliminaries. We prove the convergence theorem under Condition 12 in Section 3. In Section 4, we give out a series of numerical experiments, which demonstrated that the PRH method under Condition 12 is more efficient than under Condition 10. Section 5 concludes the paper.


## 2. Preliminaries

In order to proof the later convergence theorem, we introduce several lemmas and the main results in the following.Lemma 1.
In a real Hilbert space H, there holds the inequality(5)∥x+y∥2≤∥x∥2+2〈y,x+y〉,∀x,y∈H.The lemma is a basic result of a Hilbert space with the inner product.Lemma 2 (demiclosedness principle).
Assume thatT is a nonexpansive self-mapping on a nonempty closed convex subset K of a Hilbert space H. If T has a fixed point, then (I-T) is demiclosed. That is, whenever xn is a sequence in K weakly converging to some x∈K and the sequence (I-T)xn strongly converges to some y∈H, it follows that (I-T)x=y. Here I is the identity operator of H.The following lemma is an immediate result of a projection mapping onto a closed convex subset of a Hilbert space.Lemma 3.
LetK be a nonempty closed convex subset of H. For allx,y∈H and z∈K, then(1)
〈PK(x)-x,z-PK(y)〉≥0,(2)
∥PK(x)-PK(y)∥2≤∥x-y∥2−∥PK(x)-x+y-PK(y)∥2.Lemma 4 (see [13]).
Let{xn} and {yn} be bounded sequence in a Banach space X and let {ζn} be a sequence in [0,1] with 0<liminfn→∞ζn≤limsupn→∞ζn<1. Suppose xn+1=(1-ζn)yn+ζnxn for all integers n≥0 and limsupn→∞(∥yn+1-yn∥-∥xn+1-xn∥)≤0. Then limsupn→∞∥yn-xn∥=0.Lemma 5 ([5, 7]).
Let{sn} be a sequence of nonnegative real numbers satisfying the inequality
(6)sn+1≤(1-αn)sn+αnτn+γn,∀n≥0,
where αn, τn, and γn satisfy the following conditions: (1)
αn⊂[0,1],∑n=0∞αn=∞,or∏n=0∞(1-αn)=0,(2)
limn→∞supτn≤0,(3)
γn⊂[0,∞),∑n=0∞γn<∞. Then limn→∞sn=0.SinceF is η-strongly monotone, VI(F,K) has a unique solution x*∈K [5]. Assume that T:H→H is a nonexpansive mapping with the fixed point set Fix(T)=K. Obviously Fix(PK)=K.For any given numbersλ∈(0,1) and μ∈(0,2η/κ2), we define the mapping Tμλ:H→H by(7)Tμλx:Tx-λμF(Tx),∀x∈H.Lemma 6 (see [5]).
If0<μ<2η/κ2 and 0<λ<1, then Tμλ is a contraction. In fact,
(8)∥Tμλx-Tμλy∥≤(1-λδ)∥x-y∥,
where δ=1-1-μ(2η-μκ2), for all x,y∈H.Lemma 7 (see [7]).
Let{αn} be a sequence of nonnegative numbers with limsupn→∞αn<∞ and let {βn} be sequence of real numbers with limsupn→∞βn≤0. Then(9)limsupn→∞αnβn≤0.


## 3. Convergence Theorem

Before analyzing the convergence theorem, we first review the PRH method and related results [15].Algorithm 8 (see [15]).
Take three fixed numberst,ρ,γ∈(0,2η/κ2), starting with arbitrarily chosen initial points x0∈H, compute the sequences {xn},{x-n},{x~n},{x^n} such that;Prediction
Step  1:x-n=γnxn+(1-γn)[Txn-λn+1′′γF(Txn)],Step  2:x~n=βnxn+(1-βn)[Tx-n-λn+1′ρF(Tx-n)],Step  3:x^n=θnx-n+(1-θn)x~n,0≤θn≤1,Correction
Step  4:xn+1=αnx-n+(1-αn)[Tx^n-λn+1tF(Tx^n)],whereT:H→H is a nonexpansive mapping.Let{αn}⊂[0,1),{βn}⊂[0,1] and {γn}⊂[0,1], {λn},{λn′},{λn′′}⊂(0,1) satisfy the following conditions.Remark 9.
In fact, the PRH method is the MRHSD method whenθn≡0,foralln.Condition 10.
One has(10)(1)∑1∞‍|αn-αn-1|<∞,∑1∞‍|βn-βn-1|<∞,∑1∞‍|γn-γn-1|<∞,(2)limn→∞αn=0,limn→∞βn=1,limn→∞γn=1,(3)limn→∞λn=0,limn→∞λnλn+1=1,∑1∞‍λn=∞,(4)λn≥max{λn′,λn′′},∀n≥1.Theorem 11 (see [15]).
In Condition10, the sequence {xn} converges strongly to x*∈K, and x* is the unique solution of the VI(F,K).We obtain the strong convergence theorem of PRH method for variational inequalities under different assumptions.Condition 12.
One has(11)(1)0<liminfn→∞αn≤limsupn→∞αn<1,limn→∞βn=1,limn→∞γn=1,(2)limn→∞λn=0,∑1∞‍λn=∞,(3)λn≥max{λn′,λn′′},∀n≥1.Theorem 13.
The sequence{xn} converges strongly to x*∈K, and x* is the unique solution of the VI(F,K). Assume that {αn},{βn} and {γn}, {λn},{λn′},{λn′′} satisfy Condition 12.Proof.
We divide the proof into several steps.
Step 1. {xn},{x-n},{x~n}, and {x^n} are bounded. Since F is η-strongly monotone, VI(F,K) (1) has a unique solution x*∈K, and Ttλn+1x*=x*-λn+1tF(x*), Tρλn+1′x*=x*-λn+1ρF(x*), Tγλn+1′′x*=x*-λn+1γF(x*).
A series of computations yields(12)∥xn+1-x*∥=∥αnx-n+(1-αn)Ttλn+1x^-x*∥∥xn+1-x*∥≤αn∥x-n-x*∥+(1-αn)∥Ttλn+1x^-x*∥∥xn+1-x*∥≤αn∥x-n-x*∥+(1-αn)∥xn+1-x*∥m×[∥Ttλn+1x^-Ttλn+1x*∥+∥Ttλn+1x*-x*∥]∥xn+1-x*∥≤αn∥x-n-x*∥+(1-αn)∥xn+1-x*∥m×[(1-λn+1τ)∥x^n-x*∥+λn+1t∥F(x*)∥],
where τ=1-1-t(2η-tκ2)∈(0,1),
(13)∥x~n-x*∥=∥βnxn+(1-βn)Tρλn+1′x-n-x*∥∥x~n-x*∥≤βn∥xn-x*∥+(1-βn)∥Tρλn+1′x-n-x*∥∥x~n-x*∥≤βn∥xn-x*∥+(1-βn)∥x~n-x*∥m×[∥Tρλn+1′x-n-Tρλn+1′x*∥+∥Tρλn+1′x*-x*∥]∥x~n-x*∥≤βn∥xn-x*∥+(1-βn)∥x~n-x*∥m×[(1-λn+1′τ′)∥x-n-x*∥+λn+1′ρ∥F(x*)∥]∥x~n-x*∥≤βn∥xn-x*∥+(1-βn)∥x-n-x*∥∥x~n-x*∥m+(1-βn)λn+1′ρ∥F(x*)∥,
where τ′=1-1-ρ(2η-tκ2)∈(0,1).
Moreover, we also obtain(14)∥x~n-x*∥=∥γnxn+(1-γn)Tγλn+1′′xn-x*∥∥x~n-x*∥≤γn∥xn-x*∥+(1-γn)∥Tγλn+1′′xn-x*∥∥x~n-x*∥≤γn∥xn-x*∥+(1-γn)∥x~n-x*∥×[∥Tγλn+1′′xn-Tγλn+1′′x*∥+∥Tγλn+1′′x*-x*∥]∥x~n-x*∥≤γn∥xn-x*∥+(1-γn)∥x~n-x*∥×[(1-λn+1′′τ′′)∥xn-x*∥+λn+1′′γ∥F(x*)∥]∥x~n-x*∥≤∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥,
where τ′′=1-1-γ(2η-tκ2)∈(0,1), subtituting; (14) into (13) and (14) into (12), we immediately obtain
(15)∥x~n-x*∥=βn∥xn-x*∥+(1-βn)∥x~n-x*∥m×[(1-λn+1′τ′)∥x-n-x*∥+λn+1′ρ∥F(x*)∥]∥x~n-x*∥≤βn∥xn-x*∥+(1-βn)∥x~n-x*∥m×[(1-λn+1′τ′)∥xn-x*∥∥x~n-x*∥m,m+(1-γn)λn+1′′γ∥F(x*)∥+λn+1′ρ∥F(x*)∥]∥x~n-x*∥≤∥xn-x*∥+(1-βn)λn+1(γ+ρ)∥F(x*)∥.
Furthermore,
(16)∥x^n-x*∥=∥θnx-n+(1-θn)x~n-x*∥∥x^n-x*∥≤θn∥x-n-x*∥+(1-θn)∥x~n-x*∥∥x^n-x*∥≤θn[∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥]∥x^n-x*∥m+(1-θn)[∥xn-x*∥+(1-βn)λn+1mmmmmmmmmmm,,×(γ+ρ)∥F(x*)∥]∥x^n-x*∥≤∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥∥x^n-x*∥m+(1-βn)λn+1(γ+ρ)∥F(x*)∥,∥xn+1-x*∥≤αn∥x-n-x*∥+(1-αn)×[(1-λn+1τ)∥x^n-x*∥+λn+1t∥F(x*)∥]≤αn[∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥]+(1-αn){(1-λn+1τ)mmmmmm,,,m×[∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥mmmmmmm,..,m+(1-βn)λn+1(γ+ρ)∥F(x*)∥]mmmmmmmm+λn+1t∥F(x*)∥}≤αn∥xn-x*∥+αn(1-γn)λn+1γ∥F(x*)∥+(1-αn)×[(1-λn+1τ)∥xn-x*∥+λn+1(2γ+ρ+t)∥F(x*)∥].
It is easy to obtain the following by induction:
(17)∥xn-x*∥≤M0,∀n≥0,
where M0=max{3∥x0-x*∥,3(ρ+γ+t)∥F(x*)∥/τ},
(18)∥x~n-x*∥≤∥xn-x*∥+(1-βn)λn+1(γ+ρ)∥F(x*)∥∥x~n-x*∥≤(1+τ3)M0,∥x-n-x*∥≤∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥∥x-n-x*∥≤(1+τ3)M0,∥x^n-x*∥≤θn∥x-n-x*∥+(1-θn)∥x~n-x*∥∥x^n-x*∥≤2(1+τ3)M0.
Hence(19){Txn},{Tx-n},{Tx~n},{Tx^n},{F(Txn)},{F(Tx-n)},{F(Tx~n)},{F(Tx^n)}
are also bounded.
Step 2. Consider ∥xn+1-xn∥→0.
Indeed, by a series of computations, we have(20)∥x-n-x-n-1∥=∥γnxn-γn-1xn-1+(1-γn)Tγλn+1′′xnm,m-(1-γn-1)Tγλn′′xn-1∥≤∥γnxn-γn-1xn-1∥+∥(1-γn)Tγλn+1′′xn-(1-γn-1)Tγλn′′xn-1∥≤∥xn-xn-1∥+|(1-γn)λn+1′′-(1-γn-1)λn′′|×γ∥F(Txn-1)∥+|γn-γn-1|(∥xn-1∥+∥Txn-1∥).
According to (20) and the prediction step of Algorithm 8, we also obtain
(21)∥x~n-x~n-1∥=∥βnxn-βn-1xn-1+(1-βn)Tρλn+1′x-n-(1-βn-1)Tρλn′x-n-1∥≤∥βnxn-βn-1xn-1∥+∥(1-βn)Tρλn+1′x-n-(1-βn-1)Tρλn′x-n-1∥≤∥xn-xn-1∥+|(1-βn)λn+1′-(1-βn-1)λn′|×ρ∥F(Tx-n-1)∥+(1-βn)(1-λn+1′τ′)×|γn-γn-1|(∥xn-1∥+∥Txn-1∥)+(1-βn)(1-λn+1′τ′)|(1-γn)λn+1′′-γn-1λn′′|×γ∥F(Txn-1)∥+|βn-βn-1|×(∥xn-1∥+∥Tx-n-1∥+∥Tx-n-1∥).
Also by the prediction step of Algorithm 8 and (20), (21), we have
(22)∥x^n-x^n-1∥≤θn∥x-n-x-n-1∥+(1-θn)∥x~n-x~n-1∥≤∥xn-xn-1∥+|(1-γn)λn+1′′-(1-γn-1)λn′′|γ∥F(Txn-1)∥+|γn-γn-1|(∥xn-1∥+∥Txn-1∥)+|(1-βn)λn+1′-(1-βn-1)λn′|ρ∥F(Tx-n-1)∥+(1-βn)(1-λn+1′τ′)|γn-γn-1|×(∥xn-1∥+∥Txn-1∥)+(1-βn)(1-λn+1′τ′)×|(1-γn)λn+1′′-γn-1λn′′|γ∥F(Txn-1)∥+|βn-βn-1|(∥xn-1∥+∥Tx-n-1∥+∥Tx-n-1∥).
Let(23)y^n=Ttλn+1x^n=Tx^n-λn+1tF(Tx^n),
so we get(24)xn+1=αnx-n+(1-αn)y^n.
Furthermore,
(25)∥y^n-y^n-1∥=∥Tx^n-Tx^n-1+λntF(Tx^n-1)-λn+1tF(Tx^n)∥≤∥Tx^n-Tx^n-1∥+λnt∥F(Tx^n-1)∥+λn+1t∥F(Tx^n)∥≤∥x^n-x^n-1∥+λnt∥F(Tx^n-1)∥+λn+1t∥F(Tx^n)∥.
Apply limn→∞βn=1,limn→∞λn=0, and limn→∞γn=1 and (22), (25) to get
(26)∥y^n-y^n-1∥-∥xn-xn-1∥≤|(1-γn)λn+1′′-(1-γn-1)λn′′|γ∥F(Txn-1)∥+|γn-γn-1|(∥xn-1∥+∥Txn-1∥)+|(1-βn)λn+1′-(1-βn-1)λn′|ρ∥F(Tx-n-1)∥+(1-βn)(1-λn+1′τ′)|γn-γn-1|(∥xn-1∥+∥Txn-1∥)+(1-βn)(1-λn+1′τ′)×|(1-γn)λn+1′′-γn-1λn′′|γ∥F(T(xn-1))∥+|βn-βn-1|(∥xn-1∥+∥Tx-n-1∥+∥Tx-n-1∥)+λnt∥F(Tx^n-1)∥+λn+1t∥F(Tx^n)∥⟶0.
According to Lemma 4, we obtain
(27)limn→∞∥y^n-1-xn-1∥=0.
Furthermore, by limn→∞γn=1, we also get
(28)∥x-n-xn∥=∥-(1-γn)xn+(1-γn)[Txn-λn+1′γF(Txn)]∥≤(1-γn)∥xn∥+(1-γn)∥Txn∥+λn+1′γ∥F(Txn)∥⟶0.
By (27), (28) and the correction step of Algorithm 8, we immediately conclude that
(29)∥xn-xn-1∥=∥αn-1x-n-1+(1-αn-1)y^n-1-xn-1∥≤αn-1∥x-n-1-xn-1∥+(1-αn-1)∥y^n-1-xn-1∥⟶0,
so we get
(30)∥xn+1-xn∥⟶0.
Step 3. Consider∥xn+1-Txn∥→0.
Indeed, by the prediction step of Algorithm8, we have
(31)∥x~n-xn∥=∥-(1-βn)xn+(1-βn)[Tx-n-λn+1′ρF(Tx-n)]∥≤(1-βn)∥xn∥+(1-βn)[∥Tx-n∥+∥λn+1′ρF(Tx-n)∥].
According to the assumption limn→∞βn=1 and limn→∞λn=0, then
(32)∥x~n-xn∥⟶0.
By (32), we immediately obtain
(33)∥x^n-xn∥≤θn∥x-n-xn∥+(1-θn)∥x~n-xn∥⟶0.
By a series of computations, we can get(34)∥xn+1-Txn∥=∥αn(x-n-Txn)+(1-αn)(Ttλn+1x^-Txn)∥≤αn∥x-n-Txn∥+(1-αn)∥Tx^n-Txn∥+(1-αn)λn+1t∥F(Tx^n)∥≤αn∥x-n-Txn∥+∥x^n-xn∥+λn+1t∥F(Tx^)∥≤αn∥xn+1-Txn∥+αn∥x-n-xn+1∥+∥x^n-xn∥+λn+1t∥F(Tx^)∥.
Hence, by (28), (33), and (34), we also obtain
(35)∥xn+1-Txn∥≤αn1-αn∥x-n-xn+1∥∥xn+1-Txn∥≤+∥x^n-xn∥1-αn+λn+1t∥F(Tx^)∥1-αn⟶0. Using Steps 2 and 3, it is easy to obtain the following corollary.
Corollary 14. Consider ∥xn-Txn∥→0.
Applying Steps
2
and
3
, one gets(36)∥xn+1-Txn∥⟶0,∥xn+1-xn∥⟶0,so it is easy to see that(37)∥xn-Txn∥≤∥xn+1-Txn∥+∥xn+1-xn∥⟶0.
Step 4. Consider limn→∞sup〈-F(x*),Tx^n-x*〉≤0.
For somex^∈H, here exits {Txni}→x^ weakly and such that
(38)limn→∞sup〈-F(x*),Txn-x*〉=limn→∞sup〈-F(x*),Txni-x*〉.
According to {Txni}→x^, we have
(39)x^∈Fix(T)=K.
By x* being the unique solution of VI(F,K), we can obtain
(40)limn→∞sup〈-F(x*),Txn-x*〉=limn→∞sup〈-F(x*),x^-x*〉≤0.
Since ∥Tx^n-Txn∥≤∥x^n-xn∥→0, we immediately conclude that
(41)limn→∞sup〈-F(x*),Tx^n-x*〉≤limn→∞sup〈-F(x*),Tx^n-Txn〉+limn→∞sup〈-F(x*),Txn-x*〉≤limn→∞sup〈-F(x*),Txn-x*〉≤0.
Step 5. By Step 1 and Lemma 1, we have
(42)∥xn+1-x*∥2=∥αn(x-n-x*)+(1-αn)(Ttλn+1x^n-x*)∥2≤∥αn(x-n-x*)∥2+(1-αn)×∥(Ttλn+1x^n-Ttλn+1x*+Ttλn+1x*-x*)∥2≤∥αn(x-n-x*)∥2+(1-αn)×[∥Ttλn+1x^n-Ttλn+1x*∥2mmmm+2〈Ttλn+1x*-x*,Ttλn+1x^n-x*〉]≤αn[∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥]2+(1-αn)(1-λn+1τ)2×[∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥+(1-βn)λn+1(γ+ρ)∥F(x*)∥∥xn-x*∥+(1-γn)λn+1′′γ∥F(x*)∥]2+2tλn+1〈-F(x*),Tx^n-x*-tλn+1F(Tx^n)〉≤αn∥xn-x*∥2+(1-γn)λn+1γM+(1-αn)(1-λn+1τ)2∥xn-x*∥2+(1-αn)(1-λn+1τ)2(1-βn)λn+1M+(1-αn)(1-λn+1τ)2(1-γn)λn+1γM+2tλn+1〈-F(x*),Tx^n-x*-tλn+1F(Tx^n)〉≤[1-(1-αn)λn+1τ]∥xn-x*∥2+(1-αn)λn+1τwn+1′,
where
(43)wn+1′=2t〈-F(x*),Tx^n-x*-tλn+1F(Tx^n)〉τ(1-αn)wn+1′=+φnτ(1-αn)+ξnτ(1-αn),φn=(1-γn)γM,ξn=(1-αn)(1-λn+1τ)2(1-βn)Mξn=+(1-αn)(1-λn+1τ)2(1-γn)λn+1γM,
and M0≪M<∞.
Denote(44)sn+1′=∥xn+1-x*∥,un=(1-αn)λn+1τ.
We can rewrite (42) as(45)sn+1′≤(1-un)sn′+unwn′+0.
In fact, un,wn′ satisfies Lemma 5; according to
(46)limn→∞βn=1,limn→∞γn=1,limn→∞λn=0,
we obtain
(47)φnτ(1-αn)⟶0,ξnτ(1-αn)⟶0.
Moreover, by Step 4, we also obtain
(48)limn→∞2t〈-F(x*),Tx^n-x*-tλn+1F(Tx^n)〉τ(1-αn)≤2tτlimn→∞sup{〈-F(x*),Tx^n-x*〉≤2tτlimn→∞..sup+λn+1〈-F(x*),-tF(Tx^n)〉}≤2tτlimn→∞sup{〈-F(x*),Tx^n-x*〉}+limn→∞sup{λn+1〈-F(x*),-tF(Tx^n)〉}≤0+0=0.
Furthermore, by (43), (47), and (48), it is easy to obtain
(49)limn→∞supwn′≤0.
Consequently apply Lemma 5 to obtain
(50)∥xn-x*∥⟶0.


## 4. Numerical Experiments

The problem considered in this section is(51)min{12∥X-C∥F2∣X∈K},
where ∥·∥F is the matrix Fröbenis norm; that is,
(52)∥C∥F=(∑i=1∞‍∑j=1∞‍|Cij|2)1/2.Note that the matrix Fröbenis norm is induced by the inner product(53)〈A,B〉=Trace(ATB).
The problems arise from finance and statistics, and we form the test problems similarly as in [9, 21].LetK=S+n∩ß, where(54)S+n={H∈ℝn×n∣HT=H,H≽0},ß={H∈ℝn×n∣HT=H,HL≤H≤HU}.
Let HL,HU be given n×n symmetric matrices, and C asymmetric which differs from previous approaches [9, 21], and it is to be noted that the extended contraction method (EC method) [9] has much difficulty in computing the examples when C is asymmetric, where HL≤HU in element wise:(55)HL≤HU:(HL)ij≤(HU)ij,∀i,j∈1,…,n.Then (51) is equivalent to the following variational inequality:
(56)〈X′-X,∇(12∥X-C∥2)〉≥0,∀X′∈K.
So we get
(57)〈X′-X,X-C〉≥0,∀X′∈K.According to Condition10, we take the following parameter sequences, and let Condition 10 denote the parameter sequences:
(58)αn=1lnn,λn=λn′=λn′′=1ln(n+1),βn=γn=1-1lnn,γ=ρ=t=c0>0.
According to Condition 12, we take the following parameter sequences, and let Condition 12 denote the parameter sequences:
(59)αn=0.8-1(10*lnn),n=2k,αn=0.3-1(10*lnn),n=2k-1,λn=λn′=λn′′=1ln(n+1),βn=1-1lnn,n=2k,βn=1-1lnn,n=2k-1,γn=1-1lnn,n=2k,γn=1-1ln(2n),n=2k-1,γ=ρ=t=c0>0.
Obviously, we have much difficulty in computing the projection of PK[X],forallx∈Sn. In order to reduce the difficulty and complexity of computing the projection PK, we define TX by
(60)TX=H(G(X)),
where
(61)G(X)=min(HU,max(X,HL)),H(X)=PS+n(X),
which can be computed without difficulty and the fixed point set of Fix(T)=K. According to Theorems 11 and 13, the sequences generated by Algorithm 8 under Conditions 10 and 12 are convergent.The computation begins with ones(n,n) in MATLAB and stops as soon as ∥xk+1-xk∥≤10-3or10-2. All codes were implemented in MATLAB 7.1 and ran at a Pentium R 1.70G processor, 2G Acer note computer.We test the problems withn=100, 200, 300, 400, 500, 1000, and 2000. The test results with the PRH method under different conditions are reported in Tables 1, 2, 3, and 4. And the CPU time is in seconds. It is to be noted that the results of extended contraction method are only given out when the iteration step (It) is less than or equal to 100.Table 1
Numerical results for the PRH method and the EC method.
Asymmetric matrix
c
0
=
0.1,  θn=0.8, tolerance = 10-4
Condition10
Condition12
EC method
n
It
cpu
It
cpu
It
cpu
tolerance
100
201
8.34
130
5.35
100
14.46
8.289
e
+
000
200
333
75.44
208
47.14
100
94.30
1.010
e
+
002
300
443
318.02
272
174.70
100
302.29
4.899
e
+
002
400
543
789.16
330
446.00
100
686.83
9.628
e
+
002
500
647
1747.70
388
972.18
100
1287.36
1.756
e
+
003
1000
1082
19884.30
634
11502.13
100
9220.50
9.826
e
+
003
2000
>2000
>150000
1052
128504.67
100
>74640.41
>5.597e + 003Table 2
Numerical results for tolerance10-4.
Asymmetric matrix
c
0
=
0.1,  θn=0.8
Condition10
Condition12
n
It
cpu
It
cpu
100
204
8.78
130
5.45
200
330
76.08
208
47.72
300
445
323.20
272
175.89
400
548
867.56
330
450.59
500
663
1916.90
388
994.18Table 3
Numerical results for tolerance10-3.
Asymmetric matrix
c
0
=
0.1,  θn=0.8
Condition10
Condition12
n
It
cpu
It
cpu
1000
193
3893.63
126
2280.74
2000
318
42981.02
200
28737.65Table 4
Numerical results for tolerance10-4.
Asymmetric matrix
γ
=
0.1, ρ=0.3, t=0.1
θ
n
=
0
θ
n
=
0.2
θ
n
=
0.4
θ
n
=
0.6
θ
n
=
0.8
n
It
cpu
It
cpu
It
cpu
It
cpu
It
cpu
100
132
5.52
134
5.60
128
5.50
134
5.67
132
5.54
200
210
48.04
206
47.22
208
48.04
204
47.15
214
48.58
300
274
177.49
268
176.08
276
178.80
274
177.68
276
178.84
400
336
468.28
328
445.93
336
468.20
334
454.24
330
453.79
500
392
977.79
394
1012.57
378
948.44
386
953.91
390
971.10Test Examples 1. In this example we generate the data in a similar manner as in [9]. The entries of diagonal elements of C are randomly generated in the interval (0,2); the entries of off-diagonal elements of C are randomly generated in the interval (-1,1) (Algorithm 1):
(62)(HU)jj=(HL)jj=1,(HU)ij=-(HL)ij=0.1,∀i≠j,i,j=1,2,…,n.
When n≥1000 and tolerance 10-4, the computation time of the proposed method is too long, so the results of the PRH method give out approximate solution with n≥1000 and tolerance 10-3 in the following. And the extended contraction method (EC method) has much difficulty in computing the examples when C is asymmetric. Furthermore, by introducing auxiliary variable, the certain projection method or relaxed-PPA method [10] can be implemented by these tests.Algorithm 1
Matlab code:
C = zeros(n,n); HU = ones(n,n)*0.1; HL = −HU;
fori=1:n
forj=1:n
t=mod(t*42108+13846,46273);
C(i,j)=t*2/46273-1;
end;
end;
fori=1:n
C(i,i) = abs(C(i,i))*2; HU(i,i)=1; HL(i,i)=1;
end;Test Examples 2. We form the data of the second problems similarly as in the first test examples. The entries of diagonal elements of C are randomly generated in the interval (0,2); the entries of off-diagonal elements of C are generated from a uniform distribution in the same interval (Algorithm 2):
(63)(HU)jj=(HL)jj=1,(HU)ij=-(HL)ij=0.1,∀i≠j,i,j=1,2,…,n.Algorithm 2
Matlab code:
C = zeros(n,n); HU = ones(n,n)*0.1; HL = −HU;
fori=1:n
forj=1:n
C=-1+2*rand(n);
end;
end;
fori=1:n
C(i,i) = abs(C(i,i))*2; HU(i,i)=1; HL(i,i)=1;
end;From Tables1 to 3, we found that the iteration numbers and CPU time of PRH under Condition 12 are more efficient than that under Condition 10. In Table 4 of our method, the tests’ results give out that the PRH method under some descent directions is more slightly efficient than those of the MRHSD method [14, 16], and it is easy to obtain these descent directions. Furthermore, it is important to find γ,ρ,andt by Tables 2 and 4.


## 5. Conclusions

We have proved the strong convergence of PRH method under Condition12, which differs from Condition 10. The result can be considered as an improvement and refinement of the previous results [14]. And more importantly, numerical experiments demonstrated that the PRH method under Condition 12 is more efficient than that under Condition 10, and the PRH method under some descent directions is more slightly efficient than that of the MRHSD method. How to select parameters of the PRH method for solving variational inequalities is worthy of further investigations in the future.



---

*Source: 515902-2013-10-23.xml*