# A Derivative-Free Liu–Storey Method for Solving Large-Scale Nonlinear Systems of Equations

Authors: Zhenhua Su; Min Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, a descent Liu–Storey conjugate gradient method is extended to solve large-scale nonlinear systems of equations. Based on certain assumptions, the global convergence property is obtained with a nonmonotone line search. The proposed method is suitable to solve large-scale problems for the low-storage requirement. Numerical experiment results show that the new method is practically effective.


---

## Body

## 1. Introduction

Consider the following nonlinear system of equations:(1)Fx=0,where F:Rn⟶Rn has continuous partial derivatives. In the past few decades, Newton’s methods have been widely used to solve problem (1) for their fast convergence speeds, see [1–10]. Newton’s methods determine the search direction by solving a linear system of equations, in which the coefficient matrix is the Jacobian matrix of F or an approximation of it. It is expensive to compute the coefficient matrix and solve the linear system of equations at each iteration. Therefore, Newton’s methods are not suitable for solving a large-scale problem in which the Jacobian matrix of F is unavailable or needs massive storage space. To overcome this shortcoming of Newton’s methods, in this paper, we attempt to develop a numerical algorithm based on a descent Liu–Storey conjugate gradient method and a nonmonotone line research.Recently, La Cruz and Raydan [11] designed the Spectral Algorithm for Nonlinear Equations (SANE) to solve (1) and analyzed the convergence property based on a modified Grippo–Lampariello–Lucidi (GLL) [12] nonmonotone line search. However, at each iteration, SANE needs to compute a directional derivative or an approximation of it. To improve the efficiency of the SANE algorithm, La Cruz et al. [13] proposed the derivative-free SANE (DF-SANE) algorithm by using a derivative-free nonmonotone line search method. Numerical experiment results show that the DF-SANE is efficient for solving large-scale problems. Similar to the DF-SANE method, Cheng and Li [14] developed the N-DF-SANE method for solving large-scale nonlinear systems of equations by combining the spectral residual method and the Zhang–Hager [15] nonmonotone line search. The global convergence of the method was established based on some mild conditions.If the continuously differentiable mappingF:Rn⟶Rn is the gradient of f:Rn⟶R, then (1) is the first-order necessary optimality condition of the optimization problem(2)minfx,x∈Rn,namely, we can get the solution of equation (1) by solving optimization problem (2). Therefore, it is reasonable to extend the numerical algorithms for solving (2) to solve large-scale nonlinear systems of equations. In this paper, we develop a derivative-free method for solving (1) based on a descent nonlinear conjugate gradient method.Nonlinear conjugate gradient methods are efficient for solving large-scale unconstrained optimization problems for their low-memory requirements and excellent convergence properties. Among the nonlinear conjugate gradient methods, the Hestenes–Stiefel (HS), Polak–Ribière–Polyak (PRP), and Liu–Storey (LS) method [16–19] are the most famous methods for the excellent performance in practice. These methods have been studied and used extensively [20–28].Recently, Li and Feng proposed a modified Liu–Storey conjugate gradient (MLS) method [24]. A good property of the MLS method is that, with any line search method, it can always generate descent search directions for objective functions. When the strong Wolfe line search is used, Li and Feng proved that their method is convergent globally.The numerical algorithm for solving nonlinear systems of equations has been widely studied in the last decades. There are some numerical algorithms for nonlinear systems based on conjugate gradient methods [29–35]. Yuan and Zhang [29] proposed a numerical method for large-scale nonlinear systems of equations based on a three-term Polak–Ribière–Polyak conjugate gradient method and the hyperplane projection strategy given by Solodov and Svaiter [8]. Abubakar and Kumam [32] improved this three-term method by combining the idea of Yan et al. [36]. Yuan et al. [30] also extended the Hestenes–Stiefel conjugate gradient method to solve large-scale nonlinear equations and establish its global convergence. Bala and Kumam [31] proposed a numerical method for nonlinear systems by combining a descent Dai–Liao conjugate gradient and hyperplane projection method. Yu [34] extended the PRP method to solve large-scale nonlinear systems of equations based on the Grippo–Lampariello–Lucidi (GLL) [12] and Li–Fukushima (LF) [5] nonmonotone line search.Inspired by the CG-type methods for the nonlinear system of equations, in this paper, we attempt to extend the MLS conjugate gradient method to solve problem (1) for the sufficient descent property, global convergence, and excellent numerical performance. To guarantee the global convergence of the new method, we determine the step length by a nonmonotone line search method which is a modification of the line search in [14, 15].Our paper is organized as follows: in the second section, we introduce the algorithm. In Section3, we analyze the global convergence of the proposed method. Some numerical experiment results are reported and analyzed in the last section.Throughout this paper, we denote the Euclidean norm of vectors by·, and Jx means the Jacobian matrix of F at x.


## 2. Algorithm

In the remainder of this paper, we let(3)fx=12Fx2.Based on the analysis in Section1, we now extend the MLS method [24] to solve (1), and the steps of the algorithm are stated as follows.Algorithm 1: Derivative-free MLS method:
Step 0: givenx0∈Rn, which is an initial guess of the solution. Let 0<ρ<1, λ1,λ2>0,0<τmin<τmax<1, and 0<αmin<αmax be given positive constants. Set k=0,C0=fx0, and Q0=1. Select a positive sequence ηk such that(4)∑k=0∞ηk=η<∞.Step 1: computedk by(5)dk=−Fk+βkMLSdk−1,d0=−F0,(6)βkMLS=−FkTyk−1Fk−1Tdk−1−tyk−12FkTdk−1Fk−1Tdk−12,whereFk=Fxk, yk−1=Fk−Fk−1 and t>1/4 is a constant.Step 2: select a suitable initial step lengthαk0∈αmin,αmax, and set αk=αk0.Step 3: nonmonotone line search step:If(7)fxk+αkdk≤Ck+ηk−λ1αk2dk4−λ2αk2fxk,then setxk+1=xk+αkdk, and go to Step 4.Else, if(8)fxk−αkdk≤Ck+ηk−λ1αk2dk4−λ2αk2fxk,then setxk+1=xk−αkdk, and go to Step 4.Else, setαk=ραk, and go to Step 3.Step 4: stop ifFxk+1=0.Step 5: selectτk∈τmin,τmax, and let(9)Qk+1=τkQk+1,Ck+1=τkQkCk+ηk+fxk+1Qk+1.Setk=k+1, and go to Step 1.The line search is the modification of the nonmonotone line search of Cheng and Li [14]. Define(10)Ak=∑i=0kfxi+iηi−1k+1,η−1=0.The following lemma shows that ifτk∈0,1, the parameter Ck lies between fk and Ak.Lemma 1.
Suppose thatfxkCk and Ak are infinite sequences generated by Algorithm 1. Then, fxk≤Ck≤Ak for all k≥0, and(11)Ck+1≤Ck+ηk.
We omit the proof of Lemma1 since it is similar to Lemma 2.2 in [14]. It is clear that Step 3 will be finished in a finite number of iterations for k=0 since C0=fx0 and f is continuously differentiable. Suppose that the line search step finishes in a finite number of iterations for index k. Then, we get from the line search conditions that(12)fxk+1≤Ck+ηk.
From the definition ofQk and Ck, we have(13)Ck+1=τkQkCk+ηk+fxk+1Qk+1,=τkQkCk+ηk+fxk+1τkQk+1,>fxk+1.
This means condition (7) or (8) will be satisfied when αk is small enough. Therefore, the algorithm is well defined.
The formula for directiondk is based on the MLS method proposed by Li and Feng [24]. From the definition of dk, we have that if Fk≠0 and Fk−1Tdk−1≠0 for some k≥1, then(14)FkTdk=−Fk2+βkMLSFkTdk−1,=−Fk2−FkTyk−1Fk−1Tdk−1+tyk−12FkTdk−1Fk−1Tdk−12FkTdk−1,=−Fk2Fk−1Tdk−12−FkTyk−1FkTdk−1Fk−1Tdk−1−tyk−12FkTdk−12Fk−1Tdk−12,≤−Fk2Fk−1Tdk−12+1/21/2tFk2Fk−1Tdk−12+1/22tyk−12FkTdk−12Fk−1Tdk−12,−tyk−12FkTdk−12Fk−1Tdk−12,=14t−1Fk2,where the inequality follows from an upper bound for the second term of the third equation, which is obtained from uTv≤1/2u2+v2 with u=−1/2tFk−1Tdk−1Fk and v=2tFkTdk−1yk−1. Obviously, inequality (14) also holds for k=0. Therefore, the search direction dk will always satisfy(15)FkTdk≤14t−1Fk2<0.
This means that the scalarβkMLS in (6) is well defined as long as Fk−1≠0 for k≥1 since Fk−1Tdk−1≠0 by (15). Moreover, Algorithm 1 does not need to calculate the Jacobian matrix of F and occupy low-memory space; therefore, it is suitable for large-scale problems. For convenience, we call this algorithm as the DF-MLS method.


## 3. Convergence Property

In this section, we devote to analyze the global convergence of our method under the following assumptions.Assumption 1.
(i)
The level setΩ=x∈Rn|fx≤fx0+η is bounded, where x0∈Rn is an arbitrary initial point and η is a constant such that(16)∑k=0∞ηk=η<∞.(ii)
The functionFx is continuously differentiable on some neighborhood Γ of Ω. Hence, Fx is Lipschitz continuous on Γ. That is, there exists a constant L>0 such that(17)Fx−Fy≤Lx−y,∀x,y∈Γ.
The assumption implies that there is a constantγ1>0 such that(18)Fx≤γ1,∀x∈Ω.Lemma 2.
Suppose thatxk is an infinite sequence generated by the DF-MLS method and Assumption 1 holds. Then, xk is contained in Ω.Proof.
Based on the line search step of the algorithm, we have(19)fxk≤Ck+ηk,∀k≥0.
Combining with (11), we have(20)fxk≤Ck+ηk≤Ck−1+ηk−1+ηk≤⋯≤fx0+∑i=0kηk≤fx0+η.
The above inequality draws the conclusion.Lemma 3.
Suppose thatxk is an infinite sequence generated by the DF-MLS method and Assumption 1 holds. Then,(21)limk⟶∞αkdk2=0,limk⟶∞αk2fxk=0.Proof.
We get from the third step of the algorithm that(22)fxk+1≤Ck+ηk−λ1αk2dk4−λ2αk2fxk.
Combining this with (9), we have(23)Ck+1=τkQkCk+ηk+fxk+1Qk+1,≤τkQkCk+ηk+Ck+ηk−λ1αk2dk4−λ2αk2fxkQk+1,=Ck+ηk−λ1αk2dk4+λ2αk2fxkQk+1.
By (4), we have(24)∑k=0∞λ1αk2dk4+λ2αk2fxkQk+1<∞.
Since0<τmin≤τk≤τmax<1 and Q0=1, we get from (9) that(25)Qk+1=τkQk+1=1+∑j=0k∏i=0jτk−i≤1+∑j=0kτmaxj+1≤11−τmax.
This together with (24) implies(26)∑k=0∞λ1αk2dk4+λ2αk2fxk<∞,which gives (21). This completes the proof.Lemma 4.
Suppose thatdk is an infinite sequence generated by the DF-MLS method and Assumption 1 holds. If there exists a constant γ>0 such that(27)Fk≥γ,∀k≥0,then there exists a constant B>0 such that(28)dk≤B,∀k≥0,(29)limk⟶∞βkMLSdk−1=0.Proof.
We get from (15), (17), (18), and (5) that(30)dk≤Fk+βkMLSdk−1,≤Fk+Fkyk−1dk−1Fk−1Tdk−1+tyk−12Fkdk−1Fk−1Tdk−12dk−1,≤γ1+4tγ1Lαk−1dk−124t−1γ2+t4t22γ12Lαk−1dk−124t−12γ4dk−1,=γ1+4tγ1L4t−1γ2αk−1dk−12+32t3γ12L4t−12γ4αk−1dk−12dk−1.
For any constantb∈0,1, we get from (21) that there exists an index k0 such that(31)32t3γ12L4t−12γ4αk−1dk−12<b,∀k>k0.
Then,(32)dk≤γ1+4t−1γ2b8t2γ1+bdk−1=c+bdk−1,where c=γ1+4t−1γ2b/8t2γ1 is a constant. For any k>k0, we have(33)dk≤c1+b+b2+⋯+bk−k0+1+bk−k0dk0≤c1−b+dk0.
So, we can letB=maxd1,d2,…,dk0,c/1−b+dk0 to get (28). By (17), (27), (21), and (28), we have(34)βkMLSdk−1=βkMLSdk−1,≤Fkyk−1dk−1Fk−1Tdk−1+tyk−12Fkdk−1Fk−1Tdk−12dk−1,≤4tγ1L4t−1γ2+32t3γ12L4t−12γ4dk−1αk−1dk−12,which shows (29).
Analogy to Theorem1 in [13], we establish the global convergence of the DF-MLS method as follows.Theorem 1.
Suppose thatxk is an infinite sequence generated by the DF-MLS method and Assumption 1 holds. Then,(35)liminfk⟶∞Fk=0,or every limit point x∗ of xk satisfies(36)Fx∗TJx∗Fx∗=0,where Jx∗ is the Jacobian matrix of Fx at x∗.Proof.
Letx∗ be a limit point of xk and K be an infinite sequence of indices such that(37)limk∈Kxk=x∗.
(21) implies(38)limk∈Kαk2fxk=limk∈K12αk2Fk2=0.
Iflimk∈Kαk≠0, then there exists an infinite subsequence K1⊆K such that αk is bounded away from zero for any k∈K1. Therefore, in this case, we get from (38) that(39)limk∈K1Fk=0.
This impliesFx∗=0, and (35) holds since F is continuous and limk∈K1xk=x∗.
Next, we analyze the case when(40)limk∈Kαk=0.
Assume that (35) does not hold; then, there exists an infinite subsequence K2⊆K such that Fk is bounded away from zero for any k∈K2. From the third step of the DF-MLS method, the step length ρ−1αk will satisfy neither (7) nor (8) when k∈K2 is large enough. This means(41)fxk+ρ−1αkdk>Ck+ηk−λ1ρ−2αk2dk4−λ2ρ−2αk2fxk,(42)fxk−ρ−1αkdk>Ck+ηk−λ1ρ−2αk2dk4−λ2ρ−2αk2fxk.
We get from the conclusion of Lemma1 that Ck≥fxk≥0. Combining this with (41), we have(43)fxk+ρ−1αkdk>fxk−λ1ρ−2αk2dk4−λ2ρ−2αk2fxk.
It follows from Lemma2 that(44)fxk≤fx0+η.
Combining this with (18) and (28), we obtain(45)fxk+ρ−1αkdk−fxk>−Mαk2,where M=λ1ρ−2B4+λ2ρ−2fx0+η. Therefore,(46)fxk+ρ−1αkdk−fxkαk>−Mαk.
By the mean value theorem and (3), there exists a parameter ξk∈0,1 such that(47)ρ−1Fxk+ξkρ−1αkdkTJxk+ξkρ−1αkdkdk>−Mαk,namely,(48)ρ−1Fxk+ξkρ−1αkdkTJxk+ξkρ−1αkdk−Fk+βkMLSdk−1>−Mαk.
Combining this with (21), (29), and (40) and taking limits in (48), we obtain(49)Fx∗TJx∗Fx∗≤0.
Using (42) and proceeding in a similar way, we can get(50)Fx∗TJx∗Fx∗≥0.
From the last two inequalities, we get (36) which completes the proof.Corollary 1.
Suppose thatxk is an infinite sequence generated by the DF-MLS method and Assumption 1 holds. If x∗ is a limit point of xk and(51)yTJx∗y≠0,∀y∈ℝn,y≠0,then(52)Fx∗=0.Proof.
We draw the conclusion straightforwardly by using Theorem1.
If the Jacobian matrix ofFx is positive definite for all x∈ℝn, we say that the mapping F is strictly monotone, namely, the Jacobian matrix Jx satisfies(53)xTJxx>0,∀x∈ℝn.
If mappingFx is strictly monotone and Fx=0 has a solution, its solution must be unique. See Chapter 5 of [37].Corollary 2.
Suppose thatxk is an infinite sequence generated by the DF-MLS method and Assumption 1 holds. If F or −F is strictly monotone, then every bounded subsequence xkk∈ℕ converges to the solution of (1).Proof.
We draw the conclusion straightforwardly by using Theorem1.


## 4. Numerical Results

In this section, we report the numerical experimental results and analyze the efficiency of our method. We compare the numerical performance of our method with some other methods such as the DF-SANE method [13], the N-DF-SANE method [14], and the DF-SCGNE method [34]. We used the aforementioned methods to find the stationary points of the test problems by using their gradients only. We tested 112 unconstrained optimization problems in the CUTEr library [38] with dimensions varying from 50 to 10,000. We ran two versions of some problems for which the dimensions can be chosen randomly.We downloaded the DF-SANE code from Professor Raydan’s home page athttp://kuainasi.ciens.ucv.ve/mraydan/mraydan_pub.html. These four methods were coded in Fortran 77 and carried out on a personal computer with 2.8 GHz CPU processor and 2 GB RAM and Linux operating system. We terminated the program when(54)Fxkn≤ea+erFx0n,where ea=10−5 and er=10−4.Table1 lists the detailed experimental results, which include the problem names (Prob), dimensions (Dim), the total number of iterations (Iter), function evaluations (Nfun), and the CPU time (Time) in seconds, respectively. The symbol “—” means that the number of iterations exceeds 1000, or the line search iterates more than 100 times. In other words, this means that the method failed to solve that problem.Table 1
Numerical results.
ProbDimDF-SANEN-DF-SANEDF-SCGNEDF-MLSIter/Nfun/TimeIter/Nfun/TimeIter/Nfun/TimeIter/Nfun/TimeARGLINA503/3/0.0013/5/0.0013/6/0.0012/5/0.001ARGLINA2003/3/0.0053/5/0.0073/6/0.0092/5/0.008ARGLINB10047/1151/0.2983/29/0.0083/30/0.00831/817/0.209ARGLINB200867/24347/25.893/33/0.0394/35/0.04131/923/0.988ARGLINC100231/5707/1.4413/29/0.0083/30/0.00933/865/0.216ARGLINC20039/1071/1.1333/33/0.0374/35/0.0434/1023/1.071ARWHEAD5007/15/0.0025/17/0.0035/17/0.0035/17/0.002ARWHEAD50006/16/0.0215/19/0.0275/19/0.0265/19/0.025BDQRTIC50067/131/0.0286/297/0.04621/52/0.00916/41/0.006BDQRTIC500050/110/0.192194/1019/1.75816/45/0.0832/35/0.062BOX10066/198/0.006309/873/0.02878/372/0.01237/153/0.005BOX1000—706/4367/1.344124/743/0.23157/1255/0.384BROWNAL1003/13/0.0023/15/0.0023/15/0.0023/15/0.002BROYDN7D1000—68/137/0.13824/49/0.04925/51/0.051BRYBND100018/29/0.01239/85/0.036102/388/0.1613/31/0.013BRYBND500023/33/0.0836/75/0.18617/37/0.09316/37/0.089CHAINWOO4000170/355/0.43194/332/0.414105/476/0.58664/201/0.247CHAINWOO1000041/67/0.235—49/178/0.60522/51/0.175CHNROSNB50————CRAGGLVY50028/44/0.01535/81/0.02519/45/0.01619/45/0.015CRAGGLVY100032/50/0.03243/125/0.07222/51/0.03418/43/0.029CURLY101000—185/752/0.161100/216/0.05118/357/0.074CURLY201000—182/942/0.324121/475/0.168182/919/0.313CURLY30100—809/4720/0.198621/4448/0.187757/5431/0.225DECONVU6119/23/0.00124/51/0.00227/57/0.00222/47/0.002DIXMAANA15006/8/0.0035/11/0.0046/13/0.0055/11/0.004DIXMAANA90006/8/0.0215/11/0.0296/13/0.0367/17/0.042DIXMAANB30007/9/0.0076/13/0.0110/21/0.0177/17/0.014DIXMAANB90007/9/0.0236/13/0.03510/21/0.0547/17/0.043DIXMAANC30009/13/0.0117/17/0.0139/21/0.0177/17/0.013DIXMAANC90009/13/0.0327/17/0.0469/21/0.0587/17/0.042DIXMAAND15007/11/0.0046/15/0.0057/17/0.0095/13/0.005DIXMAAND30007/11/0.0086/15/0.0137/17/0.0145/13/0.01DIXMAANE300022/26/0.01947/95/0.07520/41/0.03226/55/0.041DIXMAANE900022/26/0.06447/95/0.24420/41/0.10526/55/0.138DIXMAANF300017/19/0.01525/51/0.04117/35/0.02813/29/0.022DIXMAANF900017/19/0.04725/51/0.1317/35/0.0913/29/0.073DIXMAANG300014/18/0.01413/29/0.02312/27/0.02111/25/0.019DIXMAANG900014/18/0.04413/29/0.07612/27/0.0711/25/0.062DIXMAANH30009/13/0.019/21/0.0179/21/0.0178/19/0.014DIXMAANH90009/13/0.0349/21/0.0549/21/0.05411/27/0.067DIXMAANI300029/37/0.02884/169/0.13329/59/0.04837/77/0.058DIXMAANI900029/37/0.09384/169/0.431929/59/0.1537/77/0.19DIXMAANJ300018/20/0.01633/67/0.05423/47/0.03715/33/0.025DIXMAANJ900018/20/0.05133/67/0.17223/47/0.12115/33/0.083DIXMAANK150014/18/0.00615/33/0.01314/31/0.01112/27/0.01DIXMAANK300014/18/0.01315/33/0.02714/31/0.02512/27/0.021DIXMAANL150012/16/0.0069/21/0.0099/21/0.0078/19/0.007DIXMAANL300012/16/0.0129/21/0.0189/21/0.0198/19/0.014DIXON3DQ10000——609/1235/1.459—DQDRTIC50012/18/0.00156/175/0.0177/19/0.0017/19/0.002DQDRTIC100012/18/0.00340/91/0.027/19/0.0047/19/0.004EDENSCH200019/25/0.01412/29/0.01817/39/0.02313/33/0.019EG210009/15/0.0046/13/0.00416/37/0.0116/13/0.006ENGVAL110012/16/0.00114/31/0.0019/21/0.0019/21/0.001ENGVAL150008/12/0.0167/17/0.0259/21/0.036/15/0.02ERRINROS5020/32/0.00112/33/0.00116/41/0.00112/33/0.001EXTROSNB10040/55/0.00136/81/0.00119/44/0.00117/43/0EXTROSNB100022/28/0.00417/39/0.0076/19/0.00318/51/0.008FLETCBV2100001/1/0.0051/1/0.0061/1/0.0051/1/0.005FLETCBV3100————FREUROTH1000816/3457/1.06878/266/0.08564/235/0.07437/97/0.031GENHUMPS5000————GENROSE500————HILBERTA1012/12/093/193/0.0017/14/06/11/0.001HILBERTB505/7/0.0015/11/0.0026/13/0.0025/11/0.001HYDC20LS99777/3215/0.543342/1701/0.264314/1874/0.291107/447/0.069INDEF100————LIARWHD500043/97/0.109957/7417/8.45335/94/0.11616/43/0.052LIARWHD10000——419/3534/8.68122/59/0.153MANCINO1005/19/0.1185/23/0.1465/23/0.14563/351/2.1817MODBEALE2000587/2400/2.926224/1261/1.57655/183/0.23531/78/0.098MOREBV100020/22/0.00549/97/0.02121/42/0.0114/27/0.005MOREBV50005/5/0.0066/11/0.01219/38/0.0433/5/0.006MSQRTALS1024————NONCVXUN10037/45/0.00242/97/0.00430/63/0.00339/101/0.004NONDIA50003/15/0.0163/17/0.0194/19/0.0223/17/0.018NONDIA100004/18/0.0414/21/0.0524/21/0.054/21/0.048NONDQUAR100024/36/0.00422/51/0.00830/69/0.00923/55/0.007NONDQUAR1000015/27/0.03417/45/0.06130/73/0.09811/33/0.042NONMSQRT100—177/805/0.05980/285/0.022483/2815/0.198OSCIPATH50011/13/0.00112/25/0.00210/22/0.0028/17/0.001PENALTY15010/20/09/27/0.0019/28/010/31/0PENALTY220038/72/0.02658/181/0.05633/79/0.0329/71/0.026POWELLSG500048/64/0.035251/591/0.33636/77/0.04624/53/0.03POWELLSG1000048/64/0.073159/685/0.73736/77/0.09624/53/0.062POWER1000015/321/0.269/41/0.03910/43/0.04222/517/0.413SCHMVETT10000———39/96/0.930SCOSINE100————SENSORS100439/598/4.04713/33/0.20917/39/0.24638/103/0.650SINQUAD5000—305/2441/5.297—27/83/0.175SPARSQUR100013/21/0.0089/25/0.0114/35/0.0149/25/0.01SPARSQUR500013/23/0.04910/29/0.06612/33/0.07310/29/0.061SPMSRTLS10000————SROSENBR100012/20/0.003120/637/0.0776/17/0.0029/23/0.003SROSENBR500012/20/0.01282/345/0.2236/17/0.0129/23/0.015TESTQUAD100043/63/0.006154/319/0.03938/87/0.00939/89/0.008TESTQUAD500043/65/0.03159/329/0.19843/97/0.05343/97/0.05TOINTGOR50171/319/0.005130/433/0.00762/129/0.00265/145/0.003TOINTGSS10002/4/0.0023/7/0.0044/9/0.0053/7/0.004TOINTPSP50642/1771/0.015198/836/0.007162/676/0.006220/880/0.007TOINTQOR5026/30/0.00187/177/0.00222/47/0.00122/47/0TQUARTIC1000—538/4539/0.713—416/4104/0.642TQUARTIC10000————TRIDIA5000655/2455/1.118390/2181/1.075206/419/0.245195/397/0.216TRIDIA10000724/2890/2.760395/2219/2.251205/417/0.522205/419/0.484VARDIM1005/103/0.0019/43/0.00110/45/0.0014/83/0.001VARDIM20016/426/0.00910/49/0.00112/54/0.0017/187/0.004VAREIGVL100026/42/0.01827/59/0.02817/39/0.01919/43/0.019VAREIGVL5000116/290/0.745124/371/1.00042/187/0.48736/117/0.303WOODS400031/43/0.03337/81/0.0642/117/0.08314/37/0.025WOODS1000031/43/0.08137/81/0.16340/113/0.21814/37/0.071We compared the numerical performance of the methods by using the profiles designed by Dolan and Moré [39]. Figures 1 and 2 describe the numerical performance of the methods relative to the CPU time (in seconds), the total number of iterations, and function value evaluations, respectively. The curves in the figures have the following meanings.(1)
“DF-SANE” denotes the DF-SANE method proposed by La Cruz et al. [13] with nexp=2, σmin=10−10, σmax=1010, σ0=1,τmin=0.1, τmax=0.5, γ=10−4,M=10, and ηk=Fx0/2k for all k.(2)
“N-DF-SANE” means the N-DF-SANE method developed by Cheng and Li [14] with ηk=0.6,σmin=10−10, σmax=1010, ρmin=0.1, ρmaxγ=10−4, and εk=Fx0/2k for all k.(3)
“DF-MLS” stands for Algorithm1. We set the parameters as follows: ρ=0.5,τk=0.6,t=1,λ1=λ2=10−4,αmin=10−10, αmax=1010, and ηk=Fx0/2k for all k. In the line search, the initial step length αk0 is determined by(55)αk0=αmax,ifσ>αmax,σ,ifσ∈αmin,αmax,αmin,ifσ<αmin,σ=−FkTdkdkTzk,zk=Fxk+εdk−Fxkε,ε=10−8.(4)
“DF-SCGNE” means the DF-SCGNE method proposed by Yu [34] using the same line search as DF-MLS.Figure 1
Performance profiles related to the number of iterations.Figure 2
Performance profiles related to the number of function evaluations.For each method, the corresponding curve in Figure1 plots the fraction P of problems for which the method is within a factor τ of the smallest total number of iterations. We observe from Figure 1 that DF-MLS solves 60.71% (68 out of 112) of the test problems with the smallest total number of iterations. This may be because the DF-MLS method can generate more efficiently than other methods. We observe from Figures 1 and 2 that the performance of DF-MLS is better than that of N-DF-SANE and DF-SCGNE. However, the DF-MLS method requires more function evaluations and CPU time than DF-SANE. This might be because that the DF-MLS method needs an additional function evaluation to determine the initial step length αk0 at each iteration. Figure 3 compares the performance of these four methods relative to the number of function evaluations. How to improve the efficiency of the DF-MLS method will be an interesting topic for us in the future.Figure 3
Performance profiles relative to the CPU time.


## 5. Conclusion

Many practical applications give rise to nonlinear systems of equations. In the past few decades, Newton’s methods [1–10] have been widely used to solve this problem for their fast convergence speeds. However, Newton’s methods are not suitable for solving a large-scale problem in which the Jacobian matrix of the objective function is unavailable or needs massive storage space. To overcome this shortcoming of Newton’s methods, some derivative-free numerical algorithms have been developed such as the SANE, DF-SANE, and some CG-type methods [11, 13, 29–34].Inspired by the CG-type methods, we design a derivative-free method for a large-scale nonlinear system of equations based on the MLS [24] conjugate gradient method. The line search in the proposed method is a modification of the Zhang–Hager [15] and Cheng–Li [14] nonmonotone line searches. We established the global convergence based on some mild conditions. The proposed method is suitable to solve large-scale problems because it does not need the Jacobian matrix of the objective function. In the numerical experiment, we tested 112 unconstrained optimization problems in the CUTEr library [38] and compared the numerical performance of our method with that of DF-SANE [13], N-DF-SANE [14], and DF-SCGNE [34]. We used the methods to find the stationary points of the test problems by using their gradients only. The numerical results show that the proposed method is efficient and has good numerical stability.



---

*Source: 6854501-2020-10-29.xml*