# Nonlinear Conjugate Gradient Methods with Sufficient Descent Condition for Large-Scale Unconstrained Optimization

Authors: Jianguo Zhang; Yunhai Xiao; Zengxin Wei
Journal: Mathematical Problems in Engineering
 (2009)

---

## Abstract

Two nonlinear conjugate gradient-type methods for solving unconstrained optimization problems are proposed. An attractive property of the methods, is that, without any line search,
the generated directions always descend. Under some mild conditions, global convergence results for
both methods are established. Preliminary numerical results show that these proposed methods are
promising, and competitive with the well-known PRP method.


---

## Body

## 1. Introduction

In this paper, we consider the unconstrained optimization problem(1.1)min{f(x)∣x∈Rn},
where f:Rn→R is a continuously differentiable function, and its gradient at point xk is denoted by g(xk), or gk for the sake of simplicity. n is the number of variables, which is automatically assumed to be large. The iterative formula of nonlinear conjugate gradient method is given by
(1.2)xk+1=xk+αkdk,
where αk is a steplength, and dk is a search direction which is determined by
(1.3)dk={-g0,ifk=0,-gk+βkdk-1,ifk≥1,
where βk is a scalar. Since 1952, there have been many well-known formulas for the scalar βk, for example, Fletcher-Reeves (FR), Ploak-Ribiére-Polyak (PRP), Hestenes-Stiefel (HS), and Dai-Yuan (DY) (see [1–4]),
(1.4)βkFR=∥gk∥2∥gk-1∥2,βkPRP=gkTyk-1∥gk-1∥2,βkHS=gkTyk-1dk-1Tyk-1,βkDY=∥gk∥2dk-1Tyk-1,
where yk-1=gk-gk-1, symbol ∥·∥ denotes the Euclidean norm of vectors. Their corresponding methods generally specified as FR, PRP, HS, and DY conjugate gradient methods. If f is a strictly convex quadratic function, all these methods are equivalent in the case that an exact line search is used. If the objective function is nonconvex, their behaviors may be distinctly different. In the past two decades, the convergence properties of FR, PRP, HS, and DY methods have been intensively studied by many researchers (e.g., [5–13]).In practical computation, the HS and PRP methods, which share the common numeratorgkTyk-1, are generally believed to be the most efficient conjugate gradient methods, and have got meticulous in recent years. One remarkable property of both methods is that they essentially perform a restart if a bad direction occurs (see [7]). However, Powell [14] constructed an example showed that both methods can cycle infinitely without approaching any stationary point even if an exact line search is used. This counter-example also indicates that both methods have a drawback that they may not globally be convergent when the objective function is non-convex. Therefore, during the past few years, much effort has been investigated to create new formulae for βk, which not only possess global convergence for general functions but are also superior to original method from the computation point of view (see [15–22]). An excellent survey of nonlinear conjugate gradient methods with special attention to global convergence properties is made by Hager and Zhang [7].Recently, Dai and Liao [18] proposed two new formulae (called DL and DL+) for βk based on the secant condition from quasi-Newton method. More lately, Li, Tang, and Wei (see [20]) also presented another two formulae (called LTW and LTW+) based on a modified secant condition in [21]. In addition, the corresponding conjugate gradient method for βk with DL+ (or LTW+) converges globally for non-convex minimization problems, the reported numerical results showed that it excels the standard PRP method. However, the convergence result of the method for βk with formula DL (or LTW) has not been totally explored yet. In this paper, we further study conjugate gradient method for the solution of unconstrained optimization problems. Meanwhile, we focus our attention on the scalar for βk with DL (or LTW). Our motivation mainly comes from the recent work of Zhang et al. [22]. We introduce two versions of modified DL and LTW conjugate gradient-type methods. An attractive property of both proposed methods are that the generated directions are always descending. Besides, this property is independent of line search used and the convexity of objective function. Under some favorable conditions, we establish the global convergence of the proposed methods. We also do some numerical experiments by using a large set of unconstrained optimization problems, which indicate the proposed methods possess better performances when compared with the classic PRP method.We organize this paper as follows. In the next Section, we briefly review the conjugate gradient methods are proposed in [18, 20]. We present two conjugate gradient methods in Sections 3 and  4, respectively. Global convergence properties are also discussed simultaneously. In the last Section we perform the numerical experiments by using a set of large problems, and do some numerical comparisons with PRP method.


## 2. Conjugate Gradient Methods with Secant Condition

In this section we give a short description of the new conjugate gradient method of Dai and Liao in [18]. In the following, we also briefly review another effective conjugate gradient method of Li, Tang, and Wei in [20]. Motivated by the these methods, we introduce our new versions of conjugate gradient-type methods in the following sections.The following two assumptions are often utilized in convergence analysis for conjugate gradient algorithms.Assumption 2.1.
The objective functionf is bounded below, and the level set  ℱ={x∈Rn∣f(x)≤f(x0)} is bounded.Assumption 2.2.
In some neighborhood𝒩 of ℱ, f is differentiable and its gradient is Lipschitz continuous, namely, there exists a positive constant L such that
(2.1)∥g(x)-g(y)∥≤L∥x-y∥,∀x,y∈𝒩.The above assumption implies that there exists a positive constantγ¯ such that
(2.2)∥g(x)∥≤γ¯,∀x∈ℱ.


### 2.1. Dai-Liao Method

Note that, in quasi-Newton method, standard BFGS method, and limited memory BFGS method, the serch directiondk always have the common form
(2.3)dk=-Bk-1gk,
where Bk is some n×n symmetric and positive definite matrix satisfing the secant condition (or quasi-Newton equation)
(2.4)Bksk-1=yk-1.
Combing the above two equations, we obtain
(2.5)dkTyk-1=dkT(Bksk-1)=-gkTsk-1.
Keeping these relations in mind, Dai and Liao introduced the following conjugacy condition:
(2.6)dkTyk-1=-tgkTsk-1,
where t≥0 is a parameter. Multiplying (1.3) with yk-1 and making use of the new conjugacy condition (2.6), Dai and Liao obtained the following new formula for computing βk:
(2.7)βkDL=gkT(yk-1-tsk-1)dk-1Tyk-1,t≥0.
In order to ensure the global convergence for general functions, Dai and Liao restrict βk to be positive, that is,
(2.8)βkDL+=max{gkTyk-1dk-1Tyk-1,0}-tgkTsk-1dk-1Tyk-1,t≥0.
The reported numerical experiments showed that the corresponding conjugate gradient method is efficient.


### 2.2. Li-Tang-Wei Method

Recently, Wei et al. [21] proposed a modified secant condition
(2.9)Bksk-1=yk-1*=yk-1+λk-1sk-1,
where
(2.10)λk-1=2[f(xk-1)-f(xk)]+(gk+gk-1)Tsk-1∥sk-1∥2.Notice this new secant condition contains not only gradient value information, but also function value information at the present and the previous step. Additionally, this modified secant condition has inspired many further studies on optimization problems (e.g., [23–25]).Based on the modified secant condition (2.9), Li, Tang and Wei (see [20]) presented the new conjugacy condition:
(2.11)dkTyk-1*=-tgkTsk-1,t≥0.
Similar to the Dai-Liao formulas in (2.7) and (2.8), Li, Tang, and Wei also constructed the following two conjugate gradient formulas for βk:
(2.12)βkLTW=gkT(ỹk-1*-tsk-1)dk-1Tỹk-1*,t≥0,βkLTW+=max{gkTỹk-1*dk-1Tỹk-1*,0}-tgkTsk-1dk-1Tỹk-1*,t≥0,
where ỹk-1*=yk-1+max{λk-1,0}sk-1.Obviously, the new secant condition (2.11) gives a more accurate approximation for the Hessian of the objective function (see [21]). Hence the formulas (2.12) should outperform the Dai-Liao’s methods from theoretically, and the numerical results in [20] confirmed this claim. In addition, based on another modified quasi-Newton equation of Zhang et al. [26], Yabe and Takano [27] also proposed some similar conjugate gradient methods for unconstrained optimization.Combing with strong Wolfe-Powell line search, the conjugate gradient methods withβk from DL+ or LTW+ were proved convergent globally for non-convex minimization problems. But for βk from DL or LTW, there are no similar results. The major contribution of our following work is to circumvent this difficulty. However, our attention does not focus on the general iterative style (1.3), our idea mainly originate from the very recently three-term conjugate gradient method of Zhang et al. [22].


## 2.1. Dai-Liao Method

Note that, in quasi-Newton method, standard BFGS method, and limited memory BFGS method, the serch directiondk always have the common form
(2.3)dk=-Bk-1gk,
where Bk is some n×n symmetric and positive definite matrix satisfing the secant condition (or quasi-Newton equation)
(2.4)Bksk-1=yk-1.
Combing the above two equations, we obtain
(2.5)dkTyk-1=dkT(Bksk-1)=-gkTsk-1.
Keeping these relations in mind, Dai and Liao introduced the following conjugacy condition:
(2.6)dkTyk-1=-tgkTsk-1,
where t≥0 is a parameter. Multiplying (1.3) with yk-1 and making use of the new conjugacy condition (2.6), Dai and Liao obtained the following new formula for computing βk:
(2.7)βkDL=gkT(yk-1-tsk-1)dk-1Tyk-1,t≥0.
In order to ensure the global convergence for general functions, Dai and Liao restrict βk to be positive, that is,
(2.8)βkDL+=max{gkTyk-1dk-1Tyk-1,0}-tgkTsk-1dk-1Tyk-1,t≥0.
The reported numerical experiments showed that the corresponding conjugate gradient method is efficient.


## 2.2. Li-Tang-Wei Method

Recently, Wei et al. [21] proposed a modified secant condition
(2.9)Bksk-1=yk-1*=yk-1+λk-1sk-1,
where
(2.10)λk-1=2[f(xk-1)-f(xk)]+(gk+gk-1)Tsk-1∥sk-1∥2.Notice this new secant condition contains not only gradient value information, but also function value information at the present and the previous step. Additionally, this modified secant condition has inspired many further studies on optimization problems (e.g., [23–25]).Based on the modified secant condition (2.9), Li, Tang and Wei (see [20]) presented the new conjugacy condition:
(2.11)dkTyk-1*=-tgkTsk-1,t≥0.
Similar to the Dai-Liao formulas in (2.7) and (2.8), Li, Tang, and Wei also constructed the following two conjugate gradient formulas for βk:
(2.12)βkLTW=gkT(ỹk-1*-tsk-1)dk-1Tỹk-1*,t≥0,βkLTW+=max{gkTỹk-1*dk-1Tỹk-1*,0}-tgkTsk-1dk-1Tỹk-1*,t≥0,
where ỹk-1*=yk-1+max{λk-1,0}sk-1.Obviously, the new secant condition (2.11) gives a more accurate approximation for the Hessian of the objective function (see [21]). Hence the formulas (2.12) should outperform the Dai-Liao’s methods from theoretically, and the numerical results in [20] confirmed this claim. In addition, based on another modified quasi-Newton equation of Zhang et al. [26], Yabe and Takano [27] also proposed some similar conjugate gradient methods for unconstrained optimization.Combing with strong Wolfe-Powell line search, the conjugate gradient methods withβk from DL+ or LTW+ were proved convergent globally for non-convex minimization problems. But for βk from DL or LTW, there are no similar results. The major contribution of our following work is to circumvent this difficulty. However, our attention does not focus on the general iterative style (1.3), our idea mainly originate from the very recently three-term conjugate gradient method of Zhang et al. [22].


## 3. Modified Dai-Liao Method

As we have stated in the previous section, the standard conjugate gradient method with (1.2)-(1.3) and (2.7) cannot guarantee the sequence {xk} approaches to any stationary point of the problem. In this section, we will appeal to a three-term form to take the place of (1.3).The first three-term nonlinear conjugate gradient algorithm was presented by Nazareth [28], in which the search direction is determined by
(3.1)dk+1=-yk+ykTykykTdkdk+yk-1Tykyk-1Tdk-1dk-1
with d-1=0, d0=-g0. The main property of dk is that, for a quadratic function, it remains conjugate even without exact line searches. Recently, Zhang et al. [22] proposed a descent modified PRP conjugate gradient method with three terms as follows:
(3.2)dk={-g0,ifk=0,-gk+βkPRPdk-1-θkyk-1,ifk≥1,
where θk=gkTdk-1/∥gk-1∥2. A remarkable property of the method is that it produces a descent direction at each iteration. Motivated by the nice descent property, we also give a three-term conjugate gradient method based on the DL formula for βk in (2.7), that is,
(3.3)dk={-g0,ifk=0,-gk+βkDLdk-1-ξk(yk-1-tsk-1),ifk≥1,
where t≥0 and ξk=gkTdk-1/dk-1Tyk-1. It is easy to see that the sufficient descent condition also holds true if no line search is used, that is,
(3.4)gkTdk=-∥gk∥2.In order to achieve the global convergence result of the PRP method, Grippo and Lucidi [9] proposed a new line search below. For given constants τ>0, δ>0, and λ∈(0,1), let
(3.5)αk=max{λjτ|gkTdk|∥dk∥2;j=0,1,…}
satisfy
(3.6)f(xk+1)≤f(xk)-δαk2∥dk∥2,-c1∥g(xk+1)∥2≤g(xk+1)Tdk+1≤-c2∥g(xk+1)∥2,
where 0<c2<1<c1 are constants. Here we prefer this new line search to the classical Armijo one for the sake of a greater reduction of objective function and wider tolerance of α∥dk∥ (see [9]).Introducing the line search rule, we are now ready to state the steps of the modified Dai-Liao (MDL) conjugate gradient-type algorithm as follows.Algorithm 3.1 (MDL).
Step 1.
Givenx0∈Rn. Let 0<δ<σ<1, t≥0 and d0=-g0. Set k:=0.
Step 2.
If∥gk∥=0 then stop.
Step 3.
Computedk by (3.3).
Step 4.
Find the steplengthαk satisfying
(3.7)f(xk+αkdk)-f(xk)≤-δαk2∥dk∥2,(3.8)g(xk+αkdk)Tdk≥σgkTdk.
Let xk+1=xk+αkdk.
Step 5.
Setk:=k+1, go to Step 2.From now on, we usefk to denote f(xk). For MDL algorithm, we have the following two important results. The proof of the following first lemma was established by Zoutendijk [29], where it is stated for slightly different circumstances. For convenience, we give the detailed proof here.Lemma 3.2.
Consider the conjugate gradient-type method in the form (1.2) and (3.3), and let the steplength αk be obtained by the line search (3.7)-(3.8). Suppose that Assumptions 2.1-2.2 hold. Then one has
(3.9)∑k=0∞αk2∥dk∥2<∞.Proof.
Sinceαk is obtained by the line search (3.7)-(3.8). Then, by (3.4) and (3.7) we have
(3.10)fk+1-fk≤-δαk2∥dk∥2≤0.
Hence, {fk} is a decreasing sequence and the sequence {xk} is contained in ℱ. Hence, Assumptions 2.1-2.2 imply that there exists a constant f* such that
(3.11)limk→∞fk=f*.
From (3.11), we have
(3.12)∑k=0∞(fk-fk+1)<+∞.
This together with (3.10) implies that (3.9) holds.Lemma 3.3.
If there exists a constantϵ>0 such that
(3.13)∥gk∥≥ϵ,∀k≥0,
then there exists a constant M>0 such that
(3.14)∥dk∥≤M,∀k≥0.Proof.
From the line search (3.7)-(3.8) and (3.4), we have
(3.15)yk-1Tdk-1=gkTdk-1-gk-1Tdk-1≥-(1-σ)gk-1Tdk-1=(1-σ)∥gk-1∥2.
By the definition of dk in (3.3) , we get from (2.1), (2.2), (3.4), and (3.13) that
(3.16)∥dk∥≤∥gk∥+2∥gk∥∥yk-1-tsk-1∥∥dk-1∥(1-σ)∥gk-1∥2≤γ¯+2(L+t)γ¯αk-1∥dk-1∥(1-σ)ϵ2∥dk-1∥.
Lemma 3.2 indicates that αkdk→0 as k→∞, then there exists a constant γ∈(0,1) and an integer k0, such that the following inequality holds for all k≥k0:
(3.17)2(L+t)γ¯(1-σ)ϵ2αk-1∥dk-1∥≤γ.
Hence, we have for any k>k0(3.18)∥dk∥≤γ¯+γ∥dk-1∥≤γ¯(1+γ+γ2+⋯+γk-k0-1)+γk-k0∥dk0∥≤γ¯1-γ+∥dk0∥.
Setting M=max{∥d1∥,∥d2∥,…,∥dk0∥,γ¯/(1-γ)+∥dk0∥}, we deduce that ∥dk∥≤M for all k.Using the preceding lemmas, we are now ready to give the promised convergence results.Theorem 3.4.
Suppose that Assumptions2.1-2.2 hold. Let {xk} be generated by Algorithm MDL. Then one has
(3.19)liminfk→∞∥gk∥=0.Proof.
We proceed by contradiction. Assume that the conclusion is not true. Then there exists a positive constantϵ such that
(3.20)∥gk∥≥ϵ,∀k≥0.
Ifliminfk→∞αk>0, we have from (3.9) that liminfk→∞∥gk∥=0. This contradicts assumption (3.20).
Suppose thatliminfk→∞αk=0. Using Assumptions 2.1-2.2 and (3.8), we obtain
(3.21)-(1-σ)gkTdk≤(gk+1-gk)Tdk≤Lαk∥dk∥2.
Combining with (3.4) yields
(3.22)(1-σ)∥gk∥2≤Lαk∥dk∥2.
The above inequality and Lemma 3.3 imply liminfk→∞∥gk∥=0, which contradicts (3.20). This completes the proof.


## 4. Modified Li-Tang-Wei Method

In a similar manner, we provide a modified Li-Tang-Wei method with three terms in the form:(4.1)dk={-g0,ifk=0,-gk+βkLTWdk-1-ζk(ỹk-1*-tsk-1),ifk≥1,
where ζk=gkTdk-1/dk-1Tỹk-1*. It is not difficult to see that the sufficient descent property (3.4) also holds.Combing with the line search (3.7)-(3.8), we state the steps of the modified Li-Tang-Wei (MLTW) conjugate gradient-type algorithm as follows.Algorithm 4.1 (MLTW).
Step 1.
Givenx0∈Rn. Let 0<δ<σ<1, t≥0 and d0=-g0. Set k:=0.
Step 2.
If∥gk∥=0 then stop.
Step 3.
Computedk by (4.1).
Step 4.
Find the steplengthαk satisfying (3.7)-(3.8). Let xk+1=xk+αkdk.
Step 5.
Setk:=k+1, go to Step 2.Lemma 4.2.
Consider the conjugate gradient-type method in the forms (1.2) and (4.1), let the steplength αk be obtained by the line search (3.7)-(3.8). Suppose that Assumptions 2.1-2.2 hold. Then one has
(4.2)∑k=0∞αk2∥dk∥2<∞.Proof.
See Lemma3.2.Lemma 4.3.
Consider the conjugate gradient-type method in the form (1.2) and (4.1), let the steplength αk be obtained by line search (3.7)-(3.8). Suppose that Assumptions 2.1-2.2 hold. Then one has
(4.3)∥ỹk*∥≤2L∥sk∥,
where L was defined as in Assumption 2.2.Proof.
Sinceαk is obtained by (3.7)-(3.8), from (3.10) we know that
(4.4)xk∈ℱ,∀k≥1.
By mean value theorem, we know that there exists ηk∈[0,1] such that
(4.5)fk+1-fk=g(xk+ηk(xk+1-xk))T(xk+1-xk)=g(xk+ηksk)Tsk.
Using (4.4) we get
(4.6)xk+ηksk=xk+ηk(xk+1-xk)∈co¯ℱ,
where co¯ℱ denotes the closed convex hull of ℱ. It follows from the definition of λk and (4.5) that
(4.7)λk=2[f(xk)-f(xk+1)]+(gk+1+gk)Tsk∥sk∥2=[gk+gk+1-2g(xk+ηksk)]Tsk∥sk∥2≤(∥gk-g(xk+ηksk)∥+∥gk+1-g(xk+ηksk)∥)∥sk∥2∥sk∥≤(Lηk∥sk∥+L(1-ηk)∥sk∥)∥sk∥2∥sk∥=L.
From the definition of ỹk* and Assumption 2.2, we know that
(4.8)∥ỹk*∥=∥yk+max{λk,0}sk∥≤∥yk+Lsk∥≤∥yk∥+L∥sk∥≤2L∥sk∥.
This verifies our claims.Lemma 4.4.
If there exists a constantϵ>0 such that
(4.9)∥gk∥≥ϵ,∀k≥0,
then there exists a constant M>0 such that
(4.10)∥dk∥≤M,∀k≥0.Proof.
From the line search (3.7)-(3.8) and (3.4), we have
(4.11)dk-1Tỹk-1*=dk-1T(yk-1+max{λk-1,0}sk-1)≥dk-1Tyk-1≥-(1-σ)gk-1Tdk-1=(1-σ)∥gk-1∥2.
According to the definition of dk in (4.1), we get from (2.1), (2.2), (4.9), and (4.11) that
(4.12)∥dk∥≤∥gk∥+2∥gk∥∥ỹk-1*-tsk-1∥∥dk-1∥(1-σ)∥gk-1∥2≤γ¯+2γ¯(2L+t)αk-1∥dk-1∥(1-σ)ϵ2∥dk-1∥.
Lemma 4.3 shows that αkdk→0 as k→∞. Hence there exists a constant γ∈(0,1) and an integer k0, such that the following inequality holds for all k≥k0:
(4.13)2(2L+t)γ¯(1-σ)ϵ2αk-1∥dk-1∥≤γ.
Hence, we have for any k>k0(4.14)∥dk∥≤γ¯+γ∥dk-1∥≤γ1(1+γ+γ2+⋯+γk-k0-1)+γk-k0∥dk0∥≤γ¯1-γ+∥dk0∥.
Let M=max{∥d1∥,∥d2∥,…,∥dk0∥,γ¯/(1-γ)+∥dk0∥}, we get (4.10).Now we can establish the following global convergence theorem for MLTW method. Since its proof is essentially similar to Theorem3.4, we omit it.Theorem 4.5.
Suppose that Assumptions2.1-2.2 hold. Let {xk} be generated by Algorithm MLTW. Then one has
(4.15)liminfk→∞∥gk∥=0.Proof.
Omitted.To end of this section, we show that MLWT method is equivalent to all the general method (1.4) if an exact line search is used. In deriving this equivalence, we work with an exact line search rule, that is, we compute αk such that
(4.16)f(xk+αkdk)=minα≥0f(xk+αdk)
is satisfied. Hence,
(4.17)∇f(xk+αkdk)Tdk=0.
Subsequently,
(4.18)ζk=gkTdk-1dk-1Tỹk-1*=0.
Moreover, let
(4.19)f(x)=12xTGx+bTx+c,
where G is an n×n symmetric positive definite matrix, b∈Rn, and c is a real number. In this case, it is not difficult to see that λk-1=0. Note that by the definition of βkLWT in (2.12), we have
(4.20)βkMLWT=gkT(ỹk-1*-tsk-1)dk-1Tỹk-1*=gkTỹk-1*dk-1Tỹk-1*=gkTyk-1dk-1Tyk-1=βkHS.
Then we have the main properties of a conjugate gradient method. The following theorem shows that MLWT method have quadratic termination property, which means that the method terminates at most n steps when it is applied to a positive definite quadratic. The proof can be found in Theorem 4.2.1 in [30] and is omitted.Theorem 4.6.
For a positive definite quadratic function (4.19), the conjugate gradient method (1.2)–(4.1) with exact line search terminates after m≤n steps, and the following properties hold for all i, (0≤i≤m),
(4.21)diTGdj=0,j=0,1,…,i-1,giTgj=0,j=0,1,…,i-1,diTgi=-giTgi,
where m is the number of distinct eigenvalues of G.The theorem also shows that conjugate gradients (1.2)–(4.1) represent conjugacy of directions, orthogonality of gradients, and descent condition. This also indicates that methods (1.2)–(4.1) preserve the property of being equivalent to the general conjugate gradient method (1.4) for strict convex quadratics with exact line search. The cases of DL, LWT, and MDL can be proved in a similar way.


## 5. Numerical Experiments

The main work of this section is to report the performance of the algorithms MDL and MLTW on a set of test problems. The codes were written in Fortran77 and in double precision arithmetic. All the tests were performed on a PC (Intel Pentium Dual E2140 1.6 GHz, 256 MB SDRAM). Our experiments were performed on a set of 73 nonlinear unconstrained problems that have second derivatives available. These test problems are contributed by N. Andrei, and the Fortran expression of their functions and gradients are available at http://www.ici.ro/camo/neculai/SCALCG/evalfg.for.  26 out of these problems are from CUTE [31] library. For each test function we have considered 10 numerical experiments with number of variables n=1000,2000,…,10000.In order to assess the reliability of our algorithms, we also tested these methods against the well-known routine PRP using the same problems. The PRP code is coauthored by Liu, Nocedal, and Waltz, it can be obtained from Nocedal’s web page athttp://www.ece.northwestern.edu/~nocedal/software.html/. While running of the PRP code, default values were used for all parameters. All these algorithms terminate when the following stopping criterion is met:
(5.1)∥gk∥≤10-5.
We also force these routines stopped if the iterations exceed 1000 or the number of function evaluations reach 2000 without achieving convergence. In MDL and MLTW, we use δ=10-4, σ=0.1. Moreover, we also test our proposed methods MDL and MLTW with different parameters t to see that t=1.0 is the best choice. Since a large set of problems is used, we describe the results fully on the first author's web page at the web site:  http://maths.henu.edu.cn/szdw/teachers/xyh.htm. The tables contain the number of the problem (Problem), the dimension of the problem (Dim), the Number of iterations (Iter), the number of function and gradient evaluations (Nfcnt), the CPU time required in seconds (Time), the final function value (Fv), and norm of the final gradient (Norm).There are30 problems that were excluded from the first two tables because they lead an “overflow error” when evaluated at some point by MDL and MLWT methods. However, the same error was occurred on 43 problems when evaluated by PRP method. From these tables, we also see that MDL and MLWT failed to satisfy the termination condition (5.1) on other 66 and 81 problems, respectively. But PRP method cannot achieve convergence on 89 problems. So only 634 problems remain where at least one method runs successfully. Now, we change our attention to consider the function values of the remaining problems founded by all three methods. We note that, on 592 problems, the differences of these functional values obtained by each method is less than the pretty small tolerance 10-7. Therefore, it is reasonable to think that all the three methods obtained the same optimal solution on these problems.To approximatively assess the performance of MDL, MLWT, and PRP methods on the remaining592 problems, we use the profile of Dolan and Moré [32] as an evaluated tool. That is, for subset of the methods being analyzed, we plot the fraction P of problems for which any given method is within a factor τ of the best. Meanwhile, we use the iterations, function and gradient evaluations, and CPU time consuming as performance measure, since they reflect the main computational cost and the efficiency for each method. The performance profiles of all three methods are plotted in Figures 1, 2, and 3.Figure 1
Performance profiles based on iterations.Figure 2
Performance profiles based on function and gradient evaluations.Figure 3
Performance profiles based on function and gradient evaluations.Observing Figures1 and 2, respectively, it concludes that MDL and MLWT are always the top performer for almost all values of τ, which shows that they perform better than PRP method regarding iterations, function, and gradient evaluations. Figure 3 shows the implementation of the these methods using the total CPU time as a measure. This figure shows that PRP method is faster than the others. Why do our methods need more computing time though requiring less iterations? We think that it is highly possible that our new version of formula is a somewhat more complicated than the standard PRP method.Taking everything into consideration and albeit both proposed conjugate gradient methods did not obtain significant development as we have expected, we think that, for some specific problems, the enhancement of the proposed methods are still noticeable. Hence, we believe that each one of the new algorithm is a valid approach for the problems and has its own potential.



---

*Source: 243290-2009-07-01.xml*