# Sufficient Descent Conjugate Gradient Methods for Solving Convex Constrained Nonlinear Monotone Equations

Authors: San-Yang Liu; Yuan-Yuan Huang; Hong-Wei Jiao
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Two unified frameworks of some sufficient descent conjugate gradient methods are considered. Combined with the hyperplane projection method of Solodov and Svaiter, they are extended to solve convex constrained nonlinear monotone equations. Their global convergence is proven under some mild conditions. Numerical results illustrate that these methods are efficient and can be applied to solve large-scale nonsmooth equations.


---

## Body

## 1. Introduction

Consider the constrained monotone equations(1)
F
(
x
)
=
0
,
x
∈
Ω
,
where F
:
R
n
→
R
n is continuous and satisfies the following monotonicity:
(2)
(
F
(
x
)
-
F
(
y
)
)
T
(
x
-
y
)
≥
0
,
∀
x
,
y
∈
Ω
,
and Ω
⊂
R
n is a nonempty closed convex set. Under these conditions, the solution set X
* of problem (1) is convex [1]. This problem has many applications, such as the power flow equation [2, 3] and some variational inequality problems which can be converted into (1) by means of fixed point maps or normal maps if the underlying function satisfies some coercive conditions [4].In recent years, the study of the iterative methods to solve problem (1) with Ω
=
R
n has received much attention. The pioneer work was introduced by Solodov and Svaiter in [5], where the proposed method was called inexact Newton method which combines elements of Newton method, proximal point method, and projection strategy and required that F is differentiable. Its convergence was proven without any regularity assumptions. And a further study about its convergence properties was given by Zhou and Toh [6]. Then utilizing the projection strategy in [5], Zhou and Li extended the BFGS methods [7] and the limited memory BFGS methods [8] to solve problem (1) with Ω
=
R
n. A significant improvement is that these methods converge globally without requiring the differentiability of F.Conjugate gradient methods are another class of numerical methods [9–15] after spectral gradient methods [16–18] extended to solve problem (1), and the study of this aspect is just catching up. As is well known, conjugate gradient methods are very efficient to solve large-scale unconstrained nonlinear optimization problem
(3)
min
f
(
x
)
,
x
∈
R
n
,
where f is smooth, due to their simple iterations and their low memory requirements. In [19], they were divided into three categories, that is, early conjugate gradient methods, descent conjugate gradient methods, and sufficient descent conjugate gradient methods. Early conjugate gradient methods rarely ensure a (sufficient) descent condition
(4)
g
k
T
d
k
≤
-
c
∥
g
k
∥
2
,
∀
k
≥
0
,
c
>
0
,
where g
k
=
g
(
x
k
) is the gradient of f at x
k (the kth iteration) and d
k is a search direction, while the later two categories always satisfy the descent property. One well-known sufficient descent conjugate gradient method, namely, CG_DESCENT, was presented by Hager and Zhang [20, 21] and satisfied the sufficient descent condition (4) with c
=
7
/
8. Inspired by Hager and Zhang’s work, a unified framework of some sufficient descent conjugate gradient methods was presented in [19, 22]. And by the use of Gram-Schmidt orthogonalization, the other unified framework of some sufficient descent conjugate gradient methods was presented in [23].Although conjugate gradient methods have been investigated extensively for solving unconstrained optimization problems, the study of them to solve nonlinear monotone equations is relatively rare. For the unconstrained case of monotone equations, Cheng [10] first introduced a PRP type method which is a combination of the well-known PRP conjugate gradient method [24, 25] and the hyperplane projection method [5]. Then some derivative-free methods were presented [11–13] which also belong to the conjugate gradient scheme. More recently, Xiao and Zhu [9] presented a modified version of the CG_DESCENT method to solve the constrained nonlinear monotone equations. And under some mild conditions, they proved that their proposed method is globally convergent. We have mentioned that there are two unified frameworks of some sufficient descent conjugate gradient methods, and the CG_DESCENT method belongs to one unified framework. Since the CG_DESCENT method can be used to solve the constrained monotone equations, then, it is natural for us to think about the two unified frameworks. So, in this paper, we extend the conjugate gradient methods who belong to the two unified frameworks to solve the constrained monotone equations and do some numerical experiments to test their efficiency.The rest of this paper is organized as follows. In Section2, the motivation to investigate two unified frameworks of some sufficient descent conjugate gradient methods is given. Then these methods are developed to solve problem (1) and are described by a model algorithm. In Section 3, we prove the global convergence of the model algorithm under some mild conditions. In Section 4, we give several specific versions of the model algorithm, test them over some test problems, and compare their numerical performance with that of the conjugate gradient method proposed in [9]. Finally, some conclusions are given in Section 5.


## 2. Motivation and Algorithms

In this section, we simply describe the hyperplane projection method of Solodov and Svaiter and introduce two classes of sufficient descent conjugate gradient methods for solving large-scale unconstrained optimization problems. Combined with the hyperplane projection method, we extend sufficient descent conjugate gradient methods to solve large-scale constrained nonlinear equations (1).For convenience, we first give the definition of projection operatorP
Ω
(
·
) which is defined as a mapping from R
n to its a nonempty closed convex subset Ω:
(5)
P
Ω
(
x
)
=
arg min
{
∥
y
-
x
∥
∣
y
∈
Ω
}
,
∀
x
∈
R
n
.
And its two fundamental properties are
(6)
∥
P
Ω
(
x
)
-
P
Ω
(
y
)
∥
≤
∥
x
-
y
∥
,
∀
x
,
y
∈
R
n
,
(7)
(
x
-
P
Ω
(
x
)
)
T
(
y
-
P
Ω
(
x
)
)
≤
0
,
∀
x
∈
R
n
,
y
∈
Ω
.Now, we recall the hyperplane projection method in [5] for the unconstrained case of problem (1). Let x
k (k
≥
0) be the current iteration and z
k
=
x
k
+
α
k
d
k, where α
k is a step length obtained by means of a one-dimensional line search and d
k is a search direction. If x
k is not a solution and satisfies
(8)
(
x
k
-
z
k
)
T
F
(
z
k
)
>
0
,
then the hyperplane
(9)
H
k
=
{
x
∈
R
n
∣
(
x
-
z
k
)
T
F
(
z
k
)
=
0
}
strictly separates the current iteration x
k from the solution set of problem (1). By the property (7) of the projection operator, it is not difficult to verify that
(10)
P
H
k
(
x
k
)
=
x
k
-
(
x
k
-
z
k
)
T
F
(
z
k
)
∥
F
(
z
k
)
∥
2
F
(
z
k
)
is closer to the solution set than the iteration x
k. Then the next iteration is generated by x
k
+
1
=
P
H
k
(
x
k
).We consider the iterative scheme of conjugate gradient methods for solving the unconstrained optimization problem (3). For any given starting point x
0
∈
R
n, a sequence {
x
k
} is generated by the following recursive relation:
(11)
x
k
+
1
=
x
k
+
α
k
d
k
,
where α
k is a steplength and d
k is a descent direction. One way to generate d
k is
(12)
d
k
=
{
-
g
k
,
if
k
=
0
,
-
g
k
+
β
k
d
k
-
1
,
if
k
≥
1
,
where g
k
=
g
(
x
k
) and β
k is a scalar. The formula of β
k in the CG_DESCENT method is defined as
(13)
β
k
H
Z
=
g
k
T
y
k
-
1
d
k
-
1
T
y
k
-
1
-
2
∥
y
k
-
1
∥
2
(
d
k
-
1
T
y
k
-
1
)
2
g
k
T
d
k
-
1
,
where y
k
-
1
=
g
k
-
g
k
-
1. Then the direction d
k from (12) satisfies the sufficient descent condition (4) with c
=
7
/
8. For more efficient versions of the CG_DESCENT method, please refer to [26, 27].In [19, 22], a generalization of (13) was given by
(14)
β
k
G
=
g
k
T
b
k
a
k
-
C
∥
b
k
∥
2
a
k
2
g
k
T
d
k
-
1
,
where a
k
∈
R, b
k
∈
R
n, and C
>
1
/
4. Obviously, β
k
H
Z is a special case of (14) with a
k
=
d
k
-
1
T
y
k
-
1, b
k
=
y
k
-
1, and C
=
2. More recently, Xiao and Zhu [9] presented a modified version of the CG_DESCENT method to solve the constrained problem (1). This work inspires us to extend the general case (14) to solve problem (1). So, we define
(15)
d
k
=
{
-
F
k
,
if
k
=
0
,
-
F
k
+
β
k
d
k
-
1
,
if
k
≥
1
,
where F
k
=
F
(
x
k
) and the scalar β
k is defined as
(16)
β
k
=
F
k
T
b
k
a
k
-
θ
k
∥
b
k
∥
2
a
k
2
F
k
T
d
k
-
1
with ϵ
∥
d
k
-
1
∥
≤
a
k
∈
R (ϵ
>
0), θ
k
>
1
/
2, and b
k
∈
R
n. Moreover, the formula of β
k proposed by Xiao and Zhu [9] corresponds to (16) with θ
k
=
2, a
k
=
d
k
-
1
T
y
k
-
1
*, and b
k
=
y
k
-
1
*, where y
k
*
=
y
k
+
λ
k
α
k
∥
F
k
∥
d
k, y
k
=
F
k
+
1
-
F
k, and λ
k
=
1
+
∥
F
k
∥
-
1
max
{
0
,
-
(
α
k
d
k
T
y
k
*
/
∥
α
k
d
k
∥
2
)
}.The other general way of producing sufficient descent conjugate gradient methods for solving the unconstrained optimization (3) was provided in [23]. By using the Gram-Schmidt orthogonalization, the search direction d
k is generated by
(17)
d
k
=
{
-
g
k
,
if
k
=
0
,
-
(
1
+
β
k
g
k
T
d
k
-
1
∥
g
k
∥
2
)
g
k
+
β
k
d
k
-
1
,
if
k
≥
1
,
where β
k is a scalar, and its definition could be the same as that in (12). Obviously, it always satisfies g
k
T
d
k
=
-
∥
g
k
∥
2. In this paper, we will prove that the class of sufficient descent conjugate gradient methods can also be extended to solve problem (1) with the corresponding search direction d
k defined as
(18)
d
k
=
{
-
F
k
,
if
k
=
0
,
-
(
1
+
β
k
F
k
T
d
k
-
1
∥
F
k
∥
2
)
F
k
+
β
k
d
k
-
1
,
if
k
≥
1
,
where the formula of β
k could be (16).Now we introduce the two unified frameworks of some sufficient descent conjugate gradient methods to solve problem (1) by adopting the projection strategy in [5]. We state the steps of the model algorithm as follows.Algorithm 1.
Step
0. Choose an initial point x
0
∈
Ω, ρ
>
0, σ
∈
(
0,1
), t
∈
(
0,1
) and ϵ
>
0. Set k
∶
=
0.Step
1. If ∥
F
(
x
k
)
∥
≤
ϵ, stop. Otherwise, generate d
k by certain iteration formula which satisfies sufficient descent condition.Step
2. Let α
k be the largest α
∈
{
ρ
t
j
∣
j
=
0,1
,
2
,
…
} such that(19)
-
F
(
x
k
+
α
d
k
)
T
d
k
≥
σ
α
∥
F
(
x
k
+
α
d
k
)
∥
∥
d
k
∥
2
,
and then compute z
k
=
x
k
+
α
k
d
k.Step
3. Compute the new iterate x
k
+
1 by
(20)
x
k
+
1
=
P
Ω
(
x
k
-
(
x
k
-
z
k
)
T
F
(
z
k
)
∥
F
(
z
k
)
∥
2
F
(
z
k
)
)
.
Set k
:
=
k
+
1. Go to Step 1.(i) If the search directiond
k in Step 1 is generated by the formula (15), we name the algorithm as Algorithm 1(a). And if the search direction d
k in Step 1 is generated by the formula (18), we name the algorithm as Algorithm 1(b).


## 3. Convergence Analysis

In this section, we analyze the convergence properties of Algorithm1. We first make the following assumptions.Assumption 2.
The mappingF is L-Lipschitz continuous on the nonempty closed convex set Ω; that is, there exists a constant L
>
0 such that
(21)
∥
F
(
x
)
-
F
(
y
)
∥
≤
L
∥
x
-
y
∥
,
∀
x
,
y
∈
Ω
.Assumption 3.
The solution setX
* of problem (1) is nonempty.Assumption 4.
The parameterβ
k satisfies inequality
(22)
|
β
k
|
≤
γ
∥
F
k
∥
∥
d
k
-
1
∥
,
where γ is a positive number.Assumption4 is not difficult to satisfy. Taking the parameter β
k in (15) as an example, if there exists a large number M
<
∞ such that ∥
b
k
∥
≤
M for all k, then it satisfies the inequality (22). In fact,
(23)
|
β
k
|
=
|
F
k
T
b
k
a
k
-
θ
k
∥
b
k
∥
2
a
k
2
F
k
T
d
k
-
1
|
≤
|
F
k
T
b
k
a
k
|
+
|
θ
k
∥
b
k
∥
2
a
k
2
F
k
T
d
k
-
1
|
≤
∥
F
k
∥
∥
b
k
∥
|
a
k
|
+
θ
k
∥
b
k
∥
2
a
k
2
∥
F
k
∥
∥
d
k
-
1
∥
≤
∥
F
k
∥
M
ϵ
∥
d
k
-
1
∥
+
θ
k
M
2
ϵ
2
∥
d
k
-
1
∥
2
∥
F
k
∥
∥
d
k
-
1
∥
=
(
M
ϵ
+
θ
k
M
2
ϵ
2
)
∥
F
k
∥
∥
d
k
-
1
∥
.The following two lemmas show that the search directiond
k, no matter from (15) or (18), satisfies the sufficient descent condition.Lemma 5.
Ifa
k
≠
0, θ
k
>
1
/
2, and d
k is generated by (15), then, for every k
≥
0,
(24)
F
k
T
d
k
≤
-
(
1
-
1
4
θ
k
)
∥
F
k
∥
2
.Proof.
Sinced
0
=
-
F
0, then F
0
T
d
0
=
-
∥
F
0
∥
2 which satisfies (24). For every k
≥
1, multiplying (15) by F
k, we have
(25)
F
k
T
d
k
=
-
∥
F
k
∥
2
+
β
k
F
k
T
d
k
-
1
=
-
∥
F
k
∥
2
+
F
k
T
b
k
a
k
F
k
T
d
k
-
1
-
θ
k
∥
b
k
∥
2
a
k
2
(
F
k
T
d
k
-
1
)
2
=
-
∥
F
k
∥
2
a
k
2
+
a
k
(
F
k
T
b
k
)
(
F
k
T
d
k
-
1
)
-
θ
k
∥
b
k
∥
2
(
F
k
T
d
k
-
1
)
2
a
k
2
.
Denote u
k
=
a
k
F
k
/
2
θ
k and v
k
=
2
θ
k
(
F
k
T
d
k
-
1
)
b
k. By applying the inequality u
k
T
v
k
≤
1
/
2
(
∥
u
k
∥
2
+
∥
v
k
∥
2
) to the second term in (25), we obtain (24).The lemma above is similar to Theorem  1.1 in [20]. And from this lemma, we can see that the descent property of d
k from (15) is independent of any line search and choices of the parameters a
k and b
k. While different choices of the parameters a
k, b
k, and θ
k may yield very different numerical behaviors.Lemma 6.
Let{
d
k
} be the sequence generated by (18), and then, for all k
≥
0, it holds that
(26)
F
k
T
d
k
=
-
∥
F
k
∥
2
≤
-
(
1
-
1
4
θ
k
)
∥
F
k
∥
2
,
where θ
k
>
1
/
2.Proof.
The desired result is very easy to obtain. In fact, ifk
=
0, it is clear that F
0
T
d
0
=
-
∥
F
0
∥
2
≤
-
(
1
-
(
1
/
4
θ
0
)
)
∥
F
0
∥
2. If k
≥
1, we have
(27)
F
k
T
d
k
=
F
k
T
(
-
(
1
+
β
k
F
k
T
d
k
-
1
∥
F
k
∥
2
)
F
k
+
β
k
d
k
-
1
)
=
-
∥
F
k
∥
2
≤
-
(
1
-
1
4
θ
k
)
∥
F
k
∥
2
.The lemma above indicates that the descent property ofd
k from (18) is independent of the choices of β
k.Lemma 7.
Suppose Assumptions2 and 3 hold. Let α
k be the steplength involved in Algorithm 1, and let sequences {
x
k
} and {
z
k
} be generated by Algorithm 1. Then steplength α
k is well defined and satisfies the following inequality:
(28)
α
k
≥
min
{
ρ
,
t
(
1
-
(
1
/
4
θ
k
)
)
L
+
σ
∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
∥
F
k
∥
2
∥
d
k
∥
2
}
.Proof.
Suppose that, atkth iteration, x
k is not a solution, that is, F
k
≠
0, and, for all j
=
0,1
,
…, inequality (19) fails to hold, and then
(29)
-
F
(
x
k
+
ρ
t
j
d
k
)
T
d
k
<
σ
ρ
t
j
∥
F
(
x
k
+
ρ
t
j
d
k
)
∥
∥
d
k
∥
2
.
Since F is continuous, taking the limits with respect to j on the both sides of (29) yields
(30)
-
F
(
x
k
)
T
d
k
≤
0
,
which contradicts Lemmas 5 and 6. So, the step length α
k is well defined and can be determined within a finite number of trials.
Now, we prove inequality (28). If α
k
≠
ρ, then by using the selection of α
k, we have
(31)
-
F
(
x
k
+
α
k
t
-
1
d
k
)
T
d
k
<
σ
α
k
t
-
1
∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
∥
d
k
∥
2
.
Combining it with (24), (26), and the Lipschitz continuity of F yields
(32)
(
1
-
1
4
θ
k
)
∥
F
k
∥
2
≤
-
F
k
T
d
k
=
(
F
(
x
k
+
α
k
t
-
1
d
k
)
-
F
k
)
T
d
k
-
F
(
x
k
+
α
k
t
-
1
d
k
)
T
d
k
≤
L
α
k
t
-
1
∥
d
k
∥
2
+
σ
α
k
t
-
1
∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
∥
d
k
∥
2
.
From Lemmas 5 and 6, we have that
(33)
∥
d
k
∥
2
=
∥
d
k
+
F
k
-
F
k
∥
2
=
∥
d
k
+
F
k
∥
2
-
2
F
k
T
d
k
-
∥
F
k
∥
2
≥
(
1
-
1
2
θ
k
)
∥
F
k
∥
2
.
Since F
k
≠
0, then (33) indicates d
k
≠
0. So, it follows from inequality (32) that
(34)
α
k
≥
t
(
1
-
(
1
/
4
θ
k
)
)
L
+
σ
∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
∥
F
k
∥
2
∥
d
k
∥
2
.
Then inequality (28) is obtained.Lemma 8.
Letx
*
∈
X
* and let sequences {
x
k
} and {
F
k
} be generated by Algorithm 1. Then one has
(35)
∥
x
k
+
1
-
x
*
∥
2
≤
∥
x
k
-
x
*
∥
2
-
σ
2
∥
x
k
-
z
k
∥
4
.
Furthermore,
(36)
lim
k
→
∞
∥
x
k
-
z
k
∥
=
lim
k
→
∞
α
k
∥
d
k
∥
=
0
.
And there exists a positive number M such that ∥
F
k
∥
≤
M and ∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
≤
M for all k
≥
0.Proof.
Sincex
*
∈
X
*, then F
(
x
*
)
=
0 and P
Ω
(
x
*
)
=
x
*. Since the mapping F is monotone, then F
(
z
k
)
T
(
z
k
-
x
*
)
≥
0; further,
(37)
F
(
z
k
)
T
(
x
k
-
x
*
)
≥
F
(
z
k
)
T
(
x
k
-
z
k
)
.
By using (19) and z
k
=
x
k
+
α
k
d
k, we have
(38)
F
(
z
k
)
T
(
x
k
-
z
k
)
=
-
α
k
F
(
z
k
)
T
d
k
≥
σ
α
k
2
∥
d
k
∥
2
∥
F
(
z
k
)
∥
,
which implies that
(39)
F
(
z
k
)
T
(
x
k
-
z
k
)
∥
F
(
z
k
)
∥
≥
σ
α
k
2
∥
d
k
∥
2
=
σ
∥
x
k
-
z
k
∥
2
.
Obviously, F
(
z
k
)
T
(
x
k
-
z
k
)
≥
0. By using the property (7) of the projection operator P
Ω
(
·
) and (37), we have
(40)
∥
x
k
+
1
-
x
*
∥
2
=
∥
P
Ω
(
x
k
-
F
(
z
k
)
T
(
x
k
-
z
k
)
∥
F
(
z
k
)
∥
2
F
(
z
k
)
)
-
P
Ω
(
x
*
)
∥
2
≤
∥
x
k
-
F
(
z
k
)
T
(
x
k
-
z
k
)
∥
F
(
z
k
)
∥
2
F
(
z
k
)
-
x
*
∥
2
≤
∥
x
k
-
x
*
∥
2
-
(
F
(
z
k
)
T
(
x
k
-
z
k
)
)
2
∥
F
(
z
k
)
∥
2
.
Substituting the second term in (40) by (39), inequality (35) follows.
The inequality (35) shows that the sequence {
∥
x
k
-
x
*
∥
} is convergent, and then taking the limits with respect to k on the both sides of (35) yields (36).
SinceF is Lipschitz continuous, then from (35), we have
(41)
∥
F
k
∥
=
∥
F
(
x
k
)
-
F
(
x
*
)
∥
≤
L
∥
x
k
-
x
*
∥
≤
L
∥
x
0
-
x
*
∥
.
And from (36), we know that there exists a positive number M
′ such that α
k
∥
d
k
∥
≤
M
′, and then
(42)
∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
=
∥
F
(
x
k
+
α
k
t
-
1
d
k
)
-
F
(
x
*
)
∥
≤
L
∥
x
k
+
α
k
t
-
1
d
k
-
x
*
∥
≤
L
∥
x
0
-
x
*
∥
+
L
M
′
t
-
1
.
Denote M
=
L
∥
x
0
-
x
*
∥
+
L
M
′
t
-
1; we have that ∥
F
k
∥
≤
M and ∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
≤
M.Theorem 9.
Let Assumption4 hold and let {
d
k
} be a sequence generated by Algorithm 1. Then
(43)
∥
d
k
∥
≤
(
1
+
2
γ
)
∥
F
k
∥
.
And one has
(44)
liminf
k
→
∞
∥
F
k
∥
=
0
.Proof.
Ifd
k is generated by (15), we have
(45)
∥
d
k
∥
≤
∥
F
k
∥
+
|
β
k
|
∥
d
k
-
1
∥
≤
(
1
+
γ
)
∥
F
k
∥
,
which satisfies (43). If d
k is generated by (18), then
(46)
∥
d
k
∥
≤
∥
F
k
∥
+
2
|
β
k
|
∥
d
k
-
1
∥
.
The inequality (43) is obtained easily. From Lemma 8, we know that there exists 0
<
M
<
∞ such that ∥
F
k
∥
≤
M, and then
(47)
∥
d
k
∥
≤
(
1
+
2
γ
)
M
.
Suppose (44) does not hold, then there exists ϵ
>
0 such that
(48)
∥
F
k
∥
≥
ϵ
,
∀
k
≥
0
.
From (33), we have that ∥
d
k
∥
≥
(
1
-
1
/
(
2
θ
k
)
)
∥
F
k
∥, which implies
(49)
∥
d
k
∥
≥
(
1
-
1
(
2
θ
k
)
)
ϵ
,
∀
k
≥
0
.
By inequalities (28), (47), (48), and (49), we have
(50)
α
k
∥
d
k
∥
≥
min
{
ρ
,
t
(
1
-
(
1
/
4
θ
k
)
)
L
+
σ
∥
F
(
x
k
+
α
k
t
-
1
d
k
)
∥
∥
F
k
∥
2
∥
d
k
∥
2
}
∥
d
k
∥
≥
min
{
ρ
,
t
(
1
-
(
1
/
4
θ
k
)
)
L
+
σ
M
ϵ
2
(
1
+
2
γ
)
2
M
2
}
×
(
1
-
1
(
2
θ
k
)
)
ϵ
>
0
.
This contradicts (36). So the conclusion (44) holds.


## 4. Numerical Experiments

In this section, we give some specific versions of Algorithm1 and investigate their numerical behaviors. Let us review the HS conjugate gradient method [28]. It generates search direction d
k by (12) and parameter β
k by
(51)
β
k
H
S
=
g
k
T
y
k
-
1
d
k
-
1
T
y
k
-
1
.
Among early conjugate gradient methods, the HS method is a relatively efficient one. And many conjugate gradient methods are its improved versions, such as the well-known CG_DESCENT method. Now based on the HS method and Assumption 4, we give several specific versions of Algorithm 1(a) as follows.Method 1.
Consider Algorithm1(a) with
(52)
β
k
1
=
F
k
T
y
k
-
1
max
{
0.5
d
k
-
1
T
y
k
-
1
+
0.5
∥
F
k
-
1
∥
2
,
ϵ
∥
d
k
-
1
∥
}
-
2
∥
y
k
-
1
∥
2
(
max
{
0.5
d
k
-
1
T
y
k
-
1
+
0.5
∥
F
k
-
1
∥
2
,
ϵ
∥
d
k
-
1
∥
}
)
2
×
F
k
T
d
k
-
1
.Method 2.
Consider Algorithm1(a) with
(53)
β
k
2
=
F
k
T
y
k
-
1
max
{
max
{
d
k
-
1
T
y
k
-
1
,
∥
F
k
-
1
∥
2
}
,
ϵ
∥
d
k
-
1
∥
}
-
2
∥
y
k
-
1
∥
2
(
max
{
max
{
d
k
-
1
T
y
k
-
1
,
∥
F
k
-
1
∥
2
}
,
ϵ
∥
d
k
-
1
∥
}
)
2
×
F
k
T
d
k
-
1
.Method 3.
Consider Algorithm1(a) with
(54)
β
k
3
=
F
k
T
y
k
-
1
*
max
{
d
k
-
1
T
y
k
-
1
*
,
ϵ
∥
d
k
-
1
∥
}
-
2
∥
y
k
-
1
*
∥
2
(
max
{
d
k
-
1
T
y
k
-
1
*
,
ϵ
∥
d
k
-
1
∥
}
)
2
F
k
T
d
k
-
1
,
where y
k
-
1
*
=
y
k
-
1
+
α
k
-
1
d
k
-
1.Since the definition of parameterβ
k in Algorithm 1(b) could be the same as that in Algorithm 1(a), and the descent property of d
k in Algorithm 1(b) is independent of the choices of parameter β
k, we can give several specific versions of Algorithm 1(b) as follows.Method 4.
Consider Algorithm1(b) with (52).Method 5.
Consider Algorithm1(b) with
(55)
β
k
5
=
F
k
T
y
k
-
1
max
{
max
{
d
k
-
1
T
y
k
-
1
,
-
F
k
-
1
T
d
k
-
1
}
,
ϵ
∥
d
k
-
1
∥
}
-
2
∥
y
k
-
1
∥
2
(
max
{
max
{
d
k
-
1
T
y
k
-
1
,
-
F
k
-
1
T
d
k
-
1
}
,
ϵ
∥
d
k
-
1
∥
}
)
2
×
F
k
T
d
k
-
1
.Method 6.
Consider Algorithm1(b) with
(56)
β
k
6
=
F
k
T
y
k
-
1
max
{
d
k
-
1
T
y
k
-
1
,
ϵ
∥
d
k
-
1
∥
}
.
From Lemma8, we know that a sequence {
F
k
} generated by Algorithm 1 is norm bounded. Then it is easy to verify that the parameters β
k in Methods 1–6 satisfy Assumption 4. So, from the convergence analysis in Section 3, we know that Methods 1–6 are convergent in the sense that liminf
k
→
∞
∥
F
k
∥
=
0.Next, we test the performance of Methods1–6 via the following four constrained monotone problems and compare them with the method (abbreviated as CGD_XZ) in [9].Problem 10 (see [29]).
The mappingF is taken as F
(
x
)
=
(
F
1
(
x
)
,
…
,
F
n
(
x
)
)
T, where F
i
(
x
)
=
e
x
i
-
1, i
=
1
,
…
,
n, and Ω
=
R
+
n.Problem 11 (see [17]).
The mappingF is taken as F
(
x
)
=
(
F
1
(
x
)
,
…
,
F
n
(
x
)
)
T, where
(57)
F
i
(
x
)
=
x
i
-
sin
(
|
x
i
-
1
|
)
,
i
=
1,2
,
…
,
n
,
and Ω
=
{
x
∈
R
n
∣
∑
i
=
1
n
‍
x
i
≤
n
,
x
i
≥
0
,
i
=
1,2
,
…
,
n
}.Problem 12 (see [30]).
The mappingF is taken as F
(
x
)
=
(
F
1
(
x
)
,
…
,
F
n
(
x
)
)
T, where
(58)
F
1
(
x
)
=
x
1
-
e
cos
(
(
x
1
+
x
2
)
/
(
n
+
1
)
)
,
F
i
(
x
)
=
x
i
-
e
cos
(
(
x
i
-
1
+
x
i
+
x
i
+
1
)
/
(
n
+
1
)
)
,
i
=
2,3
,
…
,
n
-
1
,
F
n
(
x
)
=
x
n
-
e
cos
(
(
x
n
-
1
+
x
n
)
/
(
n
+
1
)
)
,
and Ω
=
R
+
n.Problem 13 (see [31]).
The mappingF is given by
(59)
F
(
x
)
=
(
1
0
0
0
0
1
-
1
0
0
1
1
0
0
0
0
0
)
(
x
1
x
2
x
3
x
4
)
+
(
x
1
3
x
2
3
2
x
3
3
2
x
4
3
)
+
(
-
10
1
-
3
0
)
and Ω
=
{
x
∈
R
4
∣
∑
i
=
1
4
‍
x
i
≤
4
,
x
i
≥
0
,
i
=
1,2
,
3,4
}.For Methods1–6 and CGD_XZ method, we set σ
=
1
0
-
4, t
=
0.5, and ρ
=
s
k
T
s
k
/
(
s
k
T
y
k
), where s
k
=
x
k
+
1
-
x
k and ρ
≥
1
/
L which is obtained by the monotonicity and the L-Lipschitz continuity of F. The stopping criterion is ∥
F
k
∥
∞
≤
1
0
-
5.Our computations were carried out using MATLAB R2011b on a desktop computer with an Intel(R) Xeon(R) 2.40 GHZ CPU, 6.00 GB of RAM, and Windows operating system. The numerical results were reported in Tables1, 2, 3, and 4, where the initial points x
1
=
(
10,10
,
…
,
10
)
T, x
2
=
(
1,1
,
…
,
1
)
T, x
3
=
(
1,1
/
2
,
…
,
1
/
n
)
T, x
4
=
(
0.1,0.1
,
…
,
0.1
)
T, x
5
=
(
1
/
n
,
2
/
n
,
…
,
1
)
T, and x
6
=
(
1
-
1
/
n
,
1
-
2
/
n
,
…
,
0
)
T and Dim, Iter, Nf, and CPU stand for the dimension of the problem, the number of iterations, the number of function evaluations, and the CPU time elapsed in seconds, respectively. Table 5 showed the number that each method solved the test problems with the least iterations, the least function evaluations, and the best time, respectively.Table 1
Numerical results for Problem10.
Init
Method
Dim
=
5000
Dim
=
10000
Dim
=
20000
Dim
=
30000
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
x
1
CGD_XZ
10/26/0.036
10/26/0.052
10/26/0.052
10/26/0.071
Method1
13/38/0.026
13/38/0.038
13/38/0.063
13/38/0.089
Method2
15/32/0.024
19/38/0.047
19/38/0.073
31/74/0.179
Method3
10/22/0.017
10/22/0.023
10/22/0.039
10/22/0.052
Method4
13/25/0.022
13/25/0.028
13/25/0.048
13/25/0.061
Method5
13/25/0.019
13/25/0.028
13/25/0.058
13/25/0.063
Method6
19/33/0.030
19/34/0.040
19/34/0.062
29/67/0.162
x
2
CGD_XZ
5/10/0.007
5/10/0.012
5/10/0.020
5/10/0.027
Method1
7/19/0.011
7/19/0.017
7/19/0.029
7/19/0.039
Method2
5/10/0.006
5/10/0.010
7/14/0.022
7/14/0.035
Method3
4/5/0.004
4/5/0.006
4/5/0.011
4/5/0.016
Method4
5/6/0.006
5/6/0.008
5/6/0.014
5/6/0.020
Method5
5/6 /0.005
5/6/0.008
5/6/0.013
5/6/0.020
Method6
5/6/0.005
5/6/0.009
6/8/0.017
6/8/0.023
x
3
CGD_XZ
4/8/0.006
4/8/0.010
4/8/0.016
4/8/0.021
Method1
7/18/0.010
7/18/0.015
7/18/0.029
7/18/0.037
Method2
4/7/0.005
4/7/0.008
4/7/0.013
4/7/0.018
Method3
3/4/0.003
3/4/0.005
3/4/0.009
3/4/0.012
Method4
4/5/0.005
4/5/0.007
4/5/0.011
4/5/0.015
Method5
4/5/0.005
4/5/0.006
4/5/0.012
4/5/0.015
Method6
4/5/0.004
4/5/0.007
4/5/0.011
4/5/0.014
x
4
CGD_XZ
15/47/0.027
19/60/0.055
17/51/0.080
21/76/0.141
Method1
14/47/0.025
17/59/0.048
17/58/0.077
21/75/0.137
Method2
14/28/0.016
14/28/0.026
14/28/0.047
14/28/0.064
Method3
18/28/0.022
18/28/0.031
18/28/0.053
18/28/0.076
Method4
14/21/0.017
14/21/0.023
14/21/0.043
14/21/0.056
Method5
10/15/0.012
10/15/0.017
10/15/0.028
10/15/0.040
Method6
21/33/0.025
21/33/0.038
21/33/0.060
21/33/0.085
x
5
CGD_XZ
16/41/0.027
24/65/0.066
19/49/0.084
19/51/0.118
Method1
17/49/0.029
17/55/0.044
19/60/0.084
18/58/0.111
Method2
13/26/0.017
13/26/0.026
13/26/0.045
13/26/0.060
Method3
23/35/0.028
23/35/0.040
23/35/0.067
23/35/0.096
Method4
22/34/0.025
22/34/0.040
22/34/0.068
22/34/0.093
Method5
21/30/0.023
21/30/0.036
21/30/0.060
21/30/0.082
Method6
25/41/0.033
24/40/0.046
24/40/0.070
24/40/0.095
x
6
CGD_XZ
16/41/0.027
23/56/0.060
18/47/0.073
19/51/0.112
Method1
16/51/0.027
15/47/0.038
17/54/0.075
17/54/0.101
Method2
13/26/0.015
13/26/0.026
13/26/0.043
13/26/0.058
Method3
23/35/0.026
23/35/0.040
23/35/0.067
23/35/0.092
Method4
22/34/0.025
22/34/0.042
22/34/0.067
22/34/0.088
Method5
21/30/0.024
21/30/0.035
21/30/0.060
21/30/0.085
Method6
25/41/0.029
24/40/0.042
24/40/0.072
24/40/0.097Table 2
Numerical results for Problem11.
Init
Method
Dim
=
5000
Dim
=
10000
Dim
=
20000
Dim
=
30000
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
x
1
CGD_XZ
5/12/0.019
5/12/0.025
5/12/0.033
5/12/0.039
Method1
7/21/0.023
7/21/0.030
7/21/0.039
7/21/0.054
Method2
5/13/0.015
5/14/0.017
5/14/0.028
5/15/0.039
Method3
12/25/0.022
12/25/0.036
12/25/0.047
12/25/0.065
Method4
5/8/0.009
5/8/0.012
5/8/0.017
5/8/0.025
Method5
5/8/0.009
5/8/0.014
5/8/0.017
5/8/0.025
Method6
5/10/0.008
5/11/0.022
5/11/0.021
5/12/0.030
x
2
CGD_XZ
3/6/0.004
3/6/0.009
3/6/0.013
3/6/0.018
Method1
6/17/0.011
6/17/0.018
6/17/0.027
6/17/0.039
Method2
3/6/0.004
3/6/0.007
3/6/0.012
3/6/0.015
Method3
9/18/0.014
9/18/0.022
9/18/0.034
9/18/0.046
Method4
3/4/0.004
3/4/0.006
3/4/0.009
3/4/0.013
Method5
3/4/0.004
3/4/0.006
3/4/0.010
3/4/0.013
Method6
3/4/0.004
3/4/0.006
3/4/0.009
3/4/0.013
x
3
CGD_XZ
14/41/0.028
14/41/0.043
14/41/0.073
14/41/0.101
Method1
5/13/0.008
5/13/0.013
5/13/0.021
5/13/0.031
Method2
13/37/0.022
13/37/0.036
13/37/0.061
13/37/0.086
Method3
10/20/0.015
10/20/0.024
10/20/0.040
10/20/0.056
Method4
14/28/0.021
14/28/0.033
14/28/0.054
14/28/0.075
Method5
14/28/0.021
14/28/0.032
14/28/0.055
14/28/0.080
Method6
14/28/0.020
14/28/0.032
14/28/0.052
14/28/0.076
x
4
CGD_XZ
17/50/0.034
17/50/0.051
17/50/0.086
17/50/0.124
Method1
20/68/0.038
17/50/0.044
19/54/0.085
18/51/0.118
Method2
18/44/0.025
16/38/0.040
17/42/0.072
17/42/0.096
Method3
20/40/0.028
21/42/0.043
20/40/0.075
18/36/0.094
Method4
15/30/0.020
15/30/0.034
15/30/0.057
15/30/0.080
Method5
16/32/0.026
16/32/0.039
16/32/0.063
16/32/0.083
Method6
22/41/0.031
19/38/0.042
19/38/0.066
19/38/0.097
x
5
CGD_XZ
21/59/0.044
21/68/0.068
17/52/0.089
16/42/0.106
Method1
19/61/0.033
18/56/0.051
17/50/0.078
16/48/0.107
Method2
12/23/0.016
12/23/0.023
12/23/0.043
12/23/0.063
Method3
17/34/0.024
17/34/0.036
17/34/0.063
17/34/0.088
Method4
32/52/0.040
32/52/0.070
31/50/0.101
31/50/0.148
Method5
21/35/0.028
21/35/0.043
21/35/0.073
21/35/0.101
Method6
29/39/0.034
27/36/0.048
27/36/0.079
27/36/0.112
x
6
CGD_XZ
21/59/0.041
22/68/0.071
20/62/0.097
16/42/0.104
Method1
17/59/0.035
19/67/0.058
18/63/0.092
18/52/0.118
Method2
14/27/0.020
14/27/0.031
14/27/0.050
14/27/0.074
Method3
17/34/0.023
17/34/0.040
17/34/0.060
17/34/0.090
Method4
30/48/0.042
31/50/0.060
31/50/0.103
31/50/0.143
Method5
21/35/0.028
21/35/0.040
21/35/0.073
21/35/0.101
Method6
29/39/0.032
27/36/0.046
27/36/0.083
27/36/0.112Table 3
Numerical results for Problem12.
Init
Method
Dim
=
5000
Dim
=
10000
Dim
=
20000
Dim
=
30000
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
x
1
CGD_XZ
24/66/0.095
24/66/0.130
21/60/0.205
21/60/0.308
Method1
14/34/0.037
15/38/0.070
15/46/0.146
17/56/0.250
Method2
26/66/0.063
28/75/0.126
32/102/0.317
41/136/0.612
Method3
30/49/0.060
30/49/0.099
30/49/0.191
30/49/0.278
Method4
23/43/0.050
23/43/0.085
22/42/0.159
22/42/0.224
Method5
24/44/0.051
23/43/0.083
22/42/0.160
22/42/0.222
Method6
25/61/0.060
28/76/0.127
33/103/0.320
38/120/0.538
x
2
CGD_XZ
19/55/0.056
19/55/0.112
18/53/0.177
18/53/0.260
Method1
16/40/0.041
18/54/0.090
13/33/0.112
14/41/0.189
Method2
18/36/0.038
18/36/0.068
18/36/0.127
18/36/0.186
Method3
19/37/0.040
19/37/0.070
18/36/0.130
18/36/0.188
Method4
19/37/0.040
19/37/0.073
18/36/0.128
18/36/0.188
Method5
19/37/0.042
19/37/0.072
18/36/0.127
18/36/0.193
Method6
18/36/0.039
18/36/0.069
18/36/0.128
18/36/0.188
x
3
CGD_XZ
20/57/0.059
19/54/0.095
19/54/0.183
19/54/0.266
Method1
15/43/0.041
12/28/0.050
13/34/0.111
18/55/0.251
Method2
19/37/0.040
19/37/0.068
20/39/0.141
20/39/0.202
Method3
19/36/0.039
19/36/0.068
19/36/0.130
19/36/0.195
Method4
21/40/0.046
21/40/0.081
21/40/0.147
21/40/0.213
Method5
21/40/0.046
21/40/0.081
21/40/0.148
21/40/0.214
Method6
19/37/0.041
19/37/0.073
18/36/0.128
18/36/0.186
x
4
CGD_XZ
19/54/0.054
19/54/0.098
19/54/0.181
19/54/0.263
Method1
12/28/0.029
12/29/0.054
16/51/0.163
14/36/0.175
Method2
19/37/0.041
19/37/0.072
20/39/0.142
20/39/0.205
Method3
19/36/0.041
19/36/0.077
19/36/0.134
19/36/0.190
Method4
20/38/0.043
20/38/0.076
20/38/0.141
20/38/0.207
Method5
20/38/0.043
20/38/0.075
20/38/0.141
20/38/0.204
Method6
19/37/0.040
19/37/0.068
18/36/0.128
18/36/0.188
x
5
CGD_XZ
20/57/0.058
20/57/0.101
20/57/0.190
20/57/0.273
Method1
17/40/0.040
16/49/0.080
12/28/0.097
12/28/0.141
Method2
19/37/0.040
19/37/0.072
19/37/0.138
20/39/0.211
Method3
20/38/0.042
20/38/0.074
20/38/0.143
20/38/0.204
Method4
21/40/0.046
21/40/0.075
21/40/0.149
21/40/0.212
Method5
21/40/0.049
21/40/0.077
21/40/0.149
21/40/0.212
Method6
20/39/0.043
20/39/0.076
20/39/0.142
19/38/0.196
x
6
CGD_XZ
19/54/0.052
19/54/0.094
19/54/0.182
19/54/0.264
Method1
15/40/0.038
12/28/0.052
12/30/0.097
17/51/0.233
Method2
19/37/0.038
19/37/0.068
19/37/0.136
20/39/0.203
Method3
19/36/0.040
19/36/0.075
19/36/0.133
19/36/0.197
Method4
20/38/0.043
20/38/0.076
20/38/0.140
20/38/0.202
Method5
20/38/0.042
20/38/0.075
20/38/0.142
20/38/0.206
Method6
19/37/0.040
19/37/0.072
19/37/0.133
18/36/0.185Table 4
Numerical results for Problem13.
Method
Init
=
x
1
Init
=
x
2
Init
=
x
3
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
CGD_XZ
8032/100720/3.926
6960/88626/3.395
6608/83404/3.206
Method1
14474/81644/4.073
14776/83135/4.152
14105/79821/3.985
Method2
14547/80367/3.784
14535/79834/3.782
14233/78523/3.724
Method3
15974/67287/3.949
15950/67116/3.929
15522/64072/3.830
Method4
14289/77460/4.229
14583/78517/4.262
14034/76578/4.094
Method5
14633/79306/4.089
14585/78940/4.017
14428/78917/4.018
Method6
12394/61365/3.314
13192/64579/3.495
12500/60647/3.319
Method
Init
=
x
4
Init
=
x
5
Init
=
x
6
Iter/Nf/CPU
Iter/Nf/CPU
Iter/Nf/CPU
CGD_XZ
8018/100772/3.874
118/1232/0.050
7583/92362/3.612
Method1
14482/81707/4.059
125/445/0.029
14523/81523/4.078
Method2
14490/80119/3.795
65/209/0.014
14829/81427/3.871
Method3
15571/65689/3.826
125/586/0.032
15802/66762/3.889
Method4
14618/78866/4.250
132/450/0.032
14716/79737/4.267
Method5
14605/79474/4.059
127/440/0.030
14530/79232/4.032
Method6
12928/62759/3.474
126/536/0.031
12651/63054/3.378Table 5
Number of times when each method was the fastest.
Method
Iteration metric
Function evaluation metric
Time metric
CGD_XZ
17
0
3
Method1
28
16
19
Method2
26
22
24
Method3
12
19
13
Method4
12
15
11
Method5
12
15
10
Method6
10
16
11The performance of the seven methods was evaluated using the profiles of Dolan and Morè [32]. That is, we plotted the fraction P of the test problems for which each of the methods was within a factor τ of the best time. Figures 1–3 showed the performance profiles referring to the number of iterations, the number of function evaluations, and CPU time, respectively. Figure 1 indicated that relative to the number of iterations, Methods 1 and 2 performed best for τ near 1. When τ
≥
1.3, CGD_XZ was comparable with Methods 1 and 2 and had a higher number of wins than Methods 3–6. Figure 2 revealed that relative to the number of function evaluations, Method 2 performed best for τ near 1. When τ
≥
1.6, Method 5 performed more robust and then Methods 3 and 4. Figure 3 revealed that relative to the CPU time metric, Method 2 performed best for τ near 1. Method 5 performed more robust when τ
≥
1.3, and Methods 2–4 were competitive. While CGD_XZ performed worst, it had a lower number of wins than the rest of the methods. So, from the analysis above, we can conclude that all these methods were efficient to solve these test problems. If we consider the number of wins, Method 2 performed best which is also revealed by Table 5, while from the view of robustness, Method 5 performed best.Figure 1
Performance profile based on the number of iterations.Figure 2
Performance profile based on the number of function evaluations.Figure 3
Performance profile based on the CPU time.


## 5. Conclusions

In this paper, we discussed two unified frameworks of some sufficient descent conjugate gradient methods and combined them with the hyperplane projection method of Solodov and Svaiter to solve convex constrained nonlinear monotone equations. The two unified frameworks inherit the advantages of some usual conjugate gradient methods for solving large-scale unconstrained minimization problems. That is, they satisfy the sufficient descent conditionF
k
T
d
k
≤
-
c
∥
F
k
∥
2 (c
>
0) independently of any line search, and they do not require F’s Jacobian, then they are suitable to solve large-scale nonsmooth monotone equations. In Section 4, we gave several specific versions of the two unified frameworks and investigated their numerical behaviors over some test problems. From the numerical results, we concluded that these specific versions are efficient.Let us review problem (1) and introduce a monotone inclusion problem
(60)
0
∈
T
(
x
)
,
where the set-value mapping T
:
R
n
→
2
R
n is maximal monotone. Obviously, the latter is more general than the former; then, our further investigation is to extend these sufficient descent conjugate gradient methods to solve problem (60).


## Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.



---

*Source: 305643-2014-01-12.xml*