# A Three-Term Conjugate Gradient Algorithm with Quadratic Convergence for Unconstrained Optimization Problems

Authors: Gaoyi Wu; Yong Li; Gonglin Yuan
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper further studies the WYL conjugate gradient (CG) formula withβkWYL≥0 and presents a three-term WYL CG algorithm, which has the sufficiently descent property without any conditions. The global convergence and the linear convergence are proved; moreover the n-step quadratic convergence with a restart strategy is established if the initial step length is appropriately chosen. Numerical experiments for large-scale problems including the normal unconstrained optimization problems andthe engineer problems (Benchmark Problems) show that the new algorithm is competitive with the other similar CG algorithms.


---

## Body

## 1. Introduction

Consider the following minimization optimizations modelling:(1)minx∈Rnfx,where f(x):Rn→R is a continuously differentiable function. The CG algorithms for (1) have the following iterative processes: (2)xk+1=xk+αkdk,k=0,1,2,⋯,where xk is the kth iterate, αk is the step length, and dk is the search direction defined by (3)dk=-gk+βkdk-1,ifk≥1-gk,ifk=0,where gk=∇f(xk) is the gradient and the parameter βk is a scalar determining different formulas (see [1–8], etc.). The PRP algorithm [6, 7] is one of the most effective CG algorithms and its convergence can be found (see [7, 9, 10], etc.). Powell [9] suggested that βk should not be less than zero; then many new CG formulas are proposed (see [11–17], etc.) to ensure the scalar βk≥0. At present, there are many results obtained in CG algorithms (see [11, 18–26], etc.) and a modified weak Wolfe-Powell line search technique is presented to study open unconstrained optimization (see [27, 28]). If a restart strategy is used, the PRP algorithm is n-step quadratic convergence (see [29–31]). Li and Tian [32] proved that a three-term CG algorithm has quadratic convergence with a restart strategy under some inexact line searches and the suitable assumptions.Recently, Wei et al. [21] proposed a new CG formula defined by βkWYL=gkTyk-1WYL/gk-12, where yk-1WYL=gk-(gk/gk-1)gk-1, gk and gk+1 are the gradient of f at xk and xk+1, respectively, and · denotes the Euclidean norm of vectors. It is easy to deduce that βkWYL=gkT(gk-(gk/gk-1)gk-1)/gk-12≥gkT(gk-(gk/gk-1)gk-1)/gk-12=0. The global convergences of the WYL algorithm with exact linear search, the Grippo-Lucidi Armijo line search, and the Wolfe-Powell line search have been established by [21, 33–35]. By restricting the parameter ς2<1/4 under the strong Wolfe-Powell linear search, the WYL algorithm can meet the sufficiently descent property. However the quadratic convergence is still open based on this algorithm. In this paper, we mainly further research the WYL algorithm. On the base of paper [32] and the paper [21], we propose a new WYL three-term CG formula. We show that the new CG algorithm has global convergence for general functions and has the n-step quadratic convergence for uniformly convex functions with r-step restart and standard Armijo line search under appropriate conditions. The numerical results show that the new algorithm performs quite well. The main attributes of this algorithm are listed as follows.(i) A new WYL three-term CG algorithm is introduced, which has sufficiently descent property automatically.(ii) The global convergence, linear convergent rate, and the n-step quadratic convergence are established.(iii) Numerical results show that this algorithm is competitive with the normal algorithm for the given problems.This paper is arranged as follows. In Section2, we mainly review the motivation and introduce the modified WYL algorithm. We show that the global convergence and r-step linear convergence of the new algorithm with the standard Armijo line search in Section 3. In Section 4, the n-step quadratic convergence of the given algorithm is proved. In Section 5, some numerical experiments are done.


## 2. Motivation and Algorithm

In this section, we will give motivations based on the WYL formulas. Consider the WYL search direction(4)dk=-gk+βkWYLdk-1,ifk≥1-gk,ifk=0,and we all know that dk is sufficiently descent by restricting the parameter ς2<1/4 under the strong Wolfe-Powell linear search [33]. By the definition of dk in (4), for k≥1, we get (5)dkTgk=-gk2+gkTyk-1WYLgk-12dk-1Tgk.In order to ensure that the sufficiently descent property holds, then the first term of the above equality should be maintained. So the directive idea is to add another term to eliminate the second term of the above equality; at the same time, the conjugacy should be guaranteed. Therefore the new conjugate gradient formula called MWYL algorithm is defined by (6)dkWYL=-gk+βkWYLdk-1WYL-θkWYLyk-1WYL,ifk≥1-gk,ifk=0,where θkWYL=gkTdk-1WYL/gk-12 and βkWYL=gkTyk-1WYL/gk-12. It is easy to see that the above search direction is the normal WYL algorithm if the exact linear search is used. It is not difficult to see from (6) that dkWYL is a descent direction of f at xk; namely, we have (7)dkWYLTgk=-g0Tg0=-g02,k=0and (8)dkWYLTgk=-gk+βkWYLdk-1WYL-θkWYLyk-1WYLTgk=-gk2+gkT·yk-1WYLgk-12·dk-1WYLTgk-gkTdk-1WYLgk-12·yk-1WYLTgk=-gk2,k≥1.Moreover we obtain (9)dkWYLTgk=-gk2,k≥0and (10)gk≤dkWYL.Now we list some linear search techniques that will be used in the following sections.(i) The exact line search is to findαk such that the function is minimized along the direction dk, that is, αk, satisfying (11)fxk+αkdk=minα≥0fxk+αdk(ii) The Armijo line search is to find a step lengthαk=maxρi∣i=0,1,2,⋯ which satisfies (12)fxk+αkdk≤fxk+ς1αkgkTdk,where ρ∈(0,1) and ς1∈(0,1/2).(iii) The Wolfe line search conditions are(13)fxk+αkdk≤fxk+ς1αkgkTdkgxk+αkdkTdk≥ς2gkTdk,where 0<ς1<1/2 and ς1<ς2<1.In the following we will give the MWYL algorithm.Algorithm 1 (a modified WYL three-terms CG algorithm, called MWYL).
S t e p   0: Choose an initial point x0∈Rn, ς1∈(0,1/2), ρ∈[0,1), ϵ∈[0,1); let d0=-g0, k:=0. S t e p   1: If gk≤ϵ, stop. Otherwise go to the next step. S t e p   2: Compute step size αk by the Armijo line search or Wolfe line search. S t e p   3: Let xk+1=xk+αkdkWYL. If gk+1≤ϵ, then stop. S t e p   4: Compute the search direction using (6). S t e p   5: Let k:=k+1. Go to step 2.


## 3. Convergence of Algorithm1

In this part, we will prove the global convergence and the r-linear convergence of theMWYL algorithm with the Armijo line search and Wolfe line search. The following assumptions are required.Assumption i.
The level setΩ=x∣fx≤fx1 is bounded and, in some neighborhood N of co¯Ω, f is continuously differentiable and bounded below, and its gradient is globally Lipschitz continuous; namely, there exists a constant L>0 such that (14)gx-gy≤Lx-y,∀x,y∈N,where co¯Ω is the closed convex hull of Ω.Now we establish the global convergence of Algorithm1.Theorem 2.
Let Assumption i hold and the sequence{xk} be generated by Algorithm 1. Then the relation (15)limk→∞⁡inf⁡gk=0holds.Proof.
We will prove this theorem by contradiction. Suppose that (15) does not hold, then, for all k, there exists a constant ε1>0 satisfying (16)gk≥ε1.Using (9) and (12), if f is bounded from below, it is not difficult to get (17)∑k=0∞αk2dkWYL2<∞.In particular, we have (18)limk→∞⁡αkdkWYL=0.If limk→∞αk>0, by (9) and (18), we obtain limk→∞infgk=0. This contradicts (16); then (15) holds.
Otherwise iflimk→∞αk=0. Then there exists an infinite index set N satisfying (19)limk∈N,k→∞⁡αk=0.By Step 2 of Algorithm 1, when k is sufficiently large, αkρ-1 does not satisfy (12), which implies that (20)fxk+αkρ-1dkWYL-fxk>-ς1ρ-2αk2dkWYL2.By (16), similar to the proof of Lemma 2.1 in [36], it is easy to deduce that there exists a constant ϱ>0 such that (21)dkWYL≤ϱ,∀k.Using (21), (9), and the mean-value theorem, we have (22)fxk+αkρ-1dkWYL-fxk=ρ-1αkgxk+ξ0ρ-1αkdkWYLTdkWYL=ρ-1αkgkTdkWYL+ρ-1αkgxk+ξ0ρ-1αkdkWYL-gkTdkWYL≤ρ-1αkgkTdkWYL+Mρ-2αk2dkWYL2,where ξ0∈(0,1) and the last inequality follows (26). Combining with (20), for all k∈N sufficiently large, we obtain (23)gk2≤ρ-1M+ς1αkdkWYL2.By (21) and limk→∞αk=0, then the above inequality implies that limk∈N,k→∞gk=0. This is a contradiction too. The proof is complete.In the next, we will prove the linear convergence of the sequence{xk} by the MWYL algorithm with the Armijo or Wolfe line search. The following assumption is further needed.Assumption ii.
f is twice continuously differentiable and the uniformly convex function. In other words, there are positive constants M≥m>0 such that (24)md2≤dT∇2fxd≤Md2,∀x,d∈Rn,where ∇2f(x) denotes the Hessian matrix of f at x.
It is not difficult to see that, under the Assumption ii,∇2f(x) is continuous and g is Lipschitz continuous and problem (1) has a unique solution x∗ which satisfies (25)12mx-x∗2≤fx-fx∗≤12Mx-x∗2,∀x∈Rnand (26)mx-x∗≤gk≤Mxk-x∗.Lemma 3.
Let Assumption ii hold and the sequence{xk} be generated by the MWYL algorithm with the Armijo or Wolfe line search, one has (27)-∑k=0∞gkTskWYL<∞,∑k=0∞skWYL<∞,c1αkdkWYL2≤-gkTdkWYL,where skWYL=xk+1-xk and c1=(1/2)(1-σ1)-1m. In addition, if the Wolfe line search is used, the following holds:(28)-gkTdkWYL≤1-ς2-1MαkdkWYL2.Proof.
We have from line search (12) that (29)fx0-fx^k=∑k=0k^-1fxk-fxk+1≥-∑k=0k^-1σ1gkTskWYL>0hold for any k^>1, because the objective function f is uniformly convex of Assumption ii, f is bounded below, so the inequality -∑k=0k^-1gkTskWYL<+∞ holds. Combining the Taylor theorem and Assumption ii, we obtain (30)fxk+1=fxk+gkTskWYL+12skWYLT∇2fξkskWYL,where ξk belong to the segment [xk,xk+1]. Therefore, we get (31)∑k=0k^-1fxk+1-fxk-∑k=0k^-1gkTskWYL=∑k=0k^-112skWYLT∇2fξkskWYL≥∑k=0k^-112mskWYL2.By the inequalities ∑k=0k^-1(f(xk+1)-f(xk))<0 and -∑k=0k^-1gkTskWYL<+∞, we get ∑k=0∞skWYL2<+∞. Using (12), (30), and Assumption ii, we obtain (32)ς1gkTskWYL≥fxk+1-fxk=gkTskWYL+12skWYLT∇2fξkskWYL≥gkTskWYL+12mskWYL2,which includes -gkTskWYL≥(m/21-ς1)skWYL2.
It is not difficult to get that(33)-gkTdkWYL≥m21-ς1·αkdkWYL2=c1αkdkWYL2.By the second inequality of (13), we get (34)gxk+αkdkWYL=gk+∫01∇2fxk+ταkdkWYLdτ·αkdkWYLTdkWYL≥ς2gkTdkWYLand (35)αkdkWYLT∫01∇2fxk+ταkdkWYLdτ·dkWYL≥ς2-1gkTdkWYL.By Assumption ii, we obtain -gkTdkWYL≤(1-ς2)-1MαkdkWYL2. This completes the proof.Lemma 4.
Let the sequence{xk} be generated by the MWYL algorithm with the Armijo or Wolfe line search and Assumption ii hold; then there is a constant c>0 such that (36)αk>c,∀k≥0.Proof.
Set(37)Gk-1=∫01∇2fxk-1+τsk-1dτ,where sk-1WYL=xk-xk-1=αk-1dk-1WYL. By the mean-value theorem, we have (38)yk=gk-gk-1=Gk-1sk-1=αk-1Gk-1dk-1WYLand (39)yk-1WYL=gk-gkgk-1·gk-1=gk-gk-1+gk-1-gkgk-1·gk-1≤gk-gk-1+gk-1-gk≤2gk-gk-1≤2αk-1·Gk-1·dk-1WYLTherefore, by (9), (39), Lemma 3, and the Assumption ii, we get (40)βkWYL=gk·yk-1WYLgk-12≤2αkgk·Gk-1dk-1WYLc1αkdk-1WYL2≤2c1-1Mgkdk-1WYLand (41)θkWYL=gkT·dk-1WYLgk-12=gkT·dk-1WYL-gk-1T·dk-1WYL≤2c1-1Mgkdk-1WYLBy the above conclusion, (6), and the Lipschitz continuity of g, we get (42)dkWYL≤gk+βkWYL·dk-1WYL+θkWYL·yk-1WYL≤gk+2Mc1-1gk+2Mc1-1gk≤1+4Mc1-1·gkIf the Armijo line search is used, using the line search rule, if αk≠1, then αk′=αkρ-1 will not satisfy line search condition (12). Namely, (43)fxk+αk′dkWYL-fxk>ς1αk′gkTdkWYL.Using the mean-value theorem and the above inequality, there exists μk∈(0,1) satisfying (44)ς1αk′gkTdkWYL<fxk+αk′dkWYL-fxk=αk′gxk+μkαk′dkWYLTdkWYL=αk′gxk+μkαk′dkWYL-gxkTdkWYL+αk′gkTdkWYL=μkαk′2dkWYLT∫01∇2fxk+τμkαk′dk∗dτ·dkWYL+αk′gkTdkWYL≤αk′2M·dkWYL2+αk′gkTdkWYL.Thus, by the above conclusion and (42), we get (45)αk=ραk′≥-1-ς1ρM·gkTdkWYLdkWYL2=1-ς1ρM·gk2dkWYL2≥M-11-ς1ρ1+4Mc1-1-2≡c∗,and letting c=min⁡{1,c∗}, we have (36). If the Wolfe line search is used, from the second inequality of (13), we obtain (46)MαkdkWYL2≥gxk+αkdkWYL-gkTdkWYL≥-1-ς2gkTdkWYL.By similar way to that for the Armijo line search, we can find a lower positive bound of αk; the proof is completed.Similar to [32], It is easy to get the r-linear convergence theorem of Algorithm 1. So we only state it as follows but omit the proof.Theorem 5.
Let Assumption ii hold,x∗ be the unique solution of (1), and the sequence {xk} be generated by the MWYL algorithm with the Armijo or Wolfe line search. Then there are constants a>0 and r∈(0,1) satisfying (47)xk-x∗≤ark.Proof.
By (12) or the first relation of (13), we get (48)fxk+1-fx∗≤fxk-fx∗+ς1αkdkTgk=fxk-fx∗-ς1αkgk2≤fxk-fx∗-cς1m2αkxk-x∗2≤fxk-fx∗-2cς1m2Mfxk-fx∗=1-2cς1m2Mfxk-fx∗,where the first equality follows (9), the second inequality follows (26), and the last inequality (25). Setting r=[1-2cς1m2/M]1/2∈(0,1) generates (49)fxk+1-fx∗≤r2fxk-fx∗≤⋯≤r2kfx0-fx∗.By (25) again, we have (50)xk-x∗≤2mfxk-fx∗≤2mfx0-fx∗r2k,and this relation shows that the proof is complete.


## 4. The Restart MWYL Algorithm’s N-Step Quadratic Convergence

Settingαk- as exact line search step length, then (51)gxk+αk-dkWYLTdkWYL=0holds. Thus, (52)gk2=-gkTdkWYL=gxk+αk-dkWYL-gxkTdkWYL=αk-dkWYLTGk-dkWYL,where Gk-=∫01∇2f(xk+ταk-dkWYL)dτ. It is feasible to use the initial step length of the Armijo or Wolfe line search as an approximation of αk-, where αk- is defined by(53)αk-≡gk2dkWYLTGk-dkWYL≈ϵkgk2dkWYLTgxk+ϵkdkWYL-gxk≡γk,where the integer sequence {ϵk}→0 as k→∞. If f is a quadratic function, then γk and αk- are consistent; namely, (54)αk--γk=gk2dkWYLTGk-dkWYL-ϵkgk2dkWYLTgxk+ϵkdkWYL-gxk=dkWYLTgxk+ϵkdkWYL-gkgk2-dkWYLTG-kdkWYLϵkgk2dkWYLTG-kdkWYLdkWYLTgxk+ϵkdkWYL-gxk≤oϵkdkWYL2·gk2m2ϵkdkWYL4⟶0.The above discussions can also be found in [32]; in fact, our ideas are motivated by this paper partly. The following Theorem 6 will show that, for sufficiently large k, the inexact line search step γk which is defined by (53) satisfies the Armijo and Wolfe conditions.Theorem 6.
Let sequence{xk} be generated by the MWYL algorithm and Assumption ii hold. Then, when k is sufficiently large, γk satisfies the Armijo and Wolfe conditions.Proof.
LetAk=∫01∇2f(xk+τϵkdkWYL)dτ, using Assumption ii and (10), we have (55)γk=gk2dkWYLTAkdkWYL≥gk2MdkWYL2and (56)γk=gk2dkWYLTAkdkWYL≤gk2mdkWYL2≤1m.Using {dkWYL}→0, Assumption ii, (47), and (55), we get (57)fxk+γkdkWYL=fxk+γkgkTdkWYL+12γk2dkWYLTAkdkWYL+γk2odkWYL2=fxk+12γkgkTdkWYL+γk2odkWYL2=fxk+ς1γkgkTdkWYL-12-ς1γkgk2+γk2odkWYL2≤fxk+ς1γkgkTdkWYL-12-ς11+2Mc1-1-4MdkWYL2+γk2odkWYL2For k is sufficiently large, we have (58)fxk+γkdkWYL≤fxk+ς1γkgkTdkWYL.When k is sufficiently large, αk=γk satisfies the Armijo condition. Setting Ak-=∫01∇2f(xk+τγkdkWYL)dτ, we get (59)gxk+γkdkTdkWYL-ς2gkTdkWYL=gxk+γkdkWYL-gkTdkWYL+1-ς2gkTdkWYL=γkdkWYLTAk-dkWYL-1-ς2gk2=dkWYLTAk-dkWYLdkWYLTAkdkWYL-1gk2+ς2gk2≤fxk+ς1γkgkTdkWYL-12-ς11+2Mc1-1-4MdkWYL2+γk2odkWYL2=dkWYLTAk--AkdkWYLdkWYLTAkdkWYLgk2+ς2gk2=ς2gk2+ogk2.So, for sufficiently large k, we have (60)gxk+γkdkWYLTdkWYL≥ς2gkTdkWYL.This implies that αk=γk satisfy the Wolfe line search. The proof is complete.If we use the restartMWYL algorithm, the n-step quadratic convergence is desirable. In the next, we use the γk as the initial step-length and give the algorithm steps of the restart MWYL algorithm.Algorithm 7 (called RWYL).
S t e p   0: Given x0∈Rn, r>0, ς1∈(0,1/2), ρ∈[0,1), ϵ∈[0,1), let k:=0. S t e p   1: If gk≤ϵ, stop. S t e p   2: If the inequality f(xk+γkdkWYL)≤f(xk)+ς1γkgkTdkWYL holds, we set αk=γk. Otherwise, we determine αk=maxγkρj∣j=0,1,2,⋯ satisfying (61)fxk+αkdkWYL≤fxk+ς1αkgkTdkWYL. S t e p   3: Let xk+1=xk+αkdkWYL, and k:=k+1. S t e p   4: If gk≤ϵ, stop. S t e p   5: If k=r, we let x0:=xk. Go to step 1. S t e p   6: Compute dkWYL by (6). Go to step 2.Lemma 8.
Let Assumption ii hold and{xk} be generated by the RWYL algorithm. Then there exist positive numbers ci∗, i=1,2,3,4, such that (62)gk+1≤c1∗dkWYL,βk+1WYL≤c2∗,θk+1WYL≤c3∗,dk+1WYL≤c4∗dkWYL.Proof.
Considering the first inequality of (62), we get (63)gk+1=gk+gk+1-gk≤gk+γk·Ak^dkWYL≤dkWYL+Mm·dkWYL=1+MmdkWYL≡c1∗dkWYL,where Ak^=∫01∇2f(xk+τγkdkWYL)dτ. By the definition of βk+1WYL we discuss the other three inequalities of (62), respectively. Starting from βk+1WYL, by the (39) and (62), we get (64)βk+1WYL=gk+1TykWYLgk2≤gk+1T·ykWYLgk2≤2c1-1Mgk+1dkWYL≤2c1-1Mc1∗≡c2∗.By (40), (62), and the definition of θk+1WYL, we obtain (65)θk+1WYL=gk+1TdkWYLgk2≤gk+1·dkWYLgk2≤c1∗dkWYL2gk2≤c1∗1+4Mc1-12≡c3∗.By the above conclusion and the definition of dk+1WYL, we have (66)dk+1WYL=-gk+1+βk+1WYLdkWYL-θk+1WYLykWYL≤gk+1+βk+1WYL·dkWYL+θk+1WYL·ykWYL≤c1∗dkWYL+c2∗dkWYL+2c3∗MαkdkWYL≤c1∗+c2∗+2Mc3∗dkWYL≡c4∗dkWYL.The proof is complete.In the following, we will prove the n-order quadratic convergence of the RWYL algorithm. We always let Assumption ii hold and{xk} be generated by the RWYL algorithm. Using x∗ as the unique solution of problem (1), by Theorem 2, we have {xk}→x∗. The equation αk=γk always holds if only k is large enough by the Theorem 6. In order to establish this convergence of the RWYL algorithm, we further need the following assumption.Assumption iii.
In some neighborhoodN of x∗, ∇2f is Lipschitz continuous.
Based on Assumption iii and the above lemma, we have the following remarks. Letfkr^(x) be the second-order approximate function of f in the neighborhood of the initial point xkr, then we have (67)fkr^x=fxkr+gxkrTx-xkr+12x-xkrT∇2fxkrx-xkr.Let {xkri} and {dkrWYL(i)} be the iterations and directions generated by the RWYL algorithm to minimize the quadratic function fkr^(x) with initial point xkr0=xkr. Specifically, the sequence {xkri} is generated by using the following process: (68)xkr0=xkr,xkri+1=xkr0+αkridkrWYLi,i=0,1,⋯,and (69)dkrWYLi=-gkri+βkrWYLidkrWYLi-1-θkriykrWYLi-1,ifk≥1-gkr0,ifk=0,where gkri=g(xkri) for i=1,2,⋯: (70)βkrWYLi=gkriTykrWYLi-1gkri-12,ykrWYLi-1=gkri-gkri-1,θkrWYLi=gkriTdkrWYLi-1gkri-12From the proof process of Theorem 6, it is not difficult to see that when k is sufficiently large, step length γk can always be found. Because fkr^(x) is a quadratic function, γk is the same as the step length obtained by the exact line search. Consequently, we have θkrWYL(i)=0; moreover there is an index j(kr)≤n such that xkrj(kr) is the exact minimizer of fkr^.
Similar to Lemmas(A.8)-(A-10) in the paper [30], it is not difficult to get the following relations: (71)βkr+iWYLdkr+i-1WYL-βkrWYLidkrWYLi-1=Odkr+i-1WYL-dkrWYLi-1+OdkrWYL2,(72)gkr+i-gkri≤gkr+i-1-gkri-1+OdkrWYL2+Mαkr+i-1dkr+i-1WYL-αkrWYLi-1dkrWYLi-1,and (73)αkr+idkr+iWYL-αkridkrWYLi=Ogkr+i-gkri+Odkr+iWYL-dkrWYLi+OdkrWYL2.The following lemma shows that the parameterθkWYL will converge to 0.Lemma 9.
For the parameterθkWYL, one has(74)θkr+i+1WYL=Ogkr+i=Ogkr.Proof.
LetA^kr+i and Akr+i be defined by Lemma 8; we get (75)dkr+iWYLTA^kr+idkr+iWYLdkr+iWYLTAkr+idkr+iWYL-1≤dkr+iWYLTA^kr+idkr+iWYL-dkr+iWYLTAkr+idkr+iWYLmdkr+iWYL2≤1mdkr+iWYL2∫01∇2fxkr+i+ταkr+idkr+iWYLdτ-∫01∇2fxkr+i+ϵkr+iταkr+idkr+iWYLdτ·dkr+iWYL2≤Lm∫011-ϵkr+iτdτ·αkr+i·dkr+iWYL≤L2m1-ϵkr+i·dkr+iWYL≤L1-ϵkr+i1+4Mc1-12mgkr+i=Ogkr+iwhere L is Lipschitz constant for ∇2f on set N. Then we get (76)dkr+iWYLTA^kr+idkr+iWYLdkr+iWYLTAkr+idkr+iWYL-1=Ogkr+i.For k sufficiently large, we get αk=γk. By the mean value theorem, we have (77)gxkr+iTdkr+iWYL=gxkr+i+γkr+idkr+iWYLTdkr+iWYL=gxkr+iTdkr+iWYL+gxkr+i+γkr+idkr+iWYL-gxkr+iTdkr+iWYL≤gkr+iTdkr+iWYL+γkr+idkr+iWYLTA^kr+idkr+iWYL=dkr+iWYLTA^kr+idkr+iWYLdkr+iWYLTAkr+idkr+iWYL-1gkr+i2=Ogkr+i3.Therefore, by the definition of θkWYL, we have (78)θkr+i+1WYL=gxkr+i+1Tdkr+iWYLgkr+i2=Ogkr+i=Ogkr.This completes the proof.Theorem 10.
Let Assumptions ii and iii hold; then, for alli=0,1,⋯, one gets (79)αkr+idkr+iWYL-αkridkrWYLi=OdkrWYL2and (80)αkr+idkr+iWYL-αkridkrWYLi=Oxkr-x∗2.Proof.
First, we will prove the following relationship. For alli=0,1,⋯,j(kr), we have (81)gkr+i-gkri=OdkrWYL2,(82)dkr+iWYL-dkrWYLi=OdkrWYL2,and (83)αkr+idkr+iWYL-αkridkrWYLi=OdkrWYL2.For the RWYL algorithm, by xkr0=xkr and αkr=γkr. The equalities (81)-(83) obviously hold for i=0. Suppose that (81)-(83) hold for i≥0, we prove that the equalities (81)-(83) hold for i+1. By inequality (72), we get (84)gkr+i+1-gkri+1≤gkr+i-gkri+OdkrWYL2+Mαkr+idkrWYL-αkridkrWYLi=OdkrWYL2+OdkrWYL2+MOdkrWYL2=OdkrWYL2Using the equality dkr=-gkr and the mean value theorem, we get (85)dkr+i+1WYL-dkrWYLi+1=-gkr+i+1+βkr+i+1WYLdkr+iWYL-θkr+i+1WYLykr+iWYL+gkri+1-βkrWYLi+1dkrWYLi≤gkr+i+1-gkri+1+θkr+i+1WYL·ykr+iWYL+βkr+i+1WYLdkr+iWYL-βkrWYLi+1dkrWYLi≤OdkrWYL2+OdkrWYL·Ogkr+OdkrWYL2=OdkrWYL2,and (86)αkr+i+1dkr+i+1WYL-αkri+1dkrWYLi+1=Ogkr+i+1-gkri+1+O∥dkr+i+1WYL-dkrWYLi+1+OdkrWYL2≤OdkrWYL2+OdkrWYL2+OdkrWYL2=OdkrWYL2,where the above inequalities follow (71), (72), (73), (81), and (82). Thus, equalities (81)-(83) hold for all i=1,2,⋯j(kr). Moreover equality (79) holds too. Now we prove that (80) holds. Considering (87)dkrWYL=gkr=gxkr-gx∗≤M·xkr-x∗,we get (88)dkrWYL2≤M2xkr-x∗2.Therefore equality (80) holds. This completes the proof.Based on the above lemmas, similar to Theorem 4.2 of [32], we can get the n-step quadratic convergence of the RWYL algorithm. Here we only state it as follows but omit the proof too.Theorem 11.
Let Assumptions ii and iii hold; then there exists a constantc′>0 satisfying (89)limk→∞⁡sup⁡xkr+n-x∗xkr-x∗2≤c′<∞.Namely, the RWYL algorithm is quadratically convergent.


## 5. Numerical Results

This section reports some numerical experiments with Algorithm7 (RWYL). In order to show the effectiveness of the given algorithm, we will test the algorithm in [15, 19] (Hager-Zhang), the algorithm in [6, 7] (PRP), and the algorithm in [21] (WYL). In these four algorithms, the Wolfe-Powell line search technique is used as well as the parameters ς1=0.1 and ς2=0.9. The restart constant r=10. The program will be stopped if g(xk)∞≤max{10-6,10-12g(x0)∞} or g(xk)∞≤10-6(1+fxk) holds.


### 5.1. Normal Unstrained Optimization Problems

The unconstrained optimization problems with the given initial points can be found athttp://camo.ici.ro/neculai/THREECG/funcname.txt,which were collected by Neculai Andrei. The programs are written by Fortran and the codes are downloaded fromhttp://users.clas.ufl.edu/hager/papers/Software/,which are written by Hager and Zhang.All codes run on PC Core 2 Duo CPU at 3.2 GHz, 2.00GB of RAM, and Windows 7 operation system. The dimension of the test problems is 10000, 50000, and 10,0000 variables. The dimension (dim) of the variable, the CPU time in seconds (CPU) and the number of iterations (NI), function evaluations and gradient evaluations (NFG), the final function values, and the norm value of the gradient when the program is stopped for these four algorithms are computed. The profiles of Dolan and Moré [37] are used to analyze the performance data of these four algorithms. The fraction P of problems is plotted where any given algorithm is within a factor t of the best time. In a performance profile plot, the top curve shows that the algorithm solves the most problems in a time, which was within a factor t of the best time.Figures1–3 show the performance of the RWYL, Hager-Zhang, PRP, and WYL algorithms with the dimension 10000 about NI, NFG, and CPU time, respectively. It is not difficult to see that these four algorithms can successfully solve the given problems. The RWYL is the best profile among these four algorithms and the normal WYL algorithm has the worst performance.Figure 1
Performance profiles of these algorithms on NI (dim=10000).Figure 2
Performance profiles of these algorithms on NFG (dim=10000).Figure 3
Performance profiles of these algorithms on CPU (dim=10000).In Figures4–6, we use CPU time, NI, and NFG to compare the performance of the conjugate gradient codes RWYL, Hager-Zhang, PRP, and WYL algorithms on the dimension 50000. These four figures indicate that, relative to the CPU time, NI, and NFG, RWYL is fastest, then PRP, then Hager-Zhang algorithm, and then WYL. These codes only differ in their choice of the search direction; then we can conclude that the RWYL generates the best search directions for these test problems, on average.Figure 4
Performance profiles of these algorithms on NI (dim=50000).Figure 5
Performance profiles of these algorithms on NFG (dim=50000).Figure 6
Performance profiles of these algorithms on CPU (dim=50000).In Figures7–9, we use CPU time, NI, and NFG to compare the performance of the conjugate gradient codes RWYL, Hager-Zhang algorithm, PRP, and WYL on the dimension 100000. These four figures indicate that, relative to the CPU time, NI, and NFG, RWYL is fastest, then Hager-Zhang algorithm, then PRP, and then WYL.Figure 7
Performance profiles of these algorithms on NI (dim=100000).Figure 8
Performance profiles of these algorithms on NFG (dim=100000).Figure 9
Performance profiles of these algorithms on CPU (dim=100000).According to these nine figures, it is easy to see that the RWYL has the best performance for the dimensions 10000, 50000, and 100000. The Hager-Zhang algorithm becomes competitive with the dimension become large, which shows that the Hager-Zhang algorithm is very effective for large-scale problems. The PRP algorithm has the stable numerical performance for any dimensions. The normal WYL can also successfully solve the optimization problems and its efficiency is limited. To directly show the CPU time, NI, and NFG of these four algorithms, each algorithm number is listed in Table1.Table 1
Results of total.
Algorithm dim=10000 dim=50000 dim=100000 NI NFG CPU NI NFG CPU NI NFG CPU RWYL 144 4035 8.78 222 4546 76.88 151 3653 141.79 Hager-Zhang 8655 33062 116.14 16329 58406 950.75 20661 72516 2251.47 PRP 6769 25186 144.00 12563 43475 699.07 116090 354062 10985.57 WYL 59433 181937 415.10 89221 271059 3117.06 167044 503781 11868.37


### 5.2. Benchmark Problems (Engineer Problems)

The following Benchmark Problems can be found athttp://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node6.html.( 1 ) Sphere function: (90)fsphx=∑i=1nxi2,xi∈-5.12,5.12x∗=0,0,⋯,0,fsphx∗=0.( 2 ) Schwefel function: (91)fschx=418.9828n+∑i=1nxisin⁡xi,xi∈-512.03,511.97x∗=-420.9678,-420.9678,⋯,-420.9678,fschx∗=0.( 3 ) Schwefel’s function:(92)fschdsx=∑i=1n∑j=1ixj2,xi∈-65.536,65.536x∗=0,0,⋯,0,fschdsx∗=0.( 4 ) Griewank function:(93)fgrix=1+∑i=1nxi24000-∏i=1ncos⁡xii,xi∈-600,600x∗=0,0,⋯,0,fgrix∗=0.( 5 ) Rastrigin function:(94)frasx=10n+∑i=1nxi2-10cos⁡2πxi,xi∈-5.12,5.12x∗=0,0,⋯,0,frasx∗=0.Benchmark Problems are from the engineer fields and there are many scholars focusing on the studies of these problems. The given algorithm of this paper can also successfully solve them. We do the experiments about the RWYL and the normal WYL for comparing and omit the other two methods Hager-Zhang and PRP. The parameters and the stopping rule are the same as the above subsection. The codes are written by Matlab 2017 and run on PC Core 2 Duo CPU at 2.26 GHz, 6.00GB of RAM, and Windows 7 operation system. The dimension is 300 and 1000 variables. The detailed numerical results are listed in Tables 2 and 3.Table 2
Results of Benchmark Problems for RWYL.
No. 1 2 3 4 5 x0 (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 2/6/4.680e-2 1/3/1.560e-2 150/450/1.926e+1 31/93/1.092e+0 3/9/9.360e-2 n=1000 2/6/1.560e-2 1/3/0.000e+0 452/1356/2.033e+3 51/153/1.070e+1 801/6394/4.570e+0  x0 (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 2/6/1.560e-2 1/3/1.560e-02 150/450/1.931e+1 31/93/7.020e-1 3/9/6.240e-2 n=1000 2/6/1.560e-2 1/3/0.000e+0 452/1356/2.033e+3 51/153/1.065e+1 801/6394/4.243e+0Table 3
Results of Benchmark Problems for WYL.
No. 1 2 3 4 5 x0 (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 519/2075/1.684e+0 1/3/1.560e-2 801/4002/5.396e+1 141/389/1.716e+0 801/4003/1.981e+0 n=1000 549/2195/1.809e+0 1/3/0.000e+0 801/4803/1.824e+3 152/419/1.622e+1 801/4003/2.199e+0  x0 (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 519/2075/1.606e+0 1/3/0.000e+0 801/4002/5.343e+1 141/389/1.638e+0 801/4003/1.996e+0 n=1000 549/2195/1.450e+0 1/3/0.000e+0 801/4803/1.822e+3 152/419/1.597e+1 801/4003/2.230e+0To directly see the results of Tables2 and 3, we compute the total NI and NFG and set them in Table 4.Table 4
Results of Tables2 and 3.
RWYL WYL NI 2988 9134  NFG 16946 43790The results of Table4 show that the restart algorithm is more competitive with the normal algorithm for the Benchmark Problems.


### 5.3. Parameters Estimation of Nonlinear Muskingum Models

The basic Muskingum model, the continuity, and storage equations are defined by(95)dStdt=It-Qt,St=kxIt+1-xQt,where, at time t, St is channel storage, It is rate of inflow and Qt= denotes outflow, k is storage-time constant, and x is weighting factor for the river reach. The generalized trapezoidal formula [38] is(96)minfk,x,m=∑i=1n-1min⁡1-Δt2θkxIi+1+1-xQi+1m-1-Δt2θkxIi+1-xQim-Δt2Ii-Qi+Δt21-ΔtθIi+1-Qi+1.To conveniently estimate the parameters k, x, and m in the nonlinear Muskingum model, the objective function can rewritten as (97)minSSQ1=∑i=1n-11-Δt2kxIi+1+1-xQi+1m-1-Δtθ2kxIi+1-xQim-Δt2Ii-Qi-Δt21-ΔtθIi+1-Qi+12,(98)minSSQ2=∑i=1n-11-Δt2kxIi+1m+1-xQi+1m-1-Δtθ2kxIim+1-xQim-Δt2Ii-Qi-Δt21-ΔtθIi+1-Qi+12.This subsection will use our RWYL to estimate the parameters of the above two Muskingum models, named Model 1 (96) and Model 2 (98).All in all, we can conclude that that the restart algorithm is competitive with the norm algorithm without restart technique and other similar algorithms.


## 5.1. Normal Unstrained Optimization Problems

The unconstrained optimization problems with the given initial points can be found athttp://camo.ici.ro/neculai/THREECG/funcname.txt,which were collected by Neculai Andrei. The programs are written by Fortran and the codes are downloaded fromhttp://users.clas.ufl.edu/hager/papers/Software/,which are written by Hager and Zhang.All codes run on PC Core 2 Duo CPU at 3.2 GHz, 2.00GB of RAM, and Windows 7 operation system. The dimension of the test problems is 10000, 50000, and 10,0000 variables. The dimension (dim) of the variable, the CPU time in seconds (CPU) and the number of iterations (NI), function evaluations and gradient evaluations (NFG), the final function values, and the norm value of the gradient when the program is stopped for these four algorithms are computed. The profiles of Dolan and Moré [37] are used to analyze the performance data of these four algorithms. The fraction P of problems is plotted where any given algorithm is within a factor t of the best time. In a performance profile plot, the top curve shows that the algorithm solves the most problems in a time, which was within a factor t of the best time.Figures1–3 show the performance of the RWYL, Hager-Zhang, PRP, and WYL algorithms with the dimension 10000 about NI, NFG, and CPU time, respectively. It is not difficult to see that these four algorithms can successfully solve the given problems. The RWYL is the best profile among these four algorithms and the normal WYL algorithm has the worst performance.Figure 1
Performance profiles of these algorithms on NI (dim=10000).Figure 2
Performance profiles of these algorithms on NFG (dim=10000).Figure 3
Performance profiles of these algorithms on CPU (dim=10000).In Figures4–6, we use CPU time, NI, and NFG to compare the performance of the conjugate gradient codes RWYL, Hager-Zhang, PRP, and WYL algorithms on the dimension 50000. These four figures indicate that, relative to the CPU time, NI, and NFG, RWYL is fastest, then PRP, then Hager-Zhang algorithm, and then WYL. These codes only differ in their choice of the search direction; then we can conclude that the RWYL generates the best search directions for these test problems, on average.Figure 4
Performance profiles of these algorithms on NI (dim=50000).Figure 5
Performance profiles of these algorithms on NFG (dim=50000).Figure 6
Performance profiles of these algorithms on CPU (dim=50000).In Figures7–9, we use CPU time, NI, and NFG to compare the performance of the conjugate gradient codes RWYL, Hager-Zhang algorithm, PRP, and WYL on the dimension 100000. These four figures indicate that, relative to the CPU time, NI, and NFG, RWYL is fastest, then Hager-Zhang algorithm, then PRP, and then WYL.Figure 7
Performance profiles of these algorithms on NI (dim=100000).Figure 8
Performance profiles of these algorithms on NFG (dim=100000).Figure 9
Performance profiles of these algorithms on CPU (dim=100000).According to these nine figures, it is easy to see that the RWYL has the best performance for the dimensions 10000, 50000, and 100000. The Hager-Zhang algorithm becomes competitive with the dimension become large, which shows that the Hager-Zhang algorithm is very effective for large-scale problems. The PRP algorithm has the stable numerical performance for any dimensions. The normal WYL can also successfully solve the optimization problems and its efficiency is limited. To directly show the CPU time, NI, and NFG of these four algorithms, each algorithm number is listed in Table1.Table 1
Results of total.
Algorithm dim=10000 dim=50000 dim=100000 NI NFG CPU NI NFG CPU NI NFG CPU RWYL 144 4035 8.78 222 4546 76.88 151 3653 141.79 Hager-Zhang 8655 33062 116.14 16329 58406 950.75 20661 72516 2251.47 PRP 6769 25186 144.00 12563 43475 699.07 116090 354062 10985.57 WYL 59433 181937 415.10 89221 271059 3117.06 167044 503781 11868.37


## 5.2. Benchmark Problems (Engineer Problems)

The following Benchmark Problems can be found athttp://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node6.html.( 1 ) Sphere function: (90)fsphx=∑i=1nxi2,xi∈-5.12,5.12x∗=0,0,⋯,0,fsphx∗=0.( 2 ) Schwefel function: (91)fschx=418.9828n+∑i=1nxisin⁡xi,xi∈-512.03,511.97x∗=-420.9678,-420.9678,⋯,-420.9678,fschx∗=0.( 3 ) Schwefel’s function:(92)fschdsx=∑i=1n∑j=1ixj2,xi∈-65.536,65.536x∗=0,0,⋯,0,fschdsx∗=0.( 4 ) Griewank function:(93)fgrix=1+∑i=1nxi24000-∏i=1ncos⁡xii,xi∈-600,600x∗=0,0,⋯,0,fgrix∗=0.( 5 ) Rastrigin function:(94)frasx=10n+∑i=1nxi2-10cos⁡2πxi,xi∈-5.12,5.12x∗=0,0,⋯,0,frasx∗=0.Benchmark Problems are from the engineer fields and there are many scholars focusing on the studies of these problems. The given algorithm of this paper can also successfully solve them. We do the experiments about the RWYL and the normal WYL for comparing and omit the other two methods Hager-Zhang and PRP. The parameters and the stopping rule are the same as the above subsection. The codes are written by Matlab 2017 and run on PC Core 2 Duo CPU at 2.26 GHz, 6.00GB of RAM, and Windows 7 operation system. The dimension is 300 and 1000 variables. The detailed numerical results are listed in Tables 2 and 3.Table 2
Results of Benchmark Problems for RWYL.
No. 1 2 3 4 5 x0 (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 2/6/4.680e-2 1/3/1.560e-2 150/450/1.926e+1 31/93/1.092e+0 3/9/9.360e-2 n=1000 2/6/1.560e-2 1/3/0.000e+0 452/1356/2.033e+3 51/153/1.070e+1 801/6394/4.570e+0  x0 (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 2/6/1.560e-2 1/3/1.560e-02 150/450/1.931e+1 31/93/7.020e-1 3/9/6.240e-2 n=1000 2/6/1.560e-2 1/3/0.000e+0 452/1356/2.033e+3 51/153/1.065e+1 801/6394/4.243e+0Table 3
Results of Benchmark Problems for WYL.
No. 1 2 3 4 5 x0 (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯) (-0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 519/2075/1.684e+0 1/3/1.560e-2 801/4002/5.396e+1 141/389/1.716e+0 801/4003/1.981e+0 n=1000 549/2195/1.809e+0 1/3/0.000e+0 801/4803/1.824e+3 152/419/1.622e+1 801/4003/2.199e+0  x0 (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯) (0.001,⋯)  NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU NI/NFG/CPU  n=300 519/2075/1.606e+0 1/3/0.000e+0 801/4002/5.343e+1 141/389/1.638e+0 801/4003/1.996e+0 n=1000 549/2195/1.450e+0 1/3/0.000e+0 801/4803/1.822e+3 152/419/1.597e+1 801/4003/2.230e+0To directly see the results of Tables2 and 3, we compute the total NI and NFG and set them in Table 4.Table 4
Results of Tables2 and 3.
RWYL WYL NI 2988 9134  NFG 16946 43790The results of Table4 show that the restart algorithm is more competitive with the normal algorithm for the Benchmark Problems.


## 5.3. Parameters Estimation of Nonlinear Muskingum Models

The basic Muskingum model, the continuity, and storage equations are defined by(95)dStdt=It-Qt,St=kxIt+1-xQt,where, at time t, St is channel storage, It is rate of inflow and Qt= denotes outflow, k is storage-time constant, and x is weighting factor for the river reach. The generalized trapezoidal formula [38] is(96)minfk,x,m=∑i=1n-1min⁡1-Δt2θkxIi+1+1-xQi+1m-1-Δt2θkxIi+1-xQim-Δt2Ii-Qi+Δt21-ΔtθIi+1-Qi+1.To conveniently estimate the parameters k, x, and m in the nonlinear Muskingum model, the objective function can rewritten as (97)minSSQ1=∑i=1n-11-Δt2kxIi+1+1-xQi+1m-1-Δtθ2kxIi+1-xQim-Δt2Ii-Qi-Δt21-ΔtθIi+1-Qi+12,(98)minSSQ2=∑i=1n-11-Δt2kxIi+1m+1-xQi+1m-1-Δtθ2kxIim+1-xQim-Δt2Ii-Qi-Δt21-ΔtθIi+1-Qi+12.This subsection will use our RWYL to estimate the parameters of the above two Muskingum models, named Model 1 (96) and Model 2 (98).All in all, we can conclude that that the restart algorithm is competitive with the norm algorithm without restart technique and other similar algorithms.


## 6. Conclusions

Nonlinear conjugate gradient algorithm is one of the most effective algorithms in optimization algorithms, especially for large-scale optimization problems. Many scholars have obtained many interesting results in this field. This paper focuses on a modified WYL CG algorithm with restart technique for large-scale optimization. In our opinion, there are at least seven issues that warrant further research and improvement: (i) The first issue that should be considered is the choice of the restart parameterr in the RWYL algorithm; the value (r=10) used here is not the only choice. (ii) The second important issue is the termination condition; better termination conditions may exist for the CG algorithms, which may improve the numerical performance and convergence. (iii) Under the restart strategy, other similar CG algorithms with quadratic convergence are worth studying. (iv) It would be interesting to test the performance of the given algorithm when applied to other optimization problems that arise in the image processing field. (v) We all know that the nonmonotone line search techniques are very effective. In the future, we will study the possibility of combining CG algorithms with nonmonotonic techniques for large-scale optimization problems and will attempt to obtain good results. (vi) In the experiment, there are 59 optimization problems with the dimension 10000, 50000, and 100000 variables that are tested. We also do the test for the Benchmark Problems which has wild applications in engineer fields. In the future, more problems and numerical experiments should be done to turn out the performance of the CG algorithms. (vii) The last issue is the use of the CG algorithm for nonsmooth optimization and nonlinear equations, which we consider to be important for future research. All these topics will be the focus of our future work.



---

*Source: 4813030-2018-06-27.xml*