# Two Modified Three-Term Type Conjugate Gradient Methods and Their Global Convergence for Unconstrained Optimization

Authors: Zhongbo Sun; Yantao Tian; Hongyang Li
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Two modified three-term type conjugate gradient algorithms which satisfy both the descent condition and the Dai-Liao type conjugacy condition are presented for unconstrained optimization. The first algorithm is a modification of the Hager and Zhang type algorithm in such a way that the search direction is descent and satisfies Dai-Liao’s type conjugacy condition. The second simple three-term type conjugate gradient method can generate sufficient decent directions at every iteration; moreover, this property is independent of the steplength line search. Also, the algorithms could be considered as a modification of the MBFGS method, but with differentzk. Under some mild conditions, the given methods are global convergence, which is independent of the Wolfe line search for general functions. The numerical experiments show that the proposed methods are very robust and efficient.


---

## Body

## 1. Introduction

We will consider the following optimization problem:(1)min⁡fx,x∈Rn,
where f(x):Rn→R is continuously differentiable function whose gradient is ∇f(x), and ∇f(x) is denoted by g(x).Conjugate gradient method is very efficient for large-scale optimization problems. Generally, this method generates a sequence of iterations:(2)xk+1=xk+αkdk,k=0,1,…,
where the step size αk is obtained by carrying out some line search rules. The line search in conjugate gradient algorithms is often based on the following Wolfe conditions:
(3)f(xk+αkdk)-f(xk)≤δαkgkTdk,gxk+αkdkTdk≥σgkTdk,
where 0<δ≤σ<1. The direction dk is defined by
(4)dk=-gkifk=0,-gk+βkdk-1ifk>0,
where βk is conjugate gradient parameter.Some conjugate gradient methods include the Fletcher-Reeves method (FR), the Hestenes-Stiefel method (HS), the Polak-Ribiere-Polyak method (PRP), the conjugate descent method (CD), the Liu-Storey method (LS), and the Dai-Yuan method (DY) [2–8]. In these methods, the difference is parameter βk; the parameters βk of these methods are specified as follows:
(5)βkFR=gk+12gk2,βkDY=gk+12ykTdk,βkCD=-gk+12gkTdk,βkHS=gk+1TykykTdk,βkPRP=gk+1Tykgk2,βkLS=-gk+1TykgkTdk,
where sk=xk+1-xk=αkdk, gk=∇f(xk), and yk=gk+1-gk. Throughout this paper, we always use ∥·∥ to mean the Euclidean norm.


## 2. Motivation

In this paper, the motivation will be described as follows. Firstly, we will introduce some modified three-term conjugate gradient methods. One of the first three-term conjugate gradient methods was proposed by Beale [9] as
(6)dk+1=-gk+1+βkdk+γkdt,
where βk=βkHS(βkFR,βkDYetc.),
(7)γk=0,ifk=t+1,gk+1TytdtTyt,ifk>t+1,
and dt is a restart direction. McGuire and Wolfe [10] and Powell [11] made further study on Beale’s three-term conjugate gradient method. Dai and Yuan [12] studied the general three-term conjugate gradient method:
(8)dk+1=-gk+1+βkdk+γkdt(p),
where t(p) is the number of the pth restart iteration, showing that under some mild conditions the algorithm was global convergence. As we know, Dai and Liao [13] extended the classical conjugate condition ykTdk+1=0, suggesting the following one:
(9)ykTdk+1=-tskTgk+1,
where t≥0 is a scalar. Recently, Andrei [14, 15] developed two simple three-term conjugate gradient methods for unconstrained optimization problems. In [14], for the descent condition and Dai-Liao’s type conjugacy condition, the three-term conjugate gradient algorithm was satisfied at every step. The direction dk+1 was computed as
(10)dk+1=-gk+1-δksk-ηkyk,δk=1+yk2ykTskskTgk+1ykTsk-ykTgk+1ykTsk,ηk=skTgk+1ykTsk,
where δk and ηk were parameters. Similarly, Andrei [15] presented another project three-term conjugate gradient algorithm. The search direction of the algorithms from this class had three terms and was computed as modifications of the classical conjugate gradient algorithms. The search direction also satisfied both descent property and Dai-Liao’s type conjugacy conditions. Yao and Qin [16] proposed a hybrid of DL and WYL conjugate gradient methods. The given method [17] possessed the sufficient descent condition under the Wolfe-Powell line search and is global convergence for general functions. Thereafter, they proposed a new conjugacy condition and nonlinear conjugate gradient method; the given method [17] was global convergence under the strong Wolfe-Powell line search. By modifying the HS method or Hager and Zhang method [18], the above methods with satisfying the conjugacy condition type were concluded.In this paper, we present two modified simple three-term type conjugate gradient methods which are obtained by a modified BFGS (MBFGS) updating scheme of the inverse approximation of the Hessian of the functionf(x) restart as the identity matrix at every step. Firstly, in order to interpret the idea of this paper, it is necessary to introduce the MBFGS method [1]. If the objective function f(x) is nonconvex, the classical Newton direction may not be a descent direction of f(x) at xk since the Hessian matrix Bk is not necessarily positive definite. To overcome this drawback, Li and Fukushima [1] generated a direction from
(11)(Bk+rkI)dk+gk=0,
where I was the unit matrix and a positive constant rk was chosen so that Bk+rkI was a positive definite matrix. In order to obtain the global convergence, the sequence {rk} was bounded above. For the sake of the superlinear convergence, the positive constants rk should satisfy rk→0 as k→∞. If the MBFGS method was quadratic convergence, the positive constants rk should meet rk≤C∥gk∥ for all k. In other words, the global and superlinear convergence of MBFGS method depends on the choice of {rk}. Therefore, it was important to select {rk} appropriately so that it was practicable and satisfied the above conditions. How to select the optimal {rk} is very difficult for us. Actually, the MBFGS method was a modified quasi-Newton method for nonconvex unconstrained optimization problems. In order to better introduce our method, let us simply recall the MBFGS quasi-Newton method. The direction dk in the MBFGS method is given by
(12)dk=-Bk+rkI-1gk,
where Bk is obtained by the MBFGS formula:
(13)Bk+1=Bk-BkskskTBkskTBksk+zkzkTzkTsk.
From the above MBFGS formula, zk is computed as the following two cases. On the one hand,
(14)zk=yk+rksk,
where sk=xk+1-xk and rk∈[0,C]; C is a constant. On the other hand,
(15)zk=yk+t¯kgksk,
where rk=t¯k∥gk∥ and t¯k=1+max⁡{0,-ykTsk/∥sk∥2}.The MBFGS updating of the inverse approximate of the Hessian of functionf(x) is
(16)Bk+1=Bk+(sk-Bkzk)skT+sksk-BkzkTskTzk-zkT(sk-Bkzk)skTzk2skskT=I-skzkTskTzkBkI-zkskTskTzk+skskTskTzk=Bk-skzkTBk+BkzkskTzkTsk+1+zkTBkzkzkTskskskTskTzk.In order to compass our object we take a little modification of the inverse MBFGS matrixBk, namely, Bk=I; then (16) will be formulated as
(17)Qk=I-skzkT+zkskTzkTsk+1+zkTzkzkTskskskTskTzk,
but with different zk. In this paper, we compute zk as follows:
(18)zk=yk+Cgkrsk+max⁡0,-ykTsksk2sk.
From the above formula, we can see that it does not include the rk, so we need not choose the parameters {rk}. Furthermore, there is more information in zk, for instance, the gradient of f(x) at xk, that is, gk and the constants C,r. The most important property of zk is that zk satisfies the Dai-Liao condition; that is,
(19)zkTdk+1=-tkskTgk+1,
where tk=1+2∥zk∥2/zkTsk>0. Moreover, zk also satisfies the following inequality:
(20)zkTsk>0.
However, Li and Fukushima [1] proved that the zk could satisfy the following inequality:
(21)zkTsk≥gksk2≥0.
The purpose of this paper is to overcome these drawbacks. Observe that the direction dk+1 can be written as
(22)dk+1=-Qkgk+1;
therefore, the three-term type conjugate gradient algorithm is given by (2), where the direction is computed as
(23)dk+1=-gk+1,ifk=0,-gk+1-λksk-μkzk,ifk>0,
where
(24)λk=1+zk2zkTskskTgk+1zkTsk-zkTgk+1zkTsk,μk=skTgk+1zkTsk.We organize the paper as follows. In the next section, we describe the three-term type conjugate gradient method and its global convergence. In Section4, we discuss another modified sufficient descent three-term type conjugate gradient method for unconstrained optimization problems and its global convergence with Wolfe line search. In Section 5, some numerical results are given. Some conclusions and future works will be proposed in the last section.


## 3. Three-Term Conjugate Gradient Method and Its Global Convergence

In this section, we will introduce the three-term type conjugate gradient method.Algorithm 1.
Step
1 (initialization and date). Given x0∈Rn,0<δ≤σ<1. Let k:=0.
Step
2. Test a criterion for stopping the iterations. If the test criterion ∥gk∥≤ϵ is satisfied, then STOP! Otherwise, continue with Step 3.
Step
3. The direction dk is computed as follows:
(25)dk+1=-gk+1,ifk=0,-gk+1-λksk-μkzk,ifk>0,
where λk=(1+∥zk∥2/zkTsk)skTgk+1/zkTsk-zkTgk+1/zkTsk,μk=skTgk+1/zkTsk, and
(26)zk=yk+Cgkrsk+max⁡0,-ykTsksk2sk,C,r>0 are constants.
Step
4. The Wolfe line search is to find a stepsize
(27)αk=max⁡ρj∣j=0,1,2,…
satisfying
(28)f(xk+αkdk)-f(xk)≤δαkgkTdk,gxk+αkdkTdk≥σgkTdk,
where ρ∈(0,1) are constants.
Step
5. Update the variables:
(29)xk+1=xk+αkdk,
and then go to Step 2.


### 3.1. Global Convergence

Throughout this section, we assume that(H1)
the level setΩ={x∈Rn∣f(x)≤f(x0)} is bounded;(H2)
in a neighborhoodN of Ω the function f(x) is continuously differentiable. Its gradient is Lipschitz continuous; namely, there exists a constant L>0, such that
(30)∇f(x)-∇f(y)≤Lx-y,∀x,y∈N. Since {f(xk)} is decreasing, it is clear that the sequence {xk} generated by Algorithm 1 is contained in Ω. In addition, we can obtain from Algorithm 1 that there is constant κ, such that
(31)∇f(x)≤κ,∀x∈Ω.Lemma 2.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); then one has
(32)zkTsk>0.Proof.
By direct computation,(33)zkTsk=ykTsk+CgkrskTsk+max⁡0,-ykTsksk2skTsk=ykTsk+Cgkrsk2+max⁡⁡0,-ykTsksk2sk2≥ykTsk>0.Lemma 3.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has
(34)gk+1Tdk+1≤0.Proof.
We will divide (25) into two cases as follows.
Case
1. If k=0, then Lemma 3 is true.
Case
2. If k>0, combined with Lemma 2, then we have
(35)gk+1Tdk+1=gk+1T(-gk+1-λksk-μkzk)=-gk+12-1+zk2zkTskskTgk+12zkTsk≤0.
The proof of Lemma 3 is completed.Lemma 4.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has Dai-Liao’s type conjugate condition
(36)zkTdk+1=-tkskTgk+1,
where tk>0.Proof.
By direct computation, we get(37)zkTdk+1=zkT(-gk+1-λksk-μkzk)=-zkTgk+1-1+zk2zkTskskTgk+1+zkTgk+1-skTgk+1zkTskzk2=-1+2zk2zkTskskTgk+1=-tkskTgk+1,
where
(38)tk=1+2zk2zkTsk>0,
since zkTsk>0.Remark 5.
Observe that the directiondk+1 satisfies descent property. Besides, the direction dk+1 satisfies Dai-Liao’s type conjugacy condition, where tk>0 at every iteration.Theorem 6.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has
(39)zk≤ν1dk,λk≤ν2,μk≤ν3.Proof.
By direct computation, we have(40)zk≤yk+Cgkrsk+max⁡0,-ykTsksk2sk≤Ldk+Cgkrdk+Ldk=(2L+Cκr)dk=ν1dk,
where ν1=2L+Cκr. Consider
(41)λk≤1+zk2zkTskskTgk+1zkTsk+zkTgk+1zkTsk≤1+zk2ykTskskTgk+1ykTsk+zkTgk+1ykTsk≤1+zk21-σdk21(1-σ)+ν1(1-σ)≤1+κ21-σ1(1-σ)+ν1(1-σ)=ν2,
where ν2=1+κ2/1-σ1/(1-σ)+ν1/(1-σ). Consider
(42)μk=skTgk+1zkTsk≤skTgk+1ykTsk≤11-σ=ν3,
where ν3=1/1-σ. The proof is completed.Theorem 7.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has
(43)dk+1≤ωgk+1.Proof.
According to Algorithm1, we will divide (28) into two cases as follows.
Case
1. If k=0, we get dk+1=-gk+1, and then
(44)dk+1=gk+1,
where ω=1.
Case
2. If k>0, we have
(45)dk+1=-gk+1-λksk-μkzk,
and then
(46)dk+1≤gk+1+λksk+μkzk≤gk+1+1+zk2zkTskskTgk+1zkTsksk+zkTgk+1zkTsksk+skTgk+1zkTskzk≤gk+1+1+zk2zkTskskgk+1zkTsksk+zkgk+1zkTsksk+skgk+1zkTskzk=ωgk+1.
The proof is true.Theorem 8.
Let assumption (H1) hold and let{xk} and {dk} be generated by the three-term conjugate gradient method. If stepsize αk is obtained by the Wolfe line search, then one has
(47)lim⁡k→∞inf⁡gk=0.Proof.
By the use of Theorem7 and the same argument as Theorem 4.1 in [19], we will omit the proof here.


## 3.1. Global Convergence

Throughout this section, we assume that(H1)
the level setΩ={x∈Rn∣f(x)≤f(x0)} is bounded;(H2)
in a neighborhoodN of Ω the function f(x) is continuously differentiable. Its gradient is Lipschitz continuous; namely, there exists a constant L>0, such that
(30)∇f(x)-∇f(y)≤Lx-y,∀x,y∈N. Since {f(xk)} is decreasing, it is clear that the sequence {xk} generated by Algorithm 1 is contained in Ω. In addition, we can obtain from Algorithm 1 that there is constant κ, such that
(31)∇f(x)≤κ,∀x∈Ω.Lemma 2.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); then one has
(32)zkTsk>0.Proof.
By direct computation,(33)zkTsk=ykTsk+CgkrskTsk+max⁡0,-ykTsksk2skTsk=ykTsk+Cgkrsk2+max⁡⁡0,-ykTsksk2sk2≥ykTsk>0.Lemma 3.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has
(34)gk+1Tdk+1≤0.Proof.
We will divide (25) into two cases as follows.
Case
1. If k=0, then Lemma 3 is true.
Case
2. If k>0, combined with Lemma 2, then we have
(35)gk+1Tdk+1=gk+1T(-gk+1-λksk-μkzk)=-gk+12-1+zk2zkTskskTgk+12zkTsk≤0.
The proof of Lemma 3 is completed.Lemma 4.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has Dai-Liao’s type conjugate condition
(36)zkTdk+1=-tkskTgk+1,
where tk>0.Proof.
By direct computation, we get(37)zkTdk+1=zkT(-gk+1-λksk-μkzk)=-zkTgk+1-1+zk2zkTskskTgk+1+zkTgk+1-skTgk+1zkTskzk2=-1+2zk2zkTskskTgk+1=-tkskTgk+1,
where
(38)tk=1+2zk2zkTsk>0,
since zkTsk>0.Remark 5.
Observe that the directiondk+1 satisfies descent property. Besides, the direction dk+1 satisfies Dai-Liao’s type conjugacy condition, where tk>0 at every iteration.Theorem 6.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has
(39)zk≤ν1dk,λk≤ν2,μk≤ν3.Proof.
By direct computation, we have(40)zk≤yk+Cgkrsk+max⁡0,-ykTsksk2sk≤Ldk+Cgkrdk+Ldk=(2L+Cκr)dk=ν1dk,
where ν1=2L+Cκr. Consider
(41)λk≤1+zk2zkTskskTgk+1zkTsk+zkTgk+1zkTsk≤1+zk2ykTskskTgk+1ykTsk+zkTgk+1ykTsk≤1+zk21-σdk21(1-σ)+ν1(1-σ)≤1+κ21-σ1(1-σ)+ν1(1-σ)=ν2,
where ν2=1+κ2/1-σ1/(1-σ)+ν1/(1-σ). Consider
(42)μk=skTgk+1zkTsk≤skTgk+1ykTsk≤11-σ=ν3,
where ν3=1/1-σ. The proof is completed.Theorem 7.
Let assumptions (H1) and (H2) hold; the line search satisfies the Wolfe conditions (28); the search direction is computed by (25); then one has
(43)dk+1≤ωgk+1.Proof.
According to Algorithm1, we will divide (28) into two cases as follows.
Case
1. If k=0, we get dk+1=-gk+1, and then
(44)dk+1=gk+1,
where ω=1.
Case
2. If k>0, we have
(45)dk+1=-gk+1-λksk-μkzk,
and then
(46)dk+1≤gk+1+λksk+μkzk≤gk+1+1+zk2zkTskskTgk+1zkTsksk+zkTgk+1zkTsksk+skTgk+1zkTskzk≤gk+1+1+zk2zkTskskgk+1zkTsksk+zkgk+1zkTsksk+skgk+1zkTskzk=ωgk+1.
The proof is true.Theorem 8.
Let assumption (H1) hold and let{xk} and {dk} be generated by the three-term conjugate gradient method. If stepsize αk is obtained by the Wolfe line search, then one has
(47)lim⁡k→∞inf⁡gk=0.Proof.
By the use of Theorem7 and the same argument as Theorem 4.1 in [19], we will omit the proof here.


## 4. Another Modified Three-Term Type Conjugate Gradient Method and Its Global Convergence

Recently, Zhang et al. proposed a sufficient descent modified PRP conjugate gradient method with three terms [20] as
(48)dk+1=-gk+1+gk+1Tykgk2dk-gk+1Tdkgk2yk
and a sufficient descent modified HS conjugate gradient method with three terms [21] as
(49)dk+1=-gk+1+gk+1TykskTyksk-gk+1TskskTykyk.
A property of these methods is that they produce sufficient direction; that is,
(50)gkTdk=-gk2.
In the same context, Sun et al. proposed another sufficient conjugate gradient [22, 23] as
(51)dk=-gk,ifk=0,-gk+βk1dk-1-ϑkyk,ifk>0,
where βk1=gkT(gk-gk-1)/((1-μ)gk-12-μgk-1Tdk-1) and
(52)dk=-gk,ifk=0,-θkgk+βkVDYdk-1ifk>0,
where
(53)θk=1+μ1gkTdk-1μ2gkTdk-1+μ3dk-1Tyk-1.Similar to Zhang and Sun’s methods, in order to obtain the sufficient descent property, we will propose a modified three-term type conjugate gradient method; that is,(54)dk+1=-gk+1,ifk=0,-ξkgk+1-λksk-μkzk,ifk>0,
where
(55)ξk=λkgk+1Tsk+μkgk+1Tzk-gk+12gk+12.Algorithm 9 (a sufficient decent three-term conjugate gradient method).
Step
1. Step 1 is initialization and date.
Step
2 (termination condition and computation
d
k
). The direction dk is computed by (54).
Step
3. The Wolfe line search is to find a stepsize αk.
Step
4. Update the variables, xk+1=xk+αkdk, and then go to Step 2.Lemma 10.
Suppose thatx0 is a starting point for which assumptions hold. Let {xk} be generated by Algorithm 9; then one has
(56)gk+1Tdk+1=-gk+12<0.Proof.
According to Algorithm9, we will divide (54) into two cases as follows.
Case
1. If k=0, then Lemma 10 is true.
Case
2. If k>0, we get
(57)gk+1Tdk+1=gk+1T-ξkgk+1-λksk-μkzk=-ξkgk+12-1+zk2zkTskskTgk+12zkTsk-skTgk+12zkTsk=-gk+12<0.
Lemma 10 is true. The sufficient descent property is independent of the line search.Lemma 11.
Suppose thatx0 is a starting point for which assumptions hold. Let {xk} be generated by Algorithm 9. In addition, there are constants κ1,κ2, such that
(58)κ1≤gk≤κ2,∀x∈Ω;
then one has
(59)ξk≤ψ.Proof.
By direct computation, we get(60)ξk=λkgk+1Tsk+μkgk+1Tzk-gk+12gk+12≤1+λkgk+1sk+μkgk+1zkgk+12≤1+ν2κ2dk+ν3κ2Ldkκ12≤1+ν2κ22ω+ν3κ22Lωκ12=ψ,
where
(61)ψ=1+ν2κ22ω+ν3κ22Lωκ12.Theorem 12.
Let assumption (H1) hold and let{xk} and {dk} be generated by the three-term conjugate gradient Algorithm 9. If stepsize αk is obtained by the Wolfe line search, then one has
(62)lim⁡k→∞inf⁡gk=0.Proof.
By the use of Lemmas10 and 11 and the same argument as Theorem 4.1 in [19], we will omit the proof here.


## 5. Numerical Experiments

Now, let us report some numerical results attained by our sufficient descent conjugate gradient methods. We compare the performance of Algorithms1 and 9 with MBFGS method. The algorithm is implemented by MATLAB 7.0 code in double precision arithmetic. The tests are performed on a PC computer with CPU Pentium 4, 2.40 GHz, and Windows XP operation system.On the one hand, the type of objective function and the character of the problems being tested are listed in Tables1, 2, and 3. In the experiments, for easily comparing with other codes, we use the gradient errors to measure the quality of the solutions; that is, we force the iteration to stop when
(63)gk≤10-6,
where gk is the gradient of objective function. n represents the number of dimensions. m represents the number of functions. Nf represents the number of function f(x) evaluations. Ng represents the number of gradient g(x) evaluations. S represents the actual CPU-time costed in procedure operation. f* represents the problems approximate solutions which are allowed in error range region. P represents the problems in [24]. First, we compare Algorithm 1, Algorithm 9, and MBFGS method and the numerical test reports and the results of comparison are listed in Tables 1–3. We choose some test problems as our numerical examples and numerical results can be seen in Tables 1–3. The test problems with the given initial points can be found at http://camo.ici.ro/neculai/ansoft.htm which were collected by Neculai Andrei. We can see that the problems of [22] are solved by our method. Table 1 shows the numerical results of the three-term conjugate gradient Algorithm 1. In Table 2, by adopting Algorithm 9, these problems have better solutions. Table 3 shows the numerical results of the MBFGS method. In Table 2, the CPU-time is less than 130 seconds and lots of the problems are less than 70 seconds. In Table 1, the iterations of the Penalty function II and Power singular are more than 110, but, in Table 2, the Penalty function II and Power singular can be solved in less than 86 iterations and the time is less than 72 seconds. Table 3 shows the performance of the MBFGS method relative to CPU-time, the number of iterations, the number of function evaluations, and the number of gradient evaluations, respectively. From Table 1 to Table 3, as can be easily seen, Table 3 is better than Table 1 but worse than Table 2 with respect to the number of iterations and CPU-time. Tables 1 and 2 show that the three-term type conjugate gradient methods also have better performance with respect to the number of iterations and gradient evaluations. From Tables 1, 2, and 3, a conclusion is made that Algorithm 9 is better than Algorithm 1 and MBFGS method; that is, the sufficient descent direction is most important for the unconstrained optimization.Table 1
The numerical results of Algorithm1.
P
n
m
Nf
Ng
S
f
*
Rosenbrock
2
2
184
183
29.6
5.38
e
-
006
Freudenstein and Roth
2
2
77
78
96.2
5.72
e
-
006
Brown badly scaled
2
3
106
108
453.1
1.48
e
-
006
Beale
2
3
98
100
62.8
7.31
e
-
006
Brown and Dennis
4
20
77
79
100.1
85822.2
Trigonometrix
100
100
10
12
45.3
5.72
e
-
006
Trigonometrix
1000
1000
35
38
55.4
5.72
e
-
006
Trigonometrix
5000
5000
74
78
103.3
5.72
e
-
006
Broyden tridiagonal
100
100
56
56
89.2
9.54
e
-
006
Broyden tridiagonal
1000
1000
79
80
145.5
9.54
e
-
006
Broyden tridiagonal
5000
5000
82
86
170.2
9.54
e
-
006
Broyden banded
100
100
11
11
78.2
9.94
e
-
006
Broyden banded
500
500
46
46
90.3
9.94
e
-
006
Power singular
4
4
113
116
77
9.38
e
-
006
Brown almost linear
100
100
25
28
46.5
9.85
e
-
006
Brown almost linear
1000
1000
55
58
79.2
9.85
e
-
006
Watson
31
31
17
17
99.5
8.98
e
-
006
Discrete boundary value
100
100
42
42
36.2
9.54
e
-
006
Penalty function I
100
101
135
136
89.6
7.11
e
-
007
Penalty function II
100
200
56
56
70.2
5.69
e
-
007
Penalty function II
500
1000
102
105
144.6
5.69
e
-
007
Penalty function II
1000
2000
256
256
403.4
5.69
e
-
007Table 2
The numerical results of Algorithm9.
P
n
m
Nf
Ng
S
f
*
Rosenbrock
2
2
18
18
10
5.38
e
-
006
Freudenstein and Roth
2
2
47
48
28.3
5.72
e
-
006
Brown badly scaled
2
3
106
108
301.4
1.48
e
-
006
Beale
2
3
40
40
31
7.31
e
-
006
Brown and Dennis
4
20
23
23
36.4
85822.2
Trigonometrix
100
100
5
5
25
5.72
e
-
006
Trigonometrix
1000
1000
20
21
40.3
5.72
e
-
006
Trigonometrix
5000
5000
35
35
53.4
5.72
e
-
006
Power singular
4
4
45
45
63.2
9.38
e
-
006
Broyden tridiagonal
100
100
40
40
68
9.54
e
-
006
Broyden tridiagonal
1000
1000
54
54
85.4
9.54
e
-
006
Broyden tridiagonal
5000
5000
72
75
130.1
9.54
e
-
006
Broyden banded
100
100
7
7
60.7
9.94
e
-
006
Broyden banded
500
500
31
35
84.5
9.94
e
-
006
Brown almost linear
100
100
25
28
33.5
9.85
e
-
006
Brown almost linear
1000
1000
50
50
65.8
9.85
e
-
006
Watson
31
31
14
17
75.6
8.98
e
-
006
Discrete boundary value
100
100
42
42
30.4
9.54
e
-
006
Penalty function I
100
101
55
56
69.1
7.11
e
-
007
Penalty function II
100
200
41
41
64.3
5.69
e
-
007
Penalty function II
500
1000
56
56
68
5.69
e
-
007
Penalty function II
1000
2000
86
86
70.1
5.69
e
-
007Table 3
The numerical results of the MBFGS method [1].
P
n
m
Nf
Ng
S
f
*
Rosenbrock
2
2
30
30
32
6.14
e
-
006
Freudenstein and Roth
2
2
45
46
45.8
5.13
e
-
006
Brown badly scaled
2
3
120
113
317.6
0.48
e
-
007
Beale
2
3
56
56
45
5.33
e
-
006
Brown and Dennis
4
20
23
34
39.7
85856.2
Trigonometrix
100
100
23
20
53
5.72
e
-
006
Trigonometrix
1000
1000
34
38
121
5.72
e
-
006
Trigonometrix
5000
5000
45
45
135
5.72
e
-
006
Broyden tridiagonal
100
100
60
69
77
9.24
e
-
006
Broyden tridiagonal
1000
1000
90
91
186.4
9.06
e
-
006
Broyden tridiagonal
5000
5000
122
123
140.7
0.54
e
-
007
Broyden banded
100
100
22
33
100
0.91
e
-
007
Broyden banded
500
500
22
22
90
0.94
e
-
007
Power singular
4
4
56
85
78
0.34
e
-
008
Brown almost linear
100
100
56
55
143.3
0.87
e
-
006
Brown almost linear
1000
1000
50
58
128.8
0.85
e
-
007
Watson
31
31
22
22
86.5
8.98
e
-
006
Discrete boundary value
100
100
55
55
42.3
9.54
e
-
006
Penalty function I
100
101
60
60
88
7.11
e
-
007
Penalty function II
100
200
157
159
185.6
0.69
e
-
008
Penalty function II
500
1000
256
257
200.4
0.19
e
-
008
Penalty function II
1000
2000
287
287
210.4
0.69
e
-
008On the other hand, some of the test problems are from the CUTE collection established by Bongartz, Conn, Gould, and Toint. In Figure1, we adopt the performance profiles proposed by Dolan and Moré [25] to compare the CPU-time of Algorithm 1, Algorithm 9, MBFGS method, Dai’s method, and MPRP method. That is, for each method, we plot the fraction P of problems for which the method is within a factor t of the best time. The left side of the figure gives the percentage of the test problems for which 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 most of the problems in a time that is within a factor t of the best time. From Figure 1, we can see that Algorithm 1 method and Algorithm 9 method perform better than the MBFGS method and Dai’s method and MPRP method in [1, 19, 20]. Hence, the proposed methods not only possess better global convergence but also are superior to the three-term type conjugate gradient methods [1, 19, 20] in the numerical performance.Figure 1
Performance based on CPU-time.


## 6. Conclusions

In this paper, on the one hand, we improve a three-term type conjugate gradient method which is obtained by a MBFGS. On the other hand, we show another sufficient decent three-term type conjugate gradient method. In addition, under appropriate conditions, we indicate that the two methods are global convergence. Finally, some numerical experiments manifest the efficiency of the proposed methods.Certainly, we should further investigate more useful, powerful, and practical algorithms for solving large-scale unconstrained optimization problems, for instance, the hybrid conjugate gradient-GA and conjugate gradient-PSO methods and so on.



---

*Source: 394096-2014-11-23.xml*