Page 33 - IJOCTA-15-1

Global convergence property with inexact line search for a new conjugate gradient method
numerical comparisons against the NDH, HZ,
k+1 k + (1 − θ k )∥y k ∥
and BA methods, as well as the hybrid method 0 = −g T y 2
hDYHS from, 27 using 30 test problems from the 2
T
T
CUTE collection. 28 Finally, a brief conclusion is +θ k (y g k+1 − 2 ∥y k ∥ d g k+1 ),
k
k
T
presented in Section 5. d y k
k
after some algebra, the formula for θ k becomes:
2. Proposed method, algorithm
T
In this section, we describe a newly proposed CG θ k = g y k . (10)
k
T
T
method, where the parameter β k ∈ R represents a y g k − 2 ∥y k ∥ 2 d g k+1
T
k d y k k
convex combination of the HZ and BA methods, k
defined as follows:
In the second algorithm, the parameter θ k is cho-
β hyb = (1 − θ k )β BA + θ k β HZ , sen such that the direction d k+1 from (9) corre-
k k k
sponds to the Newton direction, i.e.,
∥y k ∥ 2
= (1 − θ k ) (8)
T ∥y k ∥ 2
d y k 2 −1
k −∇ f(x k+1 ) g k+1 = −g k+1 + (1 − θ k )
T
2 d y k
1 ∥y k ∥ T k
+θ k T (y k − 2d k T ) g k+1 . 1
d y k d y k T
k k
d k + θ k (y g k+1
T k
Here θ k ∈ [0, 1] is referred to as the hybridization d y k
k
parameter, which will be determined using a spe- ∥y k ∥ 2 T
−2 d g k+1 ) d k .
k
T
cific approach described later. Clearly: if θ k = 0, d y k
k
then β hyb = β BA , and if θ k = 1, then β hyb = β HZ .
k k k k
hyb
For 0 < θ k < 1, β is a convex combination of
k Having in view that ∇ f(x k+1 )d k =y k , from the
2
β BA and β HZ .
k k above relation, we get:
We consider two possibilities for selecting the pa-
rameter θ k :
T 2 T T
In the first hybrid conjugate gradient algorithm, θ k = (y g k+1 − ∥y k ∥ − d g k+1 )d y k .
k
k
k
T
T
T
T
2
the parameter θ k is selected such that the conju- (y g k+1 )(d y k ) − ∥y k ∥ (2d g k+1 + d y k )
k
k
k
k
gacy condition ( d T y (11)
k+1 k = 0)is satisfied at every
iteration, independently of the line search. From
the recurrence relation for d k+1 , we have:
We observe that the value of the parameter θ k
∥y k ∥ 2 given by (10) or (11) can be outside the interval
d T = −g T + (1 − θ k ) T d T
k
k+1
k+1
d y k [0.1]. Thus, in order to have a real convex combi-
k
1 T nation in (8), the following rule is considered: if
+θ k (y g k+1 (9) hyb BA
k
T θ k ≤ 0, then set θ k = 0 in (8) i.e., β = β , if
d y k k k
k hyb
∥y k ∥ 2 θ k ≥ 1, then take θ k = 1 in (8), i.e. β k = β HZ .
k
T
T
−2 T d g k+1 ) d . Therefore, under this rule for θ k selection, the di-
k
k
d y k
k
rection d k in (9) combines the properties of HZ
Now, multiplying both sides of relation (9) by y k , and BA algorithms.
we obtain:
Theorem 1. If the relations (8) and (9) hold,
∥y k ∥ 2
T
T
d T y k+1 k + (1 − θ k ) T d y k then
k+1 k = −g
y
k
d y k
k
1 T d hyb = (1 − θ k )d BA + θ k d HZ . (12)
k+1
k+1
+θ k (y g k+1 k+1
T k
d y k
k
∥y k ∥ 2 Proof. We have the following relation:
T
T
−2 d g k+1 ) d y k .
T k k
d y k
k 2
hyb ∥y k ∥
d = −g k+1 + (1 − θ k ) d k
k+1 T
d y k
k
Using the conjugacy condition, then the above
2
relation becomes: 1 T ∥y k ∥ T
+θ k T y g k+1 − 2 T d g k+1 d k .
k
k
d y k d y k
k k
27