# A Modified Conjugacy Condition and Related Nonlinear Conjugate Gradient Method

Authors: Shengwei Yao; Xiwen Lu; Bin Qin
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The conjugate gradient (CG) method has played a special role in solving large-scale nonlinear optimization problems due to the simplicity of their very low memory requirements. In this paper, we propose a new conjugacy condition which is similar to Dai-Liao (2001). Based on this condition, the related nonlinear conjugate gradient method is given. With some mild conditions, the given method is globally convergent under the strong Wolfe-Powell line search for general functions. The numerical experiments show that the proposed method is very robust and efficient.


---

## Body

## 1. Introduction

The conjugate gradient (CG) method has played a special role in solving large-scale nonlinear optimization problems due to the simplicity of their iterations and their very low memory requirements. In fact, the CG method is not among the fastest or most robust optimization methods for nonlinear problems available today, but it remains very popular for engineers and mathematicians who are interested in solving large-scale problems. The conjugate gradient method is designed to solve the following unconstrained optimization problem:(1)
min
⁡
{
f
(
x
)
∣
x
∈
R
n
}
,
where f
(
x
)
:
R
n
→
R is a smooth, nonlinear function whose gradient will be denoted by g
(
x
). The iterative formula of the conjugate gradient method is given by
(2)
x
k
+
1
=
x
k
+
s
k
,
s
k
=
α
k
d
k
,
where α
k is a step-length which is computed by carrying out a line search, and d
k is the search direction defined by
(3)
d
k
=
{
-
g
k
if
k
=
1
-
g
k
+
β
k
d
k
-
1
if
k
≥
2
,
where β
k is a scalar and g
k denotes the gradient ∇
f
(
x
k
). The different conjugate gradient methods correspond to different computing ways of β
k. If f is a strictly convex quadratic function, namely,
(4)
f
(
x
)
=
1
2
x
T
H
x
+
b
T
x
,
where H is a positive definite matrix, and if α
k is the exact one-dimensional minimizer along the direction d
k, then the method with (2) and (3) is called linear conjugate gradient method. Otherwise, it is called nonlinear conjugate gradient method. The most important feature of linear conjugate gradient method is that the search directions satisfy the following conjugacy condition:
(5)
d
i
T
H
d
j
=
0
,
i
≠
j
.
For nonlinear conjugate gradient methods, (5) does not hold, since the Hessian ∇
2
f
(
x
) changes at different iterations.Some well-known formulae forβ
k are the Fletcher-Reeves (FR), Polak-Ribière (PR), Hestense-Stiefel (HS), and Dai-Yuan (DY), which are given, respectively, by
(6)
β
k
FR
=
∥
g
k
∥
2
∥
g
k
-
1
∥
2
;
β
k
PR
=
g
k
T
(
g
k
-
g
k
-
1
)
∥
g
k
-
1
∥
2
;
β
k
HS
=
g
k
T
(
g
k
-
g
k
-
1
)
(
g
k
-
g
k
-
1
)
T
d
k
-
1
;
β
k
DY
=
∥
g
k
∥
2
(
g
k
-
g
k
-
1
)
T
d
k
-
1
,
where ∥
∥ denotes the Euclidean norm. Their corresponding conjugate methods are abbreviated as FR, PR, HS, and DY methods. In the past two decades, the convergence properties of these methods have been intensively studied by many researchers (e.g., [1–9]). Although all these methods are equivalent in the linear case, namely, when f is a strictly convex quadratic function and α
k are determined by exact line search, their behaviors for general objective functions may be far different.For general functions, Zoutendijk [10] proved the global convergence of FR method with exact line search. (Here and throughout this paper, for global convergence, we mean that the sequence generated by the corresponding methods will either terminate after finite steps or contain a subsequence such that it converges to a stationary point of the objective function from a given initial point.) Although one would be satisfied with its global convergence properties, the FR method performs much worse than the PR and HS methods in real computations. Powell [11] analyzed a major numerical drawback of the FR method; namely, if a small step is generated away from the solution point, the subsequent steps may be also very short. On the other hand, in practical computation, the HS method resembles the PR method, and both methods are generally believed to be the most efficient conjugate gradient methods since these two methods essentially perform a restart if a bad direction occurs. However, Powell [12] constructed a counterexample and showed that the PR and HS methods without restarts can cycle infinitely without approaching the solution. This example suggests that these two methods have a drawback that they are not globally convergent for general functions. Therefore, over the past few years, much effort has been put to find out new formulae for conjugate methods such that they are not only globally convergent for general functions but also have robust and efficient numerical performance.Recently, using a new conjugacy condition, Dai and Liao [13] proposed two new methods. Interestingly, one of their methods is not only globally convergent for general functions but also performs better than HS and PR methods. In this paper, similar to Dai and Liao's approach, we propose a new conjugacy condition. Based on the proposed condition, a new formula for computing β
k is given. And then, we analyze the convergence properties for the given method and also carry the numerical experiment which shows that the given method is robust and efficient.The remainder of this paper is organized as follows. In Section2, after a short description of Dai and Liao's conjugacy condition and related methods, the motivations of this paper are represented. According to the motivations, we propose a new conjugacy condition and related method at the end of Section 2. In Section 3, convergence analysis for the given method is presented. In the last Section we perform the numerical experiments by testing a set of large-scale problems and do some numerical comparisons with some existing methods.


## 2. Motivations, New Conjugacy Condition, and Related Method

### 2.1. Dai-Liao’s Methods

It is well-known that the linear conjugate gradient methods generate a sequence of search directionsd
k such that conjugacy condition (5) holds. Denote y
k
-
1 to be the gradient change, which means that
(7)
y
k
-
1
=
g
k
-
g
k
-
1
.
For a general nonlinear function f, we know by the mean value theorem that there exists some t
∈
(
0,1
) such that
(8)
y
k
-
1
T
d
k
=
α
k
-
1
d
k
T
∇
2
f
(
x
k
-
1
+
t
α
k
-
1
d
k
-
1
)
d
k
-
1
.
Therefore, it is reasonable to replace (5) with the following conjugacy condition:
(9)
y
k
-
1
T
d
k
=
0
.
Recently, extension of (9) has been studied by Dai and Liao in [13]. Their approach is based on the quasi-Newton techniques. Recall that, in the quasi-Newton method, an approximation matrix H
k
-
1 of the Hessian ∇
2
f
(
x
k
-
1
) is updated such that the new matrix H
k satisfies the following quasi-Newton equation:
(10)
H
k
s
k
-
1
=
y
k
-
1
.
The search direction d
k in quasi-Newton method is calculated by
(11)
d
k
=
-
H
k
-
1
g
k
.
Combining these two equations, we obtain
(12)
d
k
T
y
k
-
1
=
d
k
T
(
H
k
s
k
-
1
)
=
-
g
k
T
s
k
-
1
.
The above relation implies that (9) holds if the line search is exact since in this case g
k
T
d
k
-
1
=
0. However, practical numerical algorithms normally adopt inexact line searches instead of exact line search. For this reason, it seems more reasonable to replace conjugacy condition (9) with the condition
(13)
d
k
T
y
k
-
1
=
-
t
g
k
T
s
k
-
1
t
≥
0
,
where t
≥
0 is a scalar.To ensure that the search directiond
k satisfies conjugacy condition (13), one only needs to multiply (3) with y
k
-
1 and use (13), yielding
(14)
β
k
DL
1
=
g
k
T
(
y
k
-
1
-
t
s
k
-
1
)
d
k
-
1
T
y
k
-
1
.
It is obvious that
(15)
β
k
DL
1
=
β
k
HS
-
t
g
k
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
For simplicity, we call the method with (2), (3), and (14) as DL
1 method. Dai and Liao also proved that the conjugate gradient method with DL
1 is globally convergent for uniformly convex functions. For general functions, Powell [12] constructed an example showing that the PR method may cycle without approaching any solution point if the step-length α
k is chosen to be the first local minimizer along d
k. Since the DL
1 method reduces to the PR method in the case that g
k
T
d
k
-
1
=
0 holds, this implies that the method with (14) need not converge for general functions. To get the global convergence, Dai and Liao made a restriction on β
k
DL
1 as follows
(16)
β
k
=
max
⁡
{
β
k
PR
,
0
}
.
Dai and Liao replaced (14) by
(17)
β
k
DL
=
max
⁡
{
g
k
T
y
k
-
1
d
k
-
1
T
y
k
-
1
,
0
}
-
t
g
k
T
s
k
-
1
d
k
-
1
T
y
k
-
1
=
max
⁡
{
β
k
HS
,
0
}
-
t
g
k
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
We also call the method with (2), (3), and (17) as DL method; Dai and Liao show that DL method is globally convergent for general functions under sufficient descent condition (31) and some suitable conditions. Besides, some numerical experiments in [13] indicate the efficiency of this method.Similar to Dai and Liao's approach, Li et al. [14] proposed another conjugate condition and related conjugate gradient methods. And they also proved that the proposed methods are globally convergent under some assumptions.Recently, based on a modified secant condition given by Zhang et al. [15], Yabe and Takano [16] derive an update parameter β
k
YT and show that the YT+ scheme is globally convergent under some conditions:
(18)
β
k
YT
=
g
k
+
1
T
(
z
k
-
t
s
k
)
d
k
T
z
k
,
where
(19)
z
k
=
y
k
+
(
ρ
θ
k
s
k
T
u
k
)
u
k
,
θ
k
=
6
(
f
k
-
f
k
+
1
)
+
3
(
g
k
+
g
k
+
1
)
T
s
k
,
ρ
≥
0 is a constant
(20)
β
k
YT
+
=
max
⁡
{
g
k
+
1
T
z
k
d
k
T
z
k
,
0
}
-
t
g
k
+
1
T
s
k
d
k
T
z
k
.


### 2.2. Motivations

From the above discussions, Dai and Liao's approach is effective; the main reason is that the search directionsd
k generated by DL
1 method or DL method not only contain the gradient information but also contain some Hessian ∇
2
f
(
x
) information. From (15) and (17), β
k
DL
1 and β
k
DL are formed by two parts; the first part is β
k
HS and the second part is -
t
(
g
k
T
s
k
-
1
/
d
k
-
1
T
y
k
-
1
). So we also consider DL
1 and DL methods as the modified forms of the H
S method by adding some information of Hessian ∇
2
f
(
x
) which is contained in the second part.From the structure of (17), we know that the parameter β
k
DL may be negative since the second part -
t
(
g
k
T
s
k
-
1
/
d
k
-
1
T
y
k
-
1
) may be less than zero. In conjugate gradient methods, if the β
k
<
0 and |
β
k
| is large, then the generated directions d
k and d
k
-
1 may tend to be opposite. This type of methods is susceptible to jamming.On the other hand, in conjugate gradient methods, the following strong Wolfe-Powell line search is often used to determine the step sizeα
k:
(21)
f
(
x
k
+
α
k
d
k
)
-
f
(
x
k
)
≤
δ
α
k
g
k
T
d
k
,
(22)
|
g
(
x
k
+
α
k
d
k
)
T
d
k
|
≤
σ
|
g
k
T
d
k
|
,
where 0
<
δ
<
σ
<
1; a typical choice of σ is σ
=
0.1. From the structure of (17), we know that β
k
DL depends on the directional derivative g
k
T
d
k
-
1 which is determined by the line search. For PRP+ algorithm with the strong Wolfe-Powell line search, in order to make sufficient descent condition (31) hold, people often used Lemarechal [17], Fletcher [18], or Moré and Thuente’s [19] strategy to make the directional derivative |
g
k
T
d
k
-
1
| sufficiently small. Under this strategy, the second part of β
k
DL will tend to vanish. This means that the DL method is much line-search-dependent.The above discussions motivate us to propose a modified conjugacy condition and the related conjugate gradient method, which should possess the following properties(1)
Nonnegative propertyβ
k
≥
0.
(2)
The new formula contains not only the gradient information but also some Hessian information.
(3)
The formula should be less line-search-dependent.


### 2.3. The Modified Conjugacy Condition and Related Method

From the above discussion, it seems reasonable to replace conjugacy condition (13) with the following modified conjugacy condition:
(23)
d
k
T
y
k
-
1
=
-
t
g
k
-
1
T
s
k
-
1
,
t
>
0
.To ensure that the search directiond
k satisfies condition (23), one only needs to multiply (3) with y
k
-
1 and use (23), yielding
(24)
β
k
MDL
=
g
k
T
y
k
-
1
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
It is obvious that
(25)
β
k
MDL
=
β
k
HS
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
For simplicity, we call the method with (2), (3), and (25) as MDL method. Similar to Gilbert and Nocedal's [4] approach, we propose the following restricted parameter β
k
MDL
+:
(26)
β
k
MDL
+
=
max
⁡
{
β
k
HS
,
0
}
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
And we call the method with (2), (3), and (26) as MDL
+ method and give the nonlinear conjugate gradient algorithm as below.Algorithm 1 (MDL
+).
Step  1. Given x
1
∈
R
n, ε
≥
0, set d
1
=
-
g
1, k
=
1 if ∥
g
1
∥
≤
ε, then stop.
Step  2. Compute α
k by the strong Wolfe-Powell line search.
Step  3. Let x
k
+
1
=
x
k
+
α
k
d
k, g
k
+
1
=
g
(
x
k
+
1
); if ∥
g
k
+
1
∥
≤
ε, then stop.
Step  4. Compute β
k by (26) and generate d
k
+
1 by (3).
Step  5. Set k
:
=
k
+
1 and go to Step 2.


## 2.1. Dai-Liao’s Methods

It is well-known that the linear conjugate gradient methods generate a sequence of search directionsd
k such that conjugacy condition (5) holds. Denote y
k
-
1 to be the gradient change, which means that
(7)
y
k
-
1
=
g
k
-
g
k
-
1
.
For a general nonlinear function f, we know by the mean value theorem that there exists some t
∈
(
0,1
) such that
(8)
y
k
-
1
T
d
k
=
α
k
-
1
d
k
T
∇
2
f
(
x
k
-
1
+
t
α
k
-
1
d
k
-
1
)
d
k
-
1
.
Therefore, it is reasonable to replace (5) with the following conjugacy condition:
(9)
y
k
-
1
T
d
k
=
0
.
Recently, extension of (9) has been studied by Dai and Liao in [13]. Their approach is based on the quasi-Newton techniques. Recall that, in the quasi-Newton method, an approximation matrix H
k
-
1 of the Hessian ∇
2
f
(
x
k
-
1
) is updated such that the new matrix H
k satisfies the following quasi-Newton equation:
(10)
H
k
s
k
-
1
=
y
k
-
1
.
The search direction d
k in quasi-Newton method is calculated by
(11)
d
k
=
-
H
k
-
1
g
k
.
Combining these two equations, we obtain
(12)
d
k
T
y
k
-
1
=
d
k
T
(
H
k
s
k
-
1
)
=
-
g
k
T
s
k
-
1
.
The above relation implies that (9) holds if the line search is exact since in this case g
k
T
d
k
-
1
=
0. However, practical numerical algorithms normally adopt inexact line searches instead of exact line search. For this reason, it seems more reasonable to replace conjugacy condition (9) with the condition
(13)
d
k
T
y
k
-
1
=
-
t
g
k
T
s
k
-
1
t
≥
0
,
where t
≥
0 is a scalar.To ensure that the search directiond
k satisfies conjugacy condition (13), one only needs to multiply (3) with y
k
-
1 and use (13), yielding
(14)
β
k
DL
1
=
g
k
T
(
y
k
-
1
-
t
s
k
-
1
)
d
k
-
1
T
y
k
-
1
.
It is obvious that
(15)
β
k
DL
1
=
β
k
HS
-
t
g
k
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
For simplicity, we call the method with (2), (3), and (14) as DL
1 method. Dai and Liao also proved that the conjugate gradient method with DL
1 is globally convergent for uniformly convex functions. For general functions, Powell [12] constructed an example showing that the PR method may cycle without approaching any solution point if the step-length α
k is chosen to be the first local minimizer along d
k. Since the DL
1 method reduces to the PR method in the case that g
k
T
d
k
-
1
=
0 holds, this implies that the method with (14) need not converge for general functions. To get the global convergence, Dai and Liao made a restriction on β
k
DL
1 as follows
(16)
β
k
=
max
⁡
{
β
k
PR
,
0
}
.
Dai and Liao replaced (14) by
(17)
β
k
DL
=
max
⁡
{
g
k
T
y
k
-
1
d
k
-
1
T
y
k
-
1
,
0
}
-
t
g
k
T
s
k
-
1
d
k
-
1
T
y
k
-
1
=
max
⁡
{
β
k
HS
,
0
}
-
t
g
k
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
We also call the method with (2), (3), and (17) as DL method; Dai and Liao show that DL method is globally convergent for general functions under sufficient descent condition (31) and some suitable conditions. Besides, some numerical experiments in [13] indicate the efficiency of this method.Similar to Dai and Liao's approach, Li et al. [14] proposed another conjugate condition and related conjugate gradient methods. And they also proved that the proposed methods are globally convergent under some assumptions.Recently, based on a modified secant condition given by Zhang et al. [15], Yabe and Takano [16] derive an update parameter β
k
YT and show that the YT+ scheme is globally convergent under some conditions:
(18)
β
k
YT
=
g
k
+
1
T
(
z
k
-
t
s
k
)
d
k
T
z
k
,
where
(19)
z
k
=
y
k
+
(
ρ
θ
k
s
k
T
u
k
)
u
k
,
θ
k
=
6
(
f
k
-
f
k
+
1
)
+
3
(
g
k
+
g
k
+
1
)
T
s
k
,
ρ
≥
0 is a constant
(20)
β
k
YT
+
=
max
⁡
{
g
k
+
1
T
z
k
d
k
T
z
k
,
0
}
-
t
g
k
+
1
T
s
k
d
k
T
z
k
.


## 2.2. Motivations

From the above discussions, Dai and Liao's approach is effective; the main reason is that the search directionsd
k generated by DL
1 method or DL method not only contain the gradient information but also contain some Hessian ∇
2
f
(
x
) information. From (15) and (17), β
k
DL
1 and β
k
DL are formed by two parts; the first part is β
k
HS and the second part is -
t
(
g
k
T
s
k
-
1
/
d
k
-
1
T
y
k
-
1
). So we also consider DL
1 and DL methods as the modified forms of the H
S method by adding some information of Hessian ∇
2
f
(
x
) which is contained in the second part.From the structure of (17), we know that the parameter β
k
DL may be negative since the second part -
t
(
g
k
T
s
k
-
1
/
d
k
-
1
T
y
k
-
1
) may be less than zero. In conjugate gradient methods, if the β
k
<
0 and |
β
k
| is large, then the generated directions d
k and d
k
-
1 may tend to be opposite. This type of methods is susceptible to jamming.On the other hand, in conjugate gradient methods, the following strong Wolfe-Powell line search is often used to determine the step sizeα
k:
(21)
f
(
x
k
+
α
k
d
k
)
-
f
(
x
k
)
≤
δ
α
k
g
k
T
d
k
,
(22)
|
g
(
x
k
+
α
k
d
k
)
T
d
k
|
≤
σ
|
g
k
T
d
k
|
,
where 0
<
δ
<
σ
<
1; a typical choice of σ is σ
=
0.1. From the structure of (17), we know that β
k
DL depends on the directional derivative g
k
T
d
k
-
1 which is determined by the line search. For PRP+ algorithm with the strong Wolfe-Powell line search, in order to make sufficient descent condition (31) hold, people often used Lemarechal [17], Fletcher [18], or Moré and Thuente’s [19] strategy to make the directional derivative |
g
k
T
d
k
-
1
| sufficiently small. Under this strategy, the second part of β
k
DL will tend to vanish. This means that the DL method is much line-search-dependent.The above discussions motivate us to propose a modified conjugacy condition and the related conjugate gradient method, which should possess the following properties(1)
Nonnegative propertyβ
k
≥
0.
(2)
The new formula contains not only the gradient information but also some Hessian information.
(3)
The formula should be less line-search-dependent.


## 2.3. The Modified Conjugacy Condition and Related Method

From the above discussion, it seems reasonable to replace conjugacy condition (13) with the following modified conjugacy condition:
(23)
d
k
T
y
k
-
1
=
-
t
g
k
-
1
T
s
k
-
1
,
t
>
0
.To ensure that the search directiond
k satisfies condition (23), one only needs to multiply (3) with y
k
-
1 and use (23), yielding
(24)
β
k
MDL
=
g
k
T
y
k
-
1
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
It is obvious that
(25)
β
k
MDL
=
β
k
HS
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
For simplicity, we call the method with (2), (3), and (25) as MDL method. Similar to Gilbert and Nocedal's [4] approach, we propose the following restricted parameter β
k
MDL
+:
(26)
β
k
MDL
+
=
max
⁡
{
β
k
HS
,
0
}
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
.
And we call the method with (2), (3), and (26) as MDL
+ method and give the nonlinear conjugate gradient algorithm as below.Algorithm 1 (MDL
+).
Step  1. Given x
1
∈
R
n, ε
≥
0, set d
1
=
-
g
1, k
=
1 if ∥
g
1
∥
≤
ε, then stop.
Step  2. Compute α
k by the strong Wolfe-Powell line search.
Step  3. Let x
k
+
1
=
x
k
+
α
k
d
k, g
k
+
1
=
g
(
x
k
+
1
); if ∥
g
k
+
1
∥
≤
ε, then stop.
Step  4. Compute β
k by (26) and generate d
k
+
1 by (3).
Step  5. Set k
:
=
k
+
1 and go to Step 2.


## 3. Convergence Analysis

In the convergence analysis of conjugate gradient methods, we often make the following basic assumptions on the objective functions.Assumption A.
(i) The level setΓ
=
{
x
∈
R
n
:
f
(
x
)
≤
f
(
x
1
)
} is bounded; namely, there exists a constant B
>
0 such that
(27)
∥
x
∥
≤
B
,
∀
x
∈
Γ
.
(ii) In some neighborhoodN of Γ, f is continuously differentiable, and its gradient is Lipschitz continuous; namely, there exists a constant L
>
0 such that
(28)
∥
g
(
x
)
-
g
(
y
)
∥
≤
L
∥
x
-
y
∥
,
∀
x
,
y
∈
N
.Under the above assumptions off, there exists a constant γ
¯
≥
0 such that
(29)
∥
∇
f
(
x
)
∥
≤
γ
¯
,
∀
x
∈
Γ
.
We say the descent condition holds if for each search direction d
k,
(30)
g
k
T
d
k
<
0
∀
k
≥
1
.
In addition, we say the sufficient descent condition holds if there exists a constant c
>
0 such that, for each search direction d
k, we have
(31)
g
k
T
d
k
≤
-
c
∥
g
k
∥
2
∀
k
≥
1
.Under Assumption A, based on the Zoutendijk condition in [10], for any conjugate gradient method with the strong Wolfe-Powell line search, Dai et al. in [20] proved the following general result.Lemma 2.
Suppose that Assumption A holds. Consider any conjugate gradient method in the form (2)-(3), where d
k is a descent direction and α
k is obtained by the strong Wolfe-Powell line search. If
(32)
∑
k
≥
1
‍
1
∥
d
k
∥
2
=
∞
,
we have that
(33)
lim
⁡
inf
⁡
k
→
∞
∥
g
k
∥
=
0
.If the objective functions are uniformly convex, we can prove that the norm ofd
k generated by Algorithm 1 (MDL+) is bounded above. Thus by Lemma 2 we immediately have the following result.Theorem 3.
Suppose that Assumption A holds. ConsiderMDL+ method, where d
k is a descent direction and α
k is obtained by the strong Wolfe-Powell line search. If the objective functions are uniformly convex, namely, there exists a constant μ
>
0 such that
(34)
(
∇
f
(
x
)
-
∇
f
(
y
)
)
T
(
x
-
y
)
≥
μ
∥
x
-
y
∥
2
,
∀
x
,
y
∈
Γ
,
we have that
(35)
lim
⁡
k
→
∞
∥
g
k
∥
=
0
.Proof.
It follows from (34) that
(36)
d
k
-
1
T
y
k
-
1
≥
μ
α
k
-
1
∥
d
k
-
1
∥
2
.
By (3), (24), (28), (29), and (36), we have that
(37)
∥
d
k
∥
≤
∥
g
k
∥
+
|
β
k
MDL
|
∥
d
k
-
1
∥
≤
∥
g
k
∥
+
|
g
k
T
y
k
-
1
-
t
g
k
-
1
T
s
k
-
1
μ
α
k
-
1
∥
d
k
-
1
∥
2
|
∥
d
k
-
1
∥
≤
∥
g
k
∥
+
∥
g
k
∥
∥
g
k
-
g
k
-
1
∥
+
t
|
g
k
-
1
T
s
k
-
1
|
μ
α
k
-
1
∥
d
k
-
1
∥
2
∥
d
k
-
1
∥
≤
∥
g
k
∥
+
∥
g
k
∥
L
∥
s
k
-
1
∥
+
t
∥
g
k
-
1
∥
∥
s
k
-
1
∥
μ
α
k
-
1
∥
d
k
-
1
∥
2
∥
d
k
-
1
∥
≤
γ
-
+
γ
-
L
∥
s
k
-
1
∥
+
t
γ
-
∥
s
k
-
1
∥
μ
α
k
-
1
∥
d
k
-
1
∥
2
∥
d
k
-
1
∥
=
γ
-
μ
-
1
(
μ
+
L
+
t
)
,
which implies the truth of (32). Therefore, by Lemma 2, we have (33), which is equivalent to (35) for uniformly convex functions. The proof is completed.For the method withβ
k
MDL
+, if descent condition (30) holds and α
k satisfies Wolfe-Powell condition (22), then the parameter β
k
MDL
+ is nonnegative.Lemma 4.
In any conjugate gradient method, if the parameterβ
k is computed by (26) and d
k is a descent direction, when α
k is determined by strong Wolfe-Powell line search conditions (21) and (22), then
(38)
β
k
MDL+
≥
0
.Proof.
By SWP condition (22), we have d
k
-
1
T
y
k
-
1
≥
σ
g
k
-
1
T
d
k
-
1
-
g
k
-
1
T
d
k
-
1
≥
0 and g
k
-
1
T
s
k
-
1
<
0. So we have
(39)
β
k
MDL
+
=
max
⁡
{
β
k
HS
,
0
}
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
,
≥
0
The proof is completed.Theorem 5.
Suppose that Assumption A holds. ConsiderMDL+ method, where d
k is a sufficient descent direction and α
k is obtained by strong Wolfe-Powell line search. If there exists a constant γ
>
0 such that
(40)
∥
g
k
∥
≥
γ
,
∀
k
≥
1
,
then d
k
≠
0 and
(41)
∑
k
≥
2
‍
∥
u
k
-
u
k
-
1
∥
2
<
∞
,
where u
k
=
d
k
/
∥
d
k
∥.Proof.
First, note thatd
k
≠
0; otherwise (31) is false. Therefore u
k is well defined. In addition, by relation (40) and Lemma 2, we have that
(42)
∑
k
≥
1
‍
1
∥
d
k
∥
2
<
∞
.
Now, we divide formula β
k
MDL
+ into two parts as follows:
(43)
β
k
1
=
max
⁡
{
β
k
HS
,
0
}
,
β
k
2
=
-
t
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
,
and define
(44)
r
k
:
=
ϑ
k
∥
d
k
∥
,
δ
k
:
=
β
k
1
∥
d
k
-
1
∥
∥
d
k
∥
,
where ϑ
k
=
-
g
k
+
β
k
2
d
k
-
1.
Then by (3) we have, for all k
≥
2,
(45)
u
k
=
r
k
+
δ
k
u
k
-
1
.
Using the identity ∥
u
k
∥
=
∥
u
k
-
1
∥
=
1 and (45), we can obtain
(46)
∥
u
k
-
δ
k
u
k
-
1
∥
2
=
1
+
δ
k
2
-
2
δ
k
u
k
T
u
k
-
1
,
(47)
∥
δ
k
u
k
-
u
k
-
1
∥
2
=
1
+
δ
k
2
-
2
δ
k
u
k
T
u
k
-
1
,
(48)
∥
r
k
∥
=
∥
u
k
-
δ
k
u
k
-
1
∥
=
∥
δ
k
u
k
-
u
k
-
1
∥
.
Using the condition δ
k
=
max
⁡
{
β
k
HS
,
0
}
(
∥
d
k
-
1
∥
/
∥
d
k
∥
)
≥
0, the triangle inequality, and (48), we obtain
(49)
∥
u
k
-
u
k
-
1
∥
≤
∥
(
1
+
δ
k
)
u
k
-
(
1
+
δ
k
)
u
k
-
1
∥
≤
∥
u
k
-
δ
k
u
k
-
1
∥
+
∥
δ
k
u
k
-
u
k
-
1
∥
=
2
∥
r
k
∥
.
On the other hand, line search condition (22) gives
(50)
y
k
-
1
T
d
k
-
1
≥
(
σ
-
1
)
g
k
-
1
T
d
k
-
1
>
0
.
Equations (22), (31), and (50) imply that
(51)
|
g
k
-
1
T
d
k
-
1
d
k
-
1
T
y
k
-
1
|
≤
1
1
-
σ
.
It follows from the definition of ϑ
k, (27), (29), and (51) that
(52)
∥
ϑ
k
∥
≤
∥
g
k
∥
+
t
|
g
k
-
1
T
s
k
-
1
d
k
-
1
T
y
k
-
1
|
∥
d
k
-
1
∥
=
∥
g
k
∥
+
t
|
g
k
-
1
T
d
k
-
1
d
k
-
1
T
y
k
-
1
|
∥
s
k
-
1
∥
≤
γ
¯
+
t
1
1
-
σ
2
B
.
So we have
(53)
∑
‍
∥
u
k
-
u
k
-
1
∥
2
≤
4
∑
‍
∥
r
k
∥
2
≤
4
∑
‍
ϑ
k
2
∥
d
k
∥
2
≤
4
(
γ
¯
+
t
1
1
-
σ
2
B
)
2
∑
‍
1
∥
d
k
∥
2
<
∞
and the proof is completed.Gilbert and Nocedal [4] introduced property (*) which is very important for the convergence analysis of the conjugate gradient methods. In fact, with Assumption A, (40), and (50), if (31) holds with some constant c
>
0, the method with β
k
MDL
+ possesses such property (*).Property (
*).
Consider a method of forms (2) and (3). Suppose that
(54)
0
<
γ
≤
∥
g
k
∥
≤
γ
¯
∀
k
≥
1
.
We say that the method has property (*), if, for all k, there exist constants b
>
1, λ
>
0 such that |
β
k
|
≤
b, and if ∥
s
k
-
1
∥
≤
λ, we have |
β
k
|
≤
1
/
2
b.
In fact, by (31), (40), and (50), we have
(55)
d
k
-
1
T
y
k
-
1
≥
(
σ
-
1
)
g
k
-
1
T
d
k
-
1
≥
c
(
1
-
σ
)
∥
g
k
-
1
∥
2
≥
(
1
-
σ
)
c
γ
2
.
Combining (55) with (27) and (28) and (29), we obtain
(56)
|
β
k
MDL
+
|
≤
γ
¯
L
∥
s
k
-
1
∥
+
t
γ
¯
∥
s
k
-
1
∥
(
1
-
σ
)
c
γ
2
≤
2
B
(
L
+
t
)
γ
¯
(
1
-
σ
)
c
γ
2
=
:
b
.
Note that b can be defined such that b
>
1. Therefore we can say that b
>
1. As a result, we define
(57)
λ
:
=
(
1
-
σ
)
c
γ
2
2
b
(
L
+
t
)
γ
¯
,
and we get from the first inequality in (56) that if ∥
s
k
-
1
∥
≤
λ, then
(58)
|
β
k
MDL
+
|
≤
γ
¯
(
L
+
t
)
λ
(
1
-
σ
)
c
γ
2
=
γ
¯
(
L
+
t
)
(
1
-
σ
)
c
γ
2
(
1
-
σ
)
c
γ
2
2
b
(
L
+
t
)
γ
¯
=
1
2
b
.
LetN
* denote the set of positive integers. For λ
>
0 and a positive integer Δ, denote
(59)
K
k
,
Δ
λ
:
=
{
i
∈
N
*
:
k
≤
i
≤
k
+
Δ
-
1
,
∥
s
k
-
1
∥
>
λ
}
.
Let |
K
k
,
Δ
λ
| denote the number of elements in K
k
,
Δ
λ. From the above property (*), we can prove the following theorem.Theorem 6.
Suppose that Assumption A holds. ConsiderMDL+ method, where d
k satisfies condition (31) with c
>
0, and α
k is obtained by the strong Wolfe-Powell line search. Then if (40) holds, there exists λ
>
0 such that, for any Δ
∈
N
* and any index k
0, there is an index k
≥
k
0 such that
(60)
|
K
k
,
Δ
λ
|
>
Δ
2
.The proof of this theorem is similar to the proof of Lemma 3.5 in [13]. So, we omit the proof.According to the above lemmas and theorems, we can prove the following convergence result for the MDL+ method.Theorem 7.
Suppose that Assumption A holds. ConsiderMDL+ method, where d
k satisfies condition (31) with c
>
0, and α
k is obtained by the strong Wolfe-Powell line search. Then we have liminf
⁡
k
→
∞
∥
g
k
∥
=
0.Proof.
We proceed by contradiction. Ifliminf
⁡
k
→
∞
∥
g
k
∥
>
0, then (40) must hold. Then the conditions of Theorem 6 hold. Defining u
i
=
d
i
/
∥
d
i
∥, we have, for any indices l, k, with l
≥
k,
(61)
x
l
-
x
k
-
1
=
∑
i
=
k
l
‍
x
i
-
x
i
-
1
=
∑
i
=
k
l
‍
α
i
-
1
d
i
-
1
=
∑
i
=
k
l
‍
u
i
-
1
∥
s
i
-
1
∥
=
∑
i
=
k
l
‍
∥
s
i
-
1
∥
u
k
-
1
+
∑
i
=
k
l
‍
∥
s
i
-
1
∥
(
u
i
-
1
-
u
k
-
1
)
.
Consider ∥
u
i
∥
=
1; (27) and (61) give that
(62)
∑
i
=
k
l
‍
∥
s
i
-
1
∥
≤
∥
x
l
-
x
k
-
1
∥
+
∑
i
=
k
l
‍
∥
s
i
-
1
∥
∥
u
i
-
1
-
u
k
-
1
∥
≤
2
B
+
∑
i
=
k
l
‍
∥
s
i
-
1
∥
∥
u
i
-
1
-
u
k
-
1
∥
.
Letλ
>
0 be given by Theorem 6 and define Δ
:
=
⌈
8
B
/
λ
⌉ to be the smallest integer not less than 8
B
/
λ. By Theorem 6, we can find an index k
0
≥
1 such that
(63)
∑
i
≥
k
0
‍
∥
u
i
-
1
-
u
k
-
1
∥
2
≤
1
4
Δ
.
With this Δ and k
0, Theorem 6 gives an index k
≥
k
0 such that
(64)
|
K
k
,
Δ
λ
|
>
Δ
2
.
For any index i
∈
[
k
,
k
+
Δ
-
1
], by Cauchy-Schwarz, the geometric inequalities, and (63),
(65)
∥
u
i
-
u
k
-
1
∥
≤
∑
j
=
k
i
‍
∥
u
j
-
u
j
-
1
∥
≤
(
i
-
k
+
1
)
1
/
2
(
∑
j
=
k
i
‍
∥
u
j
-
u
j
-
1
∥
2
)
1
/
2
≤
Δ
1
/
2
(
1
4
Δ
)
1
/
2
=
1
2
.
From relations (64) and (65), by taking l
=
k
+
Δ
-
1 in (62), we get
(66)
2
B
≥
1
2
∑
i
=
k
k
+
Δ
-
1
‍
∥
s
i
-
1
∥
>
λ
2
|
K
k
,
Δ
λ
|
>
λ
Δ
4
.
Thus Δ
<
8
B
/
λ, which contradicts the definition of Δ. The proof is completed.


## 4. Numerical Results

In this section, we report the performance of Algorithm1 (MDL+) on a set of test problems. The codes were written in Fortran 77 and in double precision arithmetic. All the tests were performed on the same PC (Intel Core i3 CPU M370 @ 2.4 GH, 2 GB RAM). The experiments were performed on a set of 73 nonlinear unconstrained problems collected by Neculai Andrei. Some of the problems are from CUTE [21] library. For each test problem, we have performed 10 numerical experiments with a number of variables n
=
1000, 2000,…, 10000.In order to assess the reliability of the MDL+ algorithm, we also tested this method against the DL method and HS method using the same problems. All these algorithms terminate when∥
g
k
∥
≤
1
0
-
5. We also force the routines to stop if the iterations exceed 1000 or the number of function evaluations reaches 2000. The parameters ∆ and σ in Wolfe-Powell line search conditions (21) and (22) are set to be 10
-
4 and 10
-
1 respectively. For DL method, t
=
0.1, which is the same with [13]. We also test MDL+ algorithm with different parameters t to see that t
=
0.05 is the best choice.The comparing data contain the iterations, function, and gradient evaluations and CPU time. To approximatively assess the performance of MDL+, HS, and DL methods, we use the profile of Dolan and Moré [22] as an evaluated tool.Dolan and Moré [22] gave a new tool to analyze the efficiency of algorithms. They introduced the notion of a performance profile as a means to evaluate and compare the performance of the set of solvers S on a test set P. Assuming that there exist n
s solvers and n
p problems, for each problem p and solver s, they defined t
p
,
s
=
computing cost (iterations or function and gradient evaluations or CPU time) required to solve problem p by solver s.Requiring a baseline for comparisons, they compared the performance on problemp by solver s with the best performance by any solver on this problem; that is, using the performance ratio
(67)
r
p
,
s
=
t
p
,
s
min
⁡
{
t
p
,
s
:
s
∈
S
}
.Suppose that a parameterM
≥
r
p
,
s for all p
,
s. Set r
p
,
s
=
M if and only if solver s does not solve problem p. Then they defined
(68)
ρ
s
(
τ
)
=
1
n
p
size
{
p
∈
P
:
r
p
,
s
≤
τ
}
.
Thus ρ
s
(
τ
) is the probability for solver s that a performance ratio r
p
,
s is within factor τ
≥
1 of the best possible ratio. Then function ρ
s is the distribution function for the performance ratio. The performance profile ρ
s is a nondecreasing, piecewise constant function. That is, for subset of the methods being analyzed, we plot the fraction P of the problems for which any given method is within a factor τ of the best.For the testing problems, if all three methods can not terminate successfully, then we got rid of it. In case one method fails, but there is another method that terminates successfully, then the performance ratio of the failed method is set to beM (M is the maxima of the performance ratios). The performance profiles based on iterations, function and gradient evaluations, and CPU time of the three methods are plotted in Figures 1, 2, and 3, respectively.Figure 1
Iterations.Figure 2
Function and gradient evaluations.Figure 3
CPU time.From Figure1, which plots the performance profile based on iterations, when τ
=
1, the HS method performs better than MDL+ and DL methods. With the increasing of τ, when τ
≥
1.3, the profile of MDL+ method outperforms HS and DL methods. This means that, from the iteration points of view, for a subset of problems, HS method is better than MDL+ and DL methods. But, for all the testing problems, DML+ method is much robuster than HS and DL methods.From Figure2, which plots the performance profile based on function and gradient evaluations, it is easy to see that, for all τ
≥
1, MDL+ method performs much better than HS and DL methods. It is an interesting phenomenon, since, when τ
≤
1.3, the profiles of HS based on iterations outperform DML+ method. This means that, during process of iteration, the required function and gradient evaluations of MDL+ method are much less than HS and DL methods. Form this point of view, the CPU time consumed by MDL+ method should be much less than HS and DL methods, since the CPU time is mainly dependent on function and gradient evaluations. Figure 3 validates that the CPU time consumed by MDL+ method is much less than HS and DL methods.



---

*Source: 710376-2014-03-18.xml*