# Global Convergence of a Modified LS Method

Authors: Liu JinKui; Du Xianglin
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

The LS method is one of the effective conjugate gradient methods in solving the unconstrained optimization problems. The paper presents a modified LS method on the basis of the famous LS method and proves the strong global convergence for the uniformly convex functions and the global convergence for general functions under the strong Wolfe line search. The numerical experiments show that the modified LS method is very effective in practice.


---

## Body

## 1. Introduction

The conjugate gradient method is one of the most common methods used in the optimization, which is especially effective in solving the unconstrained optimization problem:(1.1)min⁡x∈Rnf(x),
where f:Rn→R is continuously differentiable nonlinear function.The LS method introduced by Liu and Storey [1] is one of the conjugate gradient methods, and its iteration formulas are as follows: (1.2)xk+1=xk+αkdk,(1.3)dk={-gk,fork=1;-gk+βkdk-1,fork≥2;(1.4)βk=-gkT(gk-gk-1)dk-1Tgk-1,
where gk is the gradient of f at xk; αk>0 is a step length which is determined by some line search; dk is the search direction.The convergence properties of the LS method have been studied extensively. For example, Yu et al. [2] proposed a modified LS method called the LS1 method in this paper, in which parameter βk satisfies the following formula:
(1.5)βkLS1={‖gk‖2-|gkTgk-1|ς|gkTdk-1|-gk-1Tdk-1if‖gk‖2≥|gkTgk-1|,0else.
They proved the global convergence property of the LS1 method under the Wolfe line search and verified that the LS1 method was very effective in solving the large unconstrained optimization problems. Liu et al. [3] further studied the LS method on the basis of [2] and proposed the parameter βk:(1.6)βkLS2={gkT(gk-gk-1)ρ|gkTdk-1|-gk-1Tdk-1ifmin⁡⁡{1,ρ-1-ξ}⋅‖gk‖2>|gkTgk-1|,0else,
where ρ>1+ξ, and ξ is sufficiently small positive number. The corresponding method is called the LS2 method in this paper. Jinkui Liu, among others, proved the global convergence properties of the LS2 method under the Wolfe line search and showed that the achievements of the LS2 method was comparable with the PRP+ method.In this paper, a modified LS method is proposed on the basis of [2], which can guarantee generate the sufficient descent direction in each step under the strong Wolfe line search. Moreover, the new method has the strong global convergence properties for uniformly convex functions and the global convergence properties for ordinary functions.


## 2. The Sufficient Descent Property of the New Method

MLS Method
Step 1.
Datax1∈Rn, ε≥0. Set d1=-g1, if ∥g1∥≤ε, then stop.Step 2.
Computeαk by the strong Wolfe line search (δ∈(0,1/2),σ∈(δ,1)):
(2.1)f(xk+αkdk)≤f(xk)+δαkgkTdk,|g(xk+αkdk)Tdk|≤-σgkTdk.Step 3.
Letxk+1=xk+αkdk, gk+1=g(xk+1), if ∥gk+1∥≤ε, then stop.Step 4.
Computedk+1 by (1.3), and generate βk+1 by
(2.2)βk+1=max⁡⁡{0,‖gk+1‖2-|gk+1Tgk|u|gk+1Tdk|-gkTdk-νgk+1Tsk+1u|gk+1Tdk|-gkTdk},
where sk+1=xk+1-xk, u≥1, ν≥0.Step 5.
Setk=k+1, go to Step 2.Theorem 2.1.
Let the sequences{gk} and {dk} be generated by MLS method, then
(2.3)gkTdk<-(1-σ)‖gk‖2,∀k∈N+.Proof.
The conclusion can be proved by induction. Since-g1Td1/∥g1∥2=1, the conclusion holds for k=1. Now, we assume that the conclusion is true for k-1, for k≥2. We need to prove that the conclusion holds for k.
Multiplying (1.3) by gkT, we have
(2.4)gkTdk=-‖gk‖2+βkgkTdk-1.
From (2.2), if βk=0, then gkTdk=-∥gk∥2≤-(1-σ)∥gk∥2; if βk=(∥gk∥2-|gkTgk-1|)/(u|gkTdk-1|-gk-1Tdk-1)-νgkTsk/(u|gkTdk-1|-gk-1Tdk-1)>0, the proof is divided into two parts.(i)
IfgkTdk-1≤0, then we have gkTdk≤-∥gk∥2≤-(1-σ)∥gk∥2.
IfgkTdk-1>0, then we get
(2.5)gkTdk=-‖gk‖2+(‖gk‖2-|gkTgk-1|u|gkTdk-1|-gk-1Tdk-1-νgkTsku|gkTdk-1|-gk-1Tdk-1)⋅gkTdk-1≤-‖gk‖2-ναk-1(gkTdk-1)2u|gkTdk-1|-gk-1Tdk-1-|gkTgk-1|u|gkTdk-1|-gk-1Tdk-1⋅gkTdk-1+‖gk‖2-gk-1Tdk-1⋅gkTdk-1≤-‖gk‖2-ναk-1(gkTdk-1)2u|gkTdk-1|-gk-1Tdk-1-|gkTgk-1|u|gkTdk-1|-gk-1Tdk-1⋅gkTdk-1+‖gk‖2-gk-1Tdk-1⋅(-σgk-1Tdk-1)=-(1-σ)‖gk‖2-ναk-1(gkTdk-1)2u|gkTdk-1|-gk-1Tdk-1-|gkTgk-1|u|gkTdk-1|-gk-1Tdk-1⋅gkTdk-1<-(1-σ)‖gk‖2.
From the above inequalities, we obtain that the conclusion holds for k.


## 3. The Global Convergence Properties

In order to prove the global convergence of the MLS method, we assume that the objective functionf satisfies the following assumption.Assumption H.
(i) The level setL={x∈Rn∣f(x)≤f(x1)} is bounded, where x1 is the starting point.
(ii) In a neighborhoodV of L, f is continuously differentiable and its gradient g is Lipschitz continuous, namely, there exists a constant M>0 such that
(3.1)‖g(x)-g(y)‖≤M‖x-y‖,∀x,y∈V.From Assumption H, there exists a constantr̃>0, such that(3.2)‖g(x)‖≤r̃∀x∈V.Firstly, we prove that the MLS method has the strong global convergence property for uniformly convex functions.Lemma 3.1 (see [4]).
Suppose Assumption H holds. Consider any iteration of the form (1.2)-(1.3), where dk satisfies gkTdk<0 for k∈N+ and αk satisfies the strong Wolfe line search. If
(3.3)∑k≥11‖dk‖2=+∞,
then
(3.4)lim⁡k→+∞⁡inf⁡⁡‖gk‖=0.Theorem 3.2.
Suppose Assumption H holds. Let the sequences{gk} and {dk} be generated by MLS method. If f(x) is a uniformly convex function, that is, there exists t>0, for all x,y∈L, subject to
(3.5)(g(x)-g(y))T(x-y)≥t‖x-y‖2,
then
(3.6)lim⁡k→+∞⁡‖gk‖=0.Proof.
Fromf(x) is uniformly convex function and u≥1, we have
(3.7)u|gkTdk-1|-gk-1Tdk-1≥|gkTdk-1|-gk-1Tdk-1≥gkTdk-1-gk-1Tdk-1=dk-1T(gk-gk-1)≥tαk-1‖dk-1‖2.
From Lipschitz condition and (1.2), we have
(3.8)|‖gk‖2-|gkTgk-1||≤|‖gk‖2-gkTgk-1|≤‖gk‖⋅‖gk-gk-1‖≤‖gk‖⋅Mαk-1⋅‖dk-1‖.
Then, from (1.3), (2.2), and (3.2), we have
(3.9)‖dk‖≤‖gk‖+|‖gk‖2-|gkTgk-1|u|gkTdk-1|-gk-1Tdk-1-νgkTsku|gkTdk-1|-gk-1Tdk-1|⋅‖dk-1‖≤‖gk‖+|‖gk‖2-|gkTgk-1|-νgkTsk|u|gkTdk-1|-gk-1Tdk-1⋅‖dk-1‖≤‖gk‖+|‖gk‖2-gkTgk-1|+|νgkTsk|u|gkTdk-1|-gk-1Tdk-1⋅‖dk-1‖≤‖gk‖+‖gk‖⋅Mαk-1⋅‖dk-1‖+ν‖gk‖⋅αk-1⋅‖dk-1‖tαk-1‖dk-1‖2⋅‖dk-1‖≤r̃(1+M+νt).
From the above inequality, we obtain that the conclusion (3.3) holds. Then, from Lemma 3.1, the conclusion (3.4) holds; and f(x) is uniformly convex function, so the conclusion (3.6) holds.
Secondly, we prove that the MLS method has the global convergence for ordinary functions.Lemma 3.3 (see [5]).
Suppose Assumption H holds. Let the sequence{xk} be generated by the iteration of the form (1.2)-(1.3), where dk satisfies gkTdk<0 for k∈N+ and αk satisfies the strong Wolfe line search. Then,
(3.10)∑k≥1(gkTdk)2‖dk‖2<+∞.Lemma 3.4 (see [6]).
Suppose Assumption H holds. Consider any iteration of the form (1.2)-(1.3), where βk≥0, and αk satisfies the strong Wolfe line search and (2.3) holds. If there exists a constant r>0, such that
(3.11)‖gk‖≥r,∀k≥1,
then
(3.12)∑k≥2‖uk-uk-1‖2<+∞,
where uk=dk/∥dk∥.Lemma 3.5.
Consider any iteration of the form (1.2)-(1.3), where βk satisfies (2.2) and αk satisfies the strong Wolfe line search. Suppose that
(3.13)0<r≤‖gk‖≤r̃,∀k≥1.
Say that the MLS method has property (*), that is,(1)
if there exists constantb>1, such that |βk*|≤b,(2)
if there exists constantλ>0, such that ∥xk-xk-1∥≤λ, one has |βk*|≤1/2b.Proof.
Firstly, from the strong Wolfe line search, (2.3) and (3.13), we have
(3.14)u|gkTdk-1|-gk-1Tdk-1≥|gkTdk-1|-gk-1Tdk-1≥gkTdk-1-gk-1Tdk-1≥(σ-1)gk-1Tdk-1≥(1-σ)2‖gk-1‖2≥(1-σ)2r2.
From the Assumption H (i), there exists a positive constant a, such that ∥x∥≤a, for all x∈L.  So, from (2.3) and Lipschitz condition, we have
(3.15)|βk|≤|‖gk‖2-|gkTgk-1||u|gkTdk-1|-gk-1Tdk-1+|νgkTsk|u|gkTdk-1|-gk-1Tdk-1≤|‖gk‖2-gkTgk-1|(1-σ)2r2+|νgkTsk|(1-σ)2r2≤‖gk‖⋅‖gk-gk-1‖(1-σ)2r2+ν‖gk‖⋅‖sk‖(1-σ)2r2≤(M+ν)‖gk‖⋅‖sk‖(1-σ)2r2≤2ar̃(M+ν)(1-σ)2r2=b.
Define λ=(1-σ)2r2/2br̃(M+ν). Let ∥xk-xk-1∥≤λ, then from the above inequality, we also have
(3.16)|βk|≤λr̃(M+ν)(1-σ)2r2=12b.Lemma 3.6 (see [6]).
Suppose Assumption H holds. Consider any iteration of the form (1.2)-(1.3), where βk≥0, and αk satisfies the strong Wolfe line search and (2.3) holds. If βk has the property (*), and if there exists a constant r>0, subject to
(3.17)‖gk‖≥r∀k∈N+,
then there exits λ>0, for any Δ∈Z+ and k0∈Z+, and for all k≥k0, such that
(3.18)|Rk,Δλ|>Δ2,
where ℜk,Δλ≜{i∈Z+:k≤i≤k+Δ-1,∥xi-xi-1∥≥λ}, |ℜk,Δλ| denotes the number of the ℜk,Δλ.Lemma 3.7 (see [6]).
Suppose Assumption H holds. Consider any iteration of the form (1.2)-(1.3), where βk≥0, and αk satisfies the strong Wolfe line search and (2.3) holds. If βk has the property (*), then
(3.19)lim⁡inf⁡k→+∞⁡‖gk‖=0.From above Lemmas, we also have the following convergence results, that is, MLS method has the global convergence for ordinary functions.Theorem 3.8.
Suppose Assumption H holds. Consider the method (1.2)-(1.3), where βk is computed by (2.2), and αk satisfies the strong Wolfe line search and (2.3) holds, then
(3.20)lim⁡inf⁡k→+∞⁡‖gk‖=0.


## 4. Numerical Results

In this section, we test the MLS method for problems from [7], and we compare its performance to that of the LS method, LS1 method, and LS2 method under the strong Wolfe line search. The parameters δ=0.01, σ=0.1, ς=1.25, ρ=1.5, ξ=0.001, u=1.0, ν=0.35. The termination condition is ∥gk∥≤10-6 or It-max >9999. It-max denotes the Maximum number of iterations.The numerical results of our tests are reported in Table1. The column “Problem” represents the problem’s name in [7]. “Dim” denotes the dimension of the test problems. The detailed numerical results are listed in the form NI/NF/NG, where NI, NF, NG denote the number of iterations, function evaluations, and gradient evaluations, respectively. “NaN” means the calculation failure.Table 1
The numerical results of LS method, LS1 method, LS2 method, and MLS method.
ProblemDimLSLS1LS2MLSROSE225/101/7725/125/9837/163/13826/125/103FROTH210/53/3615/85/6812/78/6012/78/62BADSCP296/399/33822/183/16827/231/21422/170/156BADSCB214/70/5213/106/9611/88/7919/148/136BEALE212/47/3315/59/4612/56/4318/68/53JENSAM810/40/17NaN/NaN/NaN11/51/2812/51/28HELIX380/217/18539/125/10628/84/7137/128/111BRAD318/67/5228/98/8117/57/4621/75/60SING4841/2515/223793/357/31241/168/14395/345/303WOOD 144125/413/34143/189/15333/161/12957/237/200KOWOSB475/216/18985/300/26745/150/13266/249/217BD472/238/19327/136/10524/126/9330/144/109BIGGS6171/445/395201/754/664187/559/500143/520/462OSB211252/609/548585/1562/1394272/681/619638/1694/1508VARDIM56/57/386/57/386/57/386/57/38107/81/527/81/527/81/527/81/52WATSON5141/408/353110/359/31191/295/250100/329/282154486/12738/113262045/7346/65171465/5138/45401769/6365/5648PEN250536/1835/1580182/851/741163/809/694177/876/76510072/220/18579/252/20876/217/186103/300/251PEN110018/120/8331/195/15330/194/15127/184/14020018/157/11430/209/15929/211/16030/208/157TRIG10057/125/11560/143/13553/109/10260/143/13320068/163/15561/138/12561/136/12850/107/99ROSEX50025/101/7726/127/9937/163/13827/131/109100025/101/7726/127/9937/163/13827/131/109SINGX500215/712/618120/483/42863/281/24897/351/3061000105/344/295119/503/44763/281/248100/408/363BV5001940/3247/3246148/358/3251722/3057/3056135/339/3131000214/347/34616/32/30158/273/27216/35/33IE5007/15/86/13/76/13/76/13/710007/15/86/13/76/13/76/13/7TRID50035/78/7431/71/5735/78/7331/71/59100034/76/7235/79/7534/76/7235/79/75In order to rank the average performance of all the above conjugate gradient methods, one can compute the total number of function and gradient evaluation by the following formula:(4.1)Ntotal=NF+l*NG,
where l is some integer. According to the results on automatic differentiation [8, 9], the value of l can be set to 5. That is to say, one gradient evaluation is equivalent to five function evaluations if automatic differentiation is used.By (4.1), we compare the MLS method with LS method, LS1 method, and LS2 method as follows: for the ith problem, compute the total numbers of function evaluations and gradient evaluations required by the MLS method, LS method, LS1 method, and LS2 method, and denote them as Ntotal,i(MLS), Ntotal,i(LS), Ntotal,i(LS1), and Ntotal,i(LS2), respectively. Then, we calculate the ratio:
(4.2)γi(LS)=Ntotal,i(LS)Ntotal,i(MLS),γi(LS1)=Ntotal,i(LS1)Ntotal,i(MLS),γi(LS2)=Ntotal,i(LS2)Ntotal,i(MLS).If thei0th problem is not run by the method, we use a constant λ=max{γi(method)∣i∈S1} instead of γi0 (method), where S1 denotes the set of test problems which can be run by the method.The geometric mean of these ratios for VLS method over all the test problems are defined by(4.3)γ(LS)=(∏i∈Sγi(LS))1/|S|,γ(LS1)=(∏i∈Sγi(LS1))1/|S|,γ(LS2)=(∏i∈Sγi(LS2))1/|S|,
where S denotes the set of the test problems, and |S| denotes the number of elements in S. One advantage of the above rule is that the comparison is relative and hence does not be dominated by a few problems for which the method requires a great deal of function evaluations and gradient functions.From the above rule, it is clear thatγ(MLS)=1. The values of γ(LS), γ(LS1), and γ(LS2) are computed and listed in Table 2.Table 2
Relative efficiency of the MLS method, LS method, LS1 method and LS2 method.
MLSLSLS1LS211.30121.25491.0580From Table2, it is clear that the MLS method is superior to the LS method and the LS1 method, and it is comparable with the LS2 method for the given test problems. So, the MLS method has certain value of research.



---

*Source: 910303-2012-03-29.xml*