EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 15, No. 3, 2022, 1254-1264
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

A Sufficient Descent Property to Improving a
Three-Term Conjugate Gradient Algorithm

Ghada M. Al-Naemi1,∗, Firas Mahmood Saeed2

1 Department of Mathematics, Faculty of Computer Science and Mathematics,
University of Mosul, Mosul, Nineveh, Iraq
2 Department of Family Medicine, College of Medicine, University of Mosul, Mosul, Nineveh,
Iraq

Abstract. The nonlinear conjugate gradient (NLCGM) methods have received attention because
due to their simplicity, low memory requirements, and global convergent property, which allows
them to be used directly to solve large-scale nonlinear unconstrained optimization problems. We
suggested a modification to the βKMAR

k formula, applied with three-term conjugate gradient
method that is both simple and effective, denoted by (TTKMAR), which has a sufficient de-
scent property (SDP) and ensures global convergence (GCP) when we use any line search. The
numerical efficiency of TTKMAR was assessed using a variety of standard test functions. TTCGM
has been demonstrated to be more numerically efficient than two-term CG methods. This paper
also quantifies the difference between TTCGM and two-term methods of performance. As a result,
we compare our new modification to an efficient two-term and TTCGM in the numerical results.
Finally, we conclude that our proposed modification.

2020 Mathematics Subject Classifications: 90C90, 90C30, 90C06, 65K05, 49M37
Key Words and Phrases: TTCGM, Nonlinear unconstrained optimization, SWPL search, SDP

1. Introduction

The NLCGM, an iterative method for solving the unconstrained optimization problem
of the form: was used in this study.

minu (x) , x ∈ Rn (1)

is investigated. u : Rn → R is smooth and g (x) = ∇u (x) is accessible, because it does
not require any matrices, the NLCGM is one option for obtaining the bare minimum (1)
[5]. CG methods are iterative methods in the form of:

xk+1 = xk + γkdk , k = 0, 1, 2, 3, . . . (2)

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v15i3.4437

Email addresses: drghadaalnaemi@uomosul.edu.iq (GH. M. Al-Naemi),
fms@uomosul.edu.iq (F. M. Saeed)

https://www.ejpam.com 1254 © 2022 EJPAM All rights reserved.



GH. M. Al-Naemi, F. M. Saeed / Eur. J. Pure Appl. Math, 15 (3) (2022), 1254-1264 1255

where γk denotes a positive step size using by cubic interpolation and dk denotes a search
direction. Typically, the search direction is defined as:

dk =

{
−gk, k = 0
−gk + βkdk−1, k ≥ 1

(3)

where βk ∈ R is a scalar parameter that defines CG-method. Typically, the parameter
βk is typically chosen in such a way (2)-(3) reduces the linear CG-method, if f(x) is a
strictly convex quadratic function and is calculated using the exact line search (ELS), the
parameter γk is usually chosen so that (2)-(3) reduces to the linear CG-method [1]. In
[8, 10–12, 14–16], six pioneering forms of βk are defined.

For some TTKMAR methods, the line search is frequently used to achieve GCP and
improve computational performance [17]

f (xk + γkdk) ≤ f (xk) + ργkdk (4)

∣∣∣g(xk + γkdk)
Tdk

∣∣∣ ≤ σ
∣∣gTk dk∣∣ (5)

where dk is the direction of descent and 0 < ρ < 0.5 < σ < 1 is a very efficient value. In
general, the different conjugate gradient parameter choices in (3) correspond to different
TTCG methods.

2. Motivation and Algorithm

Several TTCG methods for unconstrained optimization problems have recently been
proposed. This section begins with an explanation of our motivation before moving on to a
detailed explanation of our method. Recently, Zhang et al. [23] presented a threeâe“term
MPRP method and used the Armijo line search to demonstrate that the direction meets
GCP.

dk =

{
−gk, k = 0

−gk +
gTk yk−1

gTk−1gk−1
dk−1 −

gTk dk−1

gTk−1gk−1
yk−1, k ≥ 1

(6)

where yk−1 = gk − gk−1, in the same content, Zhang et al. [22] developed the three-term
HS method. Which is expressed as:

dk =

{
−gk, k = 0

−gk +
gTk yk−1

yTk−1dk−1
dk−1 −

gTk dk−1

yTk−1dk−1
yk−1, k ≥ 1

(7)

The SDP is satisfied by the three-term HS method; if an ELS is used, it reduces to the
original HS method. Furthermore, a modified three-term HS algorithm on the search
direction is used to ensure the GCP of the search direction specified in (7):

dk =

{
−gk, k = 0

−gk +
gTk µk−1

zTk−1dk−1
dk−1 −

gTk dk−1

zTk−1dk−1
yk−1, k ≥ 1

(8)



GH. M. Al-Naemi, F. M. Saeed / Eur. J. Pure Appl. Math, 15 (3) (2022), 1254-1264 1256

with µk−1 = yk−1+t||g(xk)||T sk−1. Given that modified three-term HS were introduced in
(7) to demonstrate the GCP of the search direction, one might wonder why (7) is not used
to demonstrate the GCP of the search direction. Rather than disregarding (7), it should
be made efficient and globally convergent. As a result, (7) can be modified to meet the
GCP. In terms of numerical performance, such a modification is expected to outperform
the MTTHS algorithm.

Recently, Kamilu and colleagues [13] proposed a new CG formula with the same nu-
merator as the PRP, HS, and RMIL formulas. The numerator was kept to order to give
the formula the ability to restart.

βKMAR
k =

gTk (gk − gk−1)

gTk−1 (gk + gk−1)
(9)

This formula can be reduced to the FR or PRP parameters under certain conditions.
The denominator is geometrically similar to the well-known CG denominator. Because
(gk + gk−1) forms a vector scaled by gk−1. The new vector would be slightly different
from the normal vector produced by the PRP parameter dTk (gk − gk−1). This minor
modification would boost the performance while simplifying the convergence proof.

To increase the efficiency of the one-term and two-term CG methods. The TTCG has
been extensively studied and emphasized since its exception. The performance of this class
of CG methods is heavily dependent on how the scalar parameter is chosen. Yanlin [18]
recently improved the Zhang [23] method by constructing a new modified PRP parameter,
MPRP. The performance is quite good.

At this point, we should recall that the approximation matrix Bk must satisfy the
secant condition for quasi-Newton methods:

Bksk−1 = yk−1 (10)

Zhang et al. [21] and Zhang and Xu [20] using Taylorâe™s series proposed the following
modified secant condition by expanding condition (10).

Bksk−1 = µk−1, µk−1 = yk−1 +
φk−1

||sk−1||2
.sk−1 (11)

φk−1 = 6 (uk−1 − uk) + 3 (gk−1 + gk) (12)

where uk = u (xk). Yabe and Takano [19] extended the modified secant relation (11) by
multiplying a fixed parameter ε ≥ 0, as expressed by the expression:

Bksk−1 = µk−1, µk−1 = yk−1 + ε
φk−1

||sk−1||2
sk−1 (13)

Babaie-Kafaki et al. [6] presented the following modified version of Equation (12):

Bksk−1 = µk−1, Bksk−1 = µk−1, µk−1 = yk−1 + ε
max{0, φk−1}

||sk−1||2
sk−1 (14)

In this paper, we are motivated to develop TTCGM that meets the SDP and achieves
GCP under SWPL.



GH. M. Al-Naemi, F. M. Saeed / Eur. J. Pure Appl. Math, 15 (3) (2022), 1254-1264 1257

3. Modified TTKMAR CG-Method

To develop a new method that is globally convergent in the face of inexact line search.
In the following section, we will create our new TTKMAR method using the modified
βKMAR
k by:

βMKMAR
k =

gTk µk−1

gTk−1 (gk + gk−1)
(15)

with µk−1 = yk−1 +
φk−1

||sk−1||2
.sk−1 and φk−1 =

gTk dk−1

gTk−1(gk+gk−1)
. Then the direction will be

defined by:

dk =

{
−gk, k = 0
−gk + βMKMAR

k dk−1 − φk−1yk−1, k ≥ 1
(16)

3.1. Algorithm (TTKMAR)

1. Choose x0 ∈ Rn,∈> 0, dk = −gk, set k = 0.

2. If ||gk|| ≤ 1× 10−5, then stop; otherwise, go to the next step.

3. Calculate γk−1 by using SWPL defined in (4) and (5).

4. Calculate xk by (2), and compute gk, uk.

5. Compute the direction dk by (16).

6. If ||gk|| ≤∈, stop; otherwise go to the next step.

7. If k = n or
∣∣gTk gk−1

∣∣ ≥ (0.2) .
(
||gk||2

)
is hold, proceed step 1; Otherwise, proceed to

next step.

8. Put k = k + 1, and go to (2).

The TTKMAR method meets the SDP, as demonstrated by the following lemma.

Theorem 1. Suppose that the sequences {gn} and {dn} are generated by the TTKMAR
method and the step size γk by using SWPL defined in (4) and (5). Then

dTk gk ≤ −τ.||gk||2, with τ =

[
1− δω

a.δ2

]
∀k ≥ 0 (17)

Proof. We arrive at the conclusion (16) through mathematical induction. For k =
0, dT0 g0 = −||g0||2, holds. If we assume that conclusion (17) holds true for k− 1, we have
dTk−1gk−1 ≤ −τ.||gk−1||2 We have from (16)

dk = −gk +
gTk µk−1

gTk−1 (gk + gk−1)
dk−1 −

gTk dk−1

gTk−1 (gk + gk−1)
yk−1



GH. M. Al-Naemi, F. M. Saeed / Eur. J. Pure Appl. Math, 15 (3) (2022), 1254-1264 1258

Multiply both sides of the above equation by gTk

gTk dk ≤ −||gk||2 +
gTk

(
yk−1 +

φk−1

||sk−1||2
.sk−1

)
gTk−1 (gk + gk−1)

gTk dk−1 −
gTk dk−1

gTk−1 (gk + gk−1)
gTk yk−1

≤ −||gk||2 +
(
yTk−1gk

) (
gTk dk−1

)
gTk−1 (gk + gk−1)

+
φk−1

(
sTk−1gk

) (
gTk dk−1

)
||sk−1||2

[
gTk−1 (gk + gk−1)

] − (
yTk−1gk

) (
gTk dk−1

)
gTk−1 (gk + gk−1)

≤ −||gk||2 +
(
sTk−1gk

) (
gTk dk−1

)2
||sk−1||2

(
gTk−1 (gk + gk−1)

)2
Since, gTk dk−1 ≤ ||gk||||dk−1||, we have sk−1 = γk−1dk−1, and they proved in [13] that:

0 ≤ βKMAR
k ≤ ||gk||2

||gk−1||2
(18)

we get

dTk gk ≤ −||gk||2 +
γk−1||gk||3.||dk−1||3

γk−1
2||dk−1||2.||gk−1||4

dTk gk ≤ −
[
1− ||gk||.||dk−1||

γk−1||gk−1||4

]
||gk||,

dTk gk ≤ −τ.||gk||2 where τ =

[
1− δω

a.δ2

]
The proof has been completed. The following assumptions are always useful for CG
approach convergence analysis.

4. Global Convergence of TTKMAR

Assumption (1)

1. u (x) is restricted from below to the level set Λ = {x ∈ Rn, u (x) ≤ u (x0), x0 is the
starting point. i.e., there is a constant ω > 0, which means ||xk|| ≤ ω ∀x ∈ Λ.

2. u (x) is continuously differentiable in a specific neighborhood N of Λ, and its gradient
is Lipschitz continuous, which means that there is a constant M > 0, s.t.

||g (x)− g (y) || ≤ M||x− y||, ∀x, y ∈ N (19)

It is worth noting that Assumption (1) implies existence of a positive constant δ, such
that [2]:

||gk|| ≤ δ, ∀k (20)

Theorem 2. Assume Assumption (1) is true. Consider methods (2) and (16), where dk
is a descent direction and γk is provided by SWPL. If



GH. M. Al-Naemi, F. M. Saeed / Eur. J. Pure Appl. Math, 15 (3) (2022), 1254-1264 1259

∑
k≥1

1

||dk||2
= ∞ (21)

Then
lim inf
k→∞

||gk|| = 0 (22)

Theorem 3. Assuming Assumption (1) is correct, consider Algorithm (TTKMAR), where
dk and γk satisfy the sufficient descent condition (17) as well as (4) and (5), respectively.
Then lim infk→∞ ||gk|| = 0

Proof. Because the descending property holds, we have dk ̸= 0. As a result, lemma (2)
suffices to demonstrate that ||dk|| is bounded above. Derived from (15), and (16)

||dk|| =

∣∣∣∣∣
∣∣∣∣∣−gk +

gTk µk−1∣∣gTk−1gk
∣∣+ ||gk−1||2

dk−1 −
gTk dk−1∣∣gTk−1gk
∣∣+ ||gk−1||2

yk−1

∣∣∣∣∣
∣∣∣∣∣

=

∣∣∣∣∣∣
∣∣∣∣∣∣−gk +

gTk

(
yk−1 +

φk−1

||sk−1||2
.sk−1

)
∣∣gTk−1gk

∣∣+ ||gk−1||2
dk−1 −

gTk dk−1∣∣gTk−1gk
∣∣+ ||gk−1||2

yk−1

∣∣∣∣∣∣
∣∣∣∣∣∣

As a result of 0 ≤ βKMAR
k ≤ ||gk||2

||gk−1||2
, sk−1 = γk−1dk−1, (17), and (19) we obtain

||dk|| ≤ ||gk||+
||gk||2

||gk−1||2
||dk−1||+

γk−1||gk||2.||dk−1||2

γk−1
2||dk−1||2||gk−1||2

||dk−1||+
||gk||||dk−1||
||gk−1||2

Mγk−1||dk−1||

=

[
1 +

γk−1||gk||+ ||gk||||dk−1||+Mγk−1
2||dk−1||2

γk−1||gk−1||2

]
||gk||

≤
[
1 +

aδ + δω +Ma2ω2

a.δ̄2

]
||gk|| ≤ A.δ

||dk|| ≤ V ⇒ ||dk||2 ≤ V 2 (23)

By taking the summation on both sides of (23), we get

⇒
∑
k≥1

1

||dk||2
≥ 1

V 2

∑
k≥1

1 = +∞

Inconsistency with the Zountendijk theorem [24], so

lim inf
k→∞

||gk|| = 0

CGP has been achieved by the new proposed algorithm.



GH. M. Al-Naemi, F. M. Saeed / Eur. J. Pure Appl. Math, 15 (3) (2022), 1254-1264 1260

5. Mathematical Experiments

In this part, we chose some of the test functions from CUTE [4] library, which, as well
as Andrei [3], Bongartz [7], and others have solved large-scale optimization problems. All
codes are written in FORTRAN with double precision, and compiled Visual F90 (using
the default compiler settings). To compute the value of γk, the cubic fitting procedure is
always used.

We chose twenty-four extended or generalized large-scale unconstrained optimization
problems in an extended or generalized form. Every problem was tested three times for a
progressively increasing number of dimensions: N = 1000, 10000, and 100000, respectively,
and all algorithms implemented under the SWPL (4) and (5) conditions with ρ = 0.01
and σ = 0.85, respectively, and the stopping criterion ||gn|| ≤ 1× 10−5 is used.

The execution was also analyzed using the performance profile software developed by
Dolan and Mor’e [9], as shown in Figures 1 and 2.

Figure 1: The performance profile of iteration.

For our comparison, we keep track of the number of iterations denotes (No.I), function
evaluation denotes (No.F), finally the test function denotes (T. Fn.).



GH. M. Al-Naemi, F. M. Saeed / Eur. J. Pure Appl. Math, 15 (3) (2022), 1254-1264 1261

Figure 2: The performance profile of function evaluation.

Table 1: Compares Two Terms (βKMAR
k , βPRP

k ), Three Terms Shanno and the Proposed Method TTKMAR,
Based on No. I and No. F. (N = 1000, 10000, 100000)

T. Fn.
Two-terms

βPRP
k

Two-terms
βKMAR
k

Three-terms
Shanno

Three-terms
βMKMAR
k

No. I No. F No. I No. F No. I No. F No. I No. F

Ex. Block diagonal-1 161 337 155 332 156 335 151 319
Wolfe 321 652 319 648 328 675 307 632
Diagonal-6 (Cute) 9 28 8 25 8 26 8 26
Ex. Beal 58 151 57 148 62 156 51 135
DIXMAANAB (Cute) 19 56 19 49 19 52 17 45
DIXMAANAF (Cute) 19 45 16 41 19 47 16 41
NOND 155 422 180 592 178 598 149 413
Powell 119 339 141 392 124 421 112 332
OSP 1030 1868 1029 1880 1035 2120 1021 1750
PQ 1010 1901 1007 1890 1010 1938 1008 1894
Cubic 54 131 72 197 48 149 45 127
Shallow 27 69 26 67 32 80 24 63
Wood 94 220 103 235 99 273 101 227
Ex. Wood 290 612 245 590 298 622 234 565
Strait 18 42 18 42 18 42 18 42
Ex. Three Exponential 41 81 34 117 81 152 30 69
Fred 65 179 63 172 76 196 60 162
Quadratic Fn. QF1 1191 2335 1190 2332 1193 2347 1185 2328
Cosine 34 86 34 86 34 86 34 86
Gen. Tridiagonal-2 123 256 120 251 125 275 118 253
Diagonal-5 11 40 11 40 11 40 11 40
Helical 105 242 103 238 92 218 107 248
DENSCHNB 62 130 66 138 65 144 70 146
DENSCHNF 60 183 51 177 61 190 42 167

Total No. I 5076 4967 5172 4919
No. F 11176 10691 11182 10110



REFERENCES 1262

Table 2: The Work of the Proposed Method is Shown in Percentage.

Measures
Two-terms

βPRP
k

Two-terms
βKMAR
k

Three-terms
Shanno

Three-terms
βMKMAR
k

No.I 98.14% 96.04% 100% 95.11%
No.F 99.95% 95.61% 100% 90.41%

In terms of percentage performance, Table 2 shows that the three-term βMKMAR
k

method outperforms the classic two-term βPRP
k , two-term βKMAR

k , and three-term Shanno
methods. We discovered that the three-term βMKMAR

k method saves (No. I, 4.89%),
(No.F, 9.59%), the two-term βPRP

k method saves (No.I, 1.86%), (No.F No.F, 0.05%), and
the two-term βKMAR

k method saves (No.I, 3.96%). (No.F, 4.39%). This behavior can be
explained by making a minor change and adding a third term to the direction of the two-
term βKMAR

k method, so that the generated direction always meets the sufficient descent
and globally convergent conditions.

6. Conclusions

We suggested a modification of spectral βKMAR
k using three-term conjugate gra-

dient method which defined by (16) and prove that our proposed method satisfied global
convergent and desent condition. The numerical results show that the new method (TTK-
MAR) is better than the classic two-term βPRP

k , two-term βKMAR
k , and three-term Shanno

methods and more effective in practically.

References

[1] Ghada M. Al-Naemi. A new modified hs algorithm with strong powell-wolfe line search
for unconstrained optimization. Eastern-European Journal of Enterprise Technolo-
gies, 116:14–21, 2022.

[2] Ghada M Al-Naemi and Ahmed H Sheekoo. New scaled algorithm for non-linear
conjugate gradients in unconstrained optimization. Indonesian Journal of Electrical
Engineering and Computer Science, 24(3):1589–1595, 2021.

[3] Neculai Andrei. Test functions for unconstrained optimization. Research Institute for
informatics. Center for Advanced Modeling and Optimization, pages 8–10, 2004.

[4] Neculai Andrei. An unconstrained optimization test functions collection. Adv. Model.
Optim, 10(1):147–161, 2008.

[5] Neculai Andrei. Nonlinear Conjugate Gradient Methods for Unconstrained Optimiza-
tion. Springer International Publishing, 2020.



REFERENCES 1263

[6] Saman Babaie-Kafaki, Reza Ghanbari, and Nezam Mahdavi-Amiri. Two new conju-
gate gradient methods based on modified secant equations. Journal of computational
and applied Mathematics, 234(5):1374–1386, 2010.

[7] I. Bongartz, A. R. Conn, Nick Gould, and Ph. L. Toint. CUTE. ACM Transactions
on Mathematical Software, 21(1):123–160, mar 1995.

[8] Yu-Hong Dai and Yaxiang Yuan. A nonlinear conjugate gradient method with a
strong global convergence property. SIAM Journal on optimization, 10(1):177–182,
1999.

[9] Elizabeth D. Dolan and Jorge J. Moré. Benchmarking optimization software with
performance profiles. Mathematical Programming, 91(2):201–213, jan 2002.

[10] R. Fletcher. Function minimization by conjugate gradients. The Computer Journal,
7(2):149–154, feb 1964.

[11] Roger Fletcher. Practical methods of optimization, 1987. 1987.

[12] M.R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear
systems. Journal of Research of the National Bureau of Standards, 49(6):409, dec
1952.

[13] Kamilu Kamfa, Sulaiman Ibrahim, MY Waziri, and Abdelrahman Abashar. Another
improved three term prp-cg method with global convergent properties for solving
unconstrained optimization problems. Malaysian Journal of Computing and Applied
Mathematics, 1(1):1–10, 2018.

[14] Y. Liu and C. Storey. Efficient generalized conjugate gradient algorithms, part 1:
Theory. Journal of Optimization Theory and Applications, 69(1):129–137, apr 1991.

[15] E. Polak and G. Ribiere. Note sur la convergence de méthodes de directions con-
juguées. Revue française d'informatique et de recherche opérationnelle. Série rouge,
3(16):35–43, 1969.

[16] Boris Teodorovich Polyak. The conjugate gradient method in extremal problems.
USSR Computational Mathematics and Mathematical Physics, 9(4):94–112, 1969.

[17] Philip Wolfe. Convergence conditions for ascent methods. SIAM Review, 11(2):226–
235, apr 1969.

[18] Yanlin Wu. A modified three-term prp conjugate gradient algorithm for optimization
models. Journal of inequalities and applications, 2017(1):1–14, 2017.

[19] Hiroshi Yabe and Masahiro Takano. Global convergence properties of nonlinear con-
jugate gradient methods with modified secant condition. Computational optimization
and Applications, 28(2):203–225, 2004.



REFERENCES 1264

[20] Jianzhong Zhang and Chengxian Xu. Properties and numerical performance of quasi-
newton methods with modified quasi-newton equations. Journal of Computational
and Applied Mathematics, 137(2):269–278, 2001.

[21] JZ Zhang, NY Deng, and LH0991 Chen. New quasi-newton equation and related
methods for unconstrained optimization. Journal of Optimization Theory and Appli-
cations, 102(1):147–167, 1999.

[22] Li Zhang, Weijun Zhou, and Dong-Hui Li. A descent modified polak–ribière–polyak
conjugate gradient method and its global convergence. IMA Journal of Numerical
Analysis, 26(4):629–640, oct 2006.

[23] Li Zhang, Weijun Zhou, and Donghui Li. Some descent three-term conjugate gra-
dient methods and their global convergence. Optimization Methods and Software,
22(4):697–711, aug 2007.

[24] G Zoutendijk. Nonlinear programming, computational methods. Integer and nonlin-
ear programming, pages 37–86, 1970.