# A Nonmonotone Line Search Filter Algorithm for the System of Nonlinear Equations

Authors: Zhong Jin; Yuqing Wang
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

We present a new iterative method based on the line search filter method with the nonmonotone strategy to solve the system of nonlinear equations. The equations are divided into two groups; some equations are treated as constraints and the others act as the objective function, and the two groups are just updated at the iterations where it is needed indeed. We employ the nonmonotone idea to the sufficient reduction conditions and filter technique which leads to a flexibility and acceptance behavior comparable to monotone methods. The new algorithm is shown to be globally convergent and numerical experiments demonstrate its effectiveness.


---

## Body

## 1. Introduction

We consider the following system of nonlinear equations:(1.1)ci(x)=0,i=1,2,…,m,
where each ci:Rn→R(i=1,2,…,m) is a twice continuously differentiable function. It is one of the most basic problems in mathematics and has lots of applications in many scientific fields such as physics, chemistry, and economics.In the context of solving nonlinear equations, a well-known method is the Newton method, which is known to exhibit local and second order convergence near a regular solution, but its global behavior is unpredictable. To improve the global properties, some important algorithms [1] for nonlinear equations proceed by minimizing a least square problem:
(1.2)minh(x)=c(x)Tc(x),
which can be also handled by the Newton method, while Powell [2] gives a counterexample to show a dissatisfactory fact that the iterates generated by the above least square problem may converge to a nonstationary point of h(x).However, as we all know, there are several difficulties in utilizing the penalty functions as a merit function to test the acceptability of the iterates. Hence, the filter, a new concept first introduced by Fletcher and Leyffer [3] for constrained nonlinear optimization problems in a sequential quadratic programming (SQP) trust-region algorithm, replaces the merit fuctions avoiding the penalty parameter estimation and the difficulties related to the nondifferentiability. Furthermore, Fletcher et al. [4, 5] give the global convergence of the trust-region filter-SQP method, then Ulbrich [6] gets its superlinear local convergence. Consequently, filter method has been actually applied in many optimization techniques, for instance the pattern search method [7], the SLP method [8], the interior method [9], the bundle approaches [10, 11], and so on. Also combined with the trust-region search technique, Gould et al. extended the filter method to the system of nonlinear equations and nonlinear least squares in [12], and to the unconstrained optimization problem with multidimensional filter technique in [13]. In addition, Wächter and Biegler [14, 15] presented line search filter methods for nonlinear equality-constrained programming and the global and local convergence were given.In fact, filter method exhibits a certain degree of nonmonotonicity. The idea of nonmonotone technique can be traced back to Grippo et al. [16] in 1986, combined with the line search strategy. Due to its excellent numerical exhibition, many nonmonotone techniques have been developed in recent years, for example [17, 18]. Especially in [17], a nonmonotone line search multidimensional filter-SQP method for general nonlinear programming is presented based on the Wächter and Biegler methods [14, 15].Recently, some other ways were given to attack the problem (1.1) (see [19–23]). There are two common features in these papers; one is the filter approach is utilized, and the other is that the system of nonlinear equations is transformed into a constrained nonlinear programming problem and the equations are divided into two groups; some equations are treated as constraints and the others act as the objective function. And two groups of equations are updated at every iteration in those methods. For instance combined with the filter line search technique [14, 15], the system of nonlinear equations in [23] becomes the following optimization problem with equality constraints:
(1.3)min∑i∈S1ci2(x)s.t.cj(x)=0,j∈S2.
The choice of two sets S1 and S2 are given as follows: for some positive constant n0>0, it is defined that ci12(xk)≥ci22(xk)≥⋯≥cim2(xk), then S1={ik∣k≤n0} and S2={ik∣k≥n0+1}.In this paper we present an algorithm to solve the system of nonlinear equations, combining the nonmonotone technique and line search filter method. We also divide the equations into two groups; one contains the equations that are treated as equality constraints and the square of other equations is regarded as objective function. But different from those methods in [19–23], we just update the two groups at the iterations where it is needed indeed, which can make the scale of the calculation decrease in a certain degree. Another merit of our paper is to employ the nonmonotone idea to the sufficient reduction conditions and filter which leads to a flexibility and acceptance behavior comparable to monotone methods. Moreover, in our algorithm two groups of equations cannot be changed after an f-type iteration, thus in the case that |𝒜|<∞, the two groups are fixed after finite number of iterations. And the filter should not be updated after an f-type iteration, so naturally the global convergence is discussed, respectively, according to whether the number of updated filter is infinite or not. Furthermore, the global convergent property is induced under some reasonable conditions. In the end, numerical experiments show that the method in this paper is effective.The paper is outlined as follows. In Section2, we describe and analyze the nonmonotone line search filter method. In Section 3 we prove the global convergence of the proposed algorithm. Finally, some numerical tests are given in Section 4.


## 2. A Nonmonotone Line Search Filter Algorithm

Throughout this paper, we use the notationsmk(x)=∥cS1(x)∥22=∑i∈S1ci2(x) and θk(x)=∥cS2(x)∥22=∑i∈S2ci2(x). In addition, we denote the set of indices of those iterations in which the filter has been augmented by 𝒜⊆ℕ.The linearization of the KKT condition of (1.3) at the kth iteration xk is as follows:
(2.1)(BkAS2k(AS2k)T0)(skλk+)=-(gkcS2k),
where Bk is the Hessian or approximate Hessian matrix of L(x,λ)=mk(x)+λTcS2(x), AS2k=∇cS2(xk) and g(xk)=∇mk(xk). Then the iterate formation is xk(αk,l)=xk+αk,lsk, where sk is the solution of (2.1) and αk,l∈(0,1] is a step size chosen by line search.Now we describe the nonmonotone Armijo rule. LetM be a nonnegative integer. For each k, let m(k) satisfy m(0)=1,0≤m(k)≤min{m(k-1)+1,M} for k≥1. For fixed constants γm,γθ∈(0,1), we might consider a trial point to be acceptable, if it leads to sufficient progress toward either goal, that is, if
(2.2)θk(xk(αk,l))≤(1-γθ)max{θk(xk),∑r=0m(k)-1λkrθk-r(xk-r)}ormk(xk(αk,l))≤max{mk(xk),∑r=0m(k)-1λkrmk-r(xk-r)}-γmθk(xk),
where λkr∈(0,1), ∑r=0m(k)-1λkr=1.For the convenience we setm¯(xk)=max{mk(xk),∑r=0m(k)-1λkrmk-r(xk-r)}, and θ¯(xk)=max{θk(xk),∑r=0m(k)-1λkrθk-r(xk-r)}. In order to avoid the case of convergence to a feasible but nonoptimal point, we consider the following switching condition:
(2.3)gkTsk<-ξskTBksk,-αk,lgkTsk>[θk(xk)]sθ,
with ξ∈(0,1],sθ∈(0,1). If the switching condition holds, the trial point xk(αk,l) has to satisfy the Armijo nonmonotone reduction condition,
(2.4)mk(xk(αk,l))≤m¯(xk)+τ3αk,lgkTsk,
where τ3∈(0,1/2) is a fixed constant.To ensure the algorithm cannot cycle, it maintains a filter, a “taboo region”ℱk⊆[0,∞]×[0,∞] for each iteration k. The filter contains those combinations of constraint violation value θ and the objective function value m, that are prohibited for a successful trial point in iteration k. During the line search, a trial point xk(αk,l) is rejected, if (θ¯(xk(αk,l)),m¯(xk(αk,l)))∈ℱk. We then say that the trial point is not acceptable to the current filter, which is also called xk(αk,l)∈ℱk.If a trial pointxk(αk,l)∉ℱk satisfies the switching condition (2.3) and the reduction condition (2.4), then this trial point is called an f-type point, and accordingly this iteration is called an f-type iteration. An f-type point should be accepted as xk+1 with no updating of the filter, that is
(2.5)ℱk+1=ℱk.While if a trial pointxk(αk,l)∉ℱk does not satisfy the switching condition (2.3), but this trial point satisfies (2.2), we call it an h-type point, or accordingly an h-type iteration. An h-type point should be accepted as xk+1 with updating of the filter, that is
(2.6)ℱk+1=ℱk⋃{(θ,m)∈R2:θ≥(1-γθ)θ¯(xk),m≥m¯(xk)-γmθk(xk)}.In some cases it is not possible to find a trial step size that satisfies the above criteria. We approximate a minimum desired step size using linear models of the involved functions. For this, we define(2.7)αkmin={min{1-(1-γθ)θ¯(xk)θk(xk),m¯(xk)-mk(xk)-γmθk(xk)gkTsk,[θk(xk)]sθ-gkTsk},ifgkTsk<-ξskTBksk,1-(1-γθ)θ¯(xk)θk(xk),otherwise.
If the nonmonotone line search encounters a trial step size with αk,l<αkmin, the algorithm reverts to a feasibility restoration phase. Here, we try to find a new iterate which is acceptable to the current filter and for which (2.2) holds, by reducing the constraint violation with some iterative method.The corresponding algorithm can be written as follows.Algorithm 2.1.
Step1. Initialization: choose an initial guess x0, ρ1,ρ2∈(0,1), ρ1<ρ2, and ϵ>0. Compute g0, ci(x0), S10, S20, and Ak for i∈S20. Set M>0, m(0)=1, k=0, and ℱ0=∅.
Step2. If ∥c(xk)∥≤ϵ then stop.
Step3. Compute (2.1) to obtain sk. If there exists no solution to (2.1), go to Step 8. If ∥sk∥≤ϵ then stop.
Step4. Use nonmonotone line search. Set l=0 and αk,l=1. Step4.1. If αk,l<αkmin, where the αkmin is obtained by (2.7), go to Step 8. Otherwise we get xk(αk,l)=xk+αk,lsk. If xk(αk,l)∈ℱk, go to Step 4.3.Step4.2. Check sufficient decrease with respect to current iterate.
Step4.2.1. If the switching condition (2.3) and the nonmonotone reduction condition (2.4) hold, set ℱk+1=ℱk and go to Step 5. While only the switching condition (2.3) are satisfied, go to Step 4.3.Step4.2.2. The switching conditions (2.3) are not satisfied. If the nonmonotone filter condition (2.2) holds, set xk+1=xk+αk,lsk, augment the filter using (2.6) and go to Step 6. Otherwise, go to Step 4.3.Step4.3. Choose αk,l+1∈[ρ1αk,l,ρ2αk,l]. Let l=l+1 and go to Step 4.1.
Step5. Set xk+1=xk+αk,lsk, S1k+1=S1k and S2k+1=S2k. Go to Step 7.
Step6. Compute S1k+1 and S2k+1 by (1.3). If (θ¯k+1(xk+1),m¯k+1(xk+1))∈ℱk+1, set S1k+1=S1k and S2k+1=S2k.
Step7. Compute gk+1, Bk+1, Ak+1 and m(k+1)=min{m(k)+1,M}. Let k=k+1 and go to Step 2.
Step8 (restoration stage). Find xkr=xk+αkrskr such that xkr is acceptable to xk and (θk(xkr),mk(xkr))∉ℱk. Set xk+1=xkr and augment the filter by (2.6). Let k=k+1, m(k)=1 and go to Step 2.In a restoration algorithm, the infeasibility is reduced and it is, therefore, desired to decrease the value ofθk(x). The direct way is to utilize the Newton method or the similar ways to attack θk(x+s)=0. We now give the restoration algorithm.Restoration Algorithm
Step R1. Let xk0=xk, H0=En, Δk0=Δ0, gθ=∇θk(x), j=0, η1=0.25, η2=0.75.
Step R2. If xkj is acceptable to xk and (θk(xkr),mk(xkr))∉ℱk, then let xkr=xkj and stop.
Step R3. Compute
(2.8)mingθTs+12sTHjss.t.∥s∥≤Δkj
to getskj. Let rkj=(θk(xkj)-θk(xkj+skj))/(-gθTskj-(1/2)skjTHjskj).
Step R4. If rkj≤η1, set Δkj+1=(1/2)Δkj; If rkj≥η2, set Δkj+1=2Δkj; otherwise, Δkj+1=Δkj. Let xkj+1=xkj+skj, Hj be updated to Hj+1, j=j+1 and go to Step R2.The above restoration algorithm is an SQP method forθk(x+s)=0. Of course, there are other restoration algorithms, such as the Newton method, interior point restoration algorithm, SLP restoration algorithm, and so on.


## 3. Global Convergence of Algorithm

In this section, we present a proof of global convergence of Algorithm2.1. We first state the following assumptions in technical terms.Assumptions.
(A1) All pointsxk that are sampled by algorithm lie in a nonempty closed and bounded set X.
(A2) The functionsci(x), j=1,2,…,m are all twice continuously differentiable on an open set containing X.
(A3) There exist two constantsb≥a>0 such that the matrices sequence {Bk} satisfies a∥s∥2≤sTBks≤b∥s∥2 for all k and s∈Rn.
(A4)(As2k)T has full column rank and ∥sk∥≤γs for all k with a positive constant γs.In the remainder of this section, we will not consider the case where Algorithm2.1 terminates successfully in Step 2, since in this situation the global convergence is trivial.Lemma 3.2.
Under Assumption A1, there exists the solution to (2.1) with exact (or inexact) line search which satisfies the following descent conditions:
(3.1)|θk(xk+αsk)-(1-2α)θk(xk)|≤τ1α2∥sk∥2,(3.2)|mk(xk+αsk)-mk(xk)-αgkTsk|≤τ2α2∥sk∥2,
where α∈(0,1), τ1 and τ2 are all positive constants independent of k.Proof.
By virtue of the Taylor expansion ofci2(xk+αsk) with i∈S2, we obtain
(3.3)|ci2(xk+αsk)-ci2(xk)-2αci(xk)∇ci(xk)Tsk|=|ci2(xk+αsk)-ci2(xk)-2ci(xk)∇ci(xk)T(αsk)|=|12(αsk)T[2ci(xk+ζαsk)∇ci2(xk+ζαsk)+2∇ci(xk+ζαsk)∇ci(xk+ζαsk)T](αsk)|=|α2skT[ci(xk+ζαsk)∇ci2(xk+ζαsk)+∇ci(xk+ζαsk)∇ci(xk+ζαsk)T]sk|≤1mτ1α2∥sk∥2,
where the last inequality can be done by Assumption A1 and ζ∈[0,1]. Furthermore, from (2.1) we immediately obtain ci(xk)+∇ci(xk)Tsk=0, that is, -2αci2(xk)-2αci(xk)∇ci(xk)Tsk=0. With |S2|≤m, thereby,
(3.4)|θk(xk+αsk)-(1-2α)θk(xk)|=|∑i∈S2(ci2(xk+αsk)-(1-2α)ci2(xk))|≤∑i∈S2|ci2(xk+αsk)-(1-2α)ci2(xk)|=∑i∈S2|ci2(xk+αsk)-ci2(xk)-2αci(xk)∇ci(xk)Tsk|≤m·1mτ1α2∥sk∥2≤τ1α2∥sk∥2,
then the first inequality consequently holds.
According to the Taylor expansion of∑i∈S1(ci2(xk+αsk)) (i.e., mk(xk+αsk)), we then have
(3.5)|∑i∈S1(ci2(xk+αsk))-∑i∈S1(ci2(xk))-αgkTsk|=|12α2(sk)T∇2∑i∈S1(ci2(xk+ϱαsk))sk|≤τ2α2∥sk∥2,
where the last inequality follows from Assumption A1 and ϱ∈[0,1]. That is to say,
(3.6)|mk(xk+αsk)-mk(xk)-αgkTsk|≤τ2α2∥sk∥2,
which is just (3.2).Lemma 3.3.
Let{xki} be a subsequence of iterates for which (2.3) holds and has the same S1 and S2. Then there exists some α^∈(0,1] such that
(3.7)mki(xki+α^ski)≤mki(xki)+α^τ3gkiTski.Proof.
Because{xki} have the same S1 and S2, it follows that mki(x) are fixed and by (2.3) dki is a decent direction. Hence there exists some α^∈(0,1] satisfying (3.7).Theorem 3.4.
Suppose that{xk} is an infinite sequence generated by Algorithm 2.1 and |𝒜|<∞, one has
(3.8)limk→∞∥cS2kk∥+∥sk∥=0,
namely, every limit point is the ϵ solution to (1.1) or a local infeasible point. If the gradients of ci(xk) are linear independent for all k and i=1,2,…,m, then the solution to SNE is obtained.Proof.
From|𝒜|<∞, we know the filter updates in a finite number, then there exists K∈ℕ, for k>K the filter does not update. As h-type iteration and restoration algorithm all need the updating of the filter, so for k>K our algorithm only follows the f-type iterations. We then have that for all k>K both conditions (2.3) and (2.4) are satisfied for xk+1=xk+αksk and mk(x)=mK(x).
Then by (2.4) we get mk(xk+1)≤max{mk(xk),∑r=0m(k)-1λkrmk-r(xk-r)}+τ3αkgkTsk. We first show that for all k≥K+1, it holds
(3.9)mk(xk)<m¯(xK)+λτ3∑r=Kk-2αrgrTsr+τ3αk-1gk-1Tsk-1<m¯(xK)+λτ3∑r=Kk-1αrgrTsr,
where m¯(xK)=max{mK(xK),∑r=0m(k)-1λKrmK-r(xK-r)}. We prove (3.9) by induction.
Ifk=K+1, we have mK+1(xK+1)<m¯(xK)+τ3αkgkTsk<m¯(xK)+λτ3αkgkTsk. Suppose that the claim is true for K+1,K+2,…,k, then we consider two cases.
Case1. If max{mk(xk),∑r=0m(k)-1λkrmk-r(xk-r)}=mk(xk), it is clear that
(3.10)mk+1(xk+1)<mk(xk)+τ3αkgkTsk<m¯(xK)+λτ3∑r=Kk-1αrgrTsr+τ3αkgkTsk≤m¯(xK)+λτ3∑r=KkαrgrTsr.
Case2. If max{mk(xk),∑r=0m(k)-1λkrmk-r(xk-r)}=∑r=0m(k)-1λkrmk-r(xk-r), let u=m(k)-1. By the fact that  ∑t=0uλkt=1, λ≤λkt<1, we have
(3.11)mk+1(xk+1)<∑t=0uλktmk-t(xk-t)+τ3αkgkTsk<∑t=0uλkt(m¯(xK)+λτ3∑r=Kk-t-2αrgrTsr+τ3αk-t-1gk-t-1Tsk-t-1)+τ3αkgkTsk=λk0(m¯(xK)+λτ3∑r=Kk-u-2αrgrTsr+λτ3∑r=k-u-1k-2αrgrTsr+τ3αk-1gk-1Tsk-1)+λk1(m¯(xK)+λτ3∑r=Kk-u-2αrgrTsr+λτ3∑r=k-u-1k-3αrgrTsr+τ3αk-2gk-2Tsk-2)+⋯+λku(m¯(xK)+λτ3∑r=Kk-u-2αrgrTsr+τ3αk-u-1gk-u-1Tsk-u-1)+τ3αkgkTsk<m¯(xK)+λτ3∑r=Kk-u-2αrgrTsr+λτ3∑r=k-u-1k-1αrgrTsr+τ3αkgkTsk=m¯(xK)+λτ3∑r=Kk-1αrgrTsr+τ3αkgkTsk<m¯(xK)+λτ3∑r=KkαrgrTsr.
Moreover, since mk(xk) is bounded below as k→∞, we get ∑r=KkαrgrTsr<∞, that is, limk→∞αrgrTsr=0. By Lemma 3.3, there exists a α^∈(0,1] such that αk≥α^. Then together with gkTsk<-ξskTBksk and Assumption A1, we have limk→∞∥sk∥=0. From -αk,lgkTsk>[θk(xk)]sθ it is easy to obtain that limk→∞θk(xk)=0. This completes the proof.Lemma 3.5.
Under Assumptions A1 and A2, ifgkTsk≤-ɛ0 for a positive constant ɛ0 independent of k(∈asubsequence) and for all α∈(0,1] and α≥αk,lmin with (θk(xk),mk(xk))∉ℱk, then there exists γ1, γ2>0 so that (θk(xk+αsk),mk(xk+αsk))∉ℱk for all k(∈asubsequence) and α≤min{γ1,γ2θk(xk)}.Proof.
Chooseγ1=ɛ0/τ2γs2, then α≤γ1 implies that -αɛ0+τ2α2γs2≤0. So we note from (3.2) that
(3.12)mk(xk+αsk)≤mk(xk)+αgkTsk+τ2α2∥sk∥2≤mk(xk)-αɛ0+τ2α2γs2≤mk(xk).
Letγ2=2/τ1γs2, then α≤γ2θk(xk) implies that -2αθk(xk)+τ1α2γs2≤0. So from (3.1), we obtain
(3.13)θk(xk+αsk)≤θk(xk)-2αθk(xk)+τ2α2∥sk∥2≤θk(xk)-2αθk(xk)+τ1α2γs2≤θk(xk).
We further point a fact according to the definition of filter. If(θ¯,m¯)∉ℱk and θ≤θ¯, m≤m¯, we obtain (θ,m)∉ℱk. Thus from (θk(xk),mk(xk))∉ℱk, mk(xk+αsk)≤mk(xk), and θk(xk+αsk)≤θk(xk), we have (θk(xk+αsk),mk(xk+αsk))∉ℱk.Lemma 3.6.
IfgkTsk≤-ɛ0 for a positive constant ɛ0 independent of k(∈asubsequence), then there exists a constant α¯>0, for all k(∈asubsequence) and α≤α¯ such that
(3.14)mk(xk+αsk)-max{mk(xk),∑r=0m(k)-1λkrmk-r(xk-r)}≤τ3αgkTsk.Proof.
Letα¯=(1-τ3)ɛ0/τ2γs2. In view of (3.2), ∥sk∥≤γs and α≤α¯, we know
(3.15)mk(xk+αsk)-max{mk(xk),∑r=0m(k)-1λkrmk-r(xk-r)}-αgkTsk≤mk(xk+αsk)-mk(xk)-αgkTsk≤τ2α2∥sk∥2≤τ2αα¯γs2=(1-τ3)αɛ0≤-(1-τ3)αgkTsk,
which shows that the assertion of the lemma follows.Theorem 3.7.
Suppose that{xk} is an infinite sequence generated by Algorithm 2.1 and |𝒜|=∞. Then there exists at least one accumulation which is the ϵ solution to (1.1) or a local infeasible point. Namely, one has
(3.16)limk→∞inf[∥cS2kk∥+∥sk∥]=0.
If the gradients of ci(xk) are linear independent for all k and i=1,2,…,m, then the solution to (1.1) is obtained.Proof.
We prove thatlimk→∞,k∈𝒜θk(xk)=0 first.
Suppose by contradiction that there exits an infinite subsequence{ki} of 𝒜 such that θki(xki)≥ɛ for some ɛ>0. At each iteration ki, (θki(xki),mki(xki)) is added to the filter which means that no other (θ,m) can be added to the filter at a later stage within the area:
(3.17)[θ¯(xki)-γθɛ,θ¯(xki)]×[m¯(xki)-γmɛ,m¯(xki)],
and the area of the each of these squares is at least γθγmɛ2.
By Assumption A1 we have∑i=1nci2(xk)≤Mmax. Since 0≤mk(xk)≤mk(xk)+θk(xk)=∑i=1nci2(xk) and 0≤θk(xk)≤mk(xk)+θk(xk)=∑i=1nci2(xk), then (θ,m) associated with the filter are restricted to
(3.18)ℬ=[0,Mmax]×[0,Mmax].
Therebyℬ is completely covered by at most a finite number of such areas in contraction to the infinite subsequence {ki} satisfying θki(xki)≥ɛ. Therefore, limk→∞,k∈𝒜θk(xk)=0.
By Assumption A1 and|𝒜|=∞, there exits an accumulation point x¯, that is, limi→∞xki=x¯, ki∈𝒜. It follows from limk→∞,k∈𝒜θk(xk)=0, that
(3.19)limi→∞θki(xki)=0,
which implies limi→∞∥cS2kiki∥=0. If limi→∞∥ski∥=0, then (3.16) is true. Otherwise, there exists a subsequence {xkij} of {xki} and a constant ɛ1>0 so that for all kij,
(3.20)∥skij∥≥ɛ1.
The choice of {xkij} implies
(3.21)kij∈𝒜forallkij.
According to ∥skij∥≥ɛ1, Assumption A1 as well as ξ∈(0,1), we have
(3.22)gkijTskij+ξskijTBkijskij=(ξ-1)skijTBkijskij-(λkij+)TcS2kijkij≤(ξ-1)a∥skij∥2+c1∥cS2kijkij∥≤(ξ-1)aɛ12+c1∥cS2kijkij∥.
Since ξ-1<0 and ∥cS2kijkij∥→0 as j→∞, we obtain
(3.23)gkijTskij≤-ξskijTBkijskij,
for sufficiently large j. Similarly, we have
(3.24)αgkijTskij+[θk(xk)]sθ≤-αskijTBkijskij+c1∥ckij2kij∥+[θk(xk)]sθ≤-αaɛ12+c1∥ckij2kij∥+[θk(xk)]sθ,
and thus
(3.25)-αgkijTskij≥[θk(xk)]sθ,
for sufficiently large j. This means the condition (2.3) is satisfied for sufficiently large j. Therefore, the reason for accepting xk+1 must been that xk+1 satisfies nonmonotone Armijo condition (2.4). In fact let ɛ0=ξaɛ12, then gkijTskij≤-ξskijTBkijskij≤-ξaɛ12=-ɛ0; by Lemma 3.6 we obtain nonmonotone Armijo condition (2.4) is satisfied. Consequently, the filter is not augmented in iteration kij which is a contraction to (3.21). The whole proof is completed.


## 4. Numerical Experiments

In this section, we test our algorithm on some typical test problems. In the whole process, the program is coded in MATLAB and we assume the error toleranceϵ in this paper is always 1.0e-5. The selected parameter values are γθ=0.1, γm=0.1, sθ=0.9, ρ1=0.25, ρ2=0.75, and M=3. In the following tables, the notations NIT, NOF, and NOG mean the number of iterates, number of functions, and number of gradients, respectively.Example 4.1.
Find a solution of the nonlinear equations system as follows:(4.1)(x+3y2(x-1.0)y)=(00).
The only solution of Example4.1 is (x*,y*)=(0,0). Define the line Γ={(1,y):y∈ℝ}. If the starting point (x0,y0)∈Γ, the Newton method [24] are confined to Γ. We choose two starting points which belong to Γ in the experiments and then the (x*,y*) is obtained. Table 1 shows the results.Table 1
Numerical results of Example4.1.
Starting point
NIT
NOF
NOG
(1,0)
2
5
7
(1,2)
6
13
12Example 4.2.
Consider the system of nonlinear equations:(4.2)c1(x)=x13-x23+x33-1,c2(x)=x12+x22-x32-1,c3(x)=x1+x2+x3-3.
The solution to Example4.2 is x*=(1,1,1)T. The numerical results of Example 4.2 are given in Table 2.Table 2
Numerical results of Example4.2.
Starting point
NIT
NOF
NOG
(0,0,0)
10
21
22
(1.5,1.5,1.5)
7
15
15Example 4.3.
Find a solution of the nonlinear equations system:(4.3)(x10x(x+0.1)+2y2)=(00).
The unique solution is(x*,y*)=(0,0). It has been proved in [2] that, under initial point (x0,y0)=(3,1), the iterates converge to the point z=(1.8016,0.0000), which is not a stationary point. Utilizing our algorithm, a sequence of points converging to (x*,y*) is obtained. The detailed numerical results for Example 4.3 are listed in Table 3.Table 3
Numerical results of Example4.3.
Starting point
NIT
NOF
NOG
NIT [22]
(3,1)
6
10
8
17
(30,10)
7
14
13
7
(300,100)
10
17
16
15Example 4.4.
Consider the following system of nonlinear equations:(4.4)c1(x)=x12+x1x2+2x22-x1-x2-2,c2(x)=2x12+x1x2+3x22-x1-x2-4.
There are three solutions of above example,(1,1)T, (-1,1)T, and (1,-1)T. The numerical results of Example 4.4 are given in Table 4.Table 4
Numerical results of Example4.4.
Starting point
(0.5,0.5)
(-0.5,0.5)
(0.5,-0.5)
NIT
5
5
6
NOF
8
7
9
NOG
7
6
9
Solution
(1,1)
(-1,1)
(1,-1)
NIT [22]
5
6
9Example 4.5.
Consider the system of nonlinear equations:(4.5)ci(x)=-(N+1)+2xi+∑j=1,j≠iNxj,i=1,2,…,N-1,(4.6)cN(x)=-1+∏j=1Nxj,
with the initial point xi(0)=0.5, i=1,2,…,N. The solution to Example 4.5 is x*=(1,1,…,1)T. The numerical results of Example 4.5 are given in Table 5.Table 5
Numerical results of Example4.5.
N
=
10
N
=
20
N
=
40
N
=
60
N
=
120
NIT
7
10
19
28
52
NOF
14
22
26
39
77
NOG
13
21
23
34
68
NIT [22]
8
17
22
41
FailRefer to these above problems, running the Algorithm2.1 with different starting points yields the results in the corresponding tables, which, summarized, show that our proposed algorithm is practical and effective. From the computation efficiency, we should point out our algorithm is competitive with the method in [22]. The results in Table 5 in fact show that our method also succeeds well to solve the cases when more equations are active.Constrained optimization approaches attacking the system of nonlinear equations are exceedingly interesting and are further developed by using the nonmonotone line search filter strategy in this paper. Moreover, the local property of the algorithm is a further topic of interest.



---

*Source: 971468-2012-09-04.xml*