# A Self-Adjusting Spectral Conjugate Gradient Method for Large-Scale Unconstrained Optimization

Authors: Yuanying Qiu; Dandan Cui; Wei Xue; Gaohang Yu
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

This paper presents a hybrid spectral conjugate gradient method for large-scale unconstrained optimization, which possesses a self-adjusting property. Under the standard Wolfe conditions, its global convergence result is established. Preliminary numerical results are reported on a set of large-scale problems in CUTEr to show the convergence and efficiency of the proposed method.


---

## Body

## 1. Introduction

Consider the following unconstrained optimization problem:(1)min{f(x)∣x∈ℜn},
where f:ℜn→ℜ is a nonlinear smooth function and its gradient is available. Conjugate gradient methods are very efficient for solving (1), especially when the dimension n is large, and have the following iterative form:
(2)xk+1=xk+αkdk,
where αk>0 is a steplength obtained by a line search, and dk is the search direction defined by
(3)dk={-gk,fork=1,-gk+βkdk-1,fork≥2,
where βk is a scalar and gk denotes the gradient of f at point xk.There are at least six formulas forβk, which are given below:
(4)βkFR=gkTgkgk-1Tgk-1,βkCD=-gkTgkdk-1Tyk-1,βkDY=gkTgkdk-1Tyk-1,βkPR=gkTyk-1gk-1Tgk-1,βkHS=gkTyk-1dk-1Tyk-1,βkLS=-gkTyk-1dk-1Tgk-1,
where yk-1=gk-gk-1 and ∥·∥ denotes the Euclidean norm. In the above six methods, HS, PR, and LS methods are especially efficient in real computations, but one may not globally converge for general functions. FR, CD, and DY methods are globally convergent, but they perform much worse. To combine the good numerical performance of HS method and the nice global convergence property of DY method, Dai and Yuan [1] proposed an efficient hybrid formula for βk which is defined as the following form:
(5)βkHSDY=max{0,min{βkDY,βkHS}}.Their studies suggested that the HSDY method (5) has the same advantage of avoiding the propensity of short steps as the HS method [1]. They also proved that the HSDY method with the standard wolfe line search produces a descent search direction at each iteration and converges globally. Descent condition may be crucial for the convergence analysis of conjugate gradient methods with inexact line searches [2, 3]. Further, there are some modified conjugate gradient methods [4–7] which possess the sufficiently descent property without any line search condition. Recently, Yu [8] proposed a spectral version of HSDY method:
(6)βkS-HSDY=max{0,min{βkSDY,βkSHS}},
where
(7)βkSDY=∥gk∥2δkyk-1Tdk-1,βkSHS=gkTyk-1δkyk-1Tdk-1,
with δk=yk-1Tsk-1/∥sk-1∥2,  sk-1=xk-xk-1. The numerical experiments show that this simple preconditioning technique benefits to its performance.In this paper, based on a new conjugate condition [9], we propose a new hybrid spectral conjugate gradient method with βk defined by
(8)βkDS-HSDY=max{0,min{βkDSDY,βkDSHS}},
where
(9)βkDSDY=∥gk∥2δkyk-1*Tdk-1,βkDSHS=gkTyk-1*δkyk-1*Tdk-1,yk-1*=yk-1+max{ϑk,0}∥sk-1∥2sk-1,ϑk=2{f(xk)-f(xk-1)}+[g(xk)+g(xk-1)]Tsk-1.A full description of DS-HSDY method is formally given as follows.Algorithm 1 (DS-HSDY conjugate gradient method).
d
d
d
Data. Choose constants 0<ρ<σ<1, μ>1, and 0≤ϵ≪1. Given an initial point x1∈Rn, set d1=-g1. Let k:=1.Step 1.
If∥gk∥≤ε, then stop.Step 2.
Determineαk satisfying the standard Wolfe condition:
(10)g(xk+αkdk)Tdk>σgkTdk,(11)f(xk+αkdk)-f(xk)≤ραkgkTdk.
Then update xk+1=xk+αkdk.Step 3.
Computegk+1, δk+1 and βk+1DS-HSDY. Then update dk+1 such as
(12)dk+1=-1δk+1gk+1+βk+1DS-HSDYdk.
Set k:=k+1 and go to Step 1.The rest of the paper is organized as follows. In the next section, we show that the DS-HSDY method possesses a self-adjusting property. In Section3, we establish its global convergence result under the standard Wolfe line search conditions. Section 4 gives some numerical results on a set of large-scale unconstrained test problems in CUTEr to illustrate the convergence and efficiency of the proposed method. Finally we have a Conclusion section.


## 2. Self-Adjusting Property

In this section, we prove that the DS-HSDY method possesses a self-adjusting property. To begin with, we assume that(13)gk≠0,∀k≥1,
otherwise, a stationary point has been found, and define the two following important quantities:
(14)qk=∥dk∥2(gkTdk)2,γk=-δkgkTdk∥gk∥2.
The quantity qk shows the size of dk, where γk is a quantity showing the descent degree of dk. In fact, if γk>0, dk is a descent direction. Furthermore, if γk≥C for some constant C>0, then we have the sufficient descent condition
(15)gkTdk≤-C∥gk∥2.
On the other hand, it follows from (12) that
(16)dk+1δkgk=βkDS-HSDYdk-1.
Hence
(17)∥dk∥2=(βkDS-HSDY)2∥dk-1∥2-2δkgkTdk-1δk2∥gk∥2.
Combining |βkDS-HSDY|≤|βkDSDY|≤|βkSDY| with (17) yields
(18)∥dk∥2=(βkDS-HSDY)2∥dk-1∥2-2δkgkTdk-1δk2∥gk∥2≤(βkSDY)2∥dk-1∥2-2δkgkTdk-1δk2∥gk∥2.
Dividing both sides of (18) by (gkTdk)2 and using (7), we obtain
(19)∥dk∥2(gkTdk)2≤∥dk-1∥2(gk-1Tdk-1)2-2δk1gkTdk-1δk2∥gk∥2(gkTdk)2.
It follows from (19) and the definitions of qk and γk that
(20)qk≤qk-1+1∥gk∥22γk-1∥gk∥21γk2.Additionally, we assume that there exist positive constantsγ and γ¯ such that
(21)0<γ≤∥gk∥≤γ¯,∀k≥1,
then we have the following result.Theorem 2.
Consider the method (2), (8) and (12), where dk is a descent direction. If (21) holds, there exist positive constants ξ1, ξ2, and ξ3 such that relations
(22)-gkTdk≥ξ1k,(23)∥dk∥2≥ξ2k,(24)γk≥ξ3k
hold for all k≥1.Proof.
Summing (20) over the iterates and noting that d1=-g1, we get
(25)qk≥∑i=1k‍1∥gi∥2(2γi-1γi2).
Since qk≥0, it follows from (25) that
(26)1∥gi∥2(2γi-1γi2)≤∑i=1k-1‍1∥gi∥2(2γi-1γi2).
Equations (21), (26), and 2/γi-1/γi2≤1 yield
(27)1γk2-2γk-γ-2γ2(k-1)≤0.
Furthermore, we have
(28)1γk≤1+1+γ-2γ2(k-1)≤1+γ-2γ2k≤2γ-γk.
Thus (24) holds with ξ3=γ/2γ-.
Noting that-gkTdk=∥gk∥2γk and ∥dk∥≥∥gk∥γk, it is easy to derive that (22) and (23) hold with ξ1=ξ3γ2 and ξ2=ξ32γ2, respectively. Hence the proof is complete.Theorem 3.
Consider the method (2), (8), and (12), where dk is a descent direction. If (21) holds, then for any p∈(0,1), there exist constants ξ4, ξ5, and ξ6>0 such that, for any k, the relations
(29)-giTdi≥ξ4,∥di∥2≥ξ5,γi≥ξ6k
hold for at least [pk] values of i∈[1,k].Proof.
The proof is similar to the Theorem  2 in [10], so we omit it here.Therefore, by Theorems2 and 3, it was shown that DS-HSDY method possesses a self-adjusting property which is independent of the line search and the function convexity.


## 3. Global Convergence

Throughout the paper, we assume that the following assumptions hold.Assumption 1.
(1)fis bounded below in the level set ℒ={x∈Rn:f(x)≤f(x1)};
(2) in a neighborhood𝒩 of ℒ, f is differentiable and its gradient g is Lipschitz continuous; namely, there exists a constant L>0 such that
(30)∥g(x)-g(y)∥≤L∥x-y∥,∀x,y∈𝒩.
Under Assumption 1 on f, we could get a useful lemma.Lemma 4.
Suppose thatx1 is a starting point for which Assumption 1 holds. Consider any method in the form (2), where dk is a descent direction and αk satisfies the weak Wolfe conditions; then one has that
(31)∑k≥1‍(gkTdk)2∥dk∥2<+∞.
For DS-HSDY method, one has the following global convergence result.Theorem 5.
Suppose thatx1 is a starting point for which Assumption 1 hold. Consider DS-HSDY method; if gk≠0 for all k≥1, then one has that
(32)gkTdk<0∀k≥1.
Further, the method converges in the sense that
(33)liminfk→∞∥gk∥=0.Proof.
Sinced1=-g1, it is obvious that g1Td1<0. Assume that gk-1Tdk-1<0. By (10) and the definition of the yk*, we have dk-1Tyk-1*≥dk-1Tyk-1>0, then βkDSDY>0. In addition, from (8), we have
(34)0≤βkDS-HSDY≤βkDSDY≤βkSDY.
Let λk=βkDS-HSDY/βkSDY, then we have 0≤λk≤1. By (12) with k+1 replaced by k, and multiplying it by gk, we have
(35)gkTdk=gk-1Tdk-1+(λk-1)gkTdk-1δkdk-1Tyk-1∥gk∥2.
From this and the formula for βkSDY, we get
(36)βkDS-HSDY=λkβkSDY=λkgkTdkgk-1Tdk-1+(λk-1)gkTdk-1=ξkgkTdkgk-1Tdk-1,
where
(37)ξk=λk1+(λk-1)lk-1,(38)lk-1=gkTdk-1gk-1Tdk-1.
At the same time, if we define
(39)ζk=1+(λk-1)lk-1lk-1-1,
it follows from (39) that
(40)gkTdk=ζkδk∥gk∥2.
Then we have by (10), with k replaced by k-1, that
(41)lk-1≤σ.
Furthermore, we have
(42)1+(λk-1)lk-1≥1+(-1-σ1+σ-1)σ=1-σ1+σ.
The above relation, (40), (41), and the fact that σ<1 imply that gkTdk<0. Thus by induction, (32) holds.
We now prove (33) by contradiction and assume that there exists some constant γ>0 such that
(43)∥gk∥≥γ∀k≥1.
Since dk+(1/δk)gk=βkDS-HSDYdk-1, we have that
(44)∥dk∥2=(βkDS-HSDY)2∥dk-1∥2-2δkgkTdk-1δk2∥gk∥2.
Dividing both sides of (44) by (gkTdk)2 and using (36) and (40), we obtain
(45)∥dk∥2(gkTdk)2=ξk2∥dk-1∥2(gk-1dk-1)2-1∥gk∥2(2ζk+1ζk2)=ξk2∥dk-1∥2(gk-1dk-1)2+1∥gk∥2[1-(1+1ζk)2].
In addition, since lk-1<1 and λk≤1, we have that (1-λk)(1-lk-1)≥0, or equivalently
(46)1+(λk-1)lk-1≥λk,
which with (37) yields
(47)|ξk|≤1.
By (45) and (47), we obtain
(48)∥dk∥2(gkTdk)2≤∥dk-1∥2(gk-1dk-1)2+1∥gk∥2.
Using (48) recursively and noting that ∥d1∥2=-g1Td1=∥g1∥2,
(49)∥dk∥2(gkTdk)2≤∑i=1k‍1∥gk∥2.
Then we get from this and (43) that
(50)(gkTdk)2∥dk∥2≥λ2k,
which indicates
(51)∑k≥1‍(gkTdk)2∥dk∥2=+∞.
This contradicts the Zoutendijk condition (31). Hence we complete the proof.


## 4. Numerical Result

In this section, we compare the performance of DS-HSDY method toPRP+ method [11], HSDY method [1], and S-HSDY method [8]. The test problems are taken from CUTEr (http://hsl.rl.ac.uk/cuter-www/problems.html) with the standard initial points. All codes are written in double precision Fortran and complied with f77 (default compiler settings) on a PC (AMD Athlon XP 2500 + CPU 1.84 GHz). Our line search subroutine computes αk such that the Wolfe conditions (10) and (11) hold with ρ=10-4 and σ=0.5. We use the condition ∥g(xk)∥∞≤10-6 or αkgkTdk<10-20|f(xk)| as the stopping criterion. The numerical results are presented in Tables 1, 2, 3, and 4 with the form NI/Nfg/T, where we report the dimension of the problem (n), the number of iteration (NI), the number of function evaluations (Nfg), and the CPU time (T) in 0.01 seconds.Table 1
Numerical results for PRP+ method.
Function
n
NI
Nfg
T (0.01 S)
∥
g
(
x
)
∥
∞
Quadratic QF2
10000
2227
2885
2016
9.98
E
-
07
Extended EP1
10000
4
7
3
6.09
E
-
13
Extended Tridiagonal 2
10000
39
98
47
9.29
E
-
07
ARGLINA
10000
5
15
4
1.95
E
-
07
ARWHEAD
10000
7
14
21
3.10
E
-
07
BDQRTIC
5000
157
720
526
1.47
E
-
04
BDEXP
5000
6
8
7
1.72
E
-
07
BRYBND
5000
5
11
1215
2.60
E
-
07
COSINE
10000
21
45
39
9.60
E
-
07
CRAGGLVY
10000
129
250
444
5.35
E
-
06
DIXMAANA
10000
6
12
19
4.20
E
-
07
DIXMAANB
10000
8
16
26
6.72
E
-
07
DIXMAANC
10000
11
23
38
3.38
E
-
08
DIXMAAND
10000
13
29
44
1.32
E
-
07
DIXMAANE
5000
558
799
712
9.96
E
-
07
DIXMAANF
5000
558
598
525
8.65
E
-
07
DIXMAANG
5000
519
784
684
5.99
E
-
07
DIXMAANH
5000
379
3488
2469
8.97
E
-
07
DIXMAANI
5000
593
854
755
7.51
E
-
07
DIXMAANJ
5000
492
751
651
5.08
E
-
07
DIXMAANK
5000
653
979
863
9.61
E
-
07
DQDRTIC
10000
11
23
19
9.59
E
-
08
DQRTIC
10000
33
57
42
3.44
E
-
07
EDENSCH
10000
26
90
78
9.10
E
-
06
EG2
10000
209
1426
473
1.10
E
-
03
ENGVAL1
10000
30
93
21
1.37
E
-
06
EXTROSNB
10000
29
63
25
3.77
E
-
08
FREUROTH
10000
61
145
81
2.33
E
-
07
LIARWHD
10000
25
49
36
6.54
E
-
09
NONDIA
10000
9
17
17
1.03
E
-
09
NONDQUAR
5000
1786
3258
1752
7.96
E
-
07
NONSCOMP
10000
5001
6799
9751
3.47
E
-
06Table 2
Numerical results for HSDY method.
Function
n
NI
Nfg
T (0.01 S)
∥
g
(
x
)
∥
∞
Quadratic QF2
10000
1593
1902
1876
7.11
E
-
07
Extended EP1
10000
4
7
4
6.09
E
-
13
Extended Tridiagonal 2
10000
34
55
32
9.40
E
-
07
ARGLINA
10000
5
15
4
1.95
E
-
07
ARWHEAD
10000
13
58
71
4.42
E
-
07
BDQRTIC
5000
171
567
422
6.31
E
-
04
BDEXP
5000
6
8
6
1.72
E
-
07
BRYBND
5000
5
11
1222
2.60
E
-
07
COSINE
10000
21
46
41
8.02
E
-
07
CRAGGLVY
10000
109
255
434
1.45
E
-
06
DIXMAANA
10000
5
10
16
5.13
E
-
07
DIXMAANB
10000
9
18
29
2.21
E
-
07
DIXMAANC
10000
10
21
33
5.42
E
-
07
DIXMAAND
10000
13
29
45
1.14
E
-
07
DIXMAANE
5000
446
541
493
9.24
E
-
07
DIXMAANF
5000
389
876
690
9.60
E
-
07
DIXMAANG
5000
552
660
602
9.85
E
-
07
DIXMAANH
5000
202
5106
3417
4.05
E
-
04
DIXMAANI
5000
365
450
409
9.95
E
-
07
DIXMAANJ
5000
444
532
484
4.95
E
-
07
DIXMAANK
5000
367
452
410
9.77
E
-
07
DQDRTIC
10000
8
17
14
6.35
E
-
07
DQRTIC
10000
37
68
48
3.40
E
-
07
EDENSCH
10000
30
99
85
7.97
E
-
07
EG2
10000
305
2811
879
2.08
E
-
03
ENGVAL1
10000
30
52
21
8.62
E
-
07
EXTROSNB
10000
27
54
21
6.20
E
-
09
FREUROTH
10000
143
283
177
8.01
E
-
07
LIARWHD
10000
32
62
44
1.75
E
-
07
NONDIA
10000
7
14
14
4.57
E
-
07
NONDQUAR
5000
2049
3730
2011
6.68
E
-
07
NONSCOMP
10000
58
100
98
5.03
E
-
07Table 3
Numerical results for S-HSDY method.
Function
n
NI
Nfg
T (0.01 S)
∥
g
(
x
)
∥
∞
Quadratic QF2
10000
1582
1941
1836
6.58
E
-
07
Extended EP1
10000
4
7
3
6.09
E
-
13
Extended Tridiagonal 2
10000
34
55
34
9.40
E
-
07
ARGLINA
10000
5
15
3
1.95
E
-
07
ARWHEAD
10000
13
58
75
5.60
E
-
07
BDQRTIC
5000
111
526
377
3.39
E
-
04
BDEXP
5000
6
8
5
1.72
E
-
07
BRYBND
5000
5
11
1179
2.60
E
-
07
COSINE
10000
21
46
39
9.72
E
-
07
CRAGGLVY
10000
103
189
332
1.94
E
-
06
DIXMAANA
10000
5
10
15
5.13
E
-
07
DIXMAANB
10000
9
18
30
2.21
E
-
07
DIXMAANC
10000
10
21
33
5.42
E
-
07
DIXMAAND
10000
13
29
43
1.14
E
-
07
DIXMAANE
5000
422
514
468
9.73
E
-
07
DIXMAANF
5000
310
792
618
6.77
E
-
07
DIXMAANG
5000
410
495
449
9.83
E
-
07
DIXMAANH
5000
217
6957
4642
4.13
E
-
04
DIXMAANI
5000
380
450
417
9.96
E
-
07
DIXMAANJ
5000
359
438
402
9.95
E
-
07
DIXMAANK
5000
404
485
448
6.67
E
-
07
DQDRTIC
10000
8
17
14
6.35
E
-
07
DQRTIC
10000
37
68
49
3.41
E
-
07
EDENSCH
10000
30
99
84
1.54
E
-
06
EG2
10000
242
1731
570
4.25
E
-
04
ENGVAL1
10000
29
124
22
1.78
E
-
06
EXTROSNB
10000
27
54
22
3.98
E
-
09
FREUROTH
10000
214
408
260
8.08
E
-
07
LIARWHD
10000
27
54
37
4.45
E
-
12
NONDIA
10000
7
14
14
4.58
E
-
07
NONDQUAR
5000
1782
3210
1738
8.99
E
-
07
NONSCOMP
10000
58
100
100
5.03
E
-
07Table 4
Numerical results for DS-HSDY method.
Function
n
NI
Nfg
T (0.01 S)
∥
g
(
x
)
∥
∞
Quadratic QF2
10000
1623
1978
1783
9.81
E
-
07
Extended EP1
10000
4
7
3
6.09
E
-
13
Extended Tridiagonal 2
10000
34
55
30
1.95
E
-
07
ARGLINA
10000
5
15
3
5.60
E
-
07
ARWHEAD
10000
13
58
70
5.60
E
-
07
BDQRTIC
5000
165
448
324
2.93
E
-
03
BDEXP
5000
6
8
4
1.72
E
-
07
BRYBND
5000
5
11
990
2.60
E
-
07
COSINE
10000
14
38
28
5.78
E
-
07
CRAGGLVY
10000
110
150
266
8.92
E
-
07
DIXMAANA
10000
5
10
16
5.17
E
-
07
DIXMAANB
10000
9
18
27
2.21
E
-
07
DIXMAANC
10000
10
21
31
5.42
E
-
07
DIXMAAND
10000
13
29
44
1.10
E
-
07
DIXMAANE
5000
410
493
430
9.57
E
-
07
DIXMAANF
5000
432
546
469
3.65
E
-
07
DIXMAANG
5000
476
582
505
5.89
E
-
07
DIXMAANH
5000
442
1204
7792
4.05
E
-
04
DIXMAANI
5000
397
467
408
9.45
E
-
07
DIXMAANJ
5000
445
594
503
9.66
E
-
07
DIXMAANK
5000
403
507
438
9.05
E
-
07
DQDRTIC
10000
10
21
17
1.19
E
-
07
DQRTIC
10000
35
62
43
9.73
E
-
07
EDENSCH
10000
29
87
70
5.74
E
-
06
EG2
10000
251
1121
381
4.02
E
-
03
ENGVAL1
10000
29
50
19
4.26
E
-
07
EXTROSNB
10000
65
122
44
7.11
E
-
07
FREUROTH
10000
50
133
67
1.59
E
-
07
LIARWHD
10000
47
94
61
1.16
E
-
08
NONDIA
10000
7
14
12
4.60
E
-
07
NONDQUAR
5000
1831
3262
1665
9.66
E
-
07
NONSCOMP
10000
73
126
119
5.10
E
-
07Figure1 shows the performance of these test methods relative to the CPU time, which were evaluated using the profiles of Dolan and Moré [12]. That is, for each method, we plot the fraction P of problems for which the method is within a factor t of the best time. The top curve is the method that solved the most problems in a time that was within a factor t of the best time. Clearly, the left side of the figure gives the percentage of the test problems for which a method is the fastest. As we can see from Figure 1, DS-HSDY method has the best performance which performs better than S-HSDY method, HSDY method, and the well-known PRP+ method.Figure 1
Performance profiles for CPU time.


## 5. Conclusion

In this paper, we proposed an efficient hybrid spectral conjugate gradient method with self-adjusting property. Under some suitable assumptions, we established the global convergence result for the DS-HSDY method. Numerical results indicated that the proposed method is efficient for large-scale unconstrained optimization problems.



---

*Source: 814912-2013-04-11.xml*