Page 35 - IJOCTA-15-1

Global convergence property with inexact line search for a new conjugate gradient method
hyb HZ
equation (8). If θ k ≥ 1, set β = β . If According to Lemma 2, Assumptions 1 and 2, the
k k
θ k ≤ 0, set β hyb = β BA . strong Wolfe conditions, and (15), it follows that
k k T
hyb g d k ̸= 0 for all k ≥ 0. Therefore, α k = 0 does
Step 6. Compute d = −g k+1 + β d k . If the k
k not satisfy (4). This implies that α k = 0 in the
restart criterion of Powell’s condition
new hybrid conjugate gradient algorithm is not
|g T g 2 valid, and there exists a constant λ > 0 such that
k+1 k | ≥ 0.2∥g k+1 ∥ ,
is satisfied, then set d k+1 = −g k+1 . Otherwise, α k ≥ λ, for all k ≥ 0. (22)
define d k+1 = d.
Step 7. Set k = k + 1 and continue with Step 1.
Now, we will give the following Theorem, which
3. Global convergence shows the global convergence of our new method.
In this section, we study the global convergence Theorem 3. Let Assumptions 1 and 2 hold.
properties of the proposed conjugate gradient Consider the iterative method of the form (2),(8)
method. To proceed, we make the following As- and (9). Then either g k = 0, for some k, or
sumptions and present several lemmas.
n lim inf ∥g k ∥ = 0. (23)
Assumption 1. The level set S = {x ∈ R : k→∞
f(x) ≤ f(x 0 )} is bounded, i.e., there exists a con-
stant B > 0 such that
Proof. Suppose that g k ̸= 0, for all k. We will
∥x∥ ≤ B, for all x ∈ S. (16) prove (23) by contradiction.Assume that (23)

Assumption 2. In a neighborhood N of S, the does not hold. Then, there exists a constant
function f is continuously differentiable, and its c > 0 such that
gradient ∇f(x) is Lipschitz continuous. That is,
there exists a constant 0 < L < ∞ such that ∥g k ∥ ≥ c, for all k , (24)

according to the relations (4) and (15), we obtain:
∥∇f(x) − ∇f(y)∥ ≤ L∥x − y∥, for all x, y ∈ N.
2
2
T
Under Assumptions 1 and 2 on f, there exists a d y k ≥ K(1 − σ)∥g k ∥ ≥ K(1 − σ)c .
k
constant Γ ≥ 0, such that
By using the Lipschitz condition, we get:
∥∇f(x)∥ ≤ Γ, (17) ∥y k ∥ = ∥g k+1 − g k ∥ ≤ LD,
where D = max{∥x − y∥, x, y ∈ N} is the diam-
for all x ∈ S. eter of N.
We have
Lemma 1. Let Assumptions 1 and 2 hold. Con-
sider the method (2) and (3), where d k is a de- d hyb = −g k+1 + (1 − θ k )β BA d k + θ k β HZ d k ,
scent direction and α k is obtained from the strong k+1 k k
Wolfe line search. If
since, 0 < θ k < 1, we obtain:
X 1
= ∞, (18)
∥d k ∥ 2 hyb BA HZ
k≥0 ∥d k+1 ∥ ≤ ∥g k+1 ∥ + (|β k | + |β k |)∥d k ∥. (25)
then
lim inf ∥g k ∥ = 0. (19) They proved in 20 and 31 that:
k→∞
2
L D 2
BA
Lemma 2. 1 Suppose that Assumptions 1 and 2 |β k | ≤ K(1 − σ)c 2 ,
hold. If d k is a descent direction and α k satisfies
g T d T σ < 1, (20) and
k+1 k ≥ σg d k ,
k
then
T
(1 − σ) |d g k |
α k ≥ · k . (21) |β HZ | ≤ 1 LDΓ + 2 σ (LD) 2 .
L ∥d k ∥ 2 k (1 − σ)Kc 2 (1 − σ)
Proof. The proof of Lemma 2 can be found Using the above relations and (22), the equation
in. 1 □ (25) becomes:
29