# Nonlinear Conjugate Gradient Methods with Wolfe Type Line Search

Authors: Yuan-Yuan Chen; Shou-Qiang Du
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Nonlinear conjugate gradient method is one of the useful methods for unconstrained
optimization problems. In this paper, we consider three kinds of nonlinear
conjugate gradient methods with Wolfe type line search for unstrained optimization problems.
Under some mild assumptions, the global convergence results of the given methods
are proposed. The numerical results show that the nonlinear conjugate gradient methods
with Wolfe type line search are efficient for some unconstrained optimization problems.


---

## Body

## 1. Introduction

In this paper, we focus our attention on the global convergence of nonlinear conjugate gradient method with Wolfe type line search. We consider the following unconstrained optimization problem:(1)minx∈Rnf(x).
In (1), f is continuously differentiable function, and its gradient is denoted by g(x)=∇f(x). Of course, the iterative methods are often used for (1). The iterative formula is given by
(2)xk+1=xk+αkdk,
where xk,  xk+1∈Rn is the kth and (k+1)th iterative step, αk is a step size, and dk is a search direction. Here, in the following, we define the search direction by
(3)dk={-gk,ifk=1,-gk+βkdk-1,ifk≥2.
In (3), βk is a conjugate gradient scalar, and the well-known useful formulas are βkFR, βkPRP, βkHS, and βkDY (see [1–6]). Recently, some kinds of new nonlinear conjugate gradient methods are given in [7–11]. Based on the new method, we give some new kinds of nonlinear conjugate gradient methods and analyze the global convergence of the methods with Wolfe type line search.The rest of the paper is organized as follows. In Section2, we give the methods and the global convergence results for them. In the last section, numerical results and some discussions are given.


## 2. The Methods and Their Global Convergence Results

Firstly, we give the Wolfe type line search, which will be used in our new nonlinear conjugate gradient methods. In the following section of this paper,∥·∥ stands for the 2-norm.We have used the Wolfe type line search in [12].The line search is to computeαk>0 such that
(4)f(xk+αkdk)≤f(xk)-ραk2∥dk∥2,(5)g(xk+αkdk)Tdk≥-2σαk∥dk∥2,
where ρ,σ∈(0,1),ρ<σ.Now, we present the nonlinear conjugate gradient methods as follows.Algorithm 1.
We have the following steps.
…
Step0. Given x0∈Rn, set d0=-g0,k:=0. If ∥g0∥=0, then stop.
…
Step1. Find αk>0 satisfying (4) and (5), and by (2), xk+1 is given. If ∥gk+1∥=0, then stop.
…
Step2. Compute dk by the following equation:
(6)dk=βkdk-1-(1+βkgkTdk-1∥gk∥2)gk,
in which βk=-∥gk∥2/dk-1Tgk-1. Set k:=k+1, and go to Step 1.Before giving the global convergence theorem, we need the following assumptions.Assumption 1.
(A1) The setL0={x∈Rn∣f(x)≤f(x0)} is bounded.
(A2) In the neighborhood ofL0, denoted as U, f is continuously differentiable. Its gradient is Lipschitz continuous; namely, for x,y∈U, there exists L>0 such that
(7)∥g(x)-g(y)∥≤L∥x-y∥.
In order to establish the global convergence of Algorithm 1, we also need the following lemmas.Lemma 2.
Suppose that Assumption1 holds; then, (4) and (5) are well defined.The proof is essentially the same as Lemma 1 of [12]; hence, we do not rewrite it again.Lemma 3.
Suppose that directiondk is given by (6); then, one has
(8)dkTgk=-∥gk∥2≤0
holds for all k≥0. So, one knows that dk is descent search direction.Proof.
From the definitions ofdk and βk, we can get it.Lemma 4.
Suppose that Assumption1 holds, and αk is determined by (4) and (5); one has
(9)∑k=1∞(gkTdk)2∥dk∥2<+∞.Proof.
By (4), (5), Lemma 3, and Assumption 1, we can get
(10)-(2σ+L)αk∥dk∥2≤gkTdk.
Then, we know that
(11)(2σ+L)αk∥dk∥≥-gkTdk∥dk∥.
By squaring both sides of the previous inequation, we get
(12)(2σ+L)2αk2∥dk∥2≥(gkTdk)2∥dk∥2.
By (4), we know that
(13)∑k=1∞(gkTdk)2∥dk∥2≤∑k=1∞(2σ+L)2αk2∥dk∥2≤(2σ+L)2ρ∑k=1∞{f(xk)-f(xk+1)}<+∞.
So, we get (9), and this completes the proof of the lemma.Lemma 5.
Suppose that Assumption1 holds, dk is computed by (6), and αk is determined by (4) and (5); one has
(14)∑k≥0∥gk∥4∥dk∥2<+∞.Proof.
From Lemmas3 and 4, we can obtain (14).Theorem 6.
Consider Algorithm1, and suppose that Assumption 1 holds. Then, one has
(15)liminfk→∞∥gk∥=0.Proof.
We suppose that the theorem is not true. Suppose by contradiction that there existsϵ>0 such that
(16)∥gk∥≥ϵ
holds for k≥0.
From (6) and Lemma 3, we get
(17)∥dk∥2=(βk)2∥dk-1∥2-(1+βkgkTdk-1∥gk∥2)2∥gk∥2-2(1+βkgkTdk-1∥gk∥2)dkTgk.
Dividing the previous inequation by (gkTdk)2, we get
(18)∥dk∥2∥gk∥4=∥dk∥2(gkTdk)2=βk2∥dk-1∥2(gkTdk)2-(1+βkgkTdk-1/∥gk∥2)2∥gk∥2(dkTgk)2-2(1+βkgkTdk-1/∥gk∥2)dkTgk=∥dk-1∥2∥gk-1∥4+1∥gk∥2-βk2(gkTdk-1)2/∥gk∥4∥gk∥2≤1∥gk∥2+∥dk-1∥2∥gk-1∥4≤∑i=0k-1‍1∥gi∥2≤kϵ2.
So, we obtain
(19)∑k≥1‍∥gk∥4∥dk∥2≥∑k≥1‍ϵ21k=+∞,
which contradicts (14). Hence we get this theorem.Remark 7.
In Algorithm1, we also can use the following equations to compute dk:
(20)dk=βkdk-1-βkgkTdk-1∥gk∥2-gk,
where βk=max{min{βkFR,βkPRP},0};
(21)dk=βkdk-1-βkgkTdk-1∥gk∥2-gk,
where βk=max{min{βkLS,βkCD},0}.Algorithm 8.
We have the following steps.
…
Step0. Given x0∈Rn, set d0=-g0, k=0. If ∥g0∥=0, then stop.
…
Step1. Find αk>0 satisfying (4) and (5), and by (2), xk+1 is given. If ∥gk+1∥=0, then stop.
…
Step2. Compute βk by formula
(22)βk={βkDY=gkTgk(gk-gk-1)Tdk-1,∥gk-1∥2≤gkTdk-1,βkFR=∥gk∥2∥gk-1∥2,∥gk-1∥2>gkTdk-1,
and compute dk+1 by (3). Set k:=k+1, and go to Step 1.Lemma 9.
Suppose that Assumption1  holds, and βkis computed by (22); if ∥gk∥≠0, then one gets gkTdk<0 for all k≥2 and  βkFR≥|βk| (see [9]).Lemma 10.
Suppose thatl>0, and ν is a constant. If positive series ζk satisfied
(23)∑i=1k‍ζi≥lk+ν,
one has
(24)∑i≥1‍ζi2i=+∞,∑k≥1‍ζk2∑i=1kζi=+∞.From the previous analysis, we can get the following global convergence result for Algorithm8.Theorem 11.
Suppose that Assumption1 holds, and ∥g(x)∥2≤c-, where c- is a constant. Then, one has
(25)liminfk→∞∥gk∥=0.Proof.
Suppose by contradiction that there existsε>0 such that
(26)∥gk∥2≥ε
holds for all k. From (3), we have
(27)dk=βkdk-1-gk.
Squaring both sides of the previous equation, we get
(28)∥dk∥2=(βk∥dk-1∥)2-∥gk∥2-2gkTdk.
Let ϑk=∥dk∥2/∥gk∥4 and rk=-gkTdk/∥gk∥2; from (22), we have
(29)ϑk≤ϑk-1-2rk∥gk∥2-1∥gk∥2.
By ϑ1=1/∥g1∥2,  r1=1, we know that
(30)ϑk≤∑i=1k‍2ε|ri|-kc-.
By (30), we get
(31)ϑk≤∑i=1k‍2ε|ri|,∑i=1k‍|ri|≥2εkc-.
From (31) and Lemma 10, we have
(32)∑k≥1‍(gkTdk)2∥dk∥2=+∞,
which contradicts Lemma 4. Therefore, we get this theorem.Algorithm 12.
We have the following steps.
…
Step0. Given x0∈Rn, μ>1/4, set d0=-g0,k:=0. If ∥g0∥=0, then stop.
…
Step1. Find αk>0 satisfying (4) and (5), and by (2), xk+1 is given. If ∥gk+1∥=0, then stop.
…
Step2. Compute dk by
(33)dk={-gk,k=0,βkdk-1-(1+βkgkTdk-1∥gk∥2)gk,k≥1,
where
(34)βk=gkT(gk-gk-1)∥gk-1∥2-μ∥gk-gk-1∥2gkTdk-1∥gk-1∥4.
Set k:=k+1, and go to Step 1.Lemma 13.
Suppose that directiondk is given by (33) and (34); then, one has
(35)dkTgk=-∥gk∥2≤0
holds for any k≥0.Lemma 14.
Suppose that Assumption1 holds, dk is generated by (33) and (34), and αk is determined by (4) and (5); one has
(36)∑k≥0∥gk∥4∥dk∥2<+∞.Proof.
From Lemma4 and Lemma 13, we obtain (36).Lemma 15.
Suppose thatf is convex. That is, dT∇2f(x)d≥0, for all d∈Rn, where ∇2f(x) is the Hessian matrix of f. Let {xk} and {dk} be generated by Algorithm 12; one has
(37)ραk∥dk∥2≤-gkTdk.Proof.
By Taylor’s theorem, we can get(38)f(xk+1)=f(xk)+gkTsk+12skTGksk,
where sk=xk+1-xk, and Gk=∫01‍∇2f(xk+τsk)dτsk.
By Assumption1, (4), and (38), we get
(39)-ραk2∥dk∥2≥f(xk+1)-f(xk)≥gkTsk=αkgkTdk.
So, we get (37).Theorem 16.
Consider Algorithm12, and suppose that Assumption 1 and the assumption of Lemma 15 hold. Then, one has
(40)liminfk→∞∥gk∥=0.Proof.
We suppose that the conclusion is not true. Suppose by contradiction that there existsϵ>0 such that
(41)∥gk∥≥ϵ
holds for all k≥0.
By Lemma13, we have
(42)βk=-gkT(gk-gk-1)gk-1Tdk-1-μ(∥gk-gk-1∥-gk-1Tdk-1)2gkTdk-1.
From Assumption 1, Lemma 15, and (42), we know that
(43)|βk|≤(μL2+ρLρ2)∥gk∥∥dk-1∥.
Therefore, by (33), we get
(44)∥dk∥≤∥gk∥+2(μL2+ρLρ2)∥gk∥=(1+2Lρ+2μL2ρ2)∥gk∥.
We obtain
(45)∑k≥1‍∥gk∥4∥dk∥2≥+∞,
which contradicts (36). Therefore, we have
(46)liminfk→∞∥gk∥=0.
So, we complete the proof of this theorem.Remark 17.
In Algorithm12, βk can also be computed by the following formula:
(47)βk=gkT(gk-gk-1)∥gk-1∥2-min{gkT(gk-gk-1)∥gk-1∥2,μ∥gk-gk-1∥2gkTdk-1∥gk-1∥4},
where μ>1/4.


## 3. Numerical Experiments and Discussions

In this section, we give some numerical experiments for the previous new nonlinear conjugate gradient methods with Wolfe type line search and some discussions. The problems that we tested are from [13]. We use the condition ∥gk+1∥≤10-6 as the stopping criterion. We use MATLAB 7.0 to test the chosen problems. We give the numerical results of Algorithms 1 and 12 to show that the method is efficient for unconstrained optimization problems. The numerical results of Algorithms 1 and 12 are listed in Tables 1 and 2.Table 1
Test results for Algorithm1.
Name
Dim
NI
NF
NG
GULF
3
2
52
3
VARDIM
2
3
54
6
LIN
50
1
3
3
LIN
2
1
3
3
LIN
1000
1
3
3
LIN1
2
1
51
2
LIN1
10
1
3
3
LIN0
4
1
3
3
Name: the test problem name; Dim: the problem dimension; NI: the iterations number; NF: the function evaluations number; NG: the gradient evaluations number.Table 2
Test results for Algorithm12.
Name
Dim
NI
NF
NG
GULF
3
2
52
3
BIGGS
6
1000
1149
1095
IE
50
1000
1053
1003
IE
3
1000
1101
1052
TRIG
1000
1103
1052
3
BV
10
5
203
55
BV
3
6
109
9
Name: the test problem name; Dim: the problem dimension; NI: the iterations number; NF: the function evaluations number; NG: the gradient evaluations number.…Discussion 1. From the analysis of the global convergence of Algorithm 1, we can see that if dk satisfies the property of efficient descent search direction, we can get the global convergence of the corresponding nonlinear conjugate gradient method with Wolfe type line search without other assumptions.…Discussion 2. In Algorithm 8, we use a Wolfe type line search. Overall, we also feel that nonmonotone line search (see [14]) also can be used in our algorithms.…Discussion 3. From the analysis of the global convergence of Algorithm 12, we can see that when dk is an efficient descent search direction, we can get the global convergence of the corresponding conjugate gradient method with Wolfe type line search without requiring uniformly convex function.



---

*Source: 742815-2013-03-14.xml*