Vol.3, No.1, 85-90 (2011) Natural Science
http://dx.doi.org/10.4236/ns.2011.31012
Copyright © 2011 SciRes. OPEN ACCESS
A hybrid conjugate gradient method for optimization
problems*
Xiangrong Li, Xupei Zhao
Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, China; xrli68@163.com
Received 14 October 2010; revised 18 November 2010; accepted 22 November 2010.
ABSTRACT
A hybrid method of the Polak-Ribière-Polyak
(PRP) method and the Wei-Yao-Liu (WYL) method
is proposed for unconstrained optimization pro-
blems, which possesses the following proper-
ties: i) This method inherits an important prop-
erty of the well known PRP method: the ten-
dency to turn towards the steepest descent di-
rection if a small step is generated away from
the solution, preventing a sequence of tiny
steps from happening; ii) The scalar 0
k
β
holds automatically; iii) The global convergence
with some line search rule is established for
nonconvex functions. Numerical results show
that the method is effective for the test prob-
lems.
Keywords: Line Search; Unconstrained
Optimization; Conjugate Gradient Method;
Global Convergence
1. INTRODUCTION
We are interested to consider the unconstrained opti-
mization problem

min ,
n
x
f
x
 (1.1)
where :n
f
is continuously differentiable. It is
well known that there are many methods for solving
optimization problems (see [24,26,28-32,34] etc.), where
the conjugate gradient(CG) method is a powerful line
search method because of its simplicity and its very low
memory requirement, especially for the large scale opti-
mization problems [22,23,27], which can avoid, like
steepest descent method, the computation and storage of
some matrices associated with the Hessian of objective
functions. The following iterative formula is often used
by the nonlinear CG method
1,0,1,2,
kkkk
xx dk
 (1.2)
for (1.1), where k
x
is the current iterate point, 0
k
is a steplength, and k
d is the search direction designed
by
1, if k1,
, if k= 0
kkk
k
k
gd
dg
 
(1.3)
where k
is a scalar which determines the differ-
ent conjugate gradient methods [4,5,8,9,12,13,15,16,18,
20,21,25,33] etc., and k
g
is the gradient of ()
f
x at
the point k
x
. The well-known formula for k
from the
computation point of view is the following PRP method
11
2,
T
kk k
PRP
k
k
gg g
g

(1.4)
where k
g
and 1k
g
are the gradients
k
f
xand
1k
fx
of ()fx at the point k
x
and 1k
x
, respec-
tively, and
denotes the Euclidian norm of vectors.
Throughout this paper, we also denote

k
f
x by k
f.
Polak and Ribèire [18] proved that this method with the
exact line search is globally convergent when the objec-
tive function is convex. Powell [19] gave a counter ex-
ample to show that there exist nonconvex functions on
which the PRP method does not converge globally even
the exact line search is used. He suggested that k
should not be less than zero. Considering this suggestion,
Gilbert and Nocedal [10] proved that the modified PRP
method
max 0,
P
RP
kk

is globally convergent
with the weak Wolfe-Powell (WWP ) line search tech-
nique and the assumption of sufficient descent condition.
However, the global convergence of the PRP method is
still open under the WWP line search rule.
Recently, Wei, Yao, and Liu(WYL) [21] propose a
new conjugate gradient formula
1
11
2
k
T
kk k
k
WYL
k
k
g
g
gg
g
g





(1.5)
It is not difficult to deduce that
*This work is supported by China NSF grands 10761001 and Guangxi
SF grands 0991028.
X. R. Li et al. / Natural Science 3 (2011) 85-90
Copyright © 2011 SciRes. OPEN ACCESS
86
2
11
11 11
22
0
k
Tk
kkk kk k
kk
WYL
k
kk
gg
gg g
g
gg
gg
gg
 





is true. The numerical results show that this method is
competitive to the PRP method for the test problems of
[17]. Under the sufficient descent condition, this method
is globally convergent with the WWP line search.
These observations make us know that the sufficient
descent condition
2,0
T
kk k
gdcg c is a constant holds for all 0k
(1.6)
is very important to ensure the global convergence
[1,2,10,14], and the scalar 0
k
also plays a very
important role [10,19]. This motivates us to propose a
hybrid method combining the PRP method and the
WYL method. The hybrid method will possess some
better properties of the PRP method and the WYL
method: (i) the tendency to turn towards the steepest
descent direction if a small step is generated away from
the solution, preventing a sequence of tiny steps from
happening; (ii) The scalar 0
k
holds automatically.
The global convergence with the WWP line search of
the presented method is established for nonconvex ob-
jective function. Numerical results show that this given
method is competitive to the PRP method and the WYL
method.
This paper is organized as follows. In the next section,
the algorithm is stated. The global convergence is
proved in Section 3, and the numerical results are re-
ported in Section 4. The last section gives one conclu-
sion.
2. ALGORITHM
Now we describe the given algorithm as follows. Here
we call it Algorithm 1.
Algorithm 1 (The hybrid algorithm of the PRP
method and the WYL method)
Step 0: Choose an initial point
0,0,1.
n
x
 
Set

00 0
, :0.dg fxk
Step 1: If ,
k
g
then stop; Otherwise go to the
next step.
Step 2: Compute step size k
by some line search
rules.
Step 3: Let 1.
kkkk
x
xd
 If 1,
k
g
then
stop.
Step 4: Calculate the search direction
11 ,
PW
kkkk
dg d

  (2.1)
where
max , .
P WPRPWYL
kkk

Step 5: Set :1kk
, and go to Step 2.
Remark i) If 1,
kk
x
x
we have 1kk
g
g
and
1kk
g
g
which imply that 0,
PRP
k
and 0,
WYL
k
which means that 0
PW
k
if a small step is gener-
ated for all 0k. Thus the given method inherits the
better property of the PRP method: the directions will
turn out to be the steepest descent directions if the tiny
steps from happening.
ii) By the definition of the new formula ,
P
W
k
we
have
21
11
2
max ,
0
P WPRPWYLWYL
kkkk
k
kk k
k
k
g
g
gg
g
g



3. THE GLOBAL CONVERGENCE
The following assumptions are often needed to prove
the convergence of the nonlinear conjugate gradient
methods (see [5,9,10,20,21] etc.).
Assumption 3.1 i) The function

f
x has a lower
bound on the level set



0
n
x
fx fx ,
where 0
x
is a given point and is bounded.
ii) In an open convex set 0
that contains
, J is
differentiable and its gradient g is Lipschitz continuous,
namely, there exists a constants 0L such that
0
, , .gxgyLx yxy
 (3.1)
3.1. The global Convergence with the Weak
Wolfe-Powell Line Search
The weak Wolfe-Powell (WWP) search rule is to find
a step length k
such that
T
kkk kkkk
f
xdfgd

 (3.2)
and

,
TT
kkkk k
g
xddg

 (3.3)
where
0,12, ,1.


This line search tech-
nique is often used to study the convergence of conju-
gate gradient algorithms [6,27,34]. At present, the global
convergence of the PRP method with the WWP line
search is still open.
Lemma 3.1 Suppose that Assumption 3.1 holds. Let
the sequence
k
g
and
k
d be generated by Algo-
rithm 1, 0,
T
kk
gd
and the stepsize k
be determined
X. R. Li et al. / Natural Science 3 (2011) 85-90
Copyright © 2011 SciRes. OPEN ACCESS
8787
by the WWP line search (3.2) and (3.3) Then the
zoutendijk condition [34]

2
2
0
T
kk
kk
gd
d

(3.4)
holds.
Proof. By (3.3) and Assumption 3.1 ii), we have


2
1
1,
T
T
kkkkkk k
gdgg dLd


this means that

2
1,
T
kkkk
gd Ld

  which to-
gether with 0,
T
kk
gd and (3.2) implies that


2
1
2
1
,
T
kk
kk
k
gd
f
f
Ld

summing up this inequality from 0k to , and us-
ing Assumption 3.1 i), we can obtain this lemma. This
completes the proof.
We will prove the global convergence of Algorithm 1
by contradiction. Then we assume that there exists a
positive constant 0
such that
, 0.
k
gk
 (3.5)
Using (3.5) deduces a contradiction to obtain our con-
clusion.
Similar to Lemma 3.3.1 in [6], based on Assumption
3.1, Lemma 3.1, the fact 0,
PW
k
and (3.5), we can
get the following lemma.
Lemma 3.2 Let Assumption 3.1 hold and the se-
quences

k
g
and

k
d be generated by Algorithm 1.
The sufficient descent condition (1.6) holds, and the
stepsize k
is determined by (3.2) and (3 .3). Suppose
that the inequalities (3.5) is true. Then we have 0
k
d
and
2
1
0
,
kk
k
uu

where k
k
k
d
ud
.
Proof. These two inequalities (1.6) and (3.5) imply
that 0
k
d is true, for otherwise 0,
k
g then
kkk
udd is reasonable. Denote
1
1
11
, k
PW
k
kkk
kk
d
g
rdd


 
By (2.1), for 0k, we have
11 ,
kk kk
ur u


this combining with 11
kk
uu

shows that
11 1kkkkkkk
ru uuu

 
 
(3.6)
The inequality 0
PW
k
implies that0
k
is true,
then it follows that from (3.6) and triangular inequality
 
1
1
11
1
11
2.
kk
kk kk
kkkkkk
k
uu
uu
uuuu
r



 
 
(3.7)
By (1.6) and (3.4), we get
4
22
1
11
2
01
1
k
kk
kk
k
grg
d




Which together with (3.5), we obtain
2
1
0
k
k
r

By the above inequality and (3.7), we get this lemma.
The proof is complete.
The following property (*) was introduced by Gilbert
and Nocedal [10], which pertains to the k
under the
sufficient descent condition. The WYL formula also has
this property. Now we show that this property (*) per-
tains to our method.
Property (*). Suppose that
12
0.
k
rg r
 (3.8)
We say that the method has Property (*), if for all k,
there exists constants 1b and 0
such that
kb
and
1
2
kk
sb


Lemma 3.3 Let Assumption 3.1 hold and the se-
quences
k
g
and
k
d be generated by Algorithm 1.
Then the new formula
P
W
k
possesses property (*).
Proof. The result of this lemma is proved by the fol-
lowing two cases.
Case i: we consider
P
RP
k
By (3.1), we have
1
11
22
..
T
kk
kk k
PRP
k
kk
Lg s
gg g
gg


(3.9)
From Assumption 3.1 i), then there exists a constant
10M such that
1.
k
s
M (3.10)
Let
2
21 1
max 2,1bLrrM
and
2
12
2bL

,
it follows that
PRP
kb
and
X. R. Li et al. / Natural Science 3 (2011) 85-90
Copyright © 2011 SciRes. OPEN ACCESS
88
122
22 2
11
.22
1.
2
kk
PRP
kk
k
Lg sLL
sb
g




Then the PRP formula
P
RP
k
has this property (*).
Case ii: let us consider WYL
k
. Denote 1kk
Yg
1,
kkk
g
gg
by (3.1), we get
1
1
1
1
11
11
2,
k
kkk
k
k
kkk k
k
kk kk
kkkk
k
g
Yg g
g
g
g
gg g
g
gg gg
gggg
Ls






(3.11)
By (1.5), (3.11), (3.10) and (3.8) we have
12
1
222
1
.2 ,
T
kk k
WYLkk
k
kk
g
YLs
gY
gg
 (3.12)
let


2
21 1
max2, 2bLM

and
2
12
22 ,bL

it follows that (3.12) and the definition of b and
that
1b
22
24
11
22
1
, and 2
WYL WYL
kk k
LL
bs
b

 





Thus, the formula WYL
k
also has the property (*).
Using the definition of the

max ,
P
WWYL PRP
kkk

,
we conclude that the formula
P
W
k
possesses the
property (*). The proof is complete.
By Lemma 3.3, similar to Lemma 3.3.2 in [6], it is not
difficult to prove the following result. Here we only state
it as follows, but omit the proof.
Lemma 3.4 (Lemma 3.3.2 in [6]) Let the sequences

k
g
and

k
d be generated by Algorithm 1 and the
conditions in Lemma 3.3 hold. If 0
PW
k
and has
property (*), then there exists a constant 0
such
that, for any N and any index 0
k there is an in-
dex 0
kk satisfying
,,
2
k
k
where

,:1,,
ki
kiNkik s
 N de-
notes the set of positive integers, and ,k
k
denotes the
numbers of elements in ,k
k
.
Finally, by Lemma 3.2 and Lemma 3.4, we present
the global convergence theorem of Algorithm 1 with the
WWP line search. Similar to Theorem 3.3.3 in [6], it is
not difficult to prove the result, here we also give the
process of the proof.
Theorem 3.1 Let the sequence

,
kk
g
d be gener-
ated by Algorithm 1 with the weak Wolfe-Powell line
search and the conditions in Lemma 3.3 hold. Then
lim inf0
kk
g

.
Proof. We will get this theorem by contradiction.
Suppose that (3.5) is true, then the conditions in Lemma
3.2 and 3.3 hold. By Assumption 3.1 i), then there exists
a constant 00
such that
0,xx
 (3.13)
We also denote ,
iii
udd then for all integers
,lk lk, we have

11
111 1
.
l
lki i
ik
ll
iki k
ik ik
xx su
suu u






Taking the norm in both sides of the above equality,
and using (3.13) we get
10 111
2
ll
iiik
ik ik
ssuu


 

Let 0
8

be the smallest integer where
does not less than 0
8
. By Lemma 3.2, there exists
an index 0
k such that
2
1
1
4
ii
ik
uu

(3.14)
On the other hand, by Lemma 3.3, there exists 0
kk
satisfying
,2
k
k
(3.15)
For all
,1ikk
 , by Cauchy-Schwarz inequal-
ity and (3.14), we obtain

1
11 1
1
112
2
21
1
12
2
11
.
42
i
ik jj
jk
i
jj
jk
uu uu
ikuu
 
 

 



 


By the above inequality, (3.15) and (3.13), we have
1
01,
1
2,
224
k
ik
ik
sk



Thus 0
8,
this contradicts with the definition
of .
Therefore, the conclusion of this theorem is right.
This completes the proof.
4. NUMERICAL RESULTS
In this section, we report some numerical experiments.
X. R. Li et al. / Natural Science 3 (2011) 85-90
Copyright © 2011 SciRes. OPEN ACCESS
8989
The unconstrained optimization problems with the given
initial points can be found at:
www.ici.ro/camo/neculai/SCALCG/testuo.pdf,
which were collected by Neculai Andrei. Since this new
method is the hybrid method of the PRP method and the
WYL method, we test Algorithm 1 with the WWP line
search and compare its performance with those of the
WYL [21] and the PRP [18] methods. The stop criteri-
ons are given below: we stop the program if the inequal-
ity

k
gx
is satisfied or the inequality
 

1
kk
gxf x

is satisfied, where 1.0 5.D
 All the codes were
written in Fortran and run on PC with 2.60 GHz CPU
processor and 256 MB memory and Windows XP op-
eration system. In the experiments, the parameters were
chosen as 1.0 2, 1.0 1DD
. The dimension
of the test problems is from 500 to 5000. The detailed
numerical results are listed on the web site
http://210.36.18.9:8018/publication.asp?id=35392.
In Figure 1, “WYL”, “PRP”, and “MPRP-WYL
stand for the WYL method, the PRP method, and the
new method, respectively.
Figure 1 shows the performance of these methods
relative to the iterative number of the function and gra-
dient(NFN), which were evaluated using the profiles of
Dolan and Moré [7]. It is easy to see that the
MPRP-WYL is predominant among these three methods
and the new method can solve about 99% of the test
problems successfully. The PRP method is better than
the WY L method for 11.2t and the WYL method
is better than the PRP method for 1.26t. Moreover,
the PRP method solves about 98% of the test problems
and the WYL method solve about 99% of the test prob-
lems successfully, respectively. In a word, the given
Figure 1. Performance profiles of conjugate gradient me-
thods in Table 1 (NFN).
method is competitive to the other two methods and the
hybrid formula is notable.
5. CONCLUSION
This paper gives a hybrid conjugate gradient method
for solving unconstrained optimization. The global con-
vergence for nonconvex functions with the WWP line
search is established. The numerical results show that
the given method is competitive to the other standard
conjugate gradient methods for the test problems.
For further research, we should study the convergence
of the new algorithm under other line search rules.
Moreover, more numerical experiments and testing en-
vironments (such that [3]) for large practical problems
should be done in the future.
REFERENCES
[1] Ahmed, T. and Storey, D. (1990) Efficient hybrid conju-
gate gradient techniques. Journal of Optimization Theory
and Applications, 64, 379-394.
doi:10.1007/BF00939455
[2] Al-Baali, A. (1985) Descent property and global conver-
gence of the Flecher-Reeves method with inexact line
search. IMA Journal of Numerical Analysis, 5, 121-124.
doi:10.1093/imanum/5.1.121
[3] Bongartz, K.E., Conn, A.R., Gould, N.I.M. and Toint,
P.L. (1995) CUTE: Constrained and unconstrained test-
ing environments. ACM Transactions on Mathematical
Software, 21, 123-160.
doi:10.1145/200979.201043
[4] Dai, Y. (2002) A nonmonotone conjugate gradient algo-
rithm for unconstrained optimization. Journal of Systems
Science and Complexity, 15, 139-145.
[5] Dai, Y. and Yuan, Y. (2000) A nonlinear conjugate gra-
dient with a strong global convergence properties. SIAM
Journal on Optimization, 10, 177-182.
doi:10.1137/S1052623497318992
[6] Dai, Y. and Yuan, Y. (1998) Nonlinear conjugate gradi-
ent methods. Shanghai Scientific and Technical Publish-
ers, Shanghai.
[7] Dolan, E.D. and Moré, J.J. (2002) Benchmarking opti-
mization software with performance profiles. Mathe-
matical Programming, 91, 201-213.
doi:10.1007/s101070100263
[8] Fletcher, R. (1997) Practical Method of Optimization,
Vol I: Unconstrained Optimization. 2nd Edition, Wiley,
New York.
[9] Fletcher, R. and Reeves, C. (1964) Function minimiza-
tion bu conjugate gradients. Computer Journal, 7,
149-154.
doi:10.1093/comjnl/7.2.149
[10] Gibert, J.C. and Nocedal, J. (1992) Global convergence
properties of conugate gradient methods for optimization.
SIAM Journal on Optimization, 2, 21-42.
doi:10.1137/0802003
[11] Grippo, L. and Lucidi, S. (1997) A globally convergent
version of the Polak-Ribière gradient method. Mathe-
X. R. Li et al. / Natural Science 3 (2011) 85-90
Copyright © 2011 SciRes. OPEN ACCESS
90
matical Programming, 78, 375-391.
doi:10.1007/BF02614362
[12] Hager, W.W. and Zhang, H.C. (2005) A new conjugate
gradient method with guaranteed descent and an efficient
line search. SIAM Journal on Optimization, 16, 170-192.
doi:10.1137/030601880
[13] Hestenes, M.R. and Stiefel, E. (1952) Method of conju-
gate gradient for solving linear equations. Journal of Re-
search National Bureau of Standards, 49, 409-436.
[14] Hu, Y.F. and Storey, C. (1991) Global convergence re-
sult for conjugate method. Journal of Optimization The-
ory and Applications, 71, 399-405.
doi:10.1007/BF00939927
[15] Li, G., Tang, C. and Wei, Z. (2007) New conjugacy con-
dition and related new conjugate gradient methods for
unconstrained optimization. Journal of Computational
and Applied Mathematics, 2, 523-539.
doi:10.1016/j.cam.2006.03.005
[16] Liu, Y. and Storey, C. (1992) Effcient generalized con-
jugate gradient algorithms, part 1: theory. Journal of Op-
timization Theory and Applications, 69, 17-41.
[17] Moré, J.J., Garbow, B.S. and Hillstrome, K.E. (1981)
Testing unconstrained optimization software. ACM
Transactions on Mathematical Software, 7, 17-41.
doi:10.1145/355934.355936
[18] Polak, E. and Ribiere, G. (1969) Note sur la xonvergence
de directions conjugees. Rev. Francaise informat Re-
cherche Operatinelle, 3e Annee, 16, 35-43.
[19] Powell, M.J.D. (1984) Nonconvex minimization calcula-
tions and the conjugate gradient method. Lecture Notes
in Mathematics, 1066, 122-141.
[20] Wei, Z., Li, G. and Qi, L. (2006) New nonlinear conju-
gate gradient formulas for large-scale unconstrained op-
timization problems. Applied Mathematics and Compu-
tation, 179, 407-430.
doi:10.1016/j.amc.2005.11.150
[21] Wei, Z., Yao, S. and Liu, L. (2006) The convergence
properties of some new conjugate gradient methods. Ap-
plied Mathematics and Computation, 183, 1341-1350.
doi:10.1016/j.amc.2006.05.150
[22] Yu, G.H. (2007) Nonlinear self-scaling conjugate gradi-
ent methods for large-scale optimization problems. The-
sis of Doctor’s Degree, Sun Yat-Sen University.
[23] Yuan, G.L. (2009) Modified nonlinear conjugate gradient
methods with sufficient descent property for large-scale
optimization problems. Optimization Letters, 3, 11-21.
doi:10.1007/s11590-008-0086-5
[24] Yuan, G.L. and Lu, X.W. (2008) A new line search
method with trust region for unconstrained optimization.
Communications on Applied Nonlinear Analysis, 15,
35-49.
[25] Yuan, G.L. and Lu, X.W. (2009) A modified PRP con-
jugate gradient method. Annals of Operations Research,
166, 73-90.
doi:10.1007/s10479-008-0420-4
[26] Yuan, G.L., Lu, X.W. and Wei, Z.X. (2007) New
two-point stepsize gradient methods for solving uncon-
strained optimization problems. Natural Science Journal
of Xiangtan University, 29, 13-15.
[27] Yuan, Y. and Sun, W. (1999) Theory and Methods of
Optimization. Science Press of China, Beijing.
[28] Yuan, G.L. and Wei, Z.X. (2009) New line search meth-
ods for unconstrained optimization. Journal of the Ko-
rean Statistical Society, 38, 29-39.
doi:10.1016/j.jkss.2008.05.004
[29] Yuan, G.L. and Wei, Z.X. (2008) The superlinear con-
vergence analysis of a nonmonotone BFGS algorithm on
convex objective functions. Acta Mathematica Sinica, 24,
35-42.
doi:10.1007/s10114-007-1012-y
[30] Yuan, G.L. and Wei, Z.X. (2010) Convergence analysis
of a modified BFGS method on convex minimizations.
Computational Optimization and Applications, 47,
237-255.
doi:10.1007/s10589-008-9219-0
[31] Yuan, G.L. and Wei, Z.X. (2009) A Rank-One fitting
method for unconstrained optimization problems. Mathe-
matica Applicata, 22, 118-122.
[32] Zhang, H.C. and Hager, W.W. (2004) A nonmonotone
line search technique and its application to unconstrained
optimization. SIAM Journal on Optimization, 14,
1043-1056.
doi:10.1137/S1052623403428208
[33] Zhang, L., Zhou, W. and Li, D. (2006) A descent modi-
fied Polak-Ribiére-Polyak conjugate method and its
global convergence. IMA Journal on Numerical Analysis,
26, 629-649.
doi:10.1093/imanum/drl016
[34] Zoutendijk, G. (1970) Nonlinear programming computa-
tional methods. In: Abadie, J. Ed., Integer and Nonlinear
Programming, NorthHolllad, Amsterdam, 37-86.