# A Truncated Descent HS Conjugate Gradient Method and Its Global Convergence

Authors: Wanyou Cheng; Zongguo Zhang
Journal: Mathematical Problems in Engineering
 (2009)

---

## Abstract

Recently, Zhang (2006) proposed a three-term modified HS (TTHS) method for unconstrained optimization problems. An attractive property of the TTHS method is that the
direction generated by the method is always descent. This property is independent of the
line search used. In order to obtain the global convergence of the TTHS method, Zhang
proposed a truncated TTHS method. A drawback is that the numerical performance of the
truncated TTHS method is not ideal. In this paper, we prove that the TTHS method with
standard Armijo line search is globally convergent for uniformly convex problems. Moreover,
we propose a new truncated TTHS method. Under suitable conditions, global convergence is
obtained for the proposed method. Extensive numerical experiment show that the proposed
method is very efficient for the test problems from the CUTE Library.


---

## Body

## 1. Introduction

Consider the unconstrained optimization problem:(1.1)minf(x),x∈Rn,
where f is continuously  differentiable. Conjugate gradient methods are very important methods for solving (1.1), especially if the dimension n is large. The methods are of the form
(1.2)xk+1=xk+αkdk,k=0,1,…,(1.3)dk={-gk,ifk=0,-gk+βkdk-1,ifk>0,
where gk denotes the gradient of f at xk,αk is the step length obtained by a line search and βk is a scalar. The strong Wolfe line search is to find a step length αk such that
(1.4)f(xk+αkdk)≤f(xk)+δαkgkTdk,(1.5)|g(xk+αkdk)Tdk|≤-σgkTdk,
where δ∈(0,1/2) and σ∈(δ,1). In the conjugate gradient methods field, it is also possible to use the Wolfe line search [1, 2], which calculates an αk satisfying (1.4) and
(1.6)g(xk+αkdk)Tdk≥σgkTdk.
In particular, some conjugate gradient methods admit to use the Armijo line search, namely, the step length αk can be obtained by letting αk=max{βρj,j=0,1,2,…} satisfy
(1.7)f(xk+βρjdk)≤f(xk)+δ1βρjgkTdk,
where 0<β≤1,0<ρ<1, and 0<δ1<1. Varieties of this method differ in the way of selecting βk. In this paper, we are interested in the HS method [3], namely,
(1.8)βkHS=gkTyk-1dk-1Tyk-1.
Here and throughout the paper, without specification, we always use ∥·∥ to denote the Euclidian norm of vectors, yk-1=gk-gk-1 and sk=αkdk.We refer to a book [4] and a recent review paper [5] about progress of the global convergence of conjugate gradient methods. We know that the study in the HS method has made great progress. In practical computation, the HS method is generally believed to be one of the most efficient conjugate gradient methods. Theoretically, the HS method has the property that the conjugacy condition
(1.9)dkTyk-1=0,
always holds, which is independent of line search used. Expecting the fast convergence of the method, Dai and Liao [6] modified the numerator of the HS method to obtain DL method by using the secant condition of quasi-Newton methods. Due to Powell's [7] example, the DL method may not converge with exact line search for general function. Similar to the PRP+ method [8], Dai and Liao [6] proposed the DL+ method from a view of global convergence. In a further development of this update strategy, Yabe and Takano [9] used another modified secant condition in [10, 11] and proposed the YT and YT+ methods. Recently, Hager and Zhang [5] modified the HS method to propose a new conjugate gradient method called CG_DESCENT method. A good property of the CG_DESCENT method lies in that the direction dk satisfies sufficient descent property gkTdk≤-(7/8)∥gk∥2 which is independent of the line search used. Hager and Zhang [5] proved that the CG_DESCENT method with Wolfe line search is globally convergent even for nonconvex problems. Zhang [12] proposed the TTHS method. The sufficient descent property of the TTHS method is also independent of line search used. In order to obtain the global convergence of the TTHS method, Zhang truncated the search direction of the TTHS method. Numerical experiments in [12] show the truncated TTHS method is not very effective. In this paper, we further study the TTHS method. We prove that the TTHS method with standard Armijo line search is globally convergent for uniformly convex problems. To improve the efficiency of the truncated TTHS method, we propose a new truncated strategy to the TTHS method. Under suitable conditions, global convergence is obtained for the proposed method. Numerical experiments show that the proposed method outperforms the known CG_DESCENT method.The paper is organized as follows. In Section2, we propose our algorithm. Convergence analysis is provided under suitable conditions. Preliminary numerical results are presented in Section 3.


## 2. Global Convergence Analysis

Recently, Zhang [12] proposed a three-term modified HS method as follows
(2.1)dk={-gk,ifk=0,-gk+βkHSdk-1-θkyk-1,ifk>0,
where θk=gkTdk-1/dk-1Tyk-1. An attractive property of the TTHS method is that the direction always satisfies
(2.2)gkTdk=-∥gk∥2,
which is independent of the line search used. In order to obtain the global convergence of the TTHS method, Zhang truncated the TTHS method as follows
(2.3)dk={-gk,ifskTyk<ε1∥gk∥rskTsk,-gk+βkHSdk-1-θkyk-1,ifskTyk≥ε1∥gk∥rskTsk,
where ε1 and r are positive constants. Zhang proved that the truncated TTHS method converges globally with the Wolfe line search (1.4) and (1.6). However, numerical results show the truncated TTHS method is not very effective. In this paper, we will study the TTHS method again. In the rest of this section, we will establish two preliminary convergent results for the TTHS method.(i)
Uniformly convex functions: converge globally with the standard Armijo line search (1.7).(ii)
General functions: converge globally with the strong Wolfe line search (1.4) and (1.5) by using a new truncated strategy to the TTHS method.In order to establish the global convergence of our method, we need the following assumption.Assumption 2.1.
(i) The level setΩ={x∈Rn∣f(x)≤f(x0)} is bounded.
(ii) In some neighborhoodN of Ω,f is continuously differentiable and its gradient is Lipschitz continuous, namely, there exists a constant L>0 such that
(2.4)∥g(x)-g(y)∥≤L∥x-y∥,∀x,y∈N.Under Assumption2.1, It is clear that there exist positive constants B and γ such that
(2.5)∥x-y∥≤B∀x,y∈Ω,(2.6)∥g(x)∥≤γ∀x∈Ω.Lemma 2.2.
Suppose that Assumption2.1 holds. Consider {xk} be generated by the TTHS method, where αk is obtained by the Armijo line search (1.7), one has
(2.7)∑k=0∞∥gk∥4∥dk∥2<∞.Proof.
Ifαk=β, then
(2.8)δ1∥gk∥2=-δ1gkTdk≤1β[f(xk)-f(xk+1)].
Combining with
(2.9)∥gkTdk∥2≤∥gk∥2∥dk∥2,
yields
(2.10)∥gk∥4∥dk∥2≤∥gk∥2≤1βδ1(f(xk)-f(xk+1)).
On the other hand, if αk≠β, by the line search rule, then ρ-1αk does not satisfy (1.7). This implies
(2.11)f(xk+ρ-1αkdk)>f(xk)+δ1ρ-1αkgkTdk.
By the mean-value theorem, there exists μk∈(0,1) such that
(2.12)f(xk+ρ-1αkdk)=f(xk)+ρ-1αkg(xk+μkρ-1αkdk)Tdk.
This together with (2.11) implies
(2.13)(g(xk+μkρ-1αkdk)-gk)Tdk≥-(1-δ1)gkTdk.
Since g is Lipschitz continuous, the last inequality shows
(2.14)αk≥-(1-δ1)ρgkTdkL∥dk∥2=(1-δ1)ρ∥gk∥2L∥dk∥2.
That is
(2.15)f(xk+1)-f(xk)≤δ1αkgkTdk=-(1-δ1)δ1ρL∥gk∥4∥dk∥2.
This implies that there is a constant M1>0 such that
(2.16)∥gk∥4∥dk∥2≤M1(f(xk)-f(xk+1)).
Inequality (2.10) together with (2.16) shows that
(2.17)∥gk∥4∥dk∥2≤M2(f(xk)-f(xk+1)),
with some constant M2>0. Summing these inequalities, we obtain (2.7).The following theorem establishes the global convergence of the TTHS method with the standard Armijo line search (1.7) for uniformly convex problems.Theorem 2.3.
Suppose that Assumption2.1 holds and f is a uniformly convex function. Consider the TTHS method, where αk is obtained by the Armijo line search (1.7), one has that
(2.18)limk→∞inf∥gk∥=0.Proof.
We proceed by contradiction. If (2.18) does not hold, there exists a positive constant ε such that for all k(2.19)∥gk∥≥ε.
From Lemma 2.2, we get
(2.20)∑k=0∞1∥dk∥2<∞.
Since f is a uniformly convex function, there exists a constant μ>0 such that
(2.21)(g(x)-g(y))T(x-y)≥μ∥x-y∥2,∀x,y∈N.
This means
(2.22)dk-1Tyk-1≥μαk-1∥dk-1∥2.
By (2.1), (2.4), (2.6), and (2.22), one has
(2.23)∥dk∥≤∥gk∥+|βkHS|∥dk-1∥+|θk|∥yk-1∥≤∥gk∥+|βkHS|∥dk-1∥+∥gk∥∥dk-1∥|dk-1Tyk-1|∥yk-1∥≤∥gk∥+2∥gk∥∥dk-1∥|dk-1Tyk-1|∥yk-1∥≤∥gk∥+2L∥gk∥∥sk-1∥μαk-1∥dk-1∥2∥dk-1∥≤2L+μμγ.
This implies
(2.24)∑k=0∞1∥dk∥2≥∑k=0∞μ2(μ+2L)2γ2→∞.
This yield a contradiction with (2.20).We are going to investigate the global convergence of the TTHS method with the strong Wolfe line search (1.4) and (1.5). Similar to the PRP+ method [8], we restrict βkHS=max{βkHS,0}. In this case, the search direction (2.1) may not be a descent direction. Noting the search direction (2.1) can be rewritten as
(2.25)dk={-gk,ifk=0,-gk+βkdk-1-βkgkTdk-1gkTyk-1yk-1,ifk>0,
where βk=βkHS. Since the term gkTyk-1 may be zero in practice computation, we consider the following search direction
(2.26)dk={-gk,if|gkTyk-1|<c∥gk∥2,-gk+βkHS+dk-1-βkHS+gkTdk-1gkTyk-1yk-1,if|gkTyk-1|≥c∥gk∥2,
where c is a positive constant and βkHS+=max{βkHS,0}. It is clear that the relation (2.2) always holds. For simplicity, we regard the method defined by (1.2) and (2.26) as the method (2.26).Now, we describe a lemma for the search directions, which shows that they change slowly, asymptotically. The lemma is similar to [8, Lemma  3.4].Lemma 2.4.
Suppose that Assumption2.1 holds. Consider {xk} be generated the method (2.26), where αk is obtained by the strong Wolfe line search (1.4) and (1.5). If there exists a constant ε>0 such that for all k(2.27)∥gk∥≥ε,
then dk≠0 and
(2.28)∑k≥0∥uk+1-uk∥2<∞,
where uk=dk/∥dk∥.Proof.
Noting thatdk=0, for otherwise (2.2) would imply gk=0. Therefore, uk is well defined. Now, let us define rk=vk/∥dk∥ and δk=βkHS+(∥dk-1∥/∥dk∥), where
(2.29)vk=-(1+βkHS+gkTdk-1gkTyk-1)gk.
From (2.26), we have
(2.30)uk=rk+δkuk-1.
Since uk are unit vectors, we have
(2.31)∥rk∥=∥uk-δkuk-1∥=∥δkuk-uk-1∥.
Since δk>0, it follows that
(2.32)∥uk-uk-1∥≤∥(1+δk)(uk-uk-1)∥≤∥uk-δkuk-1∥+∥δkuk-uk-1∥=2∥rk∥.
Then we have
(2.33)∥uk-uk-1∥2≤4rk2.
Now, we evaluate the quantityvk. If gkTyk-1≥c∥gk∥2, by (1.5), we have
(2.34)dk-1Tyk-1=dk-1T(gk-gk-1)≥(σ-1)gk-1Tdk-1=(1-σ)∥gk-1∥2.
By the strong Wolfe condition (1.5) and the relation (2.2), we obtain
(2.35)|gkTdk-1|≤σ|gk-1Tdk-1|=σ∥gk-1∥2.
Inequalities (2.34) and (2.35) yield
(2.36)|gkTdk-1||dk-1Tyk-1|≤σ1-σ.
This implies
(2.37)∥vk∥≤(1+βkHS+|gkTdk-1gkTyk-1|)∥gk∥≤(1+|gkTdk-1dk-1Tyk-1|)∥gk∥≤11-σ∥gk∥.
If gkTyk-1<c∥gk∥2, then ∥vk∥=∥gk∥. The relation (2.37) also holds. It follows from the definition of rk, Lemma 2.2, (2.27) and (2.37) that
(2.38)∑k≥0rk2≤∑k≥0∥gk∥4(1-σ)2ε2∥dk∥2<∞.
By (2.33), we get the conclusion (2.28).The next theorem establishes the global convergence of method (2.26) with the strong Wolfe line search (1.4) and (1.5). The proof of the theorem is similar to [15, Theorem  3.2].Theorem 2.5.
Suppose that Assumption2.1 holds. Consider {xk} be generated by the method (2.26), where αk is obtained by the strong Wolfe line search (1.4) and (1.5), one has
(2.39)limk→∞inf∥gk∥=0.Proof.
We assume that the conclusion (2.39) is not true, then there exists a constant ε>0 such that for all k(2.40)∥gk∥≥ε.
The proof is divided into the following three steps.
Step 1.
A bound forβkHS+. From (2.4), (2.6), and (2.34), we get
(2.41)|βkHS+|≤|gkTyk-1dk-1Tyk-1|≤L∥gk∥·∥sk-1∥(1-σ)∥gk-1∥2≤Lγ∥sk-1∥(1-σ)ε2≜C1∥sk-1∥.Step 2.
A bound on the stepssk. This is a modified version of [8, Theorem  4.3]. Observe that for any l≥k,(2.42)xl-xk=∑j=kl-1xj+1-xj=∑j=kl-1∥sj∥uj=∑j=kl-1∥sj∥uk+∑j=kl-1∥sj∥(uj-uk).
Taking norms and by the triangle inequality to the last equality, we get from (2.5) that
(2.43)∑j=kl-1∥sj∥≤∥xl-xk∥+∑j=kl-1∥sj∥∥uj-uk∥≤B+∑j=kl-1∥sj∥∥uj-uk∥.
Let Δ be a positive integer, chosen large enough that
(2.44)Δ≥4BC,
where C=(1+σγ2/ε2)C1. By Lemma 2.4, we can chose k0 large enough that
(2.45)∑i≥k0∥ui+1-ui∥2≤14Δ.
If j>k≥k0 and j-k≤Δ, then by (2.45) and the Cauchy-Schwarz inequality, we have
(2.46)∥uj-uk∥≤∑i=kj-1∥ui+1-ui∥≤j-k(∑i=kj-1∥ui+1-ui∥2)1/2≤Δ(14Δ)1/2=12.
Combining this with (2.43) yields
(2.47)∑j=kl-1∥sj∥≤2B,
where l>k≥k0 and l-k≤Δ.Step 3.
A bound on the directiondl determined by (2.26). If glTyl-1≥c∥gl∥2, from (2.26), (2.27), (2.35), and (2.41), we have
(2.48)∥dl∥2≤(∥gl∥+βlHS+∥dl-1∥+βlHS+|glTdl-1|∥gl∥2yl-1)2≤(∥gl∥+(1+LBσγ2ε2)βlHS+∥dl-1∥)2≤2γ2+2(1+LBσγ2ε2)2C12∥sl-1∥2.
If glTyl-1<c∥gl∥2, then dl=-gl, we know that the relation (2.48) also holds. Define Si=2C2∥si∥2, we conclude that for l>k0,
(2.49)∥dl∥2≤2γ2(∑i=k0+1l∏j=il-1Sj)+∥dk0∥2∏j=k0l-1Sj.
Proceeding the similar proof as the case III of [15, Theorem  3.2], we get the conclusion.


## 3. Numerical Experiments

In this section, we report some numerical results. We tested 111 problems that are from the CUTE [13] library. We compared the performance of the method (2.26) with the CG_DESECENT method. The CG_DESECNT code can be obtained from Hager's web page at http://www.math.ufl.edu/hager/papers/CG.In the numerical experiments, we used the latest version—Source code Fortran 77 Version 1.4 (November 14, 2005) with default parameters. We implemented the method (2.26) with the approximate Wolfe line search in [5]. Namely, the method (2.26) used the same line search and parameters as the CG_DESECENT method. The stop criterion is that the inequality ∥g(x)∥∞≤max{10-8,10-12∥∇f(x0)∥∞} is satisfied or the iteration number exceeds 4×104. All codes were written in Fortran 77 and run on a PC with PIII 866 processor and 192 RAM memory and Linux operation system. Detailed results are  posted at the following web site: http://hi.814e.com/wanyoucheng/results.htm.We adopt the performance profiles by Dolan and Moré [14] to compare the performance between different methods. That is, for each method, we plot the fraction P of problems for which the method is within a factor τ of the best time. The left side of the figure gives the percentage of the test problems for which a method is the fastest; the right side gives the percentage of the test problems that are successfully solved by each of the methods. The top curve is the method that solved the most problems in a time that is within a factor τ of the best time.The curves in Figures1, 2, 3, and 4 have the following meaning:Figure 1
Performance based on the number of iteration.Figure 2
Performance based on the number of function evaluations.Figure 3
Performance based on the number of gradient evaluations.Figure 4
Performance based on CPU time.(i)
cg-descent: the CG_DSCENT method with the approximate Wolfe line search proposed by Hager and Zhang [15];(ii)
mhs+: the method (2.26) with the same line search as “cg-descent” and c=10-8.From Figures1–4, it is clear that the “mhs+” method outperforms the “cg-descent” method.



---

*Source: 875097-2009-07-15.xml*