# An Efficient Hybrid Conjugate Gradient Method with the Strong Wolfe-Powell Line Search

Authors: Ahmad Alhawarat; Mustafa Mamat; Mohd Rivaie; Zabidin Salleh
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Conjugate gradient (CG) method is an interesting tool to solve optimization problems in many fields, such as design, economics, physics, and engineering. In this paper, we depict a new hybrid of CG method which relates to the famous Polak-Ribière-Polyak (PRP) formula. It reveals a solution for the PRP case which is not globally convergent with the strong Wolfe-Powell (SWP) line search. The new formula possesses the sufficient descent condition and the global convergent properties. In addition, we further explained about the cases where PRP method failed with SWP line search. Furthermore, we provide numerical computations for the new hybrid CG method which is almost better than other related PRP formulas in both the number of iterations and the CPU time under some standard test functions.


---

## Body

## 1. Introduction

The nonlinear conjugate gradient (CG) method is a useful tool to find the minimum value for unconstrained optimization problems. Consider the following form:(1)min⁡fx∣x∈Rn,where f:Rn→R is continuously differentiable function and its gradient is denoted by g(x)=∇f(x). The CG method is to find a sequence of points xk, k≥1, starting from initial point x1∈Rn which is given as the following iterative formula:(2)xk+1=xk+αkdk,where xk is the current iteration point and αk>0 is the step length obtained by some line search. The search direction dk is defined by(3)dk=-gk,k=1,-gk+βkdk-1,k>1,where gk=g(xk) and βk is known as CG method, formula, or coefficient.To find the step length (αk) we can use the exact line search which is given by(4)fxk+αkdk=min⁡fxk+αdk,α≥0.In fact, (4) is not an effective line search since it needs heavy computations in function and gradient evaluations. Therefore, we prefer to use inexpensive line search. The strong Wolfe-Powell (SWP) line search [1, 2], which is given as follows, (5)fxk+αkdk≤fxk+δαkgkTdk,(6)gxk+αkdkTdk≤-σgkTdk,where 0<δ<σ<1, is to find an approximation of αk where the descent property (see (14)) must be satisfied and no longer searching in the direction when xk is far from the solution. Thus, by using SWP line search we inherit the advantages of exact line search with inexpensive and low computational cost. However, different choices of αk and dk imply different CG methods. In fact the SWP line search is a strong version of weak Wolfe-Powell (WWP) line search where the latter is given by (5) and (7)gxk+αkdkTdk≥σgkTdk.The CG method has been developed recently based on its simplicity, numerical efficiency, and low memory requirements. Thus, it is used widely in engineering medical science and other fields. As an application in engineering we can use CG method to solve some real life problem similar to that mentioned in [3]. The CG method is limited for the functions where their gradient is available. Thus, the heuristic algorithm [4] can be used as an alternative method to find the solution for general functions. A heuristic algorithm is to find an approximation solution for the objective functions with accepted time. In addition, the heuristic algorithms can be applied without using computers. We refer the reader to see some applications for this algorithm in [5–7].The most popular formulas forβk are Hestenes-Stiefel (HS) [8], Fletcher-Reeves (FR) [9], Polak-Ribière-Polyak (PRP) [10], and Wei et al. (WYL) [11], respectively, as follows:(8)βkHS=gkTyk-1dk-1Tyk-1,(9)βkFR=gk2gk-12,(10)βkPRP=gkTyk-1gk-12,(11)βkWYL=gkTgk-gk/gk-1gk-1gk-12,where yk-1=gk-gk-1.Hestenes-Stiefel [8] proposed the first formula for solving the quadratic functions in 1952. Fletcher and Reeves [9] presented the first formula (9) for nonlinear functions in 1964. The convergence properties of FR method with exact line search were obtained by Zoutendijk [12]. Al-Baali [13] proved that FR method is globally convergent with the SWP line search when σ<1/2. Later on Guanghui et al. [14] extended the result to σ≤1/2. The global convergence of PRP method (10) with the exact line search was proved by Elijah and Ribiere in [10]. Powell [15] gave out a counterexample showing that there exists nonconvex function, where PRP method does not converge globally, even when the exact line search is used. Powell suggested using nonnegative PRP method to reveal this problem. Gilbert and Nocedal [16] proved that nonnegative PRP (PRP+) method, that is, βk=max{βkPRP,0}, is globally convergent under complicated line searches. However, there is no guarantee that PRP+ is convergent with SWP line search for general nonlinear functions. Touati-Ahmed and Storey [17] suggest the following hybrid method:(12)βkTS=βkPRP,if0≤βkPRP≤βkFR,βkFR,otherwise.In 2006 Wei et al. [11] presented a new positive CG method (11), which is quite similar to original PRP method which has been studied in both exact and inexact line search. Many modifications have appeared, such as the following [18–20], respectively:(13)βkVHS=gk2-gk/gk-1gkgk-1dk-1Tyk-1,βkNPRP=gk2-gk/gk-1gkgk-1gk-12,βkDPRP=gk2-gk/gk-1gkgk-1mgkTdk-1+gk-12,wherem≥1.Recently many CG formulas were constructed in order to get the efficiency and robustness. For more about the latest CG methods we refer the reader to see [21, 22].One of the important rules in CG methods is the descent condition; that is, if one can prove(14)gkTdk<0then we have a guarantee for f(xk+1)<f(xk). If we extended (14) to the following form,(15)gkTdk≤-cgk2,k≥0,c>0,then (15) is called the sufficient descent condition.This paper is organized as follows; in Section2 we will present the current problem for PRP and nonnegative PRP method with SWP line search. Later on we will suggest the new hybrid CG formula and its simplifications. Furthermore, we will establish the global convergence properties with the SWP line search, in Section 3. Numerical results with conclusion will be presented in Sections 4 and 5, respectively.


## 2. Motivation and the Hybrid Formula

The PRP formula is one of the best CG methods in this century. However, as we mentioned before this method fails to solve some standard test problems for nonconvex functions; even the exact line search is used. Thus, the main contribution of this paper is to extend using PRP formula in several cases with SWP line search under mild condition and restart the CG algorithm by using NPRP CG formula when PRP failed to satisfy that condition.The following discussion illustrates the cases in which PRP method fails and succeeds with SWP line search to obtain the convergence properties. The PRP method could be simplified as follows:(16)βkPRP=gkTgk-gk-1gk-12=gk2-gkTgk-1gk-12.Therefore we have the following cases.Case A.
IfgkTgk-1>0, then we have the following two possibilities.
Case  A1. If gk2>gkTgk-1, then we have 0≤βkPRP≤βkFR. In this case, PRP method is efficient and has global convergence properties.
Case A2. If gk2<gkTgk-1, then we have βkPRP<0. In this case based on [16] we fail to obtain the global convergence properties for nonconvex functions.Case B.
IfgkTgk-1<0, then(17)βkPRP=gkTgk-gk-1gk-12=gk2+gkTgk-1gk-12=βkFR+gkTgk-1gk-12.In Case B there is no guarantee that this method will satisfy the sufficient descent condition.For the next discussion, we will discuss the nonnegative PRP method which is given as follows:(18)βkPRP+=max⁡βkPRP,0i.e.βkPRP+=max⁡Case  A1,  Case  A2,  Case  B,0.Therefore, we have a problem in Case B. To solve this problem Gilbert and Nocedal [16] used another line search to satisfy the convergence properties. In addition, if βkPRP+=0, the CG method returns to the steepest descent method which is sometimes a weak tool to find the optimum point for functions. Furthermore we can notice that (19)βkTS=Case  A1βkFR,otherwise.So from PRP method we can use only Case  A1.To improve the above ideas, we suggest the following hybrid method:(20)βkPRP∗∗=βkPRP=gkTgk-gk-1gk-12,ifgk2>gkTgk-1,βkNPRP=gk2-gk/gk-1gkgk-1gk-12,otherwise.If βkPRP∗∗=gk2-gkTgk-1/gk-12, then under the condition gk2>gkTgk-1, we obtain(21)0<βkPRP∗∗=gk2-gkTgk-1gk-12≤gk2+gkTgk-1gk-12<2gk2gk-12.And if (22)βkPRP∗∗=βkNPRP=gk2-gk/gk-1gkTgk-1gk-12,we obtain(23)0≤βkPRP∗∗<gk2gk-12=βkFR.One of the advantages for βkPRP∗∗ is that we can use Case  A1 and Case B under the condition gk2>gkTgk-1.ChoosingβkNPRP as a restart CG formula in (20), if the condition gk2>gkTgk-1 is not satisfied that means (24)gk2≤gkTgk-1.Thus, NPRP method is a suitable nonnegative value to use.The following algorithm is an algorithm of CG method with the new coefficientβkPRP∗∗.Algorithm 1.
Consider the following.
Step  1. Initialization: given x1, set k=1.
Step  2. Compute βk based on (20).
Step  3. Compute dk based on (3).
Step  4. Compute αk based on (5) and (6).
Step  5. Update new point based on (2).
Step  6. Convergent test and stopping criteria: if gk≤ε then stop; otherwise go to Step  2 with k=k+1.


## 3. The Global Convergence Properties forβkPRP∗∗ with SWP Line Search

The following standard assumptions are necessary for this work.Assumption 1.
The level setΧ={x∈Rn:f(x)≤f(x1)}, with x1 to the starting point of the iterative method (2), is bounded.Assumption 2.
In some open convex neighborhoodN of Χ, f is continuous and differentiable, and its gradient is Lipschitz continuous; that is, for any x, y∈N, there exists a constant L>0 such that g(x)-g(y)≤Lx-y.The following lemma is one of the most important lemmas which is used to prove the global convergence properties.Lemma 2 (see [12]).
Suppose Assumptions1 and 2 are true. Consider any form of (2) and (3), with αk computed by WWP line search direction dk, is descent for all k≥1; then(25)∑k=1∞cos2⁡θkgk2<∞,where(26)cos⁡θk=-gkTdkdkgk.Equation (25) is known as Zoutendijk condition.The following discussion will discuss the global convergence properties forβkPRP∗∗ with SWP line search.Case 1 (βkPRP∗∗=βkNPRP).
Since0≤βkNPRP≤βkFR the proof of the global convergence properties is similar to βkFR. We refer the reader to see [13, 14].Case 2 (βkPRP∗∗=βkPRP, where gk2>gkTgk-1).
In this case we have(27)0≤βkPRP∗∗=gk2-gkTgk-1gk-12≤gk2+gkTgk-1gk-12≤2gk2gk-12.The following theorem demonstrates βkPRP∗∗ in Case 2 satisfies the sufficient descent condition with SWP line search.Theorem 3.
Consider the sequencesgk and dk are constructed by Algorithm 1 and αk  is computed by (5) and (6) if  σ∈0,1/4. Then (15) holds.Proof.
From (3), for k=1, it is obvious. Suppose it is true until k-1; that is, gk-1Tdk-1=-gk-12. Multiply (3) by gk; we obtain(28)gkTdk=gkT-gkT+βkdk-1=-gk2+βkgkTdk-1.Dividing both sides by gk-12, and by using Case 2 and (6), then we obtain(29)-1+2σgk-1Tdk-1gk-12≤gkTdkgk2≤-1-2σgk-1Tdk-1gk-12.From (29) we obtain(30)-∑j=0k-12σj≤gkTdkgk2≤-2+∑j=0k-12σj.Since(31)∑j=0k-12σj≤1-2σk1-2σ,we have(32)-1-2σk1-2σ≤gkTdkgk2≤-2+1-2σk1-2σ.If σ≤1/4 we get(33)1-2σk1-2σ<2.Let(34)c=2-1-σk1-σ;then(35)c-2≤gkTdkgk2≤-c.Thus(36)gkTdk≤-cgk2,where c∈(0,1). The proof is complete.Gilbert and Nocedal [16] presented an important theorem (Theorem 4) to find the global convergence properties for nonnegative PRP method if the descent condition is satisfied. Furthermore [16] presented nice property called Property∗ as follows.P
r
o
p
e
r
t
y
∗. Consider a CG method of forms (2) and (3), and suppose 0<γ≤gk≤γ-; we say that the CG method possesses Property∗ if there exists constant b>1, and λ>0, such that, for all k≥1, we get βk≤b, and if xk-xk-1≤λ, we obtain(37)βk≤12b.Theorem 4.
Consider any CG method of forms (2) and (3) achieves the following properties: (I)
βk≥0.(II)
The sufficient descent condition (15) holds.(III)
The Zoutendijk condition (25) is satisfied by the line search.(IV)
Property∗ holds.(V)
Assumptions1 and 2 hold.Then the iterates are globally convergent.The next lemma shows that if the gradients are bounded away from zero andProperty∗ holds, then a certain fraction of steps cannot be too small. The proof is given in [16]. However, we state it for readability.Lemma 5.
Consider a CG algorithm as defined in (2) and (3) with the parameter βkPRP∗∗. If Assumptions 1 and 2 are satisfied, then Property∗ holds.Proof.
Letb=2γ-2/γ2≥1 and λ≤γ2/2Lγ-b:(38)βkPRP∗∗≤gk2-gkTgk-1gk-12≤gk2+gkTgk-1gk-12≤gkgk+gk-1gk-12≤2γ-2γ2=b>1.Using sk≤λ, we have(39)βkPRP∗∗≤gkTgk-gk-1gk-12≤gkgk-gk-1gk-12.By Assumption 2,(40)βkPRP∗∗≤Lλγ-γ2≤12b.The proof is complete.Lemma 6.
The CG formula presented in Case2 has the following properties:
(1)
β
k
P
R
P
∗
∗
>
0, since the condition gk2>gkTgk-1 forces the CG formula in (20) to be nonnegative.
(2)
β
k
P
R
P
∗
∗ satisfies Property∗, based on Lemma 5.
(3)
β
k
P
R
P
∗
∗ satisfies the sufficient descent condition based on Theorem 3 and c∈0,1.By using Theorems3 and 4 and Lemma 6 we have the following convergence result. The proof is similar to Theorem  4.3 which is presented in [16].Theorem 7.
Suppose that Assumption1 holds. Consider the CG method of forms (2) and (3) and βk as in Case 2, where αk is computed by (5) and (6) with σ≤1/4; then limk→∞⁡inf⁡gk=0.


## 4. Numerical Results and Discussions

To evaluate the efficiency of the new method, we selected some of the test functions in Table1 from CUTEr [24], Neculai [23], and Adorio and Diliman [25]. We performed a comparison with other CG methods, including VHS, NPRP, PRP+, FR, and PRP∗∗ formulas. The tolerance ε is selected to 10-6 for all algorithms to investigate the rapidity of the iteration methods towards the optimal solution. The gradient value is used as the stopping criteria. Here, the stopping criteria considered gk≤10-6. We considered the method failed if the number of iterations exceeds 1000 times.Table 1
A list of problem functions used with the SWP condition withδ=0.01 and σ=0.1.
Number
Function
Dimension/s
Initial points
1
Extended White & Holst function  [23]
500,  1000,  5000,  10000
(−1.2,  1,  −1.2,  1,  …, −1.2,  1),  (5,  5,  …,  5),  (10,  10,  …,  10),   (15,  15,  …,  15)
2
Extended Rosenbrock function  [24]
500,  1000,  5000,  10000
(−1.2,  1,  −1.2,  1, …,  −1.2,  1),  (5,  5,  …,  5),  (10,  10,  …,  10),  (15,  15, …,  15)
3
Six-hump function [25]
2
(1,  1),  (5,  5),  (10,  10),  (15,  15)
4
Extended Beale function  [23]
500,  1000,  5000,  10000
(−1,  −1,  …,  −1),  (0.5, 0.5,..., 0.5),  (10,  10, …,  10),  (1,  1,  …,  1)
5
Three-hump function [25]
2
(1,  1),  (5,  5),  (10,  10),  (15,  15)
6
Extended  Himmelblau function  [23]
500,  1000,  5000,  10000
(1,  1,  …,  1),  (5,  5,  …,  5),  (10,  10, …,  10),  (15,  15,  …,  15)
7
Diagonal 2 function  [23]
500,  1000,  5000,  10000
(0.2,  0.2,  …,  0.2),  (0.25,  0.25, …,  0.25),  (0.5,  0.5, …,  0.5),  (1,  1,  …,  1)
8
NONSCOMP function [24]
500, 1000,  5000,  10000
(1,  1,  …,  1),  (−1,  −1,  …,  −1),  (−2,  −2, …,  −2),  (−5,  −5,  …,  −5)
9
Extended DENSCHNB function  [24]
500,  1000,  5000,  10000
(1,  1,  …,  1),  (5,  5,  …,  5),  (10,  10, …,  10),  (15,  15,  …,  15)
10
Booth function [25]
2
(1,  1),  (5,  5),  (10,  10),  (15,  15)
11
Extended quadratic penalty function  QP2  [24]
100,  200,  300,  400
(2,  2,  …,  2),  (5,  5,  …,  5),  (10,  10, …,  10),  (15,  15,  …,  15)
12
DIXMAANA function  [24]
1500,  3000,  6000,  9000
(1,  1, …,  1),  (2,  2,  …,  2),  (3,  3,  …, 3),  (5,  5, …, 5)
13
DIXMAANB function  [24]
1500,  3000,  6000,  9000
(1,  1,  …,  1),  (2,  2,  …,  2),  (3,  3,  …,  3),  (5,  5,  …,  5)
14
DIXMAANC function  [24]
1500,  3000,  6000,  9000
(1,  1, …,  1),  (2,  2,  …,  2),  (3,  3,  …, 3),  (5,  5, …, 5)
15
DIXMAAND function  [24]
1500,  3000,  6000, 9000
(1,  1, …,  1),  (2,  2,  …,  2),  (3,  3,  …, 3),  (5,  5, …, 5)
16
DIXMAANE function  [24]
1500,  3000,  6000,  9000
(1,  1, …,  1),  (2,  2,  …,  2),  (3,  3,  …, 3),  (5,  5, …, 5)
17
DIXMAANF function  [24]
1500,  3000,  6000,  9000
(1,  1, …,  1),  (2,  2,  …,  2),  (3,  3,  …, 3),  (5,  5, …, 5)
18
DIXMAANG function  [24]
1500,  3000,  6000,  9000
(1,  1, …,  1),  (2,  2,  …,  2),  (3,  3,  …, 3),  (5,  5, …, 5)
19
NONDIA function   [24]
500,  1000,  5000,  10000
(−2,  −2,  …,  −2),  (−1,  −1,  …,  −1),  (0,  0, …,  0),  (1,  1,  …,  1)
20
Extended Tridiagonal 1 function [24]
500,  1000,  5000,  10000
(1,  1,  …,  1),  (5,  5, …,  5),  (10,  10, …,  10),  (15,  15,  …,  15)
21
DQDRTIC function  [24]
500,  1000, 5000, 10000
(−1,  −1, …,  −1),  (1,  1,  …,  1),  (2,  2, …,  2),  (3,  3,  …,  3)
22
Diagonal 4 function  [24]
500, 1000,  5000,  10000
(1,  1,  …,  1),  (5,  5,  …,  5),  (10,  10, …,  10),  (15,  15,  …,  15)
23
DQDRTIC  function  [24]
10,  20,  30,  40
(1,  1, …,  1),  (−1,  −1,  …,  −1),  (1,  1, …,  1),  (2,  2,  …,  2)
24
Extended Cliff function  [24]
100,  200,  300,  400
(1,  1,  …,  1),  (5,  5,  …,  5),  (10,  10, …,  10),  (15,  15,  …,  15)In Table1 we selected different initial points for every function. Thus, this demonstrated that this method can be used in several real life functions from other fields such as engineering and medical science as we mentioned before. In addition different dimensions from 500 until 10000 are used. We also choose from different group of functions. We used Matlab 7.9 subroutine program, with CPU processor Intel (R) Core (TM), i3 CPU, and 2 GB DDR2 RAM under SWP line search to find the optimum point. The efficiency comparisons results are shown in Figures 1 and 2, respectively, using a performance profile introduced by Dolan and Moré [26].Figure 1
Performance profile based on the number of iterations.Figure 2
Performance profile based on the CPU time.This performance measure was introduced to compare a set of solversS on a set of problems P. Assuming ns solvers and np problems in S and P, respectively, the measure tp,s is defined as the computation time (e.g., the number of iterations or the CPU time) required to solve problem p by solver s.To create a baseline for comparison, the performance of solvers on problem p is scaled by the best performance of any solver in S on the problem using the ratio(41)rp,s=tp,smin⁡tp,s:s∈S.Suppose that a parameter rM≥rp,s for all p,s is chosen, and rp,s=rM if and only if solver s does not solve problem p. Because we would like to obtain an overall assessment of the performance of a solver, we defined the measure(42)ρst=1npsizep∈P:rp,s≤t.Thus, ρs(t) is the probability for solver s∈S that the performance ratio rp,s is within a factor t∈R of the best possible ratio. If we define the function ps as the cumulative distribution function for the performance ratio, then the performance measure ps:R→[0,1] for a solver is nondecreasing and piecewise continuous from the right. The value of ps(1) is the probability that the solver has the best performance of all of the solvers. In general, a solver with high values of p(t), which would appear in the upper right corner of the figure, is preferable.Based on the left side of Figures1 and 2 the PRP∗∗ formula is above the other curves. Therefore, it is the most efficient method among related PRP methods in terms of efficiency and robustness. In Figure 2 we see that the curve of PRP∗∗ is still the best, but the efficiency is not good as the number of iterations since we use the complicated hybrid algorithm leads to high CPU time. Thus, using high processors computers to find the solution will be more efficient since the number of iterations decreased rapidly under PRP∗∗ method.


## 5. Conclusion

In this paper, we proposed hybrid conjugate gradient method by using nonnegative PRP and NPRP formulas with the SWP line search which extended the cases of using PRP method under mild condition. The global convergence property is established and it is very simple. Our numerical results had shown that the hybrid method is the best when compared to other related PRP CG methods.



---

*Source: 103517-2015-07-22.xml*