# Extension of Modified Polak-Ribière-Polyak Conjugate Gradient Method to Linear Equality Constraints Minimization Problems

Authors: Zhifeng Dai
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Combining the Rosen gradient projection method with the two-term Polak-Ribière-Polyak (PRP) conjugate gradient method, we propose a two-term Polak-Ribière-Polyak (PRP) conjugate gradient projection method for solving linear equality constraints optimization problems. The proposed method possesses some attractive properties: (1) search direction generated by the proposed method is a feasible descent direction; consequently the generated iterates are feasible points; (2) the sequences of function are decreasing. Under some mild conditions, we show that it is globally convergent with Armijio-type line search. Preliminary numerical results show that the proposed method is promising.


---

## Body

## 1. Introduction

In this paper, we consider solving the following linear equality constraints optimization problem:(1)
min
⁡
f
(
x
)
s
.
t
.
A
x
=
b
,
where f
(
x
)
:
R
n
→
R is a smooth function and A is a m
×
n matrix of rank m
(
m
≤
n
). In this paper, the feasible region D and the feasible direction set S are defined, respectively, as follows:
(2)
D
=
{
A
x
=
b
}
,
S
=
{
A
d
=
0
}
.Taking the negative gradient for a search direction (d
=
-
∇
f
(
x
k
)) is a natural way of solving unconstrained optimization problems. However, this approach does not work for constrained problems, since the gradient may not be a feasible direction. A basic technique to overcome this difficulty was initiated by Rosen [1] in 1960. To obtain a feasible search direction, Rosen projected the gradient into the feasible region; that is,
(3)
d
=
-
P
∇
f
(
x
k
)
,
P
=
I
-
A
T
(
A
A
T
)
-
1
A
.
The convergence of Rosen’s gradient projection method can be proved by Du; see [2–4].In fact, Rosen’s gradient projection method is an extension of the steepest-descent method. It is well known that the drawback of the steepest-descent method is easy to suffer from zig-zagging specially when the graph off
(
x
) has an “elongated” form. To overcome the zig-zagging, we want to use the conjugate gradient method to modify the projection direction.It is well known that nonlinear conjugate gradient methods such as the Polak-Ribière-Polyak (PRP) method [5, 6] are very efficient for large-scale unconstrained optimization problems due to their simplicity and low storage. However, it does not necessarily satisfy the descent conditions g
k
T
d
k
≤
-
c
∥
g
k
∥
2, c
>
0.Recently, Cheng [7] proposed a two-term modified PRP method (called TMPRP), in which the direction d
k is given by
(4)
d
k
=
{
-
g
k
,
if
k
=
0
,
-
g
k
+
β
k
PRP
(
I
-
g
k
g
k
T
∥
g
k
∥
2
)
d
k
-
1
,
if
k
≥
1
.
An attractive property of the TMPRP method is that the direction generated by the method satisfies
(5)
g
k
T
d
k
=
-
∥
g
k
∥
2
,
which is independent of any line search. The presented numerical results show some potential advantage of the TMPRP method in Cheng [7]. In fact, we can easily rewrite the above direction d
k (4) as a three-term form:
(6)
d
k
=
{
-
g
k
,
if
k
=
0
,
-
g
k
+
β
k
PRP
d
k
-
1
-
β
k
PRP
g
k
T
d
k
-
1
∥
g
k
∥
2
g
k
,
if
k
≥
1
.
In the past few years, researchers have paid increasing attention to the conjugate gradient methods and their applications. Among others, we mention here the following works, for example, [8–29].In the past few years, some researchers also paid attention to equality constrained problems. Martínez et al. [30] proposed a spectral gradient method for linearly constrained optimization by the following way to obtain the search direction: d
k
∈
R
n is the unique solution of
(7)
min
⁡
1
2
d
T
B
k
d
+
∇
f
(
x
)
T
d
.
s
.
t
.
A
d
=
0
.
In this algorithm, B
k can be computed by quasi-Newton method in which the approximate Hessians satisfy a weak secant equation. The spectral choice of steplength is embedded into the Hessian approximation and the whole process is combined with a nonmonotone line search strategy.C. Li and D. H. Li [31] proposed a feasible Fletcher-Reeves conjugate gradient method for solving linear equality constrained optimization problem with exact line search. Their idea is to use original Fletcher-Reeves conjugate gradient method to modify the Zoutendijk direction. The Zoutendijk direction is the feasible steepest descent direction. It is a solution of the following problem:
(8)
min
⁡
∇
f
(
x
)
T
d
.
s
.
t
.
A
d
=
0
,
∥
d
∥
≤
1
.
Li et al. [32] also extended the modified Fletcher-Reeves conjugate gradient method in Zhang et al. [33] to solve linear equality constraints optimization problems which combined with the Zoutendijk feasible direction method. Under some mild conditions, Li et al. [32] showed that the proposed method with Armijo-type line search is globally convergent.In this paper, we will extend the two-term Polak-Ribière-Polyak (PRP) conjugate gradient method in Cheng [7] to solve linear equality constraints optimization problems (1), which combines with the Rosen gradient projection method in Rosen [1]. Under some mild conditions, we show that it is globally convergent with Armijo-type line search.The rest of this paper is organized as follows. In Section2, we firstly propose the algorithm and prove the the feasible descent direction. In Section 3, we prove the global convergence of the proposed method. In Section 4, we give some improvement for the algorithm. In Section 5, we report some numerical results to test the proposed method.


## 2. Algorithm and the Feasible Descent Direction

In this section, we propose a two-term Polak-Ribière-Polyak conjugate gradient projection method for solving the linear equality constraints optimization problem (1). The proposed method is a combination of the well-known Rose gradient projection method and the two-term Polak-Ribière-Polyak (PRP) conjugate gradient method in Cheng [7].The iterative process of the proposed method is given by(9)
x
k
+
1
=
x
k
+
α
k
d
k
,
and the search direction d
k is defined by
(10)
d
k
=
{
-
P
g
k
,
if
k
=
0
,
-
P
g
k
+
β
k
PRP
d
k
-
1
-
β
k
PRP
g
k
T
d
k
-
1
∥
P
g
k
∥
2
P
g
k
,
if
k
≥
1
,
where
(11)
P
=
I
-
A
T
(
A
A
T
)
-
1
A
,
g
k
=
∇
f
(
x
k
)
,
y
k
-
1
=
g
k
-
g
k
-
1
,
β
k
PRP
=
(
P
g
k
)
T
y
k
-
1
∥
P
g
k
-
1
∥
2
,
and α
k
>
0 is a steplength obtained by a line search.For convenience, we call the method (9) and (10) as EMPRP method. Now we prove that the direction d
k defined by (10) and (11) is a feasible descent direction of f at x
k.Theorem 1.
Suppose thatx
k
∈
D, P
=
I
-
A
T
(
A
A
T
)
-
1
A. d
k is defined by (10). If d
k
≠
0, then d
k is a feasible descent direction of f at x
k.Proof.
From (9), (10), and the definition of P, we have
(12)
g
k
T
d
k
=
g
k
T
(
-
P
g
k
+
β
k
PRP
d
k
-
1
-
β
k
PRP
g
k
T
d
k
-
1
∥
P
g
k
∥
2
P
g
k
)
=
-
∥
P
g
k
∥
2
+
β
k
PRP
g
k
T
d
k
-
1
-
β
k
PRP
g
k
T
d
k
-
1
∥
P
g
k
∥
2
∥
P
g
k
∥
2
=
-
∥
P
g
k
∥
2
.
This implies that d
k provides a descent direction of f at x
k.
In what follows, we show thatd
k is a feasible descent direction of f at x
k. From (9), we have that
(13)
A
(
P
g
k
)
=
A
(
I
-
A
T
(
A
A
T
)
-
1
A
)
g
k
=
0
.
It follows from (10) and (13) that
(14)
A
d
k
=
A
(
-
P
g
k
+
β
k
PRP
d
k
-
1
-
β
k
PRP
g
k
T
d
k
-
1
∥
P
g
k
∥
2
P
g
k
)
=
β
k
PRP
A
d
k
-
1
.
When k
=
0, we have
(15)
A
d
0
=
A
P
g
0
=
0
.
It is easy to get from (14) and (15) that, for all k, A
d
k
=
0 is satisfied. That is, d
k is feasible direction.In the remainder of this paper, we always assume thatf
(
x
) satisfies the following assumptions.Assumption A.
(i) The level set(16)
Ω
=
{
x
∈
R
n
∣
f
(
x
)
≤
f
(
x
0
)
}
is bounded.
(ii) Functionf
:
R
n
→
R is continuously differentiable and bounded from below. Its gradient is Lipschitz continuous, on an open ball N containing Ω; that is, there is a constant L
>
0 such that
(17)
∥
g
(
x
)
-
g
(
y
)
∥
≤
L
∥
x
-
y
∥
,
∀
x
,
y
∈
N
.Sincef
(
x
k
) is decreasing, it is clear that the sequence {
x
k
} generated by Algorithm 2 is contained in Ω. In addition, we get from Assumption A that there is a constant γ
>
0, such that
(18)
∥
g
(
x
)
∥
≤
γ
,
∀
x
∈
Ω
.
Since the matrix P is a projection matrix, it is reasonable to assume that there is a constant C
>
0, such that
(19)
∥
P
g
(
x
)
∥
≤
C
,
∀
x
∈
Ω
.We state the steps of the algorithm as follows.Algorithm 2 (EMPRP method with Armijio-type line search).
Step
0. Choose an initial point x
0
∈
D, ε
>
0. Let k
∶
=
0.
Step
1. Compute d
k by (10), where β
k is computed by (11).
Step
2. If ∥
P
g
k
∥
≤
ε stop, else go to Step 3.
Step
3. Given δ
∈
(
0
,
1
/
2
), ρ
∈
(
0,1
). Determine a stepsize α
k
=
max
⁡
(
ρ
j
∣
j
=
0,1
,
2
,
…
) satisfying
(20)
f
(
x
k
+
α
k
d
k
)
≤
f
(
x
k
)
-
δ
α
k
2
∥
d
k
∥
2
.
Step
4. Let x
k
+
1
=
x
k
+
α
k
d
k, and k
∶
=
k
+
1. Go to Step 1.


## 3. Global Convergence

In what follows, we establish the global convergence theorem of the EMPRP method for general nonlinear objective functions. We firstly give some important lemmas of the EMPRP method.Lemma 3.
Suppose thatx
k
∈
D, P
=
I
-
A
T
(
A
A
T
)
-
1
A. d
k is defined by (10) and (11). Then we have (
P
g
k
)
T
d
k
=
g
k
T
d
k, (
P
g
k
+
1
)
T
d
k
=
g
k
+
1
T
d
k, (
P
g
k
)
T
d
k
=
g
k
T
d
k
=
-
∥
P
g
k
∥
2.Proof.
By the definition ofd
k, we have
(21)
(
P
g
k
)
T
d
k
=
g
k
T
(
I
-
A
T
(
A
A
T
)
-
1
A
)
d
k
=
g
k
T
d
k
-
g
k
T
(
A
T
(
A
A
T
)
-
1
)
A
d
k
=
g
k
T
d
k
.
It follows from (12) and (21) that
(22)
(
P
g
k
)
T
d
k
=
g
k
T
d
k
=
-
∥
P
g
k
∥
2
.
On the other hand, we also have
(23)
(
P
g
k
+
1
)
T
d
k
=
g
k
+
1
T
(
I
-
A
T
(
A
A
T
)
-
1
A
)
d
k
=
g
k
+
1
T
d
k
-
g
k
+
1
T
(
A
T
(
A
A
T
)
-
1
)
A
d
k
=
g
k
+
1
T
d
k
.Lemma 4.
Suppose that Assumption A holds.{
x
k
} is generated by Algorithm 2. If there exists a constant ε
>
0 such that
(24)
∥
P
g
k
∥
≥
ε
,
∀
k
;
then there exists a constant M
>
0 such that
(25)
∥
d
k
∥
≤
M
,
∀
k
.Proof.
It follows from (20) that the function value sequence {
f
(
x
k
)
} is decreasing. We also have from (20) that
(26)
∑
i
=
1
∞
‍
-
δ
α
k
2
∥
d
k
∥
2
<
+
∞
,
as f is bounded from below. In particular, we have
(27)
lim
⁡
k
→
∞
α
k
∥
d
k
∥
=
0
.
By the definition of d
k, we get from (17), (19), and (24) that
(28)
∥
d
k
∥
≤
∥
P
g
k
∥
+
∥
P
g
k
∥
∥
y
k
-
1
∥
∥
d
k
-
1
∥
∥
P
g
k
-
1
∥
2
+
∥
P
g
k
∥
∥
y
k
-
1
∥
∥
P
g
k
-
1
∥
2
·
∥
g
k
∥
∥
d
k
-
1
∥
∥
P
g
k
∥
∥
P
g
k
∥
2
≤
C
+
C
L
α
k
-
1
∥
d
k
-
1
∥
ε
2
∥
d
k
-
1
∥
+
γ
L
α
k
-
1
∥
d
k
-
1
∥
ε
2
∥
d
k
-
1
∥
≤
C
+
(
C
L
ε
2
+
γ
L
ε
2
)
α
k
-
1
∥
d
k
-
1
∥
2
.
Since α
k
-
1
d
k
-
1
→
0, as k
→
∝, there exist a constant r
∈
(
0,1
) and an integer k
0, such that the following inequality holds for all k
≥
k
0:
(29)
(
C
L
ε
2
+
γ
L
ε
2
)
α
k
-
1
∥
d
k
-
1
∥
≤
r
.
Hence, we have, for any k
>
k
0,
(30)
∥
d
k
∥
≤
C
+
r
∥
d
k
-
1
∥
≤
C
(
1
+
r
+
r
2
+
⋯
+
r
k
-
k
0
-
1
)
+
r
k
-
k
0
∥
d
k
0
∥
≤
C
1
-
r
+
∥
d
k
0
∥
.
Letting M
=
max
⁡
{
∥
d
1
∥
,
∥
d
1
∥
,
…
,
∥
d
k
0
∥
,
C
/
(
1
-
r
)
+
∥
d
k
0
∥
}, we can get (25).We now establish the global convergence theorem of the EMPRP method for general nonlinear objective functions.Theorem 5.
Suppose that Assumption A holds.{
x
k
} is generated by Algorithm 2. Then we have
(31)
liminf
⁡
k
→
∞
∥
P
g
k
∥
=
0
.Proof.
Suppose thatliminf
⁡
k
→
∞
∥
P
g
k
∥
≠
0 for all k. Then there exists a constant ε
>
0 such that
(32)
∥
P
g
k
∥
>
ε
,
∀
k
≥
0
.
We now prove (31) by considering the following two cases.
Case (i). liminf
⁡
k
→
∞
α
k
>
0. We get from (22) and (27) that liminf
⁡
k
→
∞
∥
P
g
k
∥
=
0. This contradicts assumption (32).
Case (ii). liminf
⁡
k
→
∞
α
k
=
0. That is, there is an infinite index set K such that
(33)
lim
⁡
k
∈
K
,
k
→
∞
α
k
=
0
.
When k
∈
K is sufficiently large, by the line search condition, ρ
-
1
α
k does not satisfy inequality (20). This means
(34)
f
(
x
k
+
α
k
d
k
)
-
f
(
x
k
)
>
-
δ
ρ
-
2
α
k
2
∥
d
k
∥
2
.
By the mean-value theorem and inequality (17), there is a t
k
∈
(
0,1
) such that x
k
+
t
k
ρ
-
1
α
k
d
k
∈
N and
(35)
f
(
x
k
+
ρ
-
1
α
k
d
k
)
-
f
(
x
k
)
=
ρ
-
1
α
k
g
(
x
k
+
t
k
ρ
-
1
α
k
d
k
)
T
d
k
=
ρ
-
1
α
k
g
k
T
d
k
+
ρ
-
1
α
k
(
g
(
x
k
+
t
k
ρ
-
1
α
k
d
k
)
-
g
k
)
T
d
k
≤
ρ
-
1
α
k
g
k
T
d
k
+
ρ
-
1
α
k
∥
g
(
x
k
+
t
k
ρ
-
1
α
k
d
k
)
-
g
k
∥
∥
d
k
∥
≤
ρ
-
1
α
k
g
k
T
d
k
+
L
ρ
-
2
α
k
2
∥
d
k
∥
2
.
Substituting the last inequality into (34), for all k
∈
K sufficiently large, we have from (12) that
(36)
∥
P
g
k
∥
2
=
-
g
k
T
d
k
≤
ρ
-
1
(
L
+
δ
)
α
k
∥
d
k
∥
2
.
Since {
d
k
} is bounded and lim
⁡
k
→
∞
α
k
=
0, the last inequality implies
(37)
lim
⁡
k
∈
K
,
k
→
∞
∥
P
g
k
∥
=
0
.
This also yields a contradiction. The proof is then complete.


## 4. Improvement for Algorithm2

In this section, we propose techniques for improving the efficiency of Algorithm2 in practical computation which is about computing projections and the stepsize of the Armijo-type line search.


### 4.1. Computing Projection

In this paper, as in Gould et al. [34], instead of computing a basis for null space of matrix A, we choose to work directly with the matrix of constraint gradients, computing projections by normal equations. As the computation of the projection is a key step in the proposed method, following Gould et al. [34], this projection can be computed in an alternative way.Let(38)
g
+
=
-
P
g
,
P
=
I
-
A
T
(
A
A
T
)
-
1
A
.
We can express this as
(39)
g
+
=
-
g
+
A
T
v
,
where v is the solution of
(40)
A
A
T
v
=
A
g
.
Noting that (40) is the normal equation. Since A is a m
×
n matrix of rank m
(
m
≤
n
), A
A
T is symmetric positive definite matrix. We use the Doolittle (called LU) factorization of A
A
T to solve (40).For the matrixA is constant, the factorization of A
A
T needs to be carried out only once at the beginning of the iterative process. Using a Doolittle factorization of A
A
T, (40) can be computed in the following form:
(41)
L
(
U
T
v
)
=
A
g
⟺
{
L
y
=
A
g
U
T
v
=
y
,
where L, U is the Doolittle factor of A
A
T.


### 4.2. Computing Stepsize

The drawback of the Armijo line search is how to choose the initial stepsizeα
k. If α
k is too large then the procedure needs to call much more function evaluations. If α
k is too small then the efficiency of related algorithm will be decreased. Therefore, we should choose an adequate initial stepsize α
k at each iteration. In what follows, we propose a way to generate the initial stepsize.We first estimate the stepsize determined by the exact line search. Support at the moment thatf is twice continuously differentiable. We denote by G
(
x
) the Hessian of f at x and abbreviate G
(
x
k
) as G
k. Notice that the exact line search stepsize α
-
k satisfies
(42)
-
g
k
T
d
k
=
(
g
(
x
k
+
α
-
k
d
k
)
-
g
k
)
T
d
k
≈
α
-
k
d
k
T
G
k
d
k
.
This shows that scalar δ
k
≜
-
g
k
T
d
k
/
d
k
T
G
k
d
k is an estimation to α
-
k. To avoid the computation of the second derivative, we further estimate α
-
k by letting
(43)
γ
k
=
-
ϵ
k
g
k
T
d
k
d
k
T
(
g
(
x
k
+
ϵ
k
d
k
)
-
g
k
)
,
where positive sequence satisfies {
ϵ
k
}
→
0 as k
→
∞. Let the initial stepsize of the Armijo line search be an approximation to
(44)
δ
k
≜
-
g
k
T
d
k
d
k
T
G
k
d
k
≈
-
ϵ
k
g
k
T
d
k
d
k
T
(
g
(
x
k
+
ϵ
k
d
k
)
-
g
k
)
≜
γ
k
.
It is not difficult to see that if ϵ
k and ∥
d
k
∥ are sufficiently small, then δ
k and γ
k are good estimation to α
-
k.So to improve the efficiency of EMPRP method in practical computation, we utilize the following line search process.Line Search Process. If inequality,
(45)
f
(
x
k
+
|
γ
k
|
d
k
)
≤
f
(
x
k
)
+
δ
|
γ
k
|
2
∥
d
k
∥
2
,
holds, then we let α
k
=
|
γ
k
|. Otherwise we let α
k be the largest scalar in the set {
|
γ
k
|
ρ
i
,
i
=
0,1
,
…
} such that inequality (45) is satisfied.


## 4.1. Computing Projection

In this paper, as in Gould et al. [34], instead of computing a basis for null space of matrix A, we choose to work directly with the matrix of constraint gradients, computing projections by normal equations. As the computation of the projection is a key step in the proposed method, following Gould et al. [34], this projection can be computed in an alternative way.Let(38)
g
+
=
-
P
g
,
P
=
I
-
A
T
(
A
A
T
)
-
1
A
.
We can express this as
(39)
g
+
=
-
g
+
A
T
v
,
where v is the solution of
(40)
A
A
T
v
=
A
g
.
Noting that (40) is the normal equation. Since A is a m
×
n matrix of rank m
(
m
≤
n
), A
A
T is symmetric positive definite matrix. We use the Doolittle (called LU) factorization of A
A
T to solve (40).For the matrixA is constant, the factorization of A
A
T needs to be carried out only once at the beginning of the iterative process. Using a Doolittle factorization of A
A
T, (40) can be computed in the following form:
(41)
L
(
U
T
v
)
=
A
g
⟺
{
L
y
=
A
g
U
T
v
=
y
,
where L, U is the Doolittle factor of A
A
T.


## 4.2. Computing Stepsize

The drawback of the Armijo line search is how to choose the initial stepsizeα
k. If α
k is too large then the procedure needs to call much more function evaluations. If α
k is too small then the efficiency of related algorithm will be decreased. Therefore, we should choose an adequate initial stepsize α
k at each iteration. In what follows, we propose a way to generate the initial stepsize.We first estimate the stepsize determined by the exact line search. Support at the moment thatf is twice continuously differentiable. We denote by G
(
x
) the Hessian of f at x and abbreviate G
(
x
k
) as G
k. Notice that the exact line search stepsize α
-
k satisfies
(42)
-
g
k
T
d
k
=
(
g
(
x
k
+
α
-
k
d
k
)
-
g
k
)
T
d
k
≈
α
-
k
d
k
T
G
k
d
k
.
This shows that scalar δ
k
≜
-
g
k
T
d
k
/
d
k
T
G
k
d
k is an estimation to α
-
k. To avoid the computation of the second derivative, we further estimate α
-
k by letting
(43)
γ
k
=
-
ϵ
k
g
k
T
d
k
d
k
T
(
g
(
x
k
+
ϵ
k
d
k
)
-
g
k
)
,
where positive sequence satisfies {
ϵ
k
}
→
0 as k
→
∞. Let the initial stepsize of the Armijo line search be an approximation to
(44)
δ
k
≜
-
g
k
T
d
k
d
k
T
G
k
d
k
≈
-
ϵ
k
g
k
T
d
k
d
k
T
(
g
(
x
k
+
ϵ
k
d
k
)
-
g
k
)
≜
γ
k
.
It is not difficult to see that if ϵ
k and ∥
d
k
∥ are sufficiently small, then δ
k and γ
k are good estimation to α
-
k.So to improve the efficiency of EMPRP method in practical computation, we utilize the following line search process.Line Search Process. If inequality,
(45)
f
(
x
k
+
|
γ
k
|
d
k
)
≤
f
(
x
k
)
+
δ
|
γ
k
|
2
∥
d
k
∥
2
,
holds, then we let α
k
=
|
γ
k
|. Otherwise we let α
k be the largest scalar in the set {
|
γ
k
|
ρ
i
,
i
=
0,1
,
…
} such that inequality (45) is satisfied.


## 5. Numerical Experiments

This section reports some numerical experiments. Firstly, we test the EMPRP method and compare it with the Rose gradient projection method in [1] on low dimensional problems. Secondly, we test the EMPRP method and compare it with the spectral gradient method in Martínez et al. [30] and the feasible Fletcher-Reeves conjugate gradient method in Li et al. [32] on large dimensional problems. In the line search process, we set ϵ
k
=
1
0
-
6, ρ
=
0.3, δ
=
0.02.The methods in the tables have the following meanings.(i)
“EMPRP” stands for the EMPRP method with the Armijio-type line search (20).
(ii)
“ROSE” stands for Rose gradient projection method in [1] with the Armijio-type line search (20). That is, in Algorithm 2, the direction d
k
=
-
P
g
k.
(iii)
“SPG” stands for the spectral gradient method with the nonmonotone line search in Martínez et al. [30], where M
=
10, P
=
2.
(iv)
“FFR” stands for the feasible modified Fletcher-Reeves conjugate gradient method with the Armijio-type line search in Li et al. [32].We stop the iteration if the condition∥
P
g
k
∥
≤
ε is satisfied, where ε
=
1
0
-
5. If the iteration number exceeds 1
0
5, we also stop the iteration. Then we call it failure. All of the algorithms are coded in Matlab 7.0 and run on a personal computer with a 2.0 GHZ CPU processor.


### 5.1. Numerical Comparison of EMPRP and ROSE

We test the performance of EMPRP and ROSE methods on the following test problems with given initial points. The results are listed in Table1. n stands for the dimension of tested problem and n
c stands for the number of constraints. We will report the following results: the CPU timeTime (in seconds), the number of iterationsIter, the number of gradient evaluationsGeval, and the number of function evaluationsFeval.Table 1
Test results for Problems1–5 with given initial points.
Name
n
n
c
EMPRP
ROSE
Time
Iter
Geval
Feval
Time
Iter
Geval
Feval
HS28
3
1
0.0156
20
22
21
0.0468
71
72
143
HS48
5
2
0.0156
26
28
27
0.0468
65
66
122
HS49
5
2
0.0156
29
30
30
0.0780
193
194
336
HS50
5
3
0.0156
22
23
23
0.0624
76
77
139
HS51
5
3
0.0156
15
16
16
0.0624
80
81
148
HS52
5
3
0.0156
30
31
31
0.0312
70
71
141
HS50E1
10
8
0.0156
16
17
17
0.0312
63
64
127
HS50E2
20
18
0.0156
15
16
16
0.0936
63
64
127Problem 1 (HS28 [35]).
The function HS28 in [35] is defined as follows:
(46)
f
(
x
)
=
(
x
1
+
x
2
)
2
+
(
x
2
+
x
3
)
2
,
s
.
t
.
x
1
+
2
x
2
+
3
x
3
-
1
=
0
,
with the initial point x
0
=
(
-
4,1
,
1
). The optimal solution x
*
=
(
0.5
,
-
0.5,0.5
) and optimal function value f
(
x
*
)
=
0.Problem 2 (HS48 [35]).
The function HS48 in [35] is defined as follows:
(47)
f
(
x
)
=
(
x
1
-
1
)
2
+
(
x
2
-
x
3
)
2
+
(
x
4
-
x
5
)
2
,
s
.
t
.
x
1
+
x
2
+
x
3
+
x
4
+
x
5
-
5
=
0
,
x
3
+
2
(
x
4
+
x
5
)
+
3
=
0
,
with the initial point x
0
=
(
3,5
,
-
3,2
,
-
2
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0.Problem 3 (HS49 [35]).
The function HS49 in [35] is defined as follows:
(48)
f
(
x
)
=
(
x
1
-
x
2
)
2
+
(
x
3
-
1
)
2
+
(
x
4
-
1
)
4
+
(
x
5
-
1
)
6
,
s
.
t
.
x
1
+
x
2
+
x
3
+
4
x
4
-
7
=
0
,
x
3
+
5
x
5
-
6
=
0
,
with the initial point x
0
=
(
10,7
,
2
,
-
3,0.8
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0.Problem 4 (HS50 [35]).
The function HS50 in [35] is defined as follows:
(49)
f
(
x
)
=
(
x
1
-
x
2
)
2
+
(
x
2
-
x
3
)
2
+
(
x
3
-
x
4
)
2
+
(
x
4
-
x
5
)
2
,
s
.
t
.
x
1
+
2
x
2
+
3
x
3
-
6
=
0
,
x
2
+
2
x
3
+
3
x
4
-
6
=
0
,
x
3
+
2
x
4
+
3
x
5
-
6
=
0
,
with the initial point x
0
=
(
35
,
-
31,11,5
,
-
5
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0. Moreover, we extend the dimension of function HS51 [35] to 10, 20 with the initial point x
0
=
(
35
,
-
31,11
,
…
). The optimal solution x
*
=
(
1,1
,
…
,
1
) and optimal function value f
(
x
*
)
=
0.Problem 5 (HS51 [35]).
The function HS51 in [35] is defined as follows:
(50)
f
(
x
)
=
(
x
1
-
x
2
)
2
+
(
x
2
+
x
3
-
2
)
2
+
(
x
4
-
1
)
2
+
(
x
5
-
1
)
2
,
s
.
t
.
x
1
+
3
x
2
-
4
=
0
,
x
3
+
x
4
-
2
x
5
=
0
,
x
2
-
x
5
=
0
,
with the initial point x
0
=
(
2.5,0.5,2
,
-
1,0.5
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0.From Table1, we can see that the EMPRP method performs better than the Rosen gradient projection method in [1], which implies that the EMPRP method can improve the computational efficiency of the Rosen gradient projection method for solving linear equality constrained optimization problems.


### 5.2. Numerical Comparison of EMPRP, FFR, and SPCG

In this subsection, we test the EMPRP method and compare it with the spectral gradient method (called SPCG) in Martínez et al. [30] and the feasible Fletcher-Reeves conjugate gradient method (called FFR) in Li et al. [32] on the following large dimensional problems with given initial points. The results are listed in Tables 2, 3, 4, 5, and 6. We will report the following results: the CPU timeTime (in seconds), the number of iterationsIter.Table 2
Test results for Problem6 with given initial points.
k
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
50
99
49
0.0568
73
0.0660
80
0.0256
70
100
199
99
0.1048
103
0.1060
120
0.0756
90
200
399
199
0.0868
108
0.2660
123
0.0904
97
300
599
299
0.2252
121
0.4260
126
0.7504
123
400
799
399
0.3142
121
0.5150
126
0.9804
153
500
999
499
0.4045
138
0.7030
146
1.4320
176
1000
1999
999
2.6043
138
2.1560
146
3.3468
198
2000
3999
1999
8.2608
138
6.8280
146
9.1266
216
3000
5999
2999
22.4075
138
15.1720
146
28.2177
276
4000
7999
3999
40.1268
138
35.0460
146
56.0604
324
5000
9999
4999
105.6252
138
85.0460
146
128.1504
476Table 3
Test results for Problem7 with given initial points.
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
200
99
0.1468
83
0.1679
94
0.1286
79
400
199
0.2608
94
0.2860
103
0.2266
90
600
299
0.6252
121
0.8422
132
0.7504
133
800
399
1.4075
123
1.6510
138
1.4177
149
1000
499
3.280
141
2.7190
146
2.8790
168
2000
999
8.4045
189
4.6202
202
5.1280
190
3000
1499
12.0042
219
9.7030
248
10.7864
260
4000
1999
17.2608
254
13.4255
288
19.1266
316
5000
2499
20.6252
321
19.0940
330
29.1504
383Table 4
Test results for Problem8 with given initial points.
k
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
50
99
49
0.0668
78
0.0750
83
0.0286
75
100
199
99
0.0988
113
0.1462
130
0.0826
106
200
399
199
0.1978
123
0.2960
133
0.1864
124
300
599
299
0.3436
128
0.5260
136
0.3504
156
400
799
399
0.4142
134
0.7143
136
0.5804
186
500
999
499
0.6039
152
0.9030
158
0.9331
228
1000
1999
999
2.9065
152
2.9570
158
3.1260
268
2000
3999
1999
8.3408
152
7.8280
158
8.2266
298
3000
5999
2999
19.6086
152
17.4350
158
19.8672
330
4000
7999
3999
46.3268
152
38.1460
158
56.1256
368
5000
9999
4999
75.3972
152
58.3867
158
125.7680
398Table 5
Test results for Problem9 with given initial points.
k
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
50
99
49
0.0568
65
0.0640
70
0.0266
62
100
199
99
0.0868
109
0.1362
125
0.0726
103
200
399
199
0.2110
120
0.2862
128
0.2064
124
300
599
299
0.3250
127
0.5062
132
0.4524
160
400
799
399
0.4543
138
0.7456
139
0.6804
192
500
999
499
0.6246
156
0.9268
155
1.0876
258
1000
1999
999
3.9245
156
3.4268
162
3.4560
279
2000
3999
1999
9.3404
156
8.6240
162
8.6280
320
3000
5999
2999
20.6125
156
19.6548
162
20.8656
358
4000
7999
3999
48.2890
156
44.4330
162
57.7680
386
5000
9999
4999
95.4680
156
83.8650
162
128.8760
420Table 6
Test results for Problem10 with given initial points.
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
200
99
0.1842
88
0.1984
98
0.1488
92
400
199
0.2908
104
0.3260
113
0.2348
100
600
299
0.8256
132
0.9422
142
0.9804
182
800
399
1.6078
136
1.7512
148
2.6177
259
1000
499
2.9801
148
2.8192
156
3.1790
268
2000
999
7.8045
199
5.1202
212
8.1288
320
3000
1499
12.8042
248
9.9035
256
14.7862
360
4000
1999
19.2432
304
14.4258
298
22.1268
386
5000
2499
29.6846
382
20.1932
378
32.1422
393Problem 6.
Given a positive integerk, the function is defined as follows:
(51)
f
(
x
)
=
1
2
∑
i
=
1
k
-
2
‍
(
x
k
+
i
+
1
-
x
k
+
i
)
2
,
s
.
t
.
x
k
+
i
-
x
i
+
1
+
x
i
=
i
,
i
=
1
,
…
,
k
-
1
,
with the initial point x
0
=
(
1,2
,
…
,
k
,
2,3
,
…
,
k
). The optimization function value f
(
x
*
)
=
0. This problem comes from Martínez et al. [30].Problem 7.
Given a positive integern, the function is defined as follows:
(52)
f
(
x
)
=
∑
i
=
1
n
‍
cos
⁡
(
2
π
x
i
*
sin
(
π
20
)
)
,
s
.
t
.
x
i
-
x
i
+
1
=
0.4
i
=
1
,
…
,
n
-
1
,
with the initial point x
0
=
(
1,0.6,0.2
,
…
,
1
-
0
.
4
n
-
1
). This problem comes from Asaadi [36] and is called MAD6.Problem 8.
Given a positive integerk, the function is defined as follows:
(53)
f
(
x
)
=
1
2
∑
i
=
1
k
-
2
‍
(
x
k
+
i
+
1
-
x
k
+
i
)
4
,
s
.
t
.
x
k
+
i
-
x
i
+
1
+
x
i
=
i
,
i
=
1
,
…
,
k
-
1
,
with the initial point x
0
=
(
1,2
,
…
,
k
,
2,3
,
…
,
k
). The optimization function value f
(
x
*
)
=
0.Problem 9.
Given a positive integerk, the function is defined as follows:
(54)
f
(
x
)
=
∑
i
=
1
k
-
2
‍
100
(
x
k
+
i
+
1
-
x
k
+
i
)
2
+
(
1
-
x
k
+
i
)
2
,
s
.
t
.
x
k
+
i
-
x
i
+
1
+
x
i
=
i
,
i
=
1
,
…
,
k
-
1
,
with the initial point x
0
=
(
1,2
,
…
,
k
,
2,3
,
…
,
k
). The optimization function value f
(
x
*
)
=
0.Problem 10.
Given a positive integern, the function is defined as follows:
(55)
f
(
x
)
=
∑
i
=
1
n
‍
cos
⁡
2
(
2
π
x
i
*
sin
(
π
20
)
)
,
s
.
t
.
x
i
-
x
i
+
1
=
0.4
i
=
1
,
…
,
n
-
1
,
with the initial point x
0
=
(
1,0.6,0.2
,
…
,
1
-
0.4
*
(
n
-
1
)
).From Tables2–6, we can see the EMPRP method and the FFR method in [32] perform better than the SPCG method in Martínez et al. [30] for solving large-scale linear equality constrained optimization problems, as the EMPRP method and the FFR method all are first order methods. But the SPCG method in Martínez et al. [30] needs to compute B
k with quasi-Newton method in which the approximate Hessians satisfy a weak secant equation. However, as the EMPRP method also needs to compute projection, the FFR method in [32] performs better than the EMPRP method when the test problem becomes large.


## 5.1. Numerical Comparison of EMPRP and ROSE

We test the performance of EMPRP and ROSE methods on the following test problems with given initial points. The results are listed in Table1. n stands for the dimension of tested problem and n
c stands for the number of constraints. We will report the following results: the CPU timeTime (in seconds), the number of iterationsIter, the number of gradient evaluationsGeval, and the number of function evaluationsFeval.Table 1
Test results for Problems1–5 with given initial points.
Name
n
n
c
EMPRP
ROSE
Time
Iter
Geval
Feval
Time
Iter
Geval
Feval
HS28
3
1
0.0156
20
22
21
0.0468
71
72
143
HS48
5
2
0.0156
26
28
27
0.0468
65
66
122
HS49
5
2
0.0156
29
30
30
0.0780
193
194
336
HS50
5
3
0.0156
22
23
23
0.0624
76
77
139
HS51
5
3
0.0156
15
16
16
0.0624
80
81
148
HS52
5
3
0.0156
30
31
31
0.0312
70
71
141
HS50E1
10
8
0.0156
16
17
17
0.0312
63
64
127
HS50E2
20
18
0.0156
15
16
16
0.0936
63
64
127Problem 1 (HS28 [35]).
The function HS28 in [35] is defined as follows:
(46)
f
(
x
)
=
(
x
1
+
x
2
)
2
+
(
x
2
+
x
3
)
2
,
s
.
t
.
x
1
+
2
x
2
+
3
x
3
-
1
=
0
,
with the initial point x
0
=
(
-
4,1
,
1
). The optimal solution x
*
=
(
0.5
,
-
0.5,0.5
) and optimal function value f
(
x
*
)
=
0.Problem 2 (HS48 [35]).
The function HS48 in [35] is defined as follows:
(47)
f
(
x
)
=
(
x
1
-
1
)
2
+
(
x
2
-
x
3
)
2
+
(
x
4
-
x
5
)
2
,
s
.
t
.
x
1
+
x
2
+
x
3
+
x
4
+
x
5
-
5
=
0
,
x
3
+
2
(
x
4
+
x
5
)
+
3
=
0
,
with the initial point x
0
=
(
3,5
,
-
3,2
,
-
2
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0.Problem 3 (HS49 [35]).
The function HS49 in [35] is defined as follows:
(48)
f
(
x
)
=
(
x
1
-
x
2
)
2
+
(
x
3
-
1
)
2
+
(
x
4
-
1
)
4
+
(
x
5
-
1
)
6
,
s
.
t
.
x
1
+
x
2
+
x
3
+
4
x
4
-
7
=
0
,
x
3
+
5
x
5
-
6
=
0
,
with the initial point x
0
=
(
10,7
,
2
,
-
3,0.8
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0.Problem 4 (HS50 [35]).
The function HS50 in [35] is defined as follows:
(49)
f
(
x
)
=
(
x
1
-
x
2
)
2
+
(
x
2
-
x
3
)
2
+
(
x
3
-
x
4
)
2
+
(
x
4
-
x
5
)
2
,
s
.
t
.
x
1
+
2
x
2
+
3
x
3
-
6
=
0
,
x
2
+
2
x
3
+
3
x
4
-
6
=
0
,
x
3
+
2
x
4
+
3
x
5
-
6
=
0
,
with the initial point x
0
=
(
35
,
-
31,11,5
,
-
5
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0. Moreover, we extend the dimension of function HS51 [35] to 10, 20 with the initial point x
0
=
(
35
,
-
31,11
,
…
). The optimal solution x
*
=
(
1,1
,
…
,
1
) and optimal function value f
(
x
*
)
=
0.Problem 5 (HS51 [35]).
The function HS51 in [35] is defined as follows:
(50)
f
(
x
)
=
(
x
1
-
x
2
)
2
+
(
x
2
+
x
3
-
2
)
2
+
(
x
4
-
1
)
2
+
(
x
5
-
1
)
2
,
s
.
t
.
x
1
+
3
x
2
-
4
=
0
,
x
3
+
x
4
-
2
x
5
=
0
,
x
2
-
x
5
=
0
,
with the initial point x
0
=
(
2.5,0.5,2
,
-
1,0.5
). The optimal solution x
*
=
(
1,1
,
1,1
,
1
) and optimal function value f
(
x
*
)
=
0.From Table1, we can see that the EMPRP method performs better than the Rosen gradient projection method in [1], which implies that the EMPRP method can improve the computational efficiency of the Rosen gradient projection method for solving linear equality constrained optimization problems.


## 5.2. Numerical Comparison of EMPRP, FFR, and SPCG

In this subsection, we test the EMPRP method and compare it with the spectral gradient method (called SPCG) in Martínez et al. [30] and the feasible Fletcher-Reeves conjugate gradient method (called FFR) in Li et al. [32] on the following large dimensional problems with given initial points. The results are listed in Tables 2, 3, 4, 5, and 6. We will report the following results: the CPU timeTime (in seconds), the number of iterationsIter.Table 2
Test results for Problem6 with given initial points.
k
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
50
99
49
0.0568
73
0.0660
80
0.0256
70
100
199
99
0.1048
103
0.1060
120
0.0756
90
200
399
199
0.0868
108
0.2660
123
0.0904
97
300
599
299
0.2252
121
0.4260
126
0.7504
123
400
799
399
0.3142
121
0.5150
126
0.9804
153
500
999
499
0.4045
138
0.7030
146
1.4320
176
1000
1999
999
2.6043
138
2.1560
146
3.3468
198
2000
3999
1999
8.2608
138
6.8280
146
9.1266
216
3000
5999
2999
22.4075
138
15.1720
146
28.2177
276
4000
7999
3999
40.1268
138
35.0460
146
56.0604
324
5000
9999
4999
105.6252
138
85.0460
146
128.1504
476Table 3
Test results for Problem7 with given initial points.
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
200
99
0.1468
83
0.1679
94
0.1286
79
400
199
0.2608
94
0.2860
103
0.2266
90
600
299
0.6252
121
0.8422
132
0.7504
133
800
399
1.4075
123
1.6510
138
1.4177
149
1000
499
3.280
141
2.7190
146
2.8790
168
2000
999
8.4045
189
4.6202
202
5.1280
190
3000
1499
12.0042
219
9.7030
248
10.7864
260
4000
1999
17.2608
254
13.4255
288
19.1266
316
5000
2499
20.6252
321
19.0940
330
29.1504
383Table 4
Test results for Problem8 with given initial points.
k
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
50
99
49
0.0668
78
0.0750
83
0.0286
75
100
199
99
0.0988
113
0.1462
130
0.0826
106
200
399
199
0.1978
123
0.2960
133
0.1864
124
300
599
299
0.3436
128
0.5260
136
0.3504
156
400
799
399
0.4142
134
0.7143
136
0.5804
186
500
999
499
0.6039
152
0.9030
158
0.9331
228
1000
1999
999
2.9065
152
2.9570
158
3.1260
268
2000
3999
1999
8.3408
152
7.8280
158
8.2266
298
3000
5999
2999
19.6086
152
17.4350
158
19.8672
330
4000
7999
3999
46.3268
152
38.1460
158
56.1256
368
5000
9999
4999
75.3972
152
58.3867
158
125.7680
398Table 5
Test results for Problem9 with given initial points.
k
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
50
99
49
0.0568
65
0.0640
70
0.0266
62
100
199
99
0.0868
109
0.1362
125
0.0726
103
200
399
199
0.2110
120
0.2862
128
0.2064
124
300
599
299
0.3250
127
0.5062
132
0.4524
160
400
799
399
0.4543
138
0.7456
139
0.6804
192
500
999
499
0.6246
156
0.9268
155
1.0876
258
1000
1999
999
3.9245
156
3.4268
162
3.4560
279
2000
3999
1999
9.3404
156
8.6240
162
8.6280
320
3000
5999
2999
20.6125
156
19.6548
162
20.8656
358
4000
7999
3999
48.2890
156
44.4330
162
57.7680
386
5000
9999
4999
95.4680
156
83.8650
162
128.8760
420Table 6
Test results for Problem10 with given initial points.
n
n
c
EMPRP
FFR
SPCG
Time
Iter
Time
Iter
Time
Iter
200
99
0.1842
88
0.1984
98
0.1488
92
400
199
0.2908
104
0.3260
113
0.2348
100
600
299
0.8256
132
0.9422
142
0.9804
182
800
399
1.6078
136
1.7512
148
2.6177
259
1000
499
2.9801
148
2.8192
156
3.1790
268
2000
999
7.8045
199
5.1202
212
8.1288
320
3000
1499
12.8042
248
9.9035
256
14.7862
360
4000
1999
19.2432
304
14.4258
298
22.1268
386
5000
2499
29.6846
382
20.1932
378
32.1422
393Problem 6.
Given a positive integerk, the function is defined as follows:
(51)
f
(
x
)
=
1
2
∑
i
=
1
k
-
2
‍
(
x
k
+
i
+
1
-
x
k
+
i
)
2
,
s
.
t
.
x
k
+
i
-
x
i
+
1
+
x
i
=
i
,
i
=
1
,
…
,
k
-
1
,
with the initial point x
0
=
(
1,2
,
…
,
k
,
2,3
,
…
,
k
). The optimization function value f
(
x
*
)
=
0. This problem comes from Martínez et al. [30].Problem 7.
Given a positive integern, the function is defined as follows:
(52)
f
(
x
)
=
∑
i
=
1
n
‍
cos
⁡
(
2
π
x
i
*
sin
(
π
20
)
)
,
s
.
t
.
x
i
-
x
i
+
1
=
0.4
i
=
1
,
…
,
n
-
1
,
with the initial point x
0
=
(
1,0.6,0.2
,
…
,
1
-
0
.
4
n
-
1
). This problem comes from Asaadi [36] and is called MAD6.Problem 8.
Given a positive integerk, the function is defined as follows:
(53)
f
(
x
)
=
1
2
∑
i
=
1
k
-
2
‍
(
x
k
+
i
+
1
-
x
k
+
i
)
4
,
s
.
t
.
x
k
+
i
-
x
i
+
1
+
x
i
=
i
,
i
=
1
,
…
,
k
-
1
,
with the initial point x
0
=
(
1,2
,
…
,
k
,
2,3
,
…
,
k
). The optimization function value f
(
x
*
)
=
0.Problem 9.
Given a positive integerk, the function is defined as follows:
(54)
f
(
x
)
=
∑
i
=
1
k
-
2
‍
100
(
x
k
+
i
+
1
-
x
k
+
i
)
2
+
(
1
-
x
k
+
i
)
2
,
s
.
t
.
x
k
+
i
-
x
i
+
1
+
x
i
=
i
,
i
=
1
,
…
,
k
-
1
,
with the initial point x
0
=
(
1,2
,
…
,
k
,
2,3
,
…
,
k
). The optimization function value f
(
x
*
)
=
0.Problem 10.
Given a positive integern, the function is defined as follows:
(55)
f
(
x
)
=
∑
i
=
1
n
‍
cos
⁡
2
(
2
π
x
i
*
sin
(
π
20
)
)
,
s
.
t
.
x
i
-
x
i
+
1
=
0.4
i
=
1
,
…
,
n
-
1
,
with the initial point x
0
=
(
1,0.6,0.2
,
…
,
1
-
0.4
*
(
n
-
1
)
).From Tables2–6, we can see the EMPRP method and the FFR method in [32] perform better than the SPCG method in Martínez et al. [30] for solving large-scale linear equality constrained optimization problems, as the EMPRP method and the FFR method all are first order methods. But the SPCG method in Martínez et al. [30] needs to compute B
k with quasi-Newton method in which the approximate Hessians satisfy a weak secant equation. However, as the EMPRP method also needs to compute projection, the FFR method in [32] performs better than the EMPRP method when the test problem becomes large.


## 6. Conclusions

In this paper, we propose a new conjugate gradient projection method for solving linear equality constrained optimization problem (1), which combines the two-term modified Polak-Ribière-Polyak (PRP) conjugate gradient method in Cheng [7] with the Rosen projection method. The proposed method also can be regarded as an extension of the recently developed two-term modified Polak-Ribière-Polyak (PRP) conjugate gradient method in Cheng [7]. Under some mild conditions, we show that it is globally convergent with the Armijio-type line search.



---

*Source: 921364-2014-08-06.xml*