# A Three-Term Gradient Descent Method with Subspace Techniques

Authors: Shengwei Yao; Yuping Wu; Jielan Yang; Jieqiong Xu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

We proposed a three-term gradient descent method that can be well applied to address the optimization problems in this article. The search direction of the obtained method is generated in a specific subspace. Specifically, a quadratic approximation model is applied in the process of generating the search direction. In order to reduce the amount of calculation and make the best use of the existing information, the subspace was made up of the gradient of the current and prior iteration point and the previous search direction. By using the subspace-based optimization technology, the global convergence result is established under Wolfe line search. The results of numerical experiments show that the new method is effective and robust.


---

## Body

## 1. Introduction

Gradient descent and conjugate gradient (CG) methods have profound significance for dealing with unconstrained optimization problems:(1)minx∈ℜnfx,where f:Rn⟶R is a continuous-differential function. They are widely used because of the low storage requirements and the strong convergence property. Starting from an initial iteration point x0∈ℜn, in each iteration, the method produces an approximate solution sequence xk of (1):(2)xk+1=xk+αkdk,k≥0,in which xk is the current iteration point, αk≥0 is the step length, and dk is the search direction that usually has the following form (for typical CG methods):(3)dk=−gk,ifk=0,−gk+βkdk−1,ifk≥1,where gk=▽fxk is the gradient of fx at xk and βk is the CG parameter. The step-size αk is usually determined by performing a specific line search, among which Wolfe line search [1, 2] is one of the most commonly used:(4)fxk+αkdk−fxk≤ραkgkTdk,and(5)gk+1Tdk≥σgkTdk,where 0<ρ≤σ<1. Sometimes, the strong Wolfe line search given in (4) and(6)gk+1Tdk≤σgkTdk,is also widely used in the CG method for the establishment of convergence results. Different choices of βk form different versions of the CG methods. The research results of conjugate gradient algorithm are very rich, including PRP, HS, LS, and DY [3–10]. For a detailed survey of conjugate gradient methods, refer to [11].Recently, subspace technique has attracted more and more researchers’s attention. Various subspace techniques are applied to construct different approaches to deal with various optimization problems. For detailed description of subspace technique, refer to [12–14]. In [15], Yuan and Stoer came up with the SMCG method by using subspace technique in the conjugate gradient method. Specifically, a two-dimensional subspace Ωk+1=Spangk+1,sk is using in [15], to determine the search direction, that is,(7)dk+1=ξkgk+1+φksk,where ξk and φk are parameters and sk=xk+1−xk. In [16, 17], Li et al. obtained the values of ξk and φk by minimizing the dynamically selected conic approximate model and tensor model, respectively. In order to solve nonlinear optimization problems, Conn et al. [18] brought up a class of iterated-subspace minimization methods. Similar to Yuan’s idea [15], Yang et al. [19] raised a new CG method in the same subspace Ωk+1.For better convergence and robust numerical performance, some authors pay attention to study conjugate gradient methods with different forms. Zhang et al. [20] presented a three-term conjugate gradient method, which possesses sufficient descent property without line search. And, they further extended two-variant method and established the global convergence results for general function under the standard Wolfe line search. In [21], Narushima et al. proposed a specific three-term CG method, drawing on the idea of multistep quasi-Newton method. Deng and Wan [22] put forward a three-term CG algorithm, in which the direction is formed by gk+1, yk=gk+1−gk, and dk. For some other three-term conjugate gradient methods, refer to [23–27].The outline of the article is shown below. In Section2, we use the technique of subspace minimization to derive the search direction on the subspace constituted by −gk+1,sk,gk. We elaborate the proposed algorithm in Section 3. Section 4 provides the convergence analysis of the given algorithm under some suitable conditions. In Section 5, the numerical experiments compared with other methods are presented.


## 2. Derivation of the Search Direction

Different from the abovementioned subspaceΩk+1=Span−gk+1,sk, in this paper, the following subspace(8)Ωk+1=Span−gk+1,sk,gk,is used to construct the search direction. In order to simplify the calculation process, for each iteration point xk+1, the following quadratic model is used to approximate the function fx(9)mind∈Ωk+1ϕk+1d=gk+1Td+12dTBk+1d,where Bk+1 can be viewed as an approximation of Hessian matrix. Moreover, Bk+1 is supposed to be positive definite and meet quasi-Newton equation Bk+1sk=yk. Model ϕk+1d has two advantages, which is not only a good approximation of fx [14] but also convenient to minimize in the subspace Ωk+1. Since gk+1 and gk are usually not collinear, we discuss the case of dimensions 3 and 2.Case I. dim (Ωk+1) = 3.In this case, the direction has the form(10)dk+1=−gk+1+aksk+bkgk,whereakandbk are parameters to be calculated. Adding dk+1 (10) to the minimizing problem (9), we get the following minimizing problem:(11)minak,bk∈ℜϕk+1−gk+1+aksk+bkgk,thenak and bk are the solutions of the following linear system:(12)akskTyk+bkgkTyk=gk+1Tyk−gk+1Tsk,akgkTyk+bkgkTBk+1gk=gk+1TBk+1gk−gk+1Tgk.To solve system (12), we need to estimate two quantities ηk=gkTBk+1gk and ωk=gk+1TBk+1gk. Inspired by BBCG [28], we adopt(13)ηk=gkTBk+1gk=32yk2gk2skTyk.Next, we choose the BFGS [29–32] update initialized with the identity matrix to compute ωk:(14)ωk=gk+1TBk+1gk=gk+1TI+ykykTskTyk−skskTskTskgk=gk+1Tgk+gkTykgk+1TykskTyk−gkTskgk+1TskskTsk.This choice not only retains useful information but also gives numerical results that perform better than the scaling matrixskTyk/skTskI. Substituting (13) and (14) into the linear system (12), we get(15)akskTyk+bkgkTyk=gk+1Tyk−gk+1Tsk,akgkTyk+bkηk=ωk−gk+1Tgk.Combining (13), the determinant of the system (15) is calculated as(16)Δk=ηkskTyk−gkTyk2=32yk2gk2−gkTyk2>0.Then,ak and bk are obtained as(17)ak=1Δkηkgk+1Tyk−gk+1Tsk−gkTykωk−gk+1Tgk,bk=1ΔkskTykωk−gk+1Tgk−gkTykgk+1Tyk−gk+1Tsk.Case II. dim(Ωk+1) = 2.By observing numerical experiments, we find thatspan−gk+1,sk produces better numerical results. In this case, we chose Ωk+1=span−gk+1,sk as the subspace. The direction is expressed as(18)dk+1=−gk+1+aksk.Substituting (18) into (9), we get(19)minak∈ℜϕk+1−gk+1+aksk.Then, the solution of (19) can be expressed as(20)ak=gk+1TBk+1sk−gk+1TskskTBk+1sk=gk+1Tyk−gk+1TskskTyk.Therefore,(21)dk+1=−gk+1+aksk=−gk+1+gk+1Tyk−gk+1TskskTyksk.If it is an exact line search, namely,gk+1Tsk=0, then, from (17) and (21), we get(22)dk+1=−gk+1+gk+1TykskTyksk,which meansak=gk+1Tyk/skTyk,bk=0, and the obtained method is degraded to the HS method (Hestenes and Stiefel) [4].


## 3. The Proposed TCGS Algorithm

This section is mainly to elaborate the three-term CG method with subspace techniques (TCGS), in which the acceleration scheme [33] is used (Algorithm 1).Algorithm 1:TCGS.
Step 1: givenx0∈ℜn and ϵ>0, set d0:=−g0 and k:=0.Step 2: ifgk≤ϵ holds, then stop; else, go to step 3.Step 3: determine the step-sizeαk by Wolfe line search, which means that conditions (4) and (5) hold.Step 4: generatexk+1 by using the acceleration scheme [33], and compute gk+1, fxk+1, and sk=xk+1−xk.Step 5: if dim(Ωk+1) = 2, compute dk+1 by (21), and go to step 6. If dim(Ωk+1) = 3, compute dk+1 by (10) and (17), and go to step 6.Step 6: setk:=k+1, and go to step 2.


## 4. Convergence Analysis

The main content of this section is to study the convergence properties of the TCGS algorithm. Some necessary assumptions for the objective function are given as follows.Assumption 1.
The level setD=x∈ℜn:fx≤fx0 is bounded.Assumption 2.
Suppose thatf:Rn⟶R is continuous-differential, and its gradient gx is Lipschitz continuous with the constant L>0,i.e.,(23)gx−gy≤Lx−y,x,y∈ℜn.
Based on the above assumptions, it can be showed that there exists a constantΓ>0 such that(24)gx≤Γ,x∈D.
It is well known that, for optimization algorithm, the relevant properties of the search direction are very important for the convergence of the algorithm. Firstly, we will study some properties of the search direction generated by the TCGS algorithm. The following lemmas show that the direction is decreasing, and Dai–Liao conjugacy condition is satisfied.Lemma 1.
Suppose thatBk+1>0. Then, dk+1 generated by the TCGS algorithm is a descent direction.Proof.
According to (9), we can get ϕk+10=0. Since Bk+1>0 and dk+1 is generated by the TCGS algorithm, ϕk+1dk+1≤0. Furthermore,(25)gk+1Tdk+1≤−12dk+1TBk+1dk+1<0.Lemma 2.
The search directiondk+1 satisfies the Dai–Liao conjugacy condition with t=1, namely, ykTdk+1=−gk+1Tsk.Lemma 3.
Suppose thatdk is generated by the proposed TCGS algorithm and the step size αk possesses the conditions (4) and (5), then(26)αk≥1−σgkTdkLdk2.Proof.
Based on condition (5) and assumption (23), we get(27)σ−1gkTdk≤ykTdk≤ykdk≤αkLdk2.
SincegkTdk<0,σ<1, we prove it.Lemma 4.
Assume that Assumptions1 and 2 hold. Consider the algorithm TCGS in which Wolfe line search is used to compute the step size αk. Then, the Zoutendijk condition [34] holds:(28)∑k=0∞gkTdk2dk2<+∞.Proof.
Combining equation (4) and Lemma 3, we have(29)fxk−fxk+1≥−ραkgkTdk≥ρ1−σgkTdk2Ldk2.
Condition (29) and Assumption 1 deduce (28) directly.Lemma 5.
Suppose that the objective functionfx satisfies Assumptions 1 and 2, consider the algorithm TCGS in which the strong Wolfe line search (4) and (6) is used to compute the step size αk. If(30)∑k≤11dk2=+∞,holds, then(31)limk⟶∞infgk=0.Theorem 1.
Under the Assumptions1 and 2, consider the sequence xk generated by algorithm TSGS, αk satisfies the conditions (4) and (6). For uniformly convex function fx, i.e., there exists a constant μ>0 such that(32)∇fx−∇fyTx−y≥μx−y2,x,y∈N.Then, (31) holds.Proof.
From (23) and (32), we get, respectively,(33)yk≤Lsk,ykTsk≥μsk2.
On the basis of (33), combined with Cauchy inequality, it follows that(34)μsk2≤ykTsk≤yksk,i.e.μsk≤yk.
Furthermore, add the triangle inequality and (24), and we have(35)gk+1Tyk−gk+1Tsk≤gk+1Tyk+gk+1Tsk≤LΓsk+Γsk=ΓL+1sk,(36)ωk−gk+1Tgk≤gk+1TykgkTykykTsk+gk+1TskgkTskskTsk≤Γyk2gkμsk2+Γsk2gksk2≤ΓL2sk2gkμsk2+Γgk=ΓL2μ+1gk.
Next, we analyze the convergence in two cases:Case I. dim(Ωk+1) = 3.ak and bk are computed by (16), and using (24), (33), (35), and (36), we get(37)ak≤23gk2yk2−2gkTyk232yk2gk2skTykgk+1Tyk−gk+1sk+gkTykωk−gk+1Tgk≤1skTyk11−2gkTyk2/3gk2yk2gk+1Tyk−gk+1sk+2gkTyk3gk2yk2−2gkTyk2ωk−gk+1Tgk≤1μsk23ΓL+1sk+2gkTykgk2yk2ΓL2μ+1gk≤3μsk2ΓL+1sk+2gkykΓL2μ+1gk≤3μΓL+11sk+2μskΓL2μ+1=3μΓL+1+2μΓL2μ+11sk≡M11sk.Similarly, we obtain(38)bk≤23gk2yk2−2gkTyk2skTykωk−gk+1Tgk+gkTykgk+1Tyk−gk+1sk≤2skTyk3gk2yk2−2gkTyk2ωk−gk+1Tgk+2gkTyk3gk2yk2−2gkTyk2gk+1Tyk−gk+1sk≤2skTykgk2yk2ΓL2μ+1gk+2gkTykgk2yk2ΓL+1sk≤2skgkykΓL2μ+1+2gkykΓL+1sk≤2μΓL2μ+11gk+2μΓL+11gk≡M21gk.Therefore,(39)dk+1≤gk+1+aksk+bkgk≤Γ+M1+M2.Case II. dim(Ωk+1) = 2.Using (20), (24), and (33), we obtain(40)ak≤gk+1Tyk+gk+1TskykTsk≤ΓLsk+Γskμsk2=ΓL+1μ1sk≡M31sk.Therefore,(41)dk+1≤gk+1+aksk≤Γ+M3.From Lemma3, (31) holds.


## 5. Numerical Results

This section aims to observe the performance of the TCGS algorithm through numerical experiments and verify the effectiveness of the algorithm in dealing with unconstrained problems. For experimental purposes, we compared the numerical performance of TCGS with the PRP and MTHREECG [22] methods, in which MTHREECG has a structure similar to CGS, and PRP is a classic and effective CG method.In [22], Deng and Wan presented a similar three-term conjugate gradient method (MTHREECG) with the following form:(42)dk+1=−gk+1−δ∗ksk−ζ∗kyk,δ∗k=1−min1,yk2skTykgk+1TskskTyk−gk+1TykskTyk,ζ∗k=gk+1TskskTyk.We chose a total of 75 test functions, and all the test functions come from [35]. The dimension of each function is from 1000, 2000, … to 10000 for the numerical experiments. The code is written by Fortran and available at https://camo.ici.ro/neculai/THREECG/threecg.for [36]. The default parameter values of the algorithm are consistent with [36].The performance profile introduced by Dolan and Moré [37] is one of the most used tools for evaluating the performance of different methods. In this paper, we use it to investigate the numerical performance of the proposed TCGS algorithm.The performance profile for the number of iterations can be seen in Figure1. Looking at Figure 1, it can be found that the TCGS algorithm can solve about 78% of the test problems with the least iterations. With the increasing factor τ, TCGS method outperforms both MTHREECG and PRP methods. Figure 2 represents the performance profile with respect to the number of function evaluations. The result shows the similar performance with the result in Figure 1, in which TCGS also outperforms both MTHREECG and PRP methods. From the numerical experiments, it can be seen that the proposed TCGS method is efficient and robust in dealing with a set of unconstrained test problems.Figure 1
Performance profile based on iterations.Figure 2
Performance profile based on function evaluations.


## 6. Conclusion

By using the idea of subspace minimization, we come up with a new type of subspace gradient descent method in this paper. In our method, the subspace is spanned by−gk+1,sk,gk, and the quadratic approximation of the objective function is minimized to obtain the search direction. Therefore, the direction has the form dk+1=−gk+1+aksk+bkgk, where the values of ak and bk are computed by discussing in two cases. In addition, we prove the descent property of the direction dk and show that Dai–Liao conjugacy condition is satisfied. Under the Wolf line search, the convergence of the proposed TCGS algorithm is established. Observing the numerical results, the performance of the TCGS algorithm in a set of unconstrained problems is competitive.



---

*Source: 8867309-2021-01-07.xml*