# A Spectral Dai-Yuan-Type Conjugate Gradient Method for Unconstrained Optimization

Authors: Guanghui Zhou; Qin Ni
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A new spectral conjugate gradient method (SDYCG) is presented for solving unconstrained optimization problems in this paper. Our method provides a new expression of spectral parameter. This formula ensures that the sufficient descent condition holds. The search direction in the SDYCG can be viewed as a combination of the spectral gradient and the Dai-Yuan conjugate gradient. The global convergence of the SDYCG is also obtained. Numerical results show that the SDYCG may be capable of solving large-scale nonlinear unconstrained optimization problems.


---

## Body

## 1. Introduction

As well known, a great deal of issues, which are studied in scientific research fields, can be translated to unconstrained optimization problems. The spectral conjugate gradient (SCG) method does nice jobs among various algorithms for solving nonlinear optimization problems. The spectral conjugate gradient combines the spectral gradient and the conjugate gradient. To the SCG method, the choice of spectral parameter is crucially important. In this paper, we propose a new spectral conjugate gradient method based on the Dai-Yuan conjugate gradient method by providing a new spectral parameter. Our purpose is to obtain an efficient algorithm for the unconstrained optimization.An unconstrained optimization problem is customarily expressed as(1)
m
i
n
x
∈
R
n
f
x
.The nonlinear function f
:
R
n
→
R considered in this paper is continuously differentiable; the gradient of f is denoted by g
x
≔
∇
f
(
x
). We usually impose the following properties on function f.(P
1)
The functionf is bounded below and is continuously differentiable in a neighbourhood N of the level set L
≔
{
x
∈
R
n
∣
f
(
x
)
≤
f
(
x
0
)
}, where x
0 is the starting point.
(P2)
The gradientg
(
x
) of f is Lipschitz continuous in N; that is, there exists a constant L
>
0, such that g
(
x
)
-
g
(
y
)
≤
L
x
-
y for all x, y
∈
N.Generally, a sequence{
x
k
} is obtained in an algorithm for solving (1) and has the following format:(2)
x
k
+
1
=
x
k
+
α
k
d
k
,where d
k is a search direction and α
k is the step size. At each iterative point x
k, we usually determine d
k firstly and then compute α
k by some principles.There are different ways to determine the directiond
k. In the classical steepest-descent method, d
k
=
-
g
k. In the conjugate gradient (CG) method, d
k is of the form (3)
d
0
=
-
g
0
,
d
k
+
1
=
-
g
k
+
1
+
β
k
d
k
,
i
f
k
≥
0
,where β
k is a scalar parameter characterizing the conjugate gradient method. The best-known expressions of β
k are Hestenes-Stiefel (HS) [1], Fletcher-Reeves (FR) [2], Polak-Ribiere-Polyak (PRP) [3, 4], and Dai-Yuan (DY) [5] formulas. They are defined by (4)
β
k
H
S
=
g
k
+
1
T
y
k
d
k
T
y
k
,
β
k
F
R
=
g
k
+
1
2
g
k
2
,
β
k
P
R
=
g
k
+
1
T
y
k
g
k
2
,
β
k
D
Y
=
g
k
+
1
2
d
k
T
y
k
,respectively, where · denotes the Euclidean norm and y
k
≔
g
k
+
1
-
g
k.There also are some approaches to determine the step sizeα
k in (2). Unfortunately, the steepest-descent method performs poorly. Barzilai and Borwein improved the steepest-descent method greatly by providing a spectral choice of step size in [6]. Their algorithm has the form (5)
x
k
+
1
=
x
k
-
α
k
g
k
,where α
k
=
s
k
T
s
k
/
s
k
T
y
k or α
k
=
s
k
T
y
k
/
y
k
T
y
k with s
k
=
x
k
+
1
-
x
k. Many algorithms are proved convergent under the Wolfe condition; that is, the step size α
k satisfies(6)
f
x
k
-
f
x
k
+
α
k
d
k
≥
-
δ
α
k
g
k
T
d
k
,
(7)
g
x
k
+
α
k
d
k
T
d
k
≥
σ
g
k
T
d
kwith 0
<
δ
<
σ
<
1.In recent years, some scholars developed a new method—spectral conjugate gradient (SCG) method—for solving (1). For example, Raydan introduced the spectral gradient method for large-scale unconstrained optimization in [7]. He combined a nonmonotone line search strategy that guarantees global convergence with the Barzilai and Borwein method. Utilizing spectral gradient and conjugate gradient ideas, Birgin and Martinez proposed a spectral conjugate gradient method in [8]. In their algorithm, the search direction has the form(8)
d
0
=
-
g
0
,
d
k
+
1
=
-
θ
k
+
1
g
k
+
1
+
β
k
d
k
,
i
f
k
≥
0
.In [8], the best combination of this formula, the scaling, and the initial choice of step-length is also studied. Following [8], some papers discussed the various choices of the spectral parameter θ
k based on different β
k. For example, Du and Chen [9] gave a modified spectral FR conjugate gradient method with Wolfe-type line search based on FR formula. Their spectral parameters θ
k and β
k are expressed as(9)
θ
k
+
1
=
d
k
T
y
k
g
k
2
,
β
k
=
β
k
F
R
.Yu et al. [10] presented a modification of spectral Perry’s conjugate gradient formula, which possessed the sufficient descent property independent of line search condition. Their search direction d
k
+
1 is defined by (8) and β
k has the form(10)
β
k
D
S
P
=
β
k
S
P
-
C
y
k
-
δ
k
+
1
s
k
2
δ
k
+
1
y
k
T
d
k
2
g
k
+
1
T
d
k
,where(11)
C
≥
1
4
,
β
k
S
P
=
g
k
+
1
T
y
k
-
δ
k
+
1
s
k
δ
k
+
1
y
k
T
d
k
,
δ
k
+
1
=
1
θ
k
+
1
=
s
k
T
y
k
s
k
T
s
k
,
s
k
=
x
k
+
1
-
x
k
.Liu and Li [11] proposed a spectral DY-type projection method for nonlinear monotone systems of equations. The direction d
k is also determined by (8) and the parameters are defined by(12)
θ
k
+
1
=
s
k
T
s
k
s
k
T
y
k
,
β
k
=
β
k
D
Y
.We will propose a new SCG method based on the Dai-Yuan-type conjugate gradient method in this paper. A new selection ofθ
k
+
1 is introduced in our algorithm such that the sufficient descent condition holds. In addition, the global convergence of the new method is obtained.The present paper is organized as follows. In Section2, we outline our new method for unconstrained nonlinear optimization, and we show that the sufficient descent condition holds under mild assumptions. The global convergence is proved in Section 3, while the numerical results compared with CG-DESCENT are given in Section 4. At last section, we draw some conclusions about our new spectral conjugate gradient method.


## 2. Spectral Dai-Yuan-Type Conjugate Gradient Method

In this paper, we consider the spectral conjugate gradient method in which the search direction is of the form(13)
d
0
=
-
g
0
,
d
k
+
1
=
-
θ
k
+
1
g
k
+
1
+
β
k
D
Y
d
k
,
i
f
k
≥
0
,where(14)
θ
k
+
1
=
max
⁡
2
g
k
T
d
k
d
k
T
y
k
,
2
g
k
+
1
T
d
k
-
g
k
T
d
k
d
k
T
y
kand the scalar parameter β
k
D
Y is defined by (4). This is a new spectral conjugate gradient method for solving problem (1) because the expression (14) of spectral parameter θ
k
+
1 is completely different from those in other papers. The search direction (13) is a combination of the spectral gradient and the Dai-Yuan conjugate gradient. We hope that (14) may be an efficient choice.In order to obtain the global convergence of our method, we assume that the step size satisfies the strong Wolfe condition; that is, the step sizeα
k satisfies (6) and(15)
g
x
k
+
α
k
d
k
T
d
k
≤
-
σ
g
k
T
d
kwith 0
<
δ
<
σ
<
1. It is easy to see that (7) holds if (15) holds.The following is a detailed description of the spectral Dai-Yuan-type conjugate gradient (SDYCG) algorithm.SDYCG AlgorithmStep 1 (initialization).
Choosex
0
∈
R
n, set k
=
0, and take ϵ
>
0.Step 2 (check the convergence condition).
Computeg
k; if g
k
≤
ϵ, then stop.Step 3 (form the search direction).
Ifk
=
0, then d
0
=
-
g
0. Else, compute θ
k
+
1 and β
k
D
Y by formulas (14) and (4), respectively; then compute d
k by (13) and (14).Step 4 (line search).
Findα
k which satisfies the strong Wolfe conditions (6) and (15).Step 5 (compute the new point).
Setx
k
+
1
=
x
k
+
α
k
d
k and k
=
k
+
1 and go to Step 2.The framework of the SDYCG algorithm is similar to other spectral conjugate gradient algorithms. However we choose a different spectral parameterθ
k
+
1 (see (14)) which is the main difference between SDYCG and the others.The global convergence of SDYCG algorithm will be given in the next section. Before that, we will show that the search direction (13) can ensure the sufficient descent condition.Lemma 1.
Suppose that the sequence{
d
k
} is generated by the SDYCG algorithm; then(16)
g
k
T
d
k
≤
-
g
k
2for all k
≥
0.Proof.
Sinced
k is calculated by formula (13), we can get, if k
=
0, that g
0
T
d
0
=
-
g
0
2 whereas when k
≥
0, from (14), we find (17)
θ
k
+
1
≥
2
g
k
+
1
T
d
k
-
g
k
T
d
k
d
k
T
y
k
=
g
k
+
1
T
d
k
d
k
T
y
k
+
1
=
g
k
+
1
2
d
k
T
y
k
·
g
k
+
1
T
d
k
g
k
+
1
2
+
1
=
β
k
D
Y
g
k
+
1
T
d
k
g
k
+
1
2
+
1
.Furthermore,(18)
-
θ
k
+
1
g
k
+
1
2
+
β
k
D
Y
g
k
+
1
T
d
k
≤
-
g
k
+
1
2
.From the second formula of (13), we obtain(19)
g
k
+
1
T
d
k
+
1
≤
-
g
k
+
1
2
.The proof is completed.This lemma gives the fact that the directiond
k is a descent direction. Besides, d
k possesses the following property.Lemma 2.
Suppose that the SDYCG algorithm is implemented with the step sizeα
k that satisfies the strong Wolfe conditions (6) and (15). If g
k
≠
0 for all k
≥
0, then(20)
β
k
D
Y
2
g
k
+
1
T
d
k
+
1
2
≤
1
g
k
T
d
k
2
.Proof.
By (14) and 0
<
σ
<
1, we have(21)
θ
k
+
1
≥
σ
+
1
g
k
T
d
k
d
k
T
y
k
=
σ
+
1
g
k
+
1
2
d
k
T
y
k
·
g
k
T
d
k
g
k
+
1
2
=
σ
+
1
β
k
D
Y
g
k
T
d
k
g
k
+
1
2
.With (15) and (21), we get (22)
β
k
D
Y
g
k
T
d
k
≤
θ
k
g
k
+
1
2
-
σ
β
k
D
Y
g
k
T
d
k
≤
θ
k
g
k
+
1
2
-
β
k
D
Y
g
k
+
1
T
d
k
≤
-
θ
k
g
k
+
1
2
+
β
k
D
Y
g
k
+
1
T
d
k
=
g
k
+
1
T
d
k
+
1
.Therefore, inequality (20) follows. This completes the proof.Inequality (20) gives the close relationship of the inner product of gradient and direction between the adjacent two iterations. It will play an important role in our global convergence analysis.


## 3. Convergence Analysis

Dai and Yuan stated in [5] that the following result had been essentially proved by Zoutendijk and Wolfe.Lemma 3.
Suppose that the functionf
(
x
) has the properties (
P
1
) and (
P
2
). Assume that d
k is a descent direction and α
k is obtained by the Wolfe conditions (6) and (7). Then(23)
∑
k
≥
0
g
k
T
d
k
2
d
k
2
<
+
∞
.
One customarily calls (23)the Zoutendijk condition.Theorem 4.
Suppose that the functionf
(
x
) has the properties (
P
1
) and (
P
2
). Sequences {
x
k
}, {
g
k
}, and {
d
k
} are generated by SDYCG algorithm. Then either g
k
=
0 for some k or(24)
lim
inf
k
→
∞
⁡
g
k
=
0
.Proof.
Suppose thatg
k
≠
0 for all k and (24) is not true. Then there exists a constant c
>
0, such that(25)
g
k
≥
cfor all k of the iterations.
The second equality of (13) implies(26)
d
k
+
1
+
θ
k
+
1
g
k
+
1
=
β
k
D
Y
d
k
;we get(27)
d
k
+
1
2
=
β
k
D
Y
2
d
k
2
-
2
θ
k
+
1
g
k
+
1
T
d
k
+
1
-
θ
k
+
1
2
g
k
+
1
2
.
Dividing both sides byg
k
+
1
T
d
k
+
1, we have (28)
d
k
+
1
2
g
k
+
1
T
d
k
+
1
2
=
β
k
D
Y
2
g
k
+
1
T
d
k
+
1
2
d
k
2
-
2
θ
k
+
1
g
k
+
1
T
d
k
+
1
-
θ
k
+
1
2
g
k
+
1
2
g
k
+
1
T
d
k
+
1
2
=
β
k
D
Y
2
g
k
+
1
T
d
k
+
1
2
d
k
2
-
1
g
k
+
1
+
θ
k
+
1
g
k
+
1
g
k
+
1
T
d
k
+
1
2
+
1
g
k
+
1
2
.Combining (20) in Lemma 2, we see the inequality(29)
d
k
+
1
2
g
k
+
1
T
d
k
+
1
2
≤
d
k
2
g
k
T
d
k
2
+
1
g
k
+
1
2
.Summing both sides, we obtain(30)
∑
i
=
0
k
d
i
+
1
2
g
i
+
1
T
d
i
+
1
2
≤
∑
i
=
0
k
d
i
2
g
i
T
d
i
2
+
∑
i
=
0
k
1
g
i
+
1
2
.So, from (25) and (30), we get(31)
d
k
+
1
2
g
k
+
1
T
d
k
+
1
2
≤
∑
i
=
0
k
+
1
1
g
i
2
≤
k
+
2
c
.This relation is equivalent to(32)
g
k
T
d
k
2
d
k
2
≥
c
k
+
2
.Summing over k, we obtain(33)
∑
k
≥
0
g
k
T
d
k
2
d
k
2
=
+
∞
.From the SDYCG algorithm, the step size satisfies the strong Wolfe condition, so the Wolfe condition (7) holds. And the directions obtained by the algorithm are descent from Lemma 1. But the last equality contradicts the Zoutendijk condition (23). Hence, our original assertion (25) must be false, giving that either g
k
=
0 for some k or (24) holds.


## 4. Numerical Results

In order to test the numerical performance of the SDYCG algorithm, we choose some unconstrained problems with the initial points from CUTEr library [12, 13]. They are listed in Table 1.Table 1
Test problems.
Number
Function name
1
ENGVAL1
2
FLETCBV2
3
TOINTGSS
4
COSINE
5
ARWHEAD
6
EDENSCH
7
EG2
8
GENROSE
9
LIARWHD
10
Generalized White & Holst
11
Extended Wood
12
Extended quadratic penalty QP1
13
BDEXP
14
HIMMELBG
15
Hager
16
Extended TET
17
Diagonal 5
18
Extended Himmelblau
19
Diagonal 6
20
Extended DENSCHNF
21
LIARWHD
22
Extended BD1
23
Extended Hiebert
24
Extended Tridiagonal 2
25
QUARTC
26
Extended DENSCHNB
27
Extended Rosenbrock
28
Raydan 2
29
Diagonal 2
30
Diagonal 4
31
Extended Maratos
32
Quadratic QF1
33
Extended quadratic exponential EP1
34
DQDRTIC
35
NONSCOMP
36
Extended Freudenstein & Roth
37
Extended White & Holst
38
Raydan 1
39
Extended Tridiagonal 1
40
Extended Cliff
41
Extended Trigonometric
42
Extended Beale
43
Generalized Tridiagonal 1
44
Generalized PSC1
45
Extended PSC1
46
Extended Powell
47
BDQRTIC
48
FLETCBV3
49
FLETCHCR
50
FREUROTH
51
GENHUMPS
52
NONDIA
53
NONDQUAR
54
SROSENBR
55
TQUARTIC
56
Extended PenaltyThe experiments are run on a personal computer with a 64-bit processor, 2.5 GHz of CPU, and 4 GB of RAM memory. All the codes are written in MATLAB language and are compiled with this software.We would like to compare the SDYCG with the CG-DESCENT. The CG-DESCENT is a conjugate gradient algorithm with guaranteed descent proposed by Hager and Zhang in [14]. It has been proven an excellent algorithm in recent years.To make the comparison as fair as possible, we use the criteriong
≤
1
0
-
5 to terminate the executions and impose restriction on the number of iterations less than 500 in both algorithms. All the step sizes satisfy the strong Wolfe conditions (6) and (15).We use the performance profiles proposed by Dolan and Moré [15] to show the efficiency of comparisons. Performance profiles can be used as a tool for benchmarking and comparing optimization software. The performance profile for a solver is the (cumulative) distribution function for a performance metric. For example, if computing time is chosen as a metric, then we compute the ratio of the computing time of the solver versus the best time of all of the solvers. That is, for each method, we plot the fraction P(y-axis) of problems for which the method is within a factor τ(x-axis) of the best time. The curve of a solver being above others means that it has the highest probability of being the optimal solver. We use a l
o
g
2 scale for τ to capture the performance of all the solvers.In order to observe the numerical results of the SDYCG and the CG-DESCENT, we choose three different dimensions of each test function. The dimensions aren
=
1
0
2, n
=
1
0
3, and n
=
1
0
4, respectively. According to the numerical results obtained in every dimension, we plot two figures based on CPU time and iterations, respectively.We can find from Figure1 that the SDYCG is similar to the CG-DESCENT when n
=
1
0
2 because their curves crosses each other. The predominance of the SDYCG appears in Figure 2 when n
=
1
0
3. If the test dimension is chosen as n
=
1
0
4, the SDYCG is better than the CG-DESCENT from the fact that its curve is almost completely above that of the CG-DESCENT in Figure 3.Figure 1
Performance profiles in al
o
g
2 scale (n
=
1
0
2).
(a)
Based on CPU time
(b)
Based on iterationsFigure 2
Performance profiles in al
o
g
2 scale (n
=
1
0
3).
(a)
Based on CPU time
(b)
Based on iterationsFigure 3
Performance profiles in al
o
g
2 scale (n
=
1
0
4).
(a)
Based on CPU time
(b)
Based on iterationsFurthermore, we are interested in the robustness of our SDYCG algorithm. Ten problems are selected from CUTEr to be tested. The numerical results listed in Table2 are obtained by changing the initial iteration point every time. “x
0” represents the standard initial iteration point of the problem; “iter.” and “time(s)” indicate the iterative number and time (in seconds).Table 2
Test of the robustness of SDYCG.
Number
Function name
x
0
10
∗
x
0
100
∗
x
0
Iter.
Time(s)
Iter.
Time(s)
Iter.
Time(s)
1
DQDRTIC
245
0.3436
290
0.3951
338
0.4567
2
QUARTC
1
0.0012
28
0.1273
27
0.1482
3
Diagonal 6
5
0.0176
8
0.0267
4
0.0153
4
Extended DENSCHNB
13
0.0110
18
0.0159
16
0.0177
5
Extended DENSCHNF
22
0.0636
17
0.0519
24
0.0820
6
LIARWHD
12
0.0186
11
0.0193
17
0.0320
7
EDENSCH
30
0.1897
30
0.18753
30
0.1860
8
EG2
9
0.0404
9
0.0392
9
0.0404
9
ENGVAL1
28
0.0893
29
0.1064
31
0.1294
10
FLETCBV2
53
0.1080
53
0.1377
53
0.1355The conclusion that can be drawn is that the SDYCG is a robust algorithm and it may be capable of solving large-scale nonlinear unconstrained optimization problem.


## 5. Conclusions

We propose a new spectral conjugate gradient method for nonlinear unconstrained optimization. This method, which we call the SDYCG, is built based on the Dai-Yuan conjugate gradient method. A new spectral choice is provided in the search direction. Numerical results show that the SDYCG is comparable with the CG-DESCENT. The SDYCG algorithm may be capable of solving large-scale nonlinear unconstrained optimization problems.



---

*Source: 839659-2015-12-20.xml*