# A Conjugate Gradient Method with Global Convergence for Large-Scale Unconstrained Optimization Problems

Authors: Shengwei Yao; Xiwen Lu; Zengxin Wei
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The conjugate gradient (CG) method has played a special role in solving large-scale nonlinear
optimization problems due to the simplicity of their very low memory requirements. This paper
proposes a conjugate gradient method which is similar to Dai-Liao conjugate gradient method (Dai and Liao, 2001)
but has stronger convergence properties. The given method possesses the sufficient descent condition,
and is globally convergent under strong Wolfe-Powell (SWP) line search for general function. Our
numerical results show that the proposed method is very efficient for the test problems.


---

## Body

## 1. Introduction

The conjugate gradient (CG) method has played a special role in solving large-scale nonlinear optimization due to the simplicity of their iterations and their very low memory requirements. In fact, the CG method is not among the fastest or most robust optimization algorithms for nonlinear problems available today, but it remains very popular for engineers and mathematicians who are interested in solving large problems. The conjugate gradient method is designed to solve the following unconstrained optimization problem:(1)min{f(x)∣x∈Rn},
where f(x):Rn→R is a smooth, nonlinear function whose gradient will be denoted by g(x). The iterative formula of the conjugate gradient method is given by
(2)xk+1=xk+sk,sk=αkdk,
where αk is a step length which is computed by carrying out a line search, and dk is the search direction defined by
(3)dk={-gkifk=1,-gk+βkdk-1ifk≥2,
where βk is a scalar and gk denotes the gradient ∇f(xk). If f is a strictly convex quadratic function, namely,
(4)f(x)=12xTHx+bTx,
where H is a positive definite matrix and if αk is the exact one-dimensional minimizer along the direction dk, then the method with (2) and (3) are called the linear conjugate gradient method. Otherwise, (2) and (3) is called the nonlinear conjugate gradient method. The most important feature of linear conjugate gradient method is that the search directions satisfy the following conjugacy condition:
(5)diTHdj=0,i≠j.
For nonlinear conjugate gradient methods, for general objective functions, (5) does not hold, since the Hessian ∇2f(x) changes at different points.Some well-known formulas forβk are the Fletcher-Reeves (FR), Polak-Ribière (PR), Hestense-Stiefel (HS), and Dai-Yuan (DY) methods which are given, respectively, by
(6)βkFR=∥gk∥2∥gk-1∥2,(7)βkPR=gkT(gk-gk-1)∥gk-1∥2,(8)βkHS=gkT(gk-gk-1)(gk-gk-1)Tdk-1,(9)βkDY=∥gk∥2(gk-gk-1)Tdk-1,
where ∥∥ denotes the Euclidean norm. Their corresponding conjugate methods are abbreviated as FR, PR, HS, and DY methods. Although all these methods are equivalent in the linear case, namely, when f is a strictly convex quadratic function and αk are determined by exact line search, their behaviors for general objective functions may be far different.For general functions, Zoutendijk [1] proved the global convergence of FR method with exact line search (here and throughout this paper, for global convergence, we mean that the sequence generated by the corresponding methods will either terminate after finite steps or contain a subsequence such that it converges to a stationary point of the objective function from a given initial point). Although one would be satisfied with its global convergence properties, the FR method performs much worse than the PR (HS) method in real computations. Powell [2] analyzed a major numerical drawback of the FR method; namely, if a small step is generated away from the solution point, the subsequent steps may be also very short. On the other hand, in practical computation, the HS method resembles the PR method, and both methods are generally believed to be the most efficient conjugate gradient methods since these two methods essentially perform a restart if a bad direction occurs. However, Powell [3] constructed a counterexample and showed that the PR method and HS method can cycle infinitely without approaching the solution. This example suggests that these two methods have a drawback that they are not globally convergent for general functions. Therefore, in the past two decades, much effort has been exceterd to find out new formulas for conjugate methods such that not only they are globally convergent for general functions but also they have good numerical performance.Recently, using a new conjugacy condition, Dai and Liao [4] proposed two new methods. Interestingly, one of their methods is not only globally convergent for general functions but also performs better than HS and PR methods. In this paper, similar to Dai and Liao's approach, we propose another formula for βk, analyze the convergence properties for the given method, and also carry the numerical experiment which shows that the given method is robust and efficient.The remainder of this paper is organized as follows. In Section2, we firstly state the corresponding formula which is proposed by Dai and Liao [4] and the motivations of this paper, and then we propose the new nonlinear conjugate gradient method. In Section 3, convergence analysis for the given method is presented. Numerical results are reported in Section 4. Finally, some conclusions are given in Section 5.


## 2. Motivations and New Nonlinear Conjugate Gradient Method

### 2.1.  Dai-Liao's Methods

It is well known that the linear conjugate gradient methods generate a sequence of search directionsdk such that the conjugacy condition (5) holds. Denote yk-1 to be the gradient change, which means that
(10)yk-1=gk-gk-1.
For a general nonlinear function f, we know by the mean value theorem that there exists some t∈(0,1) such that
(11)yk-1Tdk=αk-1dkT∇2f(xk-1+tαk-1dk-1)dk-1.
Therefore, it is reasonable to replace (5) with the following conjugacy condition:
(12)yk-1Tdk=0.
Recently, extension of (12) has been studied by Dai and Liao in [4]. Their approach is based on the Quasi-Newton techniques. Recall that, in the Quasi-Newton method, an approximation matrix Hk-1 of the Hessian ∇2f(xk-1) is updated such that the new matrix Hk satisfies the following Quasi-Newton equation:
(13)Hksk-1=yk-1.
The search direction dk in Quasi-Newton method is calculated by
(14)dk=-Hk-1gk.
Combining these two equations, we obtain
(15)dkTyk-1=dkT(Hksk-1)=-gkTsk-1.
The previous relation implies that (12) holds if the line search is exact since in this case gkTdk-1=0. However, practical numerical algorithms normally adopt inexact line searches instead of exact line searches. For this reason, it seems more reasonable to replace the conjugacy condition (12) with the condition
(16)dkTyk-1=-tgkTsk-1,t≥0,
where t≥0 is a scalar.To ensure that the search directiondk satisfies the conjugate condition (16), one only needs to multiply (3) with yk-1 and use (16), yielding
(17)βkDL1=gkT(yk-1-tsk-1)dk-1Tyk-1.
It is obvious that
(18)βkDL1=βkHS-tgkTsk-1dk-1Tyk-1.
For simplicity, we call the method with (2), (3), and (17) as DL1 method. Dai and Liao also prove that the conjugate gradient method with DL1 is globally convergent for uniformly convex functions. For general functions, Powell [3] constructed an example showing that the PR method may cycle without approaching any solution point if the step length αk is chosen to be the first local minimizer along dk. Since the DL1 method reduces to the PR method in the case that gkTdk-1=0 holds, this implies that the method with (17) need not converge for general functions. To get the global convergence, like Gilbert and Nocedal [5], who have proved the global convergence of the PR method with the restriction that βkPR≥0, Dai and Liao replaced (17) by
(19)βkDL=max{gkTyk-1dk-1Tyk-1,0}-tgkTsk-1dk-1Tyk-1=max{βkHS,0}-tgkTsk-1dk-1Tyk-1.
We also call the method with (2), (3), and (19) as DL method, Dai and Liao show that DL method is globally convergent for general functions under the sufficient descent condition (21) and some suitable conditions. Besides, some numerical experiments in [4] indicate the efficiency of this method.Similar to Dai and Liao's approach, Li et al. [6] proposed another conjugate condition and related conjugate gradient methods, and they also prove that the proposed methods are globally convergent under some assumptions.


### 2.2. Motivations

From the above discussions, Dai and Liao's approach is effective; the main reason is that the search directionsdk generated by DL1 method or DL method not only contain the gradient information but also contain some Hessian ∇2f(x) information. From (18) and (19), βkDL1 and βkDL are formed by two parts; the first part is βkHS, and the second part is -t(gkTsk-1/dk-1Tyk-1). So, we also can consider DL1 and DL methods as some modified forms of the HS method by adding some information of Hessian ∇2f(x) which is contained in the second part. The convergence properties of the HS method are similar to PR method; it does not converge for general functions even if the line search is exact. In order to get the convergence, one also needs the nonnegative restriction βk=max{βkHS,0} and the sufficient descent assumption (21). From the above discussion, the descent condition or sufficient descent condition and nonnegative property of βk play important roles in the convergence analysis. We say that the descent condition holds if for each search directions dk(20)gkTdk<0,∀k≥1.
In addition, we say that the sufficient descent condition holds if there exists a constant c>0 such that for each search direction dk, we have
(21)gkTdk≤-c∥gk∥2,∀k≥1.
Motivated by the above ideal, in this paper, we focus on finding the new conjugate gradient method which possesses the following properties: (1)
nonnegative propertyβk≥0;(2)
the new formula contains not only the gradient information but also some Hessian information;(3)
the search directionsdk generated by the proposed method satisfy the sufficient descent conditions (21).


### 2.3. The New Conjugate Gradient Method

From the structure of (6), (7), (8), and (9), the PR and HS methods have the common numerator gkTyk-1, and the FR and DY methods have the common numerator ∥gk∥2; and this different choice makes them have different properties. Generally speaking, FR and DY methods have better convergence properties, and PR and HS methods have better numerical experiments. Powell [3] pointed out that the FR method, with exact line search, was susceptible to jamming. That is, the algorithm could take many short steps without making significant progress to the minimum. If the line search is exact, that means gkTdk-1=0, in this case, DY method will turn out to be FR method. So, these two methods have the same disadvantage. The PR and HS methods which share the common numerator gkTyk-1 possess a built-in restart feature to avoid the jamming problem: when the step xk-xk-1 is small, the factor yk-1 in the numerator of βk tends to zero. Hence, the next search direction dk is essentially the steepest descent direction -gk. So, the numerical performance of these methods is better than the performance of the methods with ∥gk∥2 in numerator of βk.Just as above discussions, great attentions were given to find the methods which not only have global convergent properties but also have nice numerical experiments.Recently, Wei et al. [7] proposed a new formula
(22)βkWYL=gkTyk-1*∥gk-1∥2,yk-1*=gk-∥gk∥∥gk-1∥gk-1.The method with formulaβkWYL not only has nice numerical results but also possesses the sufficient descent condition and global convergence properties under the strong Wolfe-Powell line search. From the structure of βkWYL, we know that the method with βkWYL can also avoid jamming: when the step xk-xk-1 is small, ∥gk∥/∥gk-1∥ tends to 1 and the next search direction tends to the steepest descent direction which is similar to PR method. But WYL method has some advantages, such as under strong Wolfe-Powell line search, βkWYL≥0, and if the parameter σ≤1/4 in SWP, WYL method possesses the sufficient descent condition which deduces the global convergence of the WYL method.In [8, 9], Shengwei et al. extended such modification to HS method as follows:
(23)βkMHS=gkTyk-1*dk-1Tyk-1,yk-1*=gk-∥gk∥∥gk-1∥gk-1.
The previous formulae βkWYL and βkMHS can be considered as the modification forms of βkPR and βkHS by using yk-1* to replace yk-1, respectively. In [8, 9], the corresponding methods are proved to be globally convergent for general functions under the strong Wolfe-Powell line search and Grippo-Lucidi line search. Based on the same approach, some authors give other discussions and modifications in [10–12]. In fact, yk-1* is not our point at the beginning, our purpose is involving the information of the angle between gk and gk-1. From this point of view, βkWYL has the following form:
(24)βkWYL=βkFR(1-cos(θ-k)),
where θ-k is the angle between gk and gk-1. By multiplying βkFR with 1-cosθ-k, the method not only has similar convergence properties with FR method, but also avoids jamming which is similar to PR method.The above analysis motivates us to propose the following formula to computeβk:
(25)βkMDL1=max{gkTyk-1*dk-1Tyk-1,0}-tgkTsk-1dk-1Tyk-1,
where yk-1*=gk-(∥gk∥/∥gk-1∥)gk-1. Since the βkMHS are nonnegative under the strong Wolfe-Powell line search, we omit the nonnegative restriction and propose the following formula:
(26)βkMDL=gkTyk-1*dk-1Tyk-1-tgkTsk-1dk-1Tyk-1=βkMHS-tgkTsk-1dk-1Tyk-1.From (25) and (26), we know that we only substitute yk-1 in the first part of the numerator of βkDL1orβkDL by yk*. The reason is that we hope the formulae (25) and (26) contain the angle information between gk and gk-1. In fact, βkMDL can be expressed as
(27)βkMDL=∥gk∥2dk-1Tyk-1(1-cosθ-k)-tgkTsk-1dk-1Tyk-1=βkDY(1-cosθ-k)-tgkTsk-1dk-1Tyk-1.
For simplicity, we call the method generated by (2), (3), and (26) as MDL method and give the algorithm as follows.Algorithm 1 (MDL).
Step  1. Given x1∈Rn, ε≥0, set d1=-g1, k=1; if ∥g1∥≤ε, then stop.
Step  2. Compute tk by some line searches.
Step  3. Let xk+1=xk+αkdk, and let gk+1=g(xk+1); if ∥gk∥≤ε, then stop.
Step  4. Compute βk by (26) and generate dk+1 by (3).
Step  5. Set k≔k+1 and go to Step  2.We make the following basic assumptions on the objective functions.Assumption A.
(i) The level setΓ={x∈Rn:f(x)≤f(x1)} is bounded; namely, there exists a constant B>0 such that
(28)∥x∥≤B,∀x∈Γ.
(ii) In some neighborhoodN of Γ, f is continuously differentiable, and its gradient is Lipschitz continuous; namely, there exists a constant L>0 such that
(29)∥g(x)-g(y)∥≤L∥x-y∥,∀x,y∈N.
Under the above assumptions of f, there exists a constant γ-≥0 such that
(30)∥∇f(x)∥≤γ-,∀x∈Γ.
The step lengthαk in Algorithm 1 (MDL) is obtained by some line search scheme. In conjugate gradient methods, the strong Wolfe-Powell conditions; namely,
(31)f(xk+αkdk)-f(xk)≤δαkgkTdk,(32)|g(xk+αkdk)Tdk|≤-σgkTdk,
where 0<δ<σ<1, are often imposed on the line search (SWP).


## 2.1.  Dai-Liao's Methods

It is well known that the linear conjugate gradient methods generate a sequence of search directionsdk such that the conjugacy condition (5) holds. Denote yk-1 to be the gradient change, which means that
(10)yk-1=gk-gk-1.
For a general nonlinear function f, we know by the mean value theorem that there exists some t∈(0,1) such that
(11)yk-1Tdk=αk-1dkT∇2f(xk-1+tαk-1dk-1)dk-1.
Therefore, it is reasonable to replace (5) with the following conjugacy condition:
(12)yk-1Tdk=0.
Recently, extension of (12) has been studied by Dai and Liao in [4]. Their approach is based on the Quasi-Newton techniques. Recall that, in the Quasi-Newton method, an approximation matrix Hk-1 of the Hessian ∇2f(xk-1) is updated such that the new matrix Hk satisfies the following Quasi-Newton equation:
(13)Hksk-1=yk-1.
The search direction dk in Quasi-Newton method is calculated by
(14)dk=-Hk-1gk.
Combining these two equations, we obtain
(15)dkTyk-1=dkT(Hksk-1)=-gkTsk-1.
The previous relation implies that (12) holds if the line search is exact since in this case gkTdk-1=0. However, practical numerical algorithms normally adopt inexact line searches instead of exact line searches. For this reason, it seems more reasonable to replace the conjugacy condition (12) with the condition
(16)dkTyk-1=-tgkTsk-1,t≥0,
where t≥0 is a scalar.To ensure that the search directiondk satisfies the conjugate condition (16), one only needs to multiply (3) with yk-1 and use (16), yielding
(17)βkDL1=gkT(yk-1-tsk-1)dk-1Tyk-1.
It is obvious that
(18)βkDL1=βkHS-tgkTsk-1dk-1Tyk-1.
For simplicity, we call the method with (2), (3), and (17) as DL1 method. Dai and Liao also prove that the conjugate gradient method with DL1 is globally convergent for uniformly convex functions. For general functions, Powell [3] constructed an example showing that the PR method may cycle without approaching any solution point if the step length αk is chosen to be the first local minimizer along dk. Since the DL1 method reduces to the PR method in the case that gkTdk-1=0 holds, this implies that the method with (17) need not converge for general functions. To get the global convergence, like Gilbert and Nocedal [5], who have proved the global convergence of the PR method with the restriction that βkPR≥0, Dai and Liao replaced (17) by
(19)βkDL=max{gkTyk-1dk-1Tyk-1,0}-tgkTsk-1dk-1Tyk-1=max{βkHS,0}-tgkTsk-1dk-1Tyk-1.
We also call the method with (2), (3), and (19) as DL method, Dai and Liao show that DL method is globally convergent for general functions under the sufficient descent condition (21) and some suitable conditions. Besides, some numerical experiments in [4] indicate the efficiency of this method.Similar to Dai and Liao's approach, Li et al. [6] proposed another conjugate condition and related conjugate gradient methods, and they also prove that the proposed methods are globally convergent under some assumptions.


## 2.2. Motivations

From the above discussions, Dai and Liao's approach is effective; the main reason is that the search directionsdk generated by DL1 method or DL method not only contain the gradient information but also contain some Hessian ∇2f(x) information. From (18) and (19), βkDL1 and βkDL are formed by two parts; the first part is βkHS, and the second part is -t(gkTsk-1/dk-1Tyk-1). So, we also can consider DL1 and DL methods as some modified forms of the HS method by adding some information of Hessian ∇2f(x) which is contained in the second part. The convergence properties of the HS method are similar to PR method; it does not converge for general functions even if the line search is exact. In order to get the convergence, one also needs the nonnegative restriction βk=max{βkHS,0} and the sufficient descent assumption (21). From the above discussion, the descent condition or sufficient descent condition and nonnegative property of βk play important roles in the convergence analysis. We say that the descent condition holds if for each search directions dk(20)gkTdk<0,∀k≥1.
In addition, we say that the sufficient descent condition holds if there exists a constant c>0 such that for each search direction dk, we have
(21)gkTdk≤-c∥gk∥2,∀k≥1.
Motivated by the above ideal, in this paper, we focus on finding the new conjugate gradient method which possesses the following properties: (1)
nonnegative propertyβk≥0;(2)
the new formula contains not only the gradient information but also some Hessian information;(3)
the search directionsdk generated by the proposed method satisfy the sufficient descent conditions (21).


## 2.3. The New Conjugate Gradient Method

From the structure of (6), (7), (8), and (9), the PR and HS methods have the common numerator gkTyk-1, and the FR and DY methods have the common numerator ∥gk∥2; and this different choice makes them have different properties. Generally speaking, FR and DY methods have better convergence properties, and PR and HS methods have better numerical experiments. Powell [3] pointed out that the FR method, with exact line search, was susceptible to jamming. That is, the algorithm could take many short steps without making significant progress to the minimum. If the line search is exact, that means gkTdk-1=0, in this case, DY method will turn out to be FR method. So, these two methods have the same disadvantage. The PR and HS methods which share the common numerator gkTyk-1 possess a built-in restart feature to avoid the jamming problem: when the step xk-xk-1 is small, the factor yk-1 in the numerator of βk tends to zero. Hence, the next search direction dk is essentially the steepest descent direction -gk. So, the numerical performance of these methods is better than the performance of the methods with ∥gk∥2 in numerator of βk.Just as above discussions, great attentions were given to find the methods which not only have global convergent properties but also have nice numerical experiments.Recently, Wei et al. [7] proposed a new formula
(22)βkWYL=gkTyk-1*∥gk-1∥2,yk-1*=gk-∥gk∥∥gk-1∥gk-1.The method with formulaβkWYL not only has nice numerical results but also possesses the sufficient descent condition and global convergence properties under the strong Wolfe-Powell line search. From the structure of βkWYL, we know that the method with βkWYL can also avoid jamming: when the step xk-xk-1 is small, ∥gk∥/∥gk-1∥ tends to 1 and the next search direction tends to the steepest descent direction which is similar to PR method. But WYL method has some advantages, such as under strong Wolfe-Powell line search, βkWYL≥0, and if the parameter σ≤1/4 in SWP, WYL method possesses the sufficient descent condition which deduces the global convergence of the WYL method.In [8, 9], Shengwei et al. extended such modification to HS method as follows:
(23)βkMHS=gkTyk-1*dk-1Tyk-1,yk-1*=gk-∥gk∥∥gk-1∥gk-1.
The previous formulae βkWYL and βkMHS can be considered as the modification forms of βkPR and βkHS by using yk-1* to replace yk-1, respectively. In [8, 9], the corresponding methods are proved to be globally convergent for general functions under the strong Wolfe-Powell line search and Grippo-Lucidi line search. Based on the same approach, some authors give other discussions and modifications in [10–12]. In fact, yk-1* is not our point at the beginning, our purpose is involving the information of the angle between gk and gk-1. From this point of view, βkWYL has the following form:
(24)βkWYL=βkFR(1-cos(θ-k)),
where θ-k is the angle between gk and gk-1. By multiplying βkFR with 1-cosθ-k, the method not only has similar convergence properties with FR method, but also avoids jamming which is similar to PR method.The above analysis motivates us to propose the following formula to computeβk:
(25)βkMDL1=max{gkTyk-1*dk-1Tyk-1,0}-tgkTsk-1dk-1Tyk-1,
where yk-1*=gk-(∥gk∥/∥gk-1∥)gk-1. Since the βkMHS are nonnegative under the strong Wolfe-Powell line search, we omit the nonnegative restriction and propose the following formula:
(26)βkMDL=gkTyk-1*dk-1Tyk-1-tgkTsk-1dk-1Tyk-1=βkMHS-tgkTsk-1dk-1Tyk-1.From (25) and (26), we know that we only substitute yk-1 in the first part of the numerator of βkDL1orβkDL by yk*. The reason is that we hope the formulae (25) and (26) contain the angle information between gk and gk-1. In fact, βkMDL can be expressed as
(27)βkMDL=∥gk∥2dk-1Tyk-1(1-cosθ-k)-tgkTsk-1dk-1Tyk-1=βkDY(1-cosθ-k)-tgkTsk-1dk-1Tyk-1.
For simplicity, we call the method generated by (2), (3), and (26) as MDL method and give the algorithm as follows.Algorithm 1 (MDL).
Step  1. Given x1∈Rn, ε≥0, set d1=-g1, k=1; if ∥g1∥≤ε, then stop.
Step  2. Compute tk by some line searches.
Step  3. Let xk+1=xk+αkdk, and let gk+1=g(xk+1); if ∥gk∥≤ε, then stop.
Step  4. Compute βk by (26) and generate dk+1 by (3).
Step  5. Set k≔k+1 and go to Step  2.We make the following basic assumptions on the objective functions.Assumption A.
(i) The level setΓ={x∈Rn:f(x)≤f(x1)} is bounded; namely, there exists a constant B>0 such that
(28)∥x∥≤B,∀x∈Γ.
(ii) In some neighborhoodN of Γ, f is continuously differentiable, and its gradient is Lipschitz continuous; namely, there exists a constant L>0 such that
(29)∥g(x)-g(y)∥≤L∥x-y∥,∀x,y∈N.
Under the above assumptions of f, there exists a constant γ-≥0 such that
(30)∥∇f(x)∥≤γ-,∀x∈Γ.
The step lengthαk in Algorithm 1 (MDL) is obtained by some line search scheme. In conjugate gradient methods, the strong Wolfe-Powell conditions; namely,
(31)f(xk+αkdk)-f(xk)≤δαkgkTdk,(32)|g(xk+αkdk)Tdk|≤-σgkTdk,
where 0<δ<σ<1, are often imposed on the line search (SWP).


## 3. Convergence Analysis

Under Assumption A, based on the Zoutendijk condition in [1], for any conjugate gradient method with the strong Wolfe-Powell line search, Dai et al. in [13] proved the following general result.Lemma 2.
Suppose that Assumption A holds. Consider any conjugate gradient method in the form (2)-(3), where dk is a descent direction and αk is obtained by the strong Wolfe-Powell line search. If
(33)∑k≥1‍1∥dk∥2=∞.
One has that
(34)liminfk→∞∥gk∥=0.
If the objective functions are uniformly convex, we can prove that the norm of dk generated by Algorithm 1 (MDL) is bounded previously. Thus, by Lemma 2 one immediately has the following result.Theorem 3.
Suppose that Assumption A holds. ConsiderMDL method, where dk is a descent direction and αk is obtained by the strong Wolfe-Powell line search. If the objective functions are uniformly convex, namely, there exists a constant μ>0 such that
(35)(∇f(x)-∇f(y))T(x-y)≥μ∥x-y∥2,∀x,y∈Γ.
One has that
(36)limk→∞∥gk∥=0.Proof.
It follows from (35) that
(37)dk-1Tyk-1≥μαk-1∥dk-1∥2.
By (3), (26), (29), (30), and (37), we have
(38)∥dk∥≤∥gk∥+|βkMDL|∥dk-1∥≤∥gk∥+gkT(gk-(∥gk∥/∥gk-1∥)gk-1-tsk-1)μαk-1∥dk-1∥2∥dk-1∥=∥gk∥+gkT(gk-gk-1+gk-1-(∥gk∥/∥gk-1∥)gk-1-tsk-1)μαk-1∥dk-1∥2×∥dk-1∥≤∥gk∥+∥gk∥(∥gk-gk-1∥+∥gk-1(1-∥gk∥/∥gk-1∥)∥+t∥sk-1∥)μαk-1∥dk-1∥2×∥dk-1∥≤∥gk∥+∥gk∥(∥gk-gk-1∥+|∥gk-1∥-∥gk∥|+t∥sk-1∥)μαk-1∥dk-1∥2∥dk-1∥≤∥gk∥+∥gk∥(2L∥sk-1∥+t∥sk-1∥)μαk-1∥dk-1∥2∥dk-1∥≤γ-(1+2L+tμ)=γ-μ-1(μ+2L+t),
which implies the truth of (33). Therefore, by Lemma 2 we have (34), which is equivalent to (36) for uniformly convex functions. The proof is completed.In order to prove the convergence of theMDL method, we need to state some properties of βkMHS.Lemma 4.
In any conjugate gradient methods, if the parameterβk is computed by (23), namely, βk=βkMHS, and αk is determined by strong Wolfe-Powell line search of (31) and (32), then
(39)βkMHS≥0.Proof.
BySWP condition (32), we have dk-1Tyk-1≥σgk-1Tdk-1-gk-1Tdk-1≥0, since σ<1 and g1Td1=-∥g1∥2<0. So we have
(40)βkMHS=gkT(gk-(∥gk∥/∥gk-1∥)gk-1)dk-1Tyk-1=∥gk∥2dk-1Tyk-1(1-cosθ-k)≥0.
The proof is completed.In addition, we can also prove that, in conjugate gradient method of forms (2)-(3), if βk is computed by βkMDL (26) and αk is determined by strong Wolfe-Powell line search, then the search direction dk satisfies the sufficient descent condition (21).Theorem 5.
In any conjugate gradient methods, in which the parameterβk is computed by (26), namely, βk=βkMDL, and αk is determined by strong Wolfe-Powell line search of (31) and (32), if σ<1/3, then the search direction dk satisfied the sufficient descent condition (21).Proof.
We prove this theorem by induction. Firstly, we prove the descent conditiondkTgk<0 as follow.
Sinceg1Td1=-∥g1∥2<0, supposing that giTdi<0 holds for i≤k-1, we deduce that the descent condition holds by proving that giTdi<0 holds for i=k as follow.
BySWP condition (32), we have dk-1Tyk-1≥(σ-1)gk-1Tdk-1>0. Combining (3) and (26), we have
(41)gkTdk∥gk∥2=-1+(1-cosθ-k)dk-1Tyk-1gkTdk-1-t*(gkTdk-1)2αk-1(dk-1Tyk-1)∥gk∥2≤-1+2-σgk-1Tdk-1dk-1Tyk-1≤-1+2-σgk-1Tdk-1(σ-1)gk-1Tdk-1≤-1+3σ1-σ<0.
Equation (41) means that descent condition holds.
Secondly, we prove the following sufficient descent condition.
Setc=1-2σ/(1-σ); since the restriction σ<1/3, we have 0<c<1. Combining g1Td1=-∥g1∥2 and (41), the sufficient descent condition (21) holds immediately.By Theorem5, we can prove the following Lemma 6.Lemma 6.
Suppose that Assumption A holds. ConsiderMDL method, where αk is obtained by strong Wolfe-Powell lien search with σ<1/3. If there exists a constant γ>0 such that
(42)∥gk∥≥γ,∀k≥1,
then dk≠0 and
(43)∑k≥2‍∥uk-uk-1∥2<∞,
where uk=dk/∥dk∥.Proof.
Firstly, note thatdk≠0; otherwise, (21) is false. Therefore, uk is well defined. In addition, by relation (42) and Lemma 2, we have
(44)∑k≥1‍1∥dk∥2<∞.
Now, we divide formula βkMDL into two parts as follows:
(45)βk1=gkTyk-1*dk-1Tyk-1,βk2=-tgkTsk-1dk-1Tyk-1,
and define
(46)rk≔ϑk∥dk∥,δk≔βk1∥dk-1∥∥dk∥,
where ϑk=-gk+βk2dk-1.
Then by (3) we have for all k≥2,
(47)uk=rk+δkuk-1.
Using the identity ∥uk∥=∥uk-1∥=1 and (47) we can obtain
(48)∥rk∥=∥uk-δkuk-1∥=∥δkuk-uk-1∥,
using the condition δk=βkMHS(∥dk-1∥/∥dk∥)≥0, the triangle inequality, and (48), it follows that
(49)∥uk-uk-1∥≤∥(1+δ)uk-(1+δ)uk-1∥≤∥uk-δkuk-1∥+∥δkuk-uk-1∥=2∥rk∥.
On the other hand, the line search condition (32) gives
(50)yk-1Tdk-1≥(σ-1)gk-1Tdk-1.
Equations (50), (32), and (21) imply that
(51)|gkTdk-1dk-1Tyk-1|≤σ1-σ.
It follows from the definition of ϑk, (51), (28), and (30) that
(52)∥ϑk∥≤∥δk∥+t|gkTsk-1dk-1Tyk-1|∥dk-1∥=∥δk∥+t|gkTdk-1dk-1Tyk-1|∥sk-1∥≤γ-+tσ1-σ2B.
So, we have
(53)∑‍∥uk-uk-1∥2≤4∑‍∥rk∥2≤4∑‍ϑk2∥dk∥2≤4(γ-+tσ1-σ2B)2∑‍1∥dk∥2<∞.
The proof is completed.Gilbert and Nocedal [5] introduced property (*) which is very important for the convergence properties of the conjugate gradient methods. We are going to show that method with βkMDL possesses such property (*).Property (*). Consider a method of forms (2) and (3). Suppose that
(54)0<γ≤∥gk∥≤γ-,∀k≥1.
We say that the method has property (*), if for all k, there exist constants b>1, λ>0 such that |βk|≤b and if ∥sk-1∥≤λ we have |βk|≤1/2b.In fact, by (50), (21), and (42), we have
(55)dk-1Tyk-1≥(σ-1)gk-1Tdk-1≥c(1-σ)∥gk-1∥2≥(1-σ)cγ2.
Using this, (28), (29), and (30) we obtain
(56)|βkMDL|≤(2L+t)∥gk∥∥sk-1∥(1-σ)cγ2≤2(2L+t)γ-B(1-σ)cγ2≕b.
Note that b can be defined such that b>1. Therefore, we can say b>1. As a result, we define
(57)λ≔(1-σ)cγ22b(2L+t)γ-,
we get from the first inequality in (56) that if ∥sk-1∥≤λ, then
(58)|βkMDL|≤(2L+t)λ-(1-σ)cλ2=12b.LetN* denote the set of positive integers. For λ>0 and a positive integer Δ, denote
(59)Kk,Δλ≔{i∈N*:k≤i≤k+Δ-1,∥sk-1∥>λ}.
Let |Kk,Δλ| denote the number of elements in Kk,Δλ. From the previous property (*), we can prove the following lemma.Lemma 7.
Suppose that Assumption A holds. ConsiderMDL method, where αk is obtained by the strong Wolfe-Powell line search in which σ<1/3. Then if (42) holds, there exists λ>0 such that, for any Δ∈N* and any index k0, there is an index k≥k0 such that
(60)|Kk,Δλ|>Δ2.The proof of this lemma is similar to the proof of Lemma6 in [4]. In [4], authors proved that method with (19) has this property, if the search direction dk satisfies the sufficient descent condition (21). In our paper, we do not need this assumption, since the directions generated by MDL method with strong Wolfe-Powell line search always possess the sufficient descent condition (21). So, we omit the proof of this lemma.According to the previous lemmas and theorems, we can prove the following convergence theorem for theMDL.Theorem 8.
Suppose that Assumption A holds. ConsiderMDL method, if αk is obtained by strong Wolfe-Powell line search with σ<1/3. Then we have liminfk→∞∥gk∥=0.Proof.
We proceed by contradiction. Ifliminfk→∞∥gk∥>0, then (42) must hold. Then the conditions of Lemmas 6 and 7 hold. Defining ui=di/∥di∥, we have for any indices l, k, with l≥k,
(61)xl-xk-1=∑i=kl‍xi-xi-1=∑i=kl‍αi-1di-1=∑i=kl‍ui-1∥si-1∥=∑i=kl‍∥si-1∥uk-1+∑i=kl‍∥si-1∥(ui-1-uk-1).
Equation (61), ∥ui∥=1, and (28) give
(62)∑i=kl‍∥si-1∥≤∥xl-xk-1∥+∑i=kl‍∥si-1∥∥ui-1-uk-1∥≤2B+∑i=kl‍∥si-1∥∥ui-1-uk-1∥.
Letλ>0 be given by Lemma 7, and define Δ≔⌈8B/λ⌉ to be the smallest integer not less than 8B/λ. By Lemma 6, we can find an index k0≥1 such that
(63)∑i≥k0‍∥ui-1-uk-1∥2≤14Δ.
With this Δ and k0, Lemma 7 gives an index k≥k0 such that
(64)|Kk,Δλ|>Δ2.
For any index i∈[k,k+Δ-1], by Cauchy-Schwartz inequality and (63),
(65)∥ui-uk-1∥≤∑j=ki‍∥uj-uj-1∥≤(i-k+1)1/2(∑j=ki‍∥uj-uj-1∥2)1/2≤Δ1/2(14Δ)1/2=12.
From these relations (65) and (64) and taking l=k+Δ-1 in (62), we get
(66)2B≥12∑i=kk+Δ-1‍∥si-1∥>λ2|Kk,Δλ|>λΔ4.
Thus, Δ<8B/λ, which contradicts the definition of Δ. The proof is completed.


## 4. Numerical Results

From (26) and (27), the MDL method can be considered as(i)
form 1: a modification form ofDL method;(ii)
form 2: a modification form ofMHS method;(iii)
form 3: a modification form ofDY method.In form 1, theβkHS in βkDL is replaced by βkMHS. By this modification, we can guarantee the nonnegativity restrictions in DL method. In form 2, βkMDL is obtained by βkMHS adding an adjusting term -t(gkTsk-1/yk-1Tdk-1) which contains some Hessian information of the objective function. In form 3, βkMDL=βkDY(1-cosθ-k)-t(gkTsk-1/dk-1Tyk-1) shows that βkMDL is obtained by multiplying βkDY with (1-cosθ-k) and adding the second term -t(gkTsk-1/yk-1Tdk-1).From the above convergence analysis, we know thatMDL method has stronger convergent properties than DL method, and similar convergent properties with MHS method and DY method. So, in this section, we test the following four CG methods:(i)
MDL method: method of the forms (2) and (3), in which βk is computed by βkMDL (26);(ii)
DL method: method of the forms (2) and (3), in which βk is computed by βkDL (19);(iii)
MHS method: method of the forms (2) and (3), in which βk is computed by βkMHS (23);(iv)
DY method: method of the forms (2) and (3), in which βk is computed by βkDY (9).The step lengthαk in all methods is determined such that the strong Wolfe-Powell conditions (31) and (32) hold with δ=0.01 and σ=0.1.The test problems are drawn from [14]. The numerical results of our tests are reported in Table 1.Table 1
Numerical results.
Problem
Dim
MDL
DL
MHS
DY
ROSE
2
35/349/83
F
38/267/91
63/800/106
FROTH
2
18/88/29
9/25/18
15/84/26
16/38/26
BADSCP
2
28/275/64
36/510/96
42/362/96
F
BADSCB
2
26/446/48
F
28/452/50
F
BEALE
3
16/87/27
11/81/22
14/83/25
47/193/74
JENSAM
2
11/31/21
F
11/31/21
11/31/21
HELIX
3
49/347/81
28/164/54
47/390/73
80/406/126
BARD
3
18/38/26
24/145/37
18/86/26
48/148/77
GAUSS
3
4/9/5
3/7/4
4/9/5
4/9/5
SING
4
134/501/209
78/396/124
111/411/172
650/3254/1104
WOOD
4
102/613/182
179/865/306
207/1352/365
F
KOWOSB
4
39/178/66
46/383/72
53/259/88
462/1760/796
BIGGS
6
18/279/25
85/564/14
20/286/31
210/644/342
OSB2
11
268/1001/445
185/888/293
186/701/310
F
WATSON
20
1455/3587/2274
1426/4240/2255
1922/4843/3018
548/1480/864
ROSEX
8
36/446/90
26/421/62
38/362/93
63/764/100
50
46/548/101
32/469/84
44/412/101
86/707/146
100
45/459/99
23/445/57
46/414/102
71/856/112
SINGX
4
134/501/209
78/396/124
111/411/172
650/3254/1104
PEN1
2
5/18/12
12/182/34
5/18/12
5/18/12
PEN2
4
10/82/26
12/89/27
11/133/29
32/167/57
50
131/764/254
405/1453/683
136/1056/256
121/724/242
VARDIM
2
3/9/7
3/9/7
3/9/7
3/9/7
50
10/52/36
10/52/36
10/52/36
10/52/36
TRIG
3
13/129/27
11/82/25
15/225/27
162/974/267
50
38/320/70
38/222/68
38/225/71
206/1662/290
100
48/340/90
43/425/76
48/294/90
225/3077/286
BV
3
9/17/11
12/25/16
11/20/13
13/27/18
10
64/171/97
50/148/81
64/172/99
59/163/93
IE
200
5/59/7
6/13/8
5/59/7
6/61/8
500
5/11/7
6/13/8
6/13/8
6/13/8
TRID
3
14/33/18
10/26/17
14/33/18
15/84/21
200
31/68/39
30/66/37
31/68/39
36/78/42
BAND
3
7/64/12
9/20/13
7/64/12
7/64/12
50
19/670/26
15/278/23
19/670/26
F
100
18/712/27
16/373/26
18/712/27
F
500
18/677/26
16/339/27
18/677/26
F
LIN
1000
1/3/3
1/3/3
1/3/3
1/3/3
LIN1
10
1/3/3
1/3/3
1/3/3
1/3/3The column problem represents the problem name in [14], Dim represents the dimension of the problems. The numerical results are given in the form of I/F/G, where I, F, and G denote the numbers of iterations, function evaluations and gradient evaluations, respectively. The stopping condition is ∥gk∥≤10-6. Since we want to compare the performance of the different methods, in the numerical results, we omit the problems if all the four methods perform equally. The notation F means that, for this problem, the corresponding method fails.


## 5. Conclusions

In this paper, based onβkDY and βkDL, a new formula is proposed to compute the parameter βk of the conjugate gradient methods. The main motivations are to improve both the convergence properties and numerical behavior of the conjugate gradient method. For general conjugate gradient methods, in order to get the global convergence results, the methods are required to possess the following major properties:(1)
the generated directionsdk are descent directions;(2)
the parametersβk are nonnegative.In addition, to ensure that the methods have robust and efficient numerical behavior, the parameterβk needs to approach zero, when the small step sk occurs.From the convergence analysis of this paper, we known that the directionsdk generated by MDL method are descent directions, which is not true for DY or DL methods, and the proposed MDL method is globally convergent for general functions. In the previous section, we compare the numerical performance of the MDL method with the DY, MHS, and DL methods. From the convergence analysis and numerical results, comparing with the DL, DY, and MHS method, we can have the following.(a)
MDL method versus DL method: from the computational point of view, for most of the test problems, MDL method performs quite similarly with DL method. There are 15 problems in which MDL method outperforms the DL method and 18 problems in which DL method outperforms the MDL method. But, from the convergent point of view, the MDL method outperforms the DL method.(b)
MDL method versus DY method: the convergence properties of MDL method are similar to DY method. By comparing the numerical results of MDL method with DY method, there are 27 test problems in which MDL method outperforms the DY method and only 4 test problems in which DY method outperforms the MDL method. Therefore, we could say that MDL method is much better than the DY method in numerical behavior.(c)
MDL method versus MHS method: they possess similar convergence properties; the numerical results show that MDL method performs little better than the MHS method.



---

*Source: 730454-2013-11-28.xml*