# Global Convergence of a Modified Spectral Conjugate Gradient Method

Authors: Huabin Jiang; Songhai Deng; Xiaodong Zheng; Zhong Wan
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

A modified spectral PRP conjugate gradient method is presented
for solving unconstrained optimization problems. The constructed search direction
is proved to be a sufficiently descent direction of the objective function. With an
Armijo-type line search to determinate the step length, a new spectral PRP conjugate
algorithm is developed. Under some mild conditions, the theory of global convergence is established. Numerical results demonstrate that this algorithm is promising,
particularly, compared with the existing similar ones.


---

## Body

## 1. Introduction

Recently, it is shown that conjugate gradient method is efficient and powerful in solving large-scale unconstrained minimization problems owing to its low memory requirement and simple computation. For example, in [1–17], many variants of conjugate gradient algorithms are developed. However, just as pointed out in [2], there exist many theoretical and computational challenges to apply these methods into solving the unconstrained optimization problems. Actually, 14 open problems on conjugate gradient methods are presented in [2]. These problems concern the selection of initial direction, the computation of step length, and conjugate parameter based on the values of the objective function, the influence of accuracy of line search procedure on the efficiency of conjugate gradient algorithm, and so forth.The general model of unconstrained optimization problem is as follows:(1.1)min⁡f(x),x∈Rn,
where f:Rn→R is continuously differentiable such that its gradient is available. Let g(x) denote the gradient of f at x, and let x0 be an arbitrary initial approximate solution of (1.1). Then, when a standard conjugate gradient method is used to solve (1.1), a sequence of solutions will be generated by(1.2)xk+1=xk+αkdk,k=0,1,…,
where αk is the steplength chosen by some line search method and dk is the search direction defined by(1.3)dk={-gkifk=0,-gk+βkdk-1ifk>0,
where βk is called conjugacy parameter and gk denotes the value of g(xk). For a strictly convex quadratical programming, βk can be appropriately chosen such that dk and dk-1 are conjugate with respect to the Hessian matrix of the objective function. If βk is taken by(1.4)βk=βkPRP=gkT(gk-gk-1)‖gk-1‖2,
where ∥·∥ stands for the Euclidean norm of vector, then (1.2)–(1.4) are called Polak-Ribiére-Polyak (PRP) conjugate gradient method (see [8, 18]).It is well known that PRP method has the property of finite termination when the objective function is a strong convex quadratic function combined with the exact line search. Furthermore, in [7], for a twice continuously differentiable strong convex objective function, the global convergence has also been proved. However, it seems to be nontrivial to establish the global convergence theory under the condition of inexact line search, especially for a general nonconvex minimization problem. Quite recently, it is noticed that there are many modified PRP conjugate gradient methods studied (see, e.g., [10–13, 17]). In these methods, the search direction is constructed to possess the sufficient descent property, and the theory of global convergence is established with different line search strategy. In [17], the search direction dk is given by(1.5)dk={-gkifk=0,-gk+βkPRPdk-1-θkyk-1ifk>0,
where(1.6)θk=gkTdk-1‖gk-1‖2,yk-1=gk-gk-1,sk-1=xk-xk-1.
Similar to the idea in [17], a new spectral PRP conjugate gradient algorithm will be developed in this paper. On one hand, we will present a new spectral conjugate gradient direction, which also possess the sufficiently descent feature. On the other hand, a modified Armijo-type line search strategy is incorporated into the developed algorithm. Numerical experiments will be used to make a comparison among some similar algorithms.The rest of this paper is organized as follows. In the next section, a new spectral PRP conjugate gradient method is proposed. Section3 will be devoted to prove the global convergence. In Section 4, some numerical experiments will be done to test the efficiency, especially in comparison with the existing other methods. Some concluding remarks will be given in the last section.


## 2. New Spectral PRP Conjugate Gradient Algorithm

In this section, we will firstly study how to determine a descent direction of objective function.Letxk be the current iterate. Let dk be defined by(2.1)dk={-gkifk=0,-θkgk+βkPRPdk-1ifk>0,
where βkPRP is specified by (1.4) and(2.2)θk=dk-1Tyk-1‖gk-1‖2-dk-1TgkgkTgk-1‖gk‖2‖gk-1‖2.It is noted thatdk given by (2.1) and (2.2) is different from those in [3, 16, 17], either for the choice of θk or for that of βk.We first prove thatdk is a sufficiently descent direction.Lemma 2.1.
Suppose thatdk is given by (2.1) and (2.2). Then, the following result
(2.3)gkTdk=-‖gk‖2
holds for any k≥0.Proof.
Firstly, fork=0, it is easy to see that (2.3) is true since d0=-g0.
Secondly, assume that(2.4)dk-1Tgk-1=-‖gk-1‖2
holds for k-1 when k≥1. Then, from (1.4), (2.1), and (2.2), it follows that
(2.5)gkTdk=-θk‖gk‖2+gkT(gk-gk-1)‖gk-1‖2dk-1Tgk=-dk-1T(gk-gk-1)‖gk-1‖2gkTgk+dk-1TgkgkTgk-1‖gk‖2‖gk-1‖2gkTgk+gkT(gk-gk-1)‖gk-1‖2dk-1Tgk=dk-1Tgk-1‖gk-1‖2gkTgk=‖gk‖2‖gk-1‖2(-‖gk-1‖2)=-‖gk‖2.
Thus, (2.3) is also true with k-1 replaced by k. By mathematical induction method, we obtain the desired result.From Lemma2.1, it is known that dk is a descent direction of f at xk. Furthermore, if the exact line search is used, then gkTdk-1=0; hence(2.6)θk=dk-1Tyk-1‖gk-1‖2-dk-1TgkgkTgk-1‖gk‖2‖gk-1‖2=-dk-1Tgk-1‖gk-1‖2=1.
In this case, the proposed spectral PRP conjugate gradient method reduces to the standard PRP method. However, it is often that the exact line search is time-consuming and sometimes is unnecessary. In the following, we are going to develop a new algorithm, where the search direction dk is chosen by (2.1)-(2.2) and the stepsize is determined by Armijio-type inexact line search.Algorithm 2.2 (Modified Spectral PRP Conjugate Gradient Algorithm).
We have the following steps.
Step 1.
Given constantsδ1, ρ∈(0,1), δ2>0, ϵ>0. Choose an initial point x0∈Rn. Let k:=0.Step 2.
If∥gk∥≤ϵ, then the algorithm stops. Otherwise, compute dk by (2.1)-(2.2), and go to Step 3.Step 3.
Determine a steplengthαk=max{ρj,j=0,1,2,…} such that
(2.7)f(xk+αkdk)≤f(xk)+δ1αkgkTdk-δ2αk2‖dk‖2.Step 4.
Setxk+1∶=xk+αkdk, and k∶=k+1. Return to Step 2.Sincedk is a descent direction of f at xk, we will prove that there must exist j0 such that αk=ρj0 satisfies the inequality (2.7).Proposition 2.3.
Letf:Rn→R be a continuously differentiable function. Suppose that d is a descent direction of f at x. Then, there exists j0 such that
(2.8)f(x+αd)≤f(x)+δ1αgTd-δ2α2‖d‖2,
where α=ρj0, g is the gradient vector of f at x, δ1, ρ∈(0,1) and δ2>0 are given constant scalars.Proof.
Actually, we only need to prove that a step lengthα is obtained in finitely many steps. If it is not true, then for all sufficiently large positive integer m, we have
(2.9)f(x+ρmd)-f(x)>δ1ρmgTd-δ2ρ2m‖d‖2.
Thus, by the mean value theorem, there is a θ∈(0,1) such that
(2.10)ρmg(x+θρmd)Td>δ1ρmgTd-δ2ρ2m‖d‖2.
It reads
(2.11)(g(x+θρmd)-g)Td>(δ1-1)gTd-δ2ρm‖d‖2.
When m→∞, it is obtained that
(2.12)(δ1-1)gTd<0.
From δ1∈(0,1), it follows that gTd>0. This contradicts the condition that d is a descent direction.Remark 2.4.
From Proposition2.3, it is known that Algorithm 2.2 is well defined. In addition, it is easy to see that more descent magnitude can be obtained at each step by the modified Armijo-type line search (2.7) than the standard Armijo rule.


## 3. Global Convergence

In this section, we are in a position to study the global convergence of Algorithm2.2. We first state the following mild assumptions, which will be used in the proof of global convergence.Assumption 3.1.
The level setΩ={x∈Rn|f(x)≤f(x0)} is bounded.Assumption 3.2.
In some neighborhoodN of Ω, f is continuously differentiable and its gradient is Lipschitz continuous, namely, there exists a constant L>0 such that
(3.1)‖g(x)-g(y)‖≤L‖x-y‖,∀x,y∈N.Since{f(xk)} is decreasing, it is clear that the sequence {xk} generated by Algorithm 2.2 is contained in a bounded region from Assumption 3.1. So, there exists a convergent subsequence of {xk}. Without loss of generality, it can be supposed that {xk} is convergent. On the other hand, from Assumption 3.2, it follows that there is a constant γ1>0 such that(3.2)‖g(x)‖≤γ1,∀x∈Ω.
Hence, the sequence {gk} is bounded.In the following, we firstly prove that the stepsizeαk at each iteration is large enough.Lemma 3.3.
With Assumption3.2, there exists a constant m>0 such that the following inequality
(3.3)αk≥m‖gk‖2‖dk‖2
holds for all k sufficiently large.Proof.
Firstly, from the line search rule (2.7), we know that αk≤1.
Ifαk=1, then we have ∥gk∥≤∥dk∥. The reason is that ∥gk∥>∥dk∥ implies that
(3.4)‖gk‖2>‖gk‖‖dk‖≥-gkTdk,
which contradicts (2.3). Therefore, taking m=1, the inequality (3.3) holds.
If0<αk<1, then the line search rule (2.7) implies that ρ-1αk does not satisfy the inequality (2.7). So, we have
(3.5)f(xk+ρ-1αkdk)-f(xk)>δ1αkρ-1gkTdk-δ2ρ-2αk2‖dk‖2.
Since(3.6)f(xk+ρ-1αkdk)-f(xk)=ρ-1αkg(xk+tkρ-1αkdk)Tdk=ρ-1αkgkTdk+ρ-1αk(g(xk+tkρ-1αkdk)-gk)Tdk≤ρ-1αkgkTdk+Lρ-2αk2‖dk‖2,
where tk∈(0,1) satisfies xk+tkρ-1αkdk∈N and the last inequality is from (3.2), it is obtained that
(3.7)δ1αkρ-1gkTdk-δ2ρ-2αk2‖dk‖2<ρ-1αkgkTdk+Lρ-2αk2‖dk‖2
due to (3.5) and (3.1). It reads
(3.8)(1-δ1)αkρ-1gkTdk+(L+δ2)ρ-2αk2‖dk‖2>0,
that is,
(3.9)(L+δ2)ρ-1αk‖dk‖2>(δ1-1)gkTdk.
Therefore,
(3.10)αk>(δ1-1)ρgkTdk(L+δ2)‖dk‖2.
From Lemma 2.1, it follows that
(3.11)αk>ρ(1-δ1)‖gk‖2(L+δ2)‖dk‖2.
Taking(3.12)m=min⁡{1,ρ(1-δ1)L+δ2},
then the desired inequality (3.3) holds.From Lemmas2.1 and 3.3 and Assumption 3.1, we can prove the following result.Lemma 3.4.
Under Assumptions3.1 and 3.2, the following results hold:
(3.13)∑k≥0‖gk‖4‖dk‖2<∞,(3.14)lim⁡k→∞αk2‖dk‖2=0.Proof.
From the line search rule (2.7) and Assumption 3.1, there exists a constant M such that
(3.15)∑k=0n-1(-δ1αkgkTdk+δ2αk2‖dk‖2)≤∑k=0n-1(f(xk)-f(xk+1))=f(x0)-f(xn)<2M.
Then, from Lemma 2.1, we have
(3.16)2M≥∑k=0n-1(-δ1αkgkTdk+δ2αk2‖dk‖2)=∑k=0n-1(δ1αk‖gk‖2+δ2αk2‖dk‖2)≥∑k=0n-1(δ1m‖gk‖2‖dk‖2‖gk‖2+δ2⋅m2⋅‖gk‖4‖dk‖4⋅‖dk‖2)=∑k=0n-1(δ1+δ2m)‖gk‖4‖dk‖2⋅m.
Therefore, the first conclusion is proved.
Since(3.17)2M≥∑k=0n-1(δ1αk‖gk‖2+δ2αk2‖dk‖2)≥δ2∑k=0n-1αk2‖dk‖2,
the series
(3.18)∑k=0∞αk2‖dk‖2
is convergent. Thus,
(3.19)lim⁡k→∞αk2‖dk‖2=0.
The second conclusion (3.14) is obtained.In the end of this section, we come to establish the global convergence theorem for Algorithm2.2.Theorem 3.5.
Under Assumptions3.1 and 3.2, it holds that
(3.20)lim⁡k→∞inf‖gk‖=0.Proof.
Suppose that there exists a positive constantϵ>0 such that
(3.21)‖gk‖≥ϵ
for all k. Then, from (2.1), it follows that
(3.22)‖dk‖2=dkTdk=(-θkgkT+βkPRPdk-1T)(-θkgk+βkPRPdk-1)=θk2‖gk‖2-2θkβkPRPdk-1Tgk+(βkPRP)2‖dk-1‖2=θk2‖gk‖2-2θk(dkT+θkgkT)gk+(βkPRP)2‖dk-1‖2=θk2‖gk‖2-2θkdkTgk-2θk2‖gk‖2+(βkPRP)2‖dk-1‖2=(βkPRP)2‖dk-1‖2-2θkdkTgk-θk2‖gk‖2.
Dividing by (gkTdk)2 in the both sides of this equality, then from (1.4), (2.3), (3.1), and (3.21), we obtain
(3.23)‖dk‖2‖gk‖4=(βkPRP)2‖dk-1‖2-2θkdkTgk-θk2‖gk‖2‖gk‖4=(gkT(gk-gk-1))2‖gk-1‖4‖dk-1‖2‖gk‖4-(θk-1)2‖gk‖2+1‖gk‖2≤‖gk-gk-1‖2‖gk-1‖4‖dk-1‖2‖gk‖2-(θk-1)2‖gk‖2+1‖gk‖2≤‖gk-gk-1‖2‖gk‖2‖dk-1‖2‖gk-1‖4+1‖gk‖2<L2αk-12‖dk-1‖2ϵ2‖dk-1‖2‖gk-1‖4+1‖gk‖2.
From (3.14) in Lemma 3.4, it follows that
(3.24)lim⁡k→∞αk-12‖dk-1‖2=0.
Thus, there exists a sufficient large number k0 such that for k≥k0, the following inequalities
(3.25)0≤αk-12‖dk-1‖2<ϵ2L2
hold.
Therefore, fork≥k0,
(3.26)‖dk‖2‖gk‖4≤‖dk-1‖2‖gk-1‖4+1‖gk‖2≤⋯≤‖dk0‖2‖gk0‖4+∑i=k0+1k1‖gi‖2<C0ϵ2+∑i=k0+1k1ϵ2=C0+k-k0ϵ2,
where C0=ϵ2∥dk0∥2/∥gk0∥2 is a nonnegative constant.
The last inequality implies(3.27)∑k≥1‖gk‖4‖dk‖2≥∑k>k0‖gk‖4‖dk‖2>ϵ2∑k>k01C0+k-k0=∞,
which contradicts the result of Lemma 3.4.
The global convergence theorem is established.


## 4. Numerical Experiments

In this section, we will report the numerical performance of Algorithm2.2. We test Algorithm 2.2 by solving the 15 benchmark problems from [19] and compare its numerical performance with that of the other similar methods, which include the standard PRP conjugate gradient method in [6], the modified FR conjugate gradient method in [16], and the modified PRP conjugate gradient method in [17]. Among these algorithms, either the updating formula or the line search rule is different from each other.All codes of the computer procedures are written in MATLAB 7.0.1 and are implemented on PC with 2.0 GHz CPU processor, 1 GB RAM memory, and XP operation system.The parameters are chosen as follows:(4.1)ϵ=10-6,ρ=0.75,δ1=0.1,δ2=1.In Tables1 and 2, we use the following denotations:Dim: the dimension of the objective function;GV: the gradient value of the objective function when the algorithm stops;NI: the number of iterations;NF: the number of function evaluations;CT: the run time of CPU;mfr: the modified FR conjugate gradient method in [16];prp: the standard PRP conjugate gradient method in [6];msprp: the modified PRP conjugate gradient method in [17];mprp: the new algorithm developed in this paper.Table 1
Comparison of efficiency with the other methods.
FunctionAlgorithmDimGVNINFCT(s)Rrosenbrockmfr28.8818e-00732870690.2970prp29.2415e-007760411891.4370mprp28.6092e-00712428160.0940msprp26.9643e-00712225970.1400Freudenstein and Rothmfr25.5723e-00723651100.2190prp27.1422e-007331187980.6250mprp22.4666e-0076719040.0940msprp28.6967e-0076214370.0780Brown badlymfr2————prp2————mprp27.9892e-007105102790.2030msprp27.6029e-0077071170.2660Bealemfr26.1730e-007747140.0780prp28.2455e-007292125680.4370mprp26.2257e-00713015390.0940msprp28.7861e-007918770.0470Powell singularmfr49.9827e-0074122105780.6870prp4————mprp49.6909e-007135652189645.2660msprp49.8512e-007118931695377.2500Woodmfr47.7937e-00726357870.2660prp49.9841e-0071284695012.3440mprp49.6484e-00728064320.1720msprp47.9229e-00740496430.4070Extended Powell singularmfr49.9827e-0074122105780.6800prp4————mprp49.6909e-007135652189645.5310msprp49.8512e-007118931695377.4070Broyden tridiagonalmfr44.8451e-007537840.0630prp46.6626e-0078744600.1180mprp45.8166e-007394300.0320msprp49.7196e-007527850.0780Table 2
Comparison of efficiency with the other methods.
FunctionAlgorithmDimGVNINFCT(s)Kowalik and Osbornemfr4————prp48.9521e-007833261911.2970mprp49.9698e-0076235354253.5940msprp49.9560e-0077059379764.9850Broyden bandedmfr68.9469e-007405050.0780prp68.4684e-00726896400.4840mprp68.9029e-00710213190.0940msprp69.3276e-007445560.0940Discrete boundarymfr69.1531e-0071075090.0780prp67.8970e-007269114490.4690mprp68.28079e-00715714730.0930msprp69.9436e-00716514710.1410Variably dimensionedmfr87.3411e-0075712330.1250prp87.3411e-00711374030.3290mprp89.0900e-0076915440.0780msprp87.3411e-0075712330.1100Broyden tridiagonalmfr99.1815e-00712921730.1250prp96.4584e-00711359150.2500mprp97.3529e-00718729670.1250msprp99.2363e-0078213040.1100Linear-rank1mfr109.7462e-0078437620.1720prp104.5647e-0079867650.2810mprp106.9140e-0075122160.0780msprp106.6630e-0075021620.1250Linear-full rankmfr127.6919e-0079360.0160prp128.2507e-0074719040.1090mprp127.6919e-0079360.0630msprp127.6919e-0079360.0150From the above numerical experiments, it is shown that the proposed algorithm in this paper is promising.


## 5. Conclusion

In this paper, a new spectral PRP conjugate gradient algorithm has been developed for solving unconstrained minimization problems. Under some mild conditions, the global convergence has been proved with an Armijo-type line search rule. Compared with the other similar algorithms, the numerical performance of the developed algorithm is promising.



---

*Source: 641276-2011-12-12.xml*