# A Nonmonotone Projection Method for Constrained System of Nonlinear Equations

Authors: Yazheng Dang; Wenwen Liu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This paper deals with the nonmonotone projection algorithm for constrained nonlinear equations. For some starting points, the previous projection algorithms for the problem may encounter slow convergence which is related to the monotone behavior of the iterative sequence as well as the iterative direction. To circumvent this situation, we adopt the nonmonotone technique introduced by Dang to develop a nonmonotone projection algorithm. After constructing the nonmonotone projection algorithm, we show its convergence under some suitable condition. Preliminary numerical experiment is reported at the end of this paper, from which we can see that the algorithm we propose converges more quickly than that of the usual projection algorithm for some starting points.


---

## Body

## 1. Introduction

Recall thatG:Rn→Rn is a nonlinear mapping with continuity and C is a nonempty closed set in Rn with convexity; then the constrained nonlinear equations are defined as seeking a point x∗∈C so that the following equation is established:(1)Gx∗=0.Many iteration methods and algorithms for solving such problem have been proposed in [1–11]. For instance, there are some variants of the Levenberg-Marquardt type methods [1–3] which have strong convergence property. In addition, Wang et al. presented a projection algorithm [5] for solving problem (1) in 2007 and a superlinearly convergent projection method [12] in 2009. From the numerical performances given in [12], we can see that the algorithm in [12] is more efficient than the method in [5] for solving such problem. Recently, a hybrid conjugate gradient projection algorithm has been established which is on the basis of the Dai-Yuan and Hestenes-Stiefel conjugate gradient method, seen in [11].However, the projection algorithms may encounter “tunneling effect” [13] which will result in slow convergence. That is to say, during the iteration, the projection onto two or more convex sets may encounter a narrow channel, and the projection iterative sequences will become very slow. Applying the nonmonotone technique to the projection algorithm is an effective way to avoid this effect, which is based on the idea of taking a big step to interrupt the monotone behavior. The “tunneling effect” is associated with the monotone iterative sequence. Inspired by the work of Dang and Gao [14] for convex feasibility problem, we propose a nonmonotone projection algorithm, which has already been confirmed to converge faster than average in the “tunneling.” From the numerical experiment, it can be verified that, comparing with the projection method in [12], this method is more effective.The remaining part of this article is distributed as follows. In the next section, some fundamental properties will been given which is useful in the following demonstration. In Section3, the nonmonotonic projection method will be shown and the algorithm convergence is proved theoretically. At the end of this article, an example will be given which elucidates the algorithm we propose, which converges more quickly than the existing algorithms. Based on the above understanding, we come to the conclusion.


## 2. Preliminaries

LetG:Rn→Rn be a nonlinear continuous mapping; then G is said to be monotone if, for ∀x,y∈Rn, it holds that (2)Gx-Gy,y-x≤0.In addition, S≔{x∈Rn∣G(x)=0} is convex if G is monotone.LetC be a convex set where C∈Rn and C∉∅. Define PC[∗]: Rn→C as a projection; it can be expressed as (3)PCx=argmin⁡y-xwherey∈C,x∈Rn.It is well known that the projectionPC has some fundamental properties. It holds that (4)PCx-PCy≤x-y,(5)PCx-PCy2≤x-y2-PCx-x+y-PCy2.According to (4) we know that PC[∗] is nonexpansive. In this paper, we mainly use formula (5).


## 3. The Algorithm and Its Convergence Analysis

The basic idea of our algorithm is as follows. Taking a well-determined big step at each of the a priori fixed moments, we try to interrupt the monotone behavior of the iteration sequence by introducing an appropriate parameter at suitable steps so as to ensure that both of the nonmonotone sequence and the iteration within the interval are monotonically decreasing. In this way, the whole sequence may converge to a point in the solution set.Algorithm 1 (the nonmonotone projection algorithm).
Step 0. Choose M>2 and N>M which are positive integer numbers. Take φ∈(0,1). B is an arithmetic number which is as large as possible.
Step 1. Pick an initial point x0∈C; set the parameters such that γ1>0, γ2>0, 0≤κ0<1, 0<α<1, and 0<β<1.
Step 2. If G(xk)=0, stop. Or else let σk=min⁡κ0,γ2Gxk1/2; solve the linear equation below: (6)γ1Gxk1/2Ix-xk+Gxk=0.Find the solution x¯k∈Rn to (6) so that rk can satisfy (7)rk≤σkγ1xk-x¯k·Gxk1/2.Step 3. Get yk by yk=xk-βmk(xk-x¯k) such that(8)Gyk,xk-x¯k≥αγ11-σkGxk1/2xk-x¯k2,where mk is the smallest nonnegative integer that satisfies (8).Step 4. Set Hk={〈G(yk),x-yk〉=0∣x∈Rn}.(1) Whenk∉{N+pM}p=0+∞ (p is nonnegative integer), put (9)αk1=Gyk,xk-ykGyk2.Construct xk+1 by (10)xk+1=PC∩HKxk-αk1Gyk.(2) Whenk∈{N+pM}p=0+∞, determine αk1 as in (1). Put (11)ωk+1=PC∩HKxk-αk1Gyk.Construct xk+1 by (12)xk+1=χk+1Gyk+ωk+1,where (13)χk+1=min⁡B,φMk+1Gyk2,(14)Mk+1=Gyk+1-M,xk+1-M-yk+1-M2Gyk+1-M2+⋯+Gyk,xk-yk2Gyk2.Then replace k by k+1 and turn to Step 2.Compared with the existing algorithms, we attempt to interrupt the monotone behavior of the iterative sequence{xk}k=0∞ by taking a big step at different moments and introducing χk+1 at every appropriate step. Therefore, for some starting points, the nonmonotone technique may avoid the tunneling effect and improve the algorithms convergence.Next, we analyse the convergence of our algorithm. To this end, we need the assumptions below:(A1)
F is a monotone mapping.(A2)
S={x∈Rn∣G(x)=0} is nonempty and convex.(A3)
Algorithm1 always generates an infinite sequence.Lemma 2 (see [15, Lemma 3.2]).
Suppose that the underlying mappingF is monotone. Then (15)PCxk-αk2Fyk=PC∩HKxk-αk1Fyk.Lemma 3 (see [12, Theorem 3.1]).
Whenk∉{N+pM}p=0+∞, take αk1 in (9) and use iteration (10). Then(16)xk+1-x∗2≤xk-x∗2-Gyk,xk-yk2Gyk2.From the inequality above we have the conclusion thatxk-x∗ is monotonically decreasing and converges. Namely, {xk} is bounded.Theorem 4.
Supposex∗∈C, when k∉{N+pM}p=0+∞, where M>2 and N>M, under Assumptions (A1) and (A2), for the sequence produced by Algorithm 1; then (17)limk+1→∞,k+1∉N+1+pMp=0+∞⁡xk-xk+1=limk+1→∞,k+1∈N+1+pMp=0+∞⁡xk-wk+1=0.Proof.
First, we claim that{yk}k=0+∞ is bounded.
From the demonstration in [12], we have (18)Gxk,xk-yk≥αγ11-σkGxk1/2xk-yk2.Substituting it into the Cauchy-Schwartz inequality with σk, we obtain (19)Gxk1/2≥α1-κ0γ1xk-yk.Due to the boundedness of {xk} and the continuity of G, {yk} is bounded.
Second, we show thatlimk→∞,k∉{N+pM}p=0+∞⁡xk-yk=0.
For one thing, whenk→∞,k∉{N+pM}p=0+∞, according to (16), we can see that xk+1-x∗ and xk-x∗ are limited to the same number. So we can draw a conclusion that (20)limk→∞,k∉N+pMp=0+∞⁡Gxk,xk-yk=0.For another,(21)Gyk,xk-yk≥βmkαγ11-σkGxk1/2xk-x¯k2,and by the substitution of α and σk, we get (22)limk→∞,k∉N+pMp=0+∞⁡xk-x¯k=0,and, combined with the equality of yk, it leads to (23)limk→∞,k∉N+pMp=0+∞xk-yk=0.
Finally, we show thatxk∈C, and (24)xk-xk+1=xk-PC∩HKxk-αk1Gyk≤αk1Gyk=xk-yk. In association with Step 2, we obtain the desired conclusion.Theorem 5.
Supposex∗∈C, when k∈{N+pM}p=0+∞, where M>2 and N>M, for the sequence produced by Algorithm 1; then (25)limk+1→∞,k+1∈N+1+pMp=0+∞⁡xk-xk+1=0.Proof.
First, according to (12), the following equality exists, for any x∗∈C: (26)xk+1-x∗2=PC∩HKxk-αk2Gyk+χk+1Gyk-x∗2.Combining this with (4), we obtain (27)xk+1-x∗2≤xk-x∗-αk2Gyk+χk+1Gyk2-xk+1-xk+αk2Gyk-χk+1Gyk2≤xk-x∗2-2αk1Gyk-χk+1Gyk,xk-x∗+αk1Gyk-χk+1Gyk2=xk-x∗2-Gyk,xk-yk2Gyk2+χk+12Gyk2≤xk-1-x∗2-Gyk-1,xk-1-yk-12Gyk-12-Gyk,xk-yk2Gyk2+χk+12Gyk2⋮≤xk+1-M-x∗2-1-φMk+1.So(28)xk+1-x∗2≤xk+1-M-x∗2.
Second, whenxk+1 was chosen as in (12), hence (29)xk+1-xk=ωk+1-xk+ηMk+12≤xk-ωk+1+ηMk+12.From (28), xk+1-M-x∗ is not incremental; thus xk+1-M-x∗ and xk+1-x∗ tend to the same number. It leads to (30)limk+1→∞,k+1∈N+1+pMp=0+∞⁡Mk+1=0.Thus, limk+1→∞,k+1∈{N+1+pM}p=0+∞⁡ηMk+12 exists and is equal to zero. Combined with Theorem 4, the conclusion above is proved.Remark 6.
We know that the value ofMk+1 generated by algorithm in [12] may be very small if the algorithm encounters “tunneling effect” during the process of iteration from the (k+1-M)th step to the (k+1)th step. In order to make the current iterate point xk as close as possible to the optimum point, Mk+1 needs to be more maximized. In Algorithm 1, we use the nonmonotone technique so that Mk+1 may be very large which is the superior place of the Algorithm 1.Theorem 7.
Under Assumptions(A1)–(A3), combined with Theorems 4 and 5, we have the conclusion that {xk}k=0+∞ constructed by our method globally converges to S.Proof.
In our algorithm,{xk}k=0+∞ contains the subsequence {xN+pM}p=0+∞ which was generated by the nonmonotone technique. For brevity, we denote {xN+pM}p=0+∞ as {xkj}j=0+∞.Next, we accomplish the demonstration in the following three steps.Firstly, there is a subsequence in{xkj}j=0+∞ converging to a point x∗. For one thing, from Theorem 5, {xkj}j=0+∞ is convergent; thus there is a subsequence converging to a point x∗∈Rn. For another, we denote the last subsequence as {xkz}. It also converges to x∗. The following iterative yields(31)xkz+1=PC∩HKxkz-αk1Gykz.From (11), we have (32)xkz+1-x∗2≤xkz-x∗2-Gykz,xkz-ykz2Gykz2.By {xkz} converging to x∗, {xkz+1} also converges to x∗.Secondly, each convergent sequence in{xkj}j=0+∞ converges to the same point x∗. From Theorem 5, we know that xk+1-x∗2≤xk+1-1-x∗2≤⋯≤xk+1-M-x∗2=xkz-x∗2; from the above, xkz-x∗→0 when k→∞. Hence, we get the above proposition.Last but not least,{xk}k=0+∞ converges to x∗. From the above analysis, we see that the sequence {xN+pM}p=0+∞ converges to x∗. Let i be an arbitrary index. Then there are successive indices kj and kt of {xN+pM}p=0+∞, where kj=N+1+(p-1)M and kt=N+1+pM. When kj<i<kt, xi-x∗≤xi-1-x∗≤⋯≤xkj+1-x∗≤xkj-x∗, and xkj-x∗→0 when kj→∞. Thus xi→x∗ when ki→∞. When i=kt, the results were significant.


## 4. Numerical Examples

Here we utilize our algorithm to solve a constrained system of nonlinear equations. To test the algorithm, we compare the results with the ones of the projection algorithm in [12]. For convenience, we denote our algorithm as NMPA and the projection algorithm in [12] as PA. We take the example in [12]. Set the parameters used in this example as κ(i.e.,κ0≈0), α=0.95, β=0.6, and γ1=γ2=1. We put M=6,N=12, and φ=0.9. The stop criterion is F(xk)≤10-6.Example 1.
Let the domain setC be taken as C=C1∩C2, where C1={x∈R120∣∑i=1120‍xi≤10} and C2={x∈R120∣∑i=1120‍xi2≤10}. Let the nonlinear equations G(x) be taken as G(x)=ρD(x)+M(x)x+q+q0, among which ρ is a constant; Di(x)=arctan⁡(xi-2), where i is an integer from 1 to 120;M is a 120∗120 asymmetrical positive definite matrix; q is the vector and q0 is a constant vector. In addition, elements of M are produced in (-5,5) randomly and q is produced by an interval range from -10 to 10.
There are two cases below to consider:Case 1:x0=(-0.01,-0.01,…,-0.01)∈R120Case 2:x0=(0.03,0.03,…,0.03)∈R120
Table1 gives the numbers of iterations that are required, in order to get the approximate solutions for the above two cases with ρ=100 and ρ=200 of Example 1 by Alg-PA and Alg-NMPA, respectively.Table 1
Results of Alg-PA and Alg-NMPA for Example1.
ρ Case Alg-PA Alg-NMPA ρ = 10 0 Case 1 260 43 Case 2 424 65  ρ = 20 0 Case 1 890 101 Case 2 1497 156From Table1, by choosing the proper initial point, we show that the sequences are generated by the nonmonotone convergent projection algorithm. Comparing with the PA, the most prominent advantage is that our algorithm can avoid the “tunnel effect.”


## 5. Conclusion

This paper presented a nonmonotone projection method for constrained nonlinear equations. With the introduction of monotone technology, the monotone behavior of the iterative sequence has been disorganized. Based on some assumption, algorithm global convergence is guaranteed. In comparison with the extant projection methods, the most prominent characteristics in this paper are that, for some starting points, the nonmonotone projection algorithm can circumvent the “tunneling effect,” which leads to slow convergence.



---

*Source: 8270649-2017-01-18.xml*