# Spectral Three-Term Constrained Conjugate Gradient Algorithm for Function Minimizations

Authors: Huda I. Ahmed; Rana Z. Al-Kawaz; Abbas Y. Al-Bayati
Journal: Journal of Applied Mathematics
 (2019)

---

## Abstract

In this work, we tend to deal within the field of the constrained optimization methods of three-term Conjugate Gradient (CG) technique which is primarily based on Dai–Liao (DL) formula. The new proposed technique satisfies the conjugacy property and the descent conditions of Karush–Kuhn–Tucker (K.K.T.). Our planned constrained technique uses the robust Wolfe line search condition with some assumptions. We tend to prove the global convergence property of the new planned technique. Numeral comparisons for (30-thirty) constrained optimization issues make sure the effectiveness of the new planned formula.


---

## Body

## 1. Introduction

All strategies for constrained problems will be classified into (2) basic categories; specifically, direct and indirect ways. Generating uncontained sub-problem ways for the later kind square measure vital even for a few special optimization interior and exterior penalty function techniques transform the constrained problem into unconstrained optimization type problems. The technique in the main easy and quite sturdy for a previous technique known as Sequential Unconstrained Minimization Technique (SUMT). The essential optimization problem with inequality constrained of this way outlined as(1)
m
i
n
f
x
s.t.
c
i
x
≤
0
i
=
1
,
⋯
m
.This problem is regenerate into unconstrained minimization technique by constructing a function of the shape(2)
φ
x
,
μ
=
f
x
+
μ
B
x
,whereμ
→
0 and B
x is defined by [1]:(3)
B
x
=
∑
j
=
1
m
1
c
j
x
.Therefore, we can rewrite the Equation (2) as follows(4)
φ
x
,
μ
=
f
x
+
μ
∑
j
=
1
m
1
c
j
x
.The derivatives of this functions are∇
f
x and ∇
c
i
x
,
for
i
=
1
,
⋯
,
n are linear independent, so that(5)
∇
φ
x
,
μ
=
∇
f
x
+
μ
∑
j
=
1
m
−
1
c
j
2
x
∇
c
j
x
.Now we turn to the second part parallel to the importance of the previous part, which is unconstrained optimization technique and let us know the problem (2), where φ
:
R
n
→
R
is a real-valued continuous and scalable derivation function. The iterative is(6)
x
k
+
1
=
x
k
+
α
k
d
k
,whereasα
k is step-length. The new search direction d
k
+
1 is:(7)
d
k
+
1
=
−
∇
φ
x
k
+
1
,
μ
k
+
1
for
k
=
0
,
−
∇
φ
x
k
+
1
,
μ
k
+
1
+
β
k
d
k
for
k
≥
1
.The value of the derivative function at the current point isg
x
k
+
1
=
∇
φ
x
k
+
1
,
μ
k
+
1 and β
k is a positive scalar called the conjugate gradient parameter.There are some known formulas ofβ
k are from Hestenes–Stiefel (HS) [2], Fletcher–Reeves (FR) [3], Polak–Ribière (PR) [4], Liu–Storey (LS) [5] and Dai–Liao (DL) [6].In the existing convergence analysis and implementation of the CG technique, the weak Wolfe condition [7] are defined as:(8)
φ
x
k
+
1
,
μ
k
+
1
−
φ
x
k
,
μ
k
≤
δ
α
k
∇
φ
x
k
,
μ
k
T
d
k
,
(9)
∇
φ
x
k
+
1
,
μ
k
+
1
T
d
k
≥
σ
∇
φ
x
k
,
μ
k
T
d
k
,and0
<
δ
<
σ
<
1.By updating one of the conditions also strong Wolfe conditions [7] consist of (8) and(10)
∇
φ
x
k
+
1
,
μ
k
+
1
T
d
k
≤
−
σ
∇
φ
x
k
,
μ
k
T
d
k
.Furthermore, the sufficient descent property, namely(11)
d
k
+
1
T
∇
φ
x
k
+
1
,
μ
k
+
1
≤
−
c
∇
φ
x
k
+
1
,
μ
k
+
1
2
.The constant c is a positive number that satisfies the descent condition.


## 2. A Modified Dai–Liao Three-Term CG Technique

Many researchers have provided different updates which are suitable for the parameter of Dai–Liao (DL) CG-method consisting of:(12)
β
k
D
L
=
g
k
+
1
T
y
k
−
t
s
k
s
k
T
y
k
.Recall the work of Liveries and Pintelas [8] which they forward a new update to the parameter β
k
D
L which was based on the modified secant equation and they replaced y
k with this new one. Other researchers, e.g. Babaie-Kafaki and Ghanbari [9] present in their work a derivation of two modified CG-methods which are based on Perry’s work; they got better numerical results than the original one given by DL. The researchers continued various updates of the DL-parameter in order to obtain some suitable formulas. See for example [10–12]. Moreover, the researcher’s Zhang et al. [13] prompt a three-term CG-technique based mostly of the DL-technique as follows:(13)
d
k
+
1
=
−
g
k
+
1
+
g
k
+
1
T
y
k
−
t
s
k
s
k
T
y
k
s
k
−
g
k
+
1
T
d
k
s
k
T
y
k
y
k
−
t
s
k
,
t
>
0
.This direction satisfying the condition (d
k
+
1
T
g
k
+
1
≤
−
c
1
‖
g
k
+
1
‖
2) for all k. Now, exploitation (13) within the constrained CG-technique outlined in (1)–(4) yields(14)
d
k
+
1
=
−
∇
φ
x
k
+
1
,
μ
k
+
1
+
∇
φ
x
k
+
1
,
μ
k
+
1
T
y
k
−
t
s
k
s
k
T
y
k
s
k
−
s
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
s
k
T
y
k
y
k
−
t
s
k
.By updating this formula using the modified techniques of Dai–Liao CG in (14), we obtain:(15)
d
k
+
1
=
−
s
k
T
y
k
−
t
s
k
s
k
T
y
k
∇
φ
x
k
+
1
,
μ
k
+
1
+
∇
φ
x
k
+
1
,
μ
k
+
1
T
y
k
−
t
s
k
s
k
T
y
k
s
k
−
s
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
s
k
T
y
k
y
k
−
t
s
k
.When rewriting the new search direction this is as follows:(16)
d
k
+
1
=
−
Q
k
+
1
∇
φ
x
k
+
1
,
μ
k
+
1
,where(17)
Q
k
+
1
=
1
s
k
T
y
k
s
k
T
y
k
−
t
s
k
.
I
+
y
k
s
k
T
−
s
k
y
k
T
.Sincey
k
T
s
k>0 (by the strong Wolfe condition), through these inequality and Quasi Newton condition we get:(18)
Q
k
+
1
s
k
=
y
k
⇒
s
k
T
Q
k
+
1
s
k
>
0
,this means thatQ
k
+
1 is a positive definite matrix.


## 3. New Theorem

The new directiond
k
+
1 in (15) satisfying the sufficiently descent condition (11).Proof.
Now multiply each side of (15) by ∇
φ
x
k
+
1
,
μ
k
+
1 that capable for unconstrained optimization then we have a tendency to get(19)
∇
φ
x
k
+
1
,
μ
k
+
1
T
d
k
+
1
=
−
y
k
−
t
s
k
T
s
k
s
k
T
y
k
∇
φ
x
k
+
1
,
μ
k
+
1
2
+
y
k
−
t
s
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
s
k
T
y
k
∇
φ
x
k
+
1
,
μ
k
+
1
s
k
−
s
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
s
k
T
y
k
∇
φ
x
k
+
1
,
μ
k
+
1
y
k
−
t
s
k
=
−
y
k
T
s
k
y
k
T
s
k
∇
φ
x
k
+
1
,
μ
k
+
1
2
−
t
s
k
2
y
k
T
s
k
∇
φ
x
k
+
1
,
μ
k
+
1
2
=
−
1
+
t
s
k
2
y
k
T
s
k
∇
φ
x
k
+
1
,
μ
k
+
1
2
.Lets
k
=
α
k
d
k
(20)
∇
φ
x
k
+
1
,
μ
k
+
1
T
d
k
+
1
=
−
1
+
t
α
k
2
d
k
2
α
k
y
k
T
d
k
∇
φ
x
k
+
1
,
μ
k
+
1
2
=
−
1
+
t
α
k
d
k
2
y
k
T
d
k
∇
φ
x
k
+
1
,
μ
k
+
1
2
.The scalarβ
k
D
L is known, this means (d
k
=
−
g
k). Moreover, when multiply the other end of the direction by y
k we get:(21)
y
k
T
d
k
=
∇
φ
x
k
+
1
,
μ
k
+
1
T
d
k
−
∇
φ
x
k
,
μ
k
T
d
k
=
∇
φ
x
k
+
1
,
μ
k
+
1
T
d
k
+
d
k
2
≥
d
k
2
(22)
∇
ϕ
x
k
+
1
,
μ
k
+
1
T
d
k
+
1
≤
−
1
+
t
α
k
d
k
2
d
k
2
∇
ϕ
x
k
+
1
,
μ
k
+
1
2
≤
−
1
+
t
α
k
∇
ϕ
x
k
+
1
,
μ
k
+
1
2
.Wherec
=
−
1
−
t
α
k (is a positive constant). Now, we have(23)
∇
φ
x
k
+
1
,
μ
k
+
1
T
d
k
+
1
≤
−
c
∇
φ
x
k
+
1
,
μ
k
+
1
2
∇
f
x
k
+
1
−
μ
k
+
1
∑
j
=
1
m
1
c
j
2
x
k
+
1
∇
c
j
x
k
+
1
T
d
k
+
1
≤
−
c
∇
f
x
k
+
1
+
μ
k
+
1
∑
j
=
1
m
−
1
c
j
2
x
k
+
1
∇
c
j
x
k
+
1
2
∇
f
x
k
+
1
−
μ
k
+
1
∑
j
=
1
m
1
c
j
2
x
k
+
1
∇
c
j
x
k
+
1
T
d
k
+
1
≤
−
c
∇
f
x
k
+
1
T
∇
f
x
k
+
1
−
2
μ
k
+
1
∇
f
x
k
+
1
T
∑
j
=
1
m
1
c
j
2
x
k
+
1
∇
c
j
x
k
+
1
+
μ
k
+
1
2
∑
j
=
1
m
1
c
j
2
x
k
+
1
∇
c
j
x
k
+
1
T
∑
j
=
1
m
1
c
j
2
x
k
+
1
∇
c
j
x
k
+
1
,which can be written differently(24)
∇
f
x
k
+
1
−
μ
k
+
1
∑
j
=
1
m
1
c
j
2
x
k
+
1
∇
c
j
x
k
+
1
T
d
k
+
1
≤
−
c
∇
f
x
k
+
1
+
μ
k
+
1
∇
B
x
k
+
1
2
,andB
x
k
+
1 is the Barrier function at point k
+
1.Then depending on one of Karush–Kuhn–Tucker, KKT’s [14] optimal conditions and some regularity conditions of [15] such that if ∇
c
x
T
d
≤
0 as well as formula(25)
μ
k
+
1
=
μ
k
10
,
μ
0
>
0
.So, whenμ
k
+
1
→
0 and in order to get a min of the function f
x we take the limit for the function φ
x
,
μ
w
h
e
n
μ
→
0, in form:(26)
∇
f
x
k
+
1
T
d
k
+
1
≤
−
c
∇
f
x
k
+
1
2
,we get the required, a sufficient descent direction of our new algorithm.Lemma 1 [16].
The new directiond
k
+
1 defined in (15) is satisfying the conjugacy condition.Proof.
Lety
~
=
y
k
−
t
s
k(27)
y
~
k
T
d
k
+
1
=
−
y
~
k
T
s
k
y
k
T
s
k
y
~
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
+
y
~
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
y
k
T
s
k
y
k
T
s
k
−
s
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
y
k
T
s
k
y
~
k
T
y
k
.
(28)
y
~
k
T
d
k
+
1
=
−
y
~
2
y
k
T
s
k
s
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
=
−
ϕ
s
k
T
∇
φ
x
k
+
1
,
μ
k
+
1
,whereϕ
>
0 and this condition is equal to y
k
T
d
k
+
1
=
−
t
s
k
T
g
k
+
1 where(29)
g
k
+
1
=
∇
φ
x
k
+
1
,
μ
k
+
1
.


## 4. Global Convergence Property

In this part of the article, we will address the convergence analysis of the new algorithm where the following assumptions are often used in CG techniques.Assumptions [17 and 18].
(i) Let the level setS
=
x
:
ϕ
x
,
μ
≤
ϕ
x
0
,
μ bounded i.e., there exists a constant q > 0 such that
(30)
x
≤
q
,
∀
x
∈
S
.
(ii) Clearly there is some neighborhoodN of S, the function f is continuously differentiable, and its gradient is Lipschitz continuous, i.e. there exists a constant L
>
0 such that
(31)
∇
ϕ
x
,
μ
−
∇
ϕ
y
,
μ
≤
L
x
−
y
,
∀
x
,
y
∈
N
.
Assuming that conditions (i) and (ii) are satisfy, we can deduce that there exists a constantγ
>
0 such that (32)
∇
ϕ
x
,
μ
≤
γ
.


## 5. Global Convergence for New Theorem

Consider the new three-term CG-technique (15) which is satisfying (13) and assume that the step-size α
k satisfies (8) and (10) then(33)
lim
k
→
∞
∇
φ
x
k
+
1
,
μ
k
+
1
=
0
.Proof.
The new search direction is:(34)
d
k
+
1
≤
y
k
−
t
s
k
s
k
y
k
s
k
∇
φ
x
k
+
1
,
μ
k
+
1
+
y
k
−
t
s
k
s
k
y
k
s
k
∇
φ
x
k
+
1
,
μ
k
+
1
+
∇
φ
x
k
+
1
,
μ
k
+
1
s
k
y
k
−
t
s
k
y
k
s
k
≤
y
k
+
t
s
k
3
∇
φ
x
k
+
1
,
μ
k
+
1
y
k
.From Lipschitz condition and(35)
μ
s
k
2
≤
y
k
T
s
k
≤
L
s
k
≤
L
s
k
+
t
s
k
3
γ
μ
s
k
≤
L
+
t
3
γ
μ
=
r
.Hence, by taking the summation of the search direction we get:(36)
∑
k
≥
1
1
d
k
+
1
2
≥
1
r
∑
k
≥
1
1
=
∞
.This means that (33) is true.


## 6. Numerical Experiments

In order to assess the performance of the planned new algorithm outlined in (15). The new constrained CG technique is checked over thirty nonlinear-selected test functions (see the Appendix of [1, 19, 20] for the details of those test problems). For all cases the stopping criterion is taken to be(37)
∇
φ
x
k
+
1
,
μ
k
+
1
≤
0.000001
or
φ
x
k
+
1
,
μ
k
+
1
−
φ
x
k
,
μ
k
φ
x
k
+
1
,
μ
k
+
1
≤
0.000001
.The comparative performance of all thought of algorithms is evaluated by considering NOF, NOI, NOC where NOF denotes the number of perform function evaluations, NOI denotes the number of iterations required to minimize the test problem and NOC denotes the number of constrained evaluations. We adopt the performance profiles given by Dolan and More [21].The following three forms have the task of clarifying the performance of the algorithm more clearly as follows:(i)
Figure1 illustrates the activity of the new algorithm in calculating the number of function values.
(ii)
Figure2 shows the level of improvement of the number of iterations.
(iii)
Figure3 illustrates the efficiency of the new algorithm in the calculation of constraints.Figure 1
Performance profiles based on function evaluation.Figure 2
Performance profiles based on number of iterations.Figure 3
Performance profiles based on number of constrained.To measure the percentages of optimization for better accuracy we give the following Table1 showing the percentage of effectiveness of the new algorithm and the efficiency of the number of updates to reach the optimal solution.Table 1
Percentage performance of algorithm (15) against algorithm (13).
Tools
Algorithm (13) Zhang algorithm
New algorithm (15)
NOF
100%
40.35
NOI
100%
52.84
NOC
100%
92.43From the last Table1, it is evident that the new proposed constrained CG-technique formulated in (15) outdo the standard three-term CG-technique formulated in (12) in about (59)% NOF; (47)% in NOI and (7)% in NOC, respectively.



---

*Source: 6378368-2019-12-25.xml*