# Modified Three-Term Conjugate Gradient Method and Its Applications

Authors: Jiankun Liu; Shouqiang Du
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

We propose a modified three-term conjugate gradient method with the Armijo line search for solving unconstrained optimization problems. The proposed method possesses the sufficient descent property. Under mild assumptions, the global convergence property of the proposed method with the Armijo line search is proved. Due to simplicity, low storage, and nice convergence properties, the proposed method is used to solveM-tensor systems and a kind of nonsmooth optimization problems with l1-norm. Finally, the given numerical experiments show the efficiency of the proposed method.


---

## Body

## 1. Introduction

We consider the following unconstrained optimization problem:(1)minz∈Rnfz,where f:Rn→R is a continuous function. It is well-known that the nonlinear conjugate gradient method is one of the most effective methods for solving large-scale unconstrained optimization problems due to its simplicity and low storage [1–8]. Let z0 be the initial approximation of the solution to (1); the general format of the nonlinear conjugate gradient method is as follows:(2)zk+1=zk+αkdk,k=0,1,···,where αk can be obtained by some linear searches, i.e., [6–8], and search direction dk is computed by(3)dk=-gkifk=0,-gk+βkdk-1ifk≥1,where gk is the gradient of f at point zk and βk is a parameter. Different choices for the parameter βk correspond to different nonlinear conjugate gradient methods. The Fletcher-Reeves (FR) method, the Polak-Ribiere-Polyak (PRP) method, the Hestenes-Stiefel (HS) method, the Dai-Yuan (DY) method, and the Conjugate Descent (CD) method are some famous nonlinear conjugate gradient methods [1, 2, 9–12], and the parameters βk of them are, respectively, defined by(4)βkFR=gk2gk-12,βkPRP=gkTyk-1gk-12,βkHS=gkTyk-1dk-1Tyk-1,βkDY=gk2dk-1Tyk-1,βkCD=gk2-dk-1Tgk-1,where yk-1=gk-gk-1 and ∥·∥ is the Euclidean norm. Because of the good numerical performance of the conjugate gradient method, in recent years, the nonlinear three-term conjugate gradient method has been paid much attention by researchers, such as the three-term conjugate gradient method [5], the three-term form of the L-BFGS method [13], the three-term PRP conjugate gradient method [14], and the new-type conjugate gradient update parameter similar with βkPRP [15]. On the other hand, we know that the Armijo line search is widely used in solving optimization problems; i.e., see [8]. So, in this paper, we propose a new modified three-term conjugate gradient method with the Armijo line search. The proposed method is used to solve M-tensor systems [16, 17] and a kind of nonsmooth optimization problems with l1-norm [18–22].The remainder of this paper is organized as follows: In the next section, we give the new modified three-term conjugate gradient method. Firstly, we give the smooth case of the proposed method and prove the sufficient descent property and the global convergence property of it. Then, we give the nonsmooth case of the proposed method. In Section3, we present M-tensor systems and a kind of nonsmooth minimization problems with l1-norm, which can be solved by the proposed method. And, we also give some numerical results to show the efficiency of the proposed method. In Section 4, we give the conclusion of this paper.


## 2. Modified Three-Term Conjugate Gradient Method

In this section, we consider the nonlinear conjugate gradient method for solving (1); we discuss the problem in two cases: (1) f is a smooth function; (2) f is a nonsmooth function.


### 2.1. Smooth Case

Based on nonlinear conjugate gradient methods in [5, 8], we propose a modified three-term conjugate gradient method with the Armijo line search. We consider the search direction(5)d0=-g0,dk=-gk+βkdk-1+θkyk-1,where gk=∇f(zk) is the gradient of f at zk, yk-1=gk-gk-1, and(6)βk=gkTyk-1dk-12,(7)θk=-gkTdk-1dk-12.From (5), (6), and (7), we can obtain that(8)dkTgk=-gk2,∀k≥0.Now, we present the modified three-term conjugate gradient method.Algorithm 1 (modified three-term conjugate gradient method).
Step 0. Choose 0<σ<1,0<ρ<1,ε>0 and give an initial point z0∈Rn, let k=0, compute g0=∇f(z0), and let d0=-g0.
Step 1. If ∇f(zk)≤ε, stop; otherwise, go to Step 2.
Step 2. Compute the search direction dk by (5), where βk and θk are defined by (6) and (7).
Step 3. Compute αk by the Armijo line search, where αk=max{ρj,j=0,1,2,…,} and αk satisfies(9)fzk+αkdk-fzk≤σαkgkTdk.
Step 4. Compute zk+1=zk+αkdk, where dk is given in Step 2 and αk is given in Step 3.
Step 5. Set k=k+1 and go to Step 1.
Next, we will give the global convergence analysis of Algorithm1. Firstly, we give the following assumptions.Assumption 2.
The level setR0={z∈Rn∣f(z)≤f(z0)} is bounded; i.e., there exists a positive constant B>0 such that z≤B for all z∈R0.Assumption 3.
In the neighborhoodN of R0, f is continuously differentiable and its gradient g is Lipschitz continuous; that is, there exists a positive constant L>0, ∀x,y∈N, such that(10)gx-gy≤Lx-y.Remark 4.
Because{f(zk)} is a decreasing sequence, so the sequence {zk} generated by Algorithm 1 is contained in R0. And by Assumptions 2 and 3, we can easily obtain that there exists a positive constant γ such that(11)gk≤γ,∀z∈R0.Lemma 5.
Suppose{gk} and {dk} are generated by Algorithm 1, then(12)∑k=0∞gk4dk2<+∞.Proof.
Firstly, we prove that there exists a constantc>0 such that, for sufficiently large k,(13)αk≥cgk2dk2.The proof of (13) can be divided into two following cases.
Case 1 (αk=1). By (8) and the Cauchy inequality, gk2=dkTgk≤dkgk, then we have gk≤dk. Let c1≤1, then we obtain (13).
Case 2 (αk<1). Due to the linear search step, that is the Step 3 of Algorithm 1, ρ-1αk does not satisfy (9); i.e.,(14)fzk+ρ-1αkdk-fzk>σρ-1αkgkTdk.By Assumption 3 and the mean value theorem, there exists tk∈(0,1) such that (15)fzk+ρ-1αkdk-fzk=ρ-1αkgzk+tkρ-1αkdkTdk=ρ-1αkgkTdk+ρ-1αkgzk+tkρ-1αkdk-gkTdk≤ρ-1αkgkTdk+Lρ-2αk2dk2. By the above formula, (8) and (14), we have(16)αk≥1-σρgk2Ldk2.Let c=min{c1,(1-σ)ρ/L}, then we obtain (13).
By (9) and Assumption 2, we have(17)-∑k=1∞αkgkTdk<+∞.
From (8), (13), and (17), we have (18)-∑k=1∞αkgkTdk=∑k=1∞αkgk2≥∑k=1∞cgk4dk2, then we get(19)∑k=0∞gk4dk2<+∞. Hence, the result follows.Now we can get the global convergence of Algorithm1.Theorem 6.
Suppose{gk} and {dk} are generated by Algorithm 1, then(20)liminfk→∞gk=0.Proof.
Using the technique similar to Theorem 3.1 in [5], we can get this theorem.Remark 7.
The Armijo type line search [7] is given as follows:(21)fzk+αkdk-fzk≤σ1αkgkTdk-σ2αk2dk2,where αk=max{ρj,j=0,1,2,…,}, ρ∈(0,1), σ1∈(0,1), and σ2>0. The Wolfe type line search [6] is given as follows:(22)fzk+αkdk-fzk≤-ραk2dk2,gzk+αkdkTdk≥-2σαkdk2,where 0<σ<1,0<ρ<1. Obviously, Algorithm 1 is also true for the Armijo type line search and the Wolfe type line search.


### 2.2. Nonsmooth Case

In this subsection, by using smoothing function, we extend Algorithm1 to the nonsmooth case. Firstly, we give the definition of smoothing function.Definition 8.
Letf:Rn→R be a local Lipschitz continuous function. If ∀z∈Rn, ∀μ>0, and μ is fixed, f~(·,μ) is continuously differentiable and satisfies(23)limμ→0⁡f~z,μ=fz,then we call f~:Rn×R+→R is a smoothing function of f.Denoteg~k=∇f~(zk,μk). Now, we present the following smoothing modified three-term conjugate gradient method.Algorithm 9 (smoothing modified three-term conjugate gradient method).
Step 0. Choose 0<σ<1,0<ρ<1,ε>0,r>0,μ0>1,0<σ1<1 and give an initial point z0∈Rn, let k=0, compute g~0=∇f~(z0,μ0), and let d0=-g~0.
Step 1. If ∥g~k∥≤ε, stop; otherwise, go to Step 2.
Step 2. Compute the search direction dk by using βk and θk, where(24)βk=g~kTyk-1dk-12,θk=-g~kTdk-1dk-12,dk=-g~kifk=0,-g~k+βkdk-1+θkyk-1ifk≥1,where yk-1=g~k-g~k-1.
Step 3. Compute αk by the Armijo line search, where αk=max⁡{ρj,j=0,1,2,…,} and αk satisfies(25)f~zk+αkdk,μk-f~zk,μk≤σαkg~kTdk.
Step 4. Compute zk+1=zk+αkdk, if ∇f~(zk+1,μk)≥rμk, set μk+1=μk; otherwise, let μk+1=σ1μk.
Step 5. Set k=k+1 and go to Step 1.
Next, we give the global convergence analysis of Algorithm9.Theorem 10.
Suppose thatf~(·,μ) is a smoothing function of f. If for every fixed μ>0, f~(·,μ) satisfies Assumptions 2 and 3, then {zk} generated by Algorithm 9 satisfies(26)liminfk→∞⁡∇f~zk,μk-1=0.Proof.
DenoteK={k|μk+1=σ1μk}. If K is finite, then there exists an integer k¯ such that, for all k>k¯,(27)∇f~zk,μk-1≥rμk-1and μk=μk¯=μ¯. That is to solve(28)minz∈Rnf~z,μ¯.Hence, from Theorem 6, we get(29)liminfk→∞⁡∇f~zk,μ¯=0,which contradicts with (27). This shows that K must be infinite and limk→∞μk=0. Since K is infinite, we can assume that K={k0,k1,⋯} with k0<k1<⋯. Then we have(30)limi→∞⁡∇f~zki+1,μki≤rlimi→∞⁡μki=0.


## 2.1. Smooth Case

Based on nonlinear conjugate gradient methods in [5, 8], we propose a modified three-term conjugate gradient method with the Armijo line search. We consider the search direction(5)d0=-g0,dk=-gk+βkdk-1+θkyk-1,where gk=∇f(zk) is the gradient of f at zk, yk-1=gk-gk-1, and(6)βk=gkTyk-1dk-12,(7)θk=-gkTdk-1dk-12.From (5), (6), and (7), we can obtain that(8)dkTgk=-gk2,∀k≥0.Now, we present the modified three-term conjugate gradient method.Algorithm 1 (modified three-term conjugate gradient method).
Step 0. Choose 0<σ<1,0<ρ<1,ε>0 and give an initial point z0∈Rn, let k=0, compute g0=∇f(z0), and let d0=-g0.
Step 1. If ∇f(zk)≤ε, stop; otherwise, go to Step 2.
Step 2. Compute the search direction dk by (5), where βk and θk are defined by (6) and (7).
Step 3. Compute αk by the Armijo line search, where αk=max{ρj,j=0,1,2,…,} and αk satisfies(9)fzk+αkdk-fzk≤σαkgkTdk.
Step 4. Compute zk+1=zk+αkdk, where dk is given in Step 2 and αk is given in Step 3.
Step 5. Set k=k+1 and go to Step 1.
Next, we will give the global convergence analysis of Algorithm1. Firstly, we give the following assumptions.Assumption 2.
The level setR0={z∈Rn∣f(z)≤f(z0)} is bounded; i.e., there exists a positive constant B>0 such that z≤B for all z∈R0.Assumption 3.
In the neighborhoodN of R0, f is continuously differentiable and its gradient g is Lipschitz continuous; that is, there exists a positive constant L>0, ∀x,y∈N, such that(10)gx-gy≤Lx-y.Remark 4.
Because{f(zk)} is a decreasing sequence, so the sequence {zk} generated by Algorithm 1 is contained in R0. And by Assumptions 2 and 3, we can easily obtain that there exists a positive constant γ such that(11)gk≤γ,∀z∈R0.Lemma 5.
Suppose{gk} and {dk} are generated by Algorithm 1, then(12)∑k=0∞gk4dk2<+∞.Proof.
Firstly, we prove that there exists a constantc>0 such that, for sufficiently large k,(13)αk≥cgk2dk2.The proof of (13) can be divided into two following cases.
Case 1 (αk=1). By (8) and the Cauchy inequality, gk2=dkTgk≤dkgk, then we have gk≤dk. Let c1≤1, then we obtain (13).
Case 2 (αk<1). Due to the linear search step, that is the Step 3 of Algorithm 1, ρ-1αk does not satisfy (9); i.e.,(14)fzk+ρ-1αkdk-fzk>σρ-1αkgkTdk.By Assumption 3 and the mean value theorem, there exists tk∈(0,1) such that (15)fzk+ρ-1αkdk-fzk=ρ-1αkgzk+tkρ-1αkdkTdk=ρ-1αkgkTdk+ρ-1αkgzk+tkρ-1αkdk-gkTdk≤ρ-1αkgkTdk+Lρ-2αk2dk2. By the above formula, (8) and (14), we have(16)αk≥1-σρgk2Ldk2.Let c=min{c1,(1-σ)ρ/L}, then we obtain (13).
By (9) and Assumption 2, we have(17)-∑k=1∞αkgkTdk<+∞.
From (8), (13), and (17), we have (18)-∑k=1∞αkgkTdk=∑k=1∞αkgk2≥∑k=1∞cgk4dk2, then we get(19)∑k=0∞gk4dk2<+∞. Hence, the result follows.Now we can get the global convergence of Algorithm1.Theorem 6.
Suppose{gk} and {dk} are generated by Algorithm 1, then(20)liminfk→∞gk=0.Proof.
Using the technique similar to Theorem 3.1 in [5], we can get this theorem.Remark 7.
The Armijo type line search [7] is given as follows:(21)fzk+αkdk-fzk≤σ1αkgkTdk-σ2αk2dk2,where αk=max{ρj,j=0,1,2,…,}, ρ∈(0,1), σ1∈(0,1), and σ2>0. The Wolfe type line search [6] is given as follows:(22)fzk+αkdk-fzk≤-ραk2dk2,gzk+αkdkTdk≥-2σαkdk2,where 0<σ<1,0<ρ<1. Obviously, Algorithm 1 is also true for the Armijo type line search and the Wolfe type line search.


## 2.2. Nonsmooth Case

In this subsection, by using smoothing function, we extend Algorithm1 to the nonsmooth case. Firstly, we give the definition of smoothing function.Definition 8.
Letf:Rn→R be a local Lipschitz continuous function. If ∀z∈Rn, ∀μ>0, and μ is fixed, f~(·,μ) is continuously differentiable and satisfies(23)limμ→0⁡f~z,μ=fz,then we call f~:Rn×R+→R is a smoothing function of f.Denoteg~k=∇f~(zk,μk). Now, we present the following smoothing modified three-term conjugate gradient method.Algorithm 9 (smoothing modified three-term conjugate gradient method).
Step 0. Choose 0<σ<1,0<ρ<1,ε>0,r>0,μ0>1,0<σ1<1 and give an initial point z0∈Rn, let k=0, compute g~0=∇f~(z0,μ0), and let d0=-g~0.
Step 1. If ∥g~k∥≤ε, stop; otherwise, go to Step 2.
Step 2. Compute the search direction dk by using βk and θk, where(24)βk=g~kTyk-1dk-12,θk=-g~kTdk-1dk-12,dk=-g~kifk=0,-g~k+βkdk-1+θkyk-1ifk≥1,where yk-1=g~k-g~k-1.
Step 3. Compute αk by the Armijo line search, where αk=max⁡{ρj,j=0,1,2,…,} and αk satisfies(25)f~zk+αkdk,μk-f~zk,μk≤σαkg~kTdk.
Step 4. Compute zk+1=zk+αkdk, if ∇f~(zk+1,μk)≥rμk, set μk+1=μk; otherwise, let μk+1=σ1μk.
Step 5. Set k=k+1 and go to Step 1.
Next, we give the global convergence analysis of Algorithm9.Theorem 10.
Suppose thatf~(·,μ) is a smoothing function of f. If for every fixed μ>0, f~(·,μ) satisfies Assumptions 2 and 3, then {zk} generated by Algorithm 9 satisfies(26)liminfk→∞⁡∇f~zk,μk-1=0.Proof.
DenoteK={k|μk+1=σ1μk}. If K is finite, then there exists an integer k¯ such that, for all k>k¯,(27)∇f~zk,μk-1≥rμk-1and μk=μk¯=μ¯. That is to solve(28)minz∈Rnf~z,μ¯.Hence, from Theorem 6, we get(29)liminfk→∞⁡∇f~zk,μ¯=0,which contradicts with (27). This shows that K must be infinite and limk→∞μk=0. Since K is infinite, we can assume that K={k0,k1,⋯} with k0<k1<⋯. Then we have(30)limi→∞⁡∇f~zki+1,μki≤rlimi→∞⁡μki=0.


## 3. Applications

In this section, the applications of the proposed modified three-term conjugate gradient method are given. The conjugate gradient method is suitable for solving unconstrained optimization problems. In the first subsection, we consider theM-tensor systems, which can be transformed into the unconstrained minimization problem and solved by Algorithm 1. Then in the second subsection, we consider a kind of nonsmooth optimization problems with l1-norm, which can be solved by Algorithm 9. And in each subsection, the numerical results are given to show the feasibility of the proposed method.


### 3.1. Applications in SolvingM-Tensor Systems

In this subsection, we consider theM-tensor systems, which can be transformed into the general unconstrained minimization problem. We use Algorithm 1 to solve it. The problem of tensor systems [16, 17] is an important problem in tensor optimization [23–26]. We consider the tensor system(31)Azm-1=b,where A∈C[m,n]:=Cn×n×⋯×n and b∈Cn. Then the ith element of (31) is defined as(32)Azm-1i=∑i2,…,im=1naii2⋯imzi2⋯zim,1≤i≤n.And if z∈Cn∖0 and λ∈C satisfy(33)Azm-1=λzm-1,where(34)zm-1=z1m-1,z2m-1,…,znm-1T,then we call λ is an eigenvalue of A and z is a corresponding eigenvector of λ [25]. The spectral radius [26] of a tensor A is defined as(35)ρA=maxλ:λisaneigenvalueofA.Let L∈C[m,n] be the identity tensor [17], i.e.,(36)Li1i2…im=1,ifi1=i2=⋯=im,0,otherwise,for all 1≤i1,i2,…,im≤n. If there exists a nonnegative tensor B and a positive real number s≥ρ(B) such that A=sL-B, then the tensor A is called an M-tensor [16]. And if s>ρ(B), it is called a nonsingular M-tensor. Suppose A is a nonsingular M-tensor, then for every positive vector b, (31) has a unique positive solution [16]. Then (31) can be transformed into the following unconstrained minimization problem(37)minz∈Rn12Azm-1-b2.Now, we present numerical experiments for solvingM-tensor systems. Some examples are taken from [16]. We implement Algorithm 1 with the codes in Matlab Version R2014a and Tensor Toolbox Version 2.6 on a laptop with an Intel(R) Core(TM) i5-2520M CPU(2.50GHz) and RAM of 4.00GB. The parameters involved in the algorithm are taken as σ=0.2,ρ=0.25,ϵ=10-6,μ=0.6.Example 11.
Consider (31) with a 3rd-order 2-dimensional M-tensor, where A=sI-B∈Rn×n×n. And B contains the entries bijk=1 with i=1,2 and j,k≥i, and other entries are zeros. Let s=10, s>ρ(B). Hence A is a upper triangular nonsingular M-tensor. The starting point z0 is set to be rand(n,1) and b is set to be ones(n,1).The numerical results are given in Table1 and Figure 1.Table 1
The numerical results of Example11.
z 0 k t z ∗ 0.7577,0.7431 T 7 0.6055 0.3902,0.3332 T 0.3922,0.6555 T 6 0.4911 0.3902,0.3332 T 0.1712,0.7060 T 6 0.4553 0.3905,0.3335 T 0.8235,0.6948 T 6 0.4623 0.3902,0.3332 T 0.3171,0.9502 T 10 0.7561 0.3902,0.3335 T 0.3816,0.7655 T 6 0.4374 0.3905,0.3335 T 0.7952,0.1869 T 7 0.4651 0.3904,0.3334 T 0.4898,0.4456 T 4 0.3351 0.3905,0.3335 TFigure 1
Numerical results for Example11(n=2).Example 12.
Consider (31) with a 3rd-order M-tensor, where A=sI-B∈Rn×n×n with(38)bijk=cos⁡i+j+k.By ρ(B)≤max1≤i1≤nΣi2,i3=1nbi1i2i3<max1≤i1≤nΣi2,i3=1n1=n2, let s=n2, s>ρ(B). Hence A is a symmetric nonsingular M-tensor. The starting point z0 is set to be rand(n,1) and b is set to be ones(n,1).Whenn=2, the corresponding numerical results are given in Table 2 and Figure 2.Table 2
The numerical results of Example12.
z 0 k t z ∗ 0.8147,0.9058 T 6 2.8056 0.8103,0.7653 T 0.9575,0.9649 T 7 0.4469 0.8108,0.7658 T 0.9572,0.4854 T 8 0.4957 0.8106,0.7654 T 0.4218,0.9157 T 9 0.4930 0.8103,0.7652 T 0.7922,0.9595 T 7 0.4878 0.8106,0.7654 T 0.8491,0.9340 T 5 0.3502 0.8105,0.7654 T 0.6787,0.7577 T 6 0.3900 0.8107,0.7655 T 0.7431,0.3922 T 7 0.4123 0.8103,0.7656 TFigure 2
Numerical results for Example12(n=2).Whenn=5, the starting points z0 are set to be rand(n,1), then the corresponding numerical results are shown as follows: (39)z0=0.6463,0.7094,0.7547,0.2760,0.6797T,k=15,t=4.1352,z∗=0.3227,0.3169,0.3212,0.3195,0.3132T,z0=0.3404,0.5853,0.2238,0.7513,0.2551T,k=19,t=2.0446,z∗=0.3226,0.3168,0.3211,0.3194,0.3131T,z0=0.1386,0.1493,0.2575,0.8407,0.2543T,k=18,t=2.7024,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,z0=0.5308,0.7792,0.9340,0.1299,0.5688T,k=37,t=3.4322,z∗=0.3227,0.3169,0.3212,0.3195,0.3132T,z0=0.3112,0.5285,0.1656,0.6020,0.2630T,k=15,t=1.2784,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,z0=0.1818,0.2638,0.1455,0.1361,0.8693T,k=17,t=1.4333,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,z0=0.3510,0.5132,0.4018,0.0760,0.2399T,k=15,t=1.2209,z∗=0.3228,0.3169,0.3212,0.3195,0.3133T,z0=0.2417,0.4039,0.0965,0.1320,0.9421T,k=16,t=1.4087,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,Figure3 shows the numerical results of this example.Figure 3
Numerical results for Example12(n=5).


### 3.2. Applications in Solvingl1-Norm Problems

In this subsection, we consider a kind of nonsmooth optimization problems withl1-norm. This kind of nonsmooth optimization problems can be solved by Algorithm 9. We consider(40)minx∈Rn12Ax-b22+τx1,where A∈Rm×n(m≪n), b∈Rm, and τ>0 is a parameter to trade off both terms for minimization. This problem is widely used in compressed sensing, signal reconstruction, and some related problems [18–22, 27–29]. In this subsection, we translate (40) into the absolute value equation problem based on the equivalence between the linear complementary problem and the absolute value equation problem [30] and then use Algorithm 9 to solve it.We first give the transformation form of (40). As in [19, 21], let(41)ui=xi+,vi=-xi+,i=1,2,…,n, where (xi)+=maxxi,0. ∀x∈Rn, we set(42)x=u-v,u≥0,v≥0.Due to the definitionx1=∑i=1nxi, we get that(43)x1=enTu+enTv, where en=[1,1,…,1]T is an n-dimensional vector. Therefore, as in [19, 21], problem (40) can be rewritten as follows:(44)minz=u,vT≥012b-Az22+τenTu+τenTv. Then, the above problem can be transformed into(45)minz≥012zTHz+cTz,where z=(u,v)T,c=τe2n+-c¯c¯,c=ATb,H=ATA-ATA-ATAATA,e2n is a 2n-dimensional vector. Solving (45) is equivalent to solving the following linear complementary problem.To findz∈R2n, such that(46)z≥0,Hz+c≥0,zTHz+c=0,then (46) can be transformed into the following absolute value equation problem(47)H+Iz+c=H-Iz+c, that is,(48)minz∈R2nfz=12H+Iz+c-H-Iz+c2.By the smoothing approximation function of|(H-I)z+c|, i.e.,(49)Φiz,μ=H-Iz+ci2+μ2,μ∈R+,i=1,2,…,2n, then we get(50)minz∈R2nf~z,μ=12∑i=12nf~i2z,μ, where (51)f~iz,μ=H+Iz+ci-Φiz,μ,i=1,2,…,2n.Now, we give some numerical experiments of Algorithm9, which are also considered in [19, 21, 22, 27, 28]. The numerical results of all examples indicate that the modified three-term conjugate gradient method is also effective for solving the l1-norm minimization problem (40). In our numerical experiments, all codes run in Matlab R2014a. For Examples 13 and 14, the parameters used in Algorithm 9 are chosen as σ=σ1=0.2, r=0.5, ε=10-6, and ρ=0.4.Example 13.
Consider (40) with(52)A=111000⋯0001000111⋯0001......⋯..........⋯..........⋯....000000⋯1111m×n,τ=3,y=1,1,…,1T.In this example, we choose m=30,n=100. The numerical results are given in Figure 4.Figure 4
Numerical results for solving Example13 with Algorithm 9.Example 14.
Consider (40) with (53)A=4-10...0001⋯1-14-1......1⋯10-14......1⋯1........⋯.....4-10.⋯.....-14-1.⋯.000...0-141⋯1m×n,τ=10,y=1,1,…,1T.In this example, we take m=200,n=210. The numerical results are given in Figure 5.Figure 5
Numerical results for solving Example14 with Algorithm 9.Example 15.
Consider a typical compressed sensing problem with the form as (40), which is also considered in [21, 22, 27, 28]. We choose m=24, n=26, σ=0.5, ρ=0.4, r=0.5, ε=10-6, μ=5, and η=2. The original signal contains 520 randomly generated ±1 spikes. Further, the m×n matrix A is obtained by first filling it with independent samples of a standard Gaussian distribution and then orthogonalization of its rows. We choose σ2=10-4 and τ=0.1ATy∞. The numerical results are shown in Figure 6.Figure 6
Numerical results for solving Example15 with Algorithm 9.


## 3.1. Applications in SolvingM-Tensor Systems

In this subsection, we consider theM-tensor systems, which can be transformed into the general unconstrained minimization problem. We use Algorithm 1 to solve it. The problem of tensor systems [16, 17] is an important problem in tensor optimization [23–26]. We consider the tensor system(31)Azm-1=b,where A∈C[m,n]:=Cn×n×⋯×n and b∈Cn. Then the ith element of (31) is defined as(32)Azm-1i=∑i2,…,im=1naii2⋯imzi2⋯zim,1≤i≤n.And if z∈Cn∖0 and λ∈C satisfy(33)Azm-1=λzm-1,where(34)zm-1=z1m-1,z2m-1,…,znm-1T,then we call λ is an eigenvalue of A and z is a corresponding eigenvector of λ [25]. The spectral radius [26] of a tensor A is defined as(35)ρA=maxλ:λisaneigenvalueofA.Let L∈C[m,n] be the identity tensor [17], i.e.,(36)Li1i2…im=1,ifi1=i2=⋯=im,0,otherwise,for all 1≤i1,i2,…,im≤n. If there exists a nonnegative tensor B and a positive real number s≥ρ(B) such that A=sL-B, then the tensor A is called an M-tensor [16]. And if s>ρ(B), it is called a nonsingular M-tensor. Suppose A is a nonsingular M-tensor, then for every positive vector b, (31) has a unique positive solution [16]. Then (31) can be transformed into the following unconstrained minimization problem(37)minz∈Rn12Azm-1-b2.Now, we present numerical experiments for solvingM-tensor systems. Some examples are taken from [16]. We implement Algorithm 1 with the codes in Matlab Version R2014a and Tensor Toolbox Version 2.6 on a laptop with an Intel(R) Core(TM) i5-2520M CPU(2.50GHz) and RAM of 4.00GB. The parameters involved in the algorithm are taken as σ=0.2,ρ=0.25,ϵ=10-6,μ=0.6.Example 11.
Consider (31) with a 3rd-order 2-dimensional M-tensor, where A=sI-B∈Rn×n×n. And B contains the entries bijk=1 with i=1,2 and j,k≥i, and other entries are zeros. Let s=10, s>ρ(B). Hence A is a upper triangular nonsingular M-tensor. The starting point z0 is set to be rand(n,1) and b is set to be ones(n,1).The numerical results are given in Table1 and Figure 1.Table 1
The numerical results of Example11.
z 0 k t z ∗ 0.7577,0.7431 T 7 0.6055 0.3902,0.3332 T 0.3922,0.6555 T 6 0.4911 0.3902,0.3332 T 0.1712,0.7060 T 6 0.4553 0.3905,0.3335 T 0.8235,0.6948 T 6 0.4623 0.3902,0.3332 T 0.3171,0.9502 T 10 0.7561 0.3902,0.3335 T 0.3816,0.7655 T 6 0.4374 0.3905,0.3335 T 0.7952,0.1869 T 7 0.4651 0.3904,0.3334 T 0.4898,0.4456 T 4 0.3351 0.3905,0.3335 TFigure 1
Numerical results for Example11(n=2).Example 12.
Consider (31) with a 3rd-order M-tensor, where A=sI-B∈Rn×n×n with(38)bijk=cos⁡i+j+k.By ρ(B)≤max1≤i1≤nΣi2,i3=1nbi1i2i3<max1≤i1≤nΣi2,i3=1n1=n2, let s=n2, s>ρ(B). Hence A is a symmetric nonsingular M-tensor. The starting point z0 is set to be rand(n,1) and b is set to be ones(n,1).Whenn=2, the corresponding numerical results are given in Table 2 and Figure 2.Table 2
The numerical results of Example12.
z 0 k t z ∗ 0.8147,0.9058 T 6 2.8056 0.8103,0.7653 T 0.9575,0.9649 T 7 0.4469 0.8108,0.7658 T 0.9572,0.4854 T 8 0.4957 0.8106,0.7654 T 0.4218,0.9157 T 9 0.4930 0.8103,0.7652 T 0.7922,0.9595 T 7 0.4878 0.8106,0.7654 T 0.8491,0.9340 T 5 0.3502 0.8105,0.7654 T 0.6787,0.7577 T 6 0.3900 0.8107,0.7655 T 0.7431,0.3922 T 7 0.4123 0.8103,0.7656 TFigure 2
Numerical results for Example12(n=2).Whenn=5, the starting points z0 are set to be rand(n,1), then the corresponding numerical results are shown as follows: (39)z0=0.6463,0.7094,0.7547,0.2760,0.6797T,k=15,t=4.1352,z∗=0.3227,0.3169,0.3212,0.3195,0.3132T,z0=0.3404,0.5853,0.2238,0.7513,0.2551T,k=19,t=2.0446,z∗=0.3226,0.3168,0.3211,0.3194,0.3131T,z0=0.1386,0.1493,0.2575,0.8407,0.2543T,k=18,t=2.7024,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,z0=0.5308,0.7792,0.9340,0.1299,0.5688T,k=37,t=3.4322,z∗=0.3227,0.3169,0.3212,0.3195,0.3132T,z0=0.3112,0.5285,0.1656,0.6020,0.2630T,k=15,t=1.2784,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,z0=0.1818,0.2638,0.1455,0.1361,0.8693T,k=17,t=1.4333,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,z0=0.3510,0.5132,0.4018,0.0760,0.2399T,k=15,t=1.2209,z∗=0.3228,0.3169,0.3212,0.3195,0.3133T,z0=0.2417,0.4039,0.0965,0.1320,0.9421T,k=16,t=1.4087,z∗=0.3226,0.3168,0.3210,0.3193,0.3131T,Figure3 shows the numerical results of this example.Figure 3
Numerical results for Example12(n=5).


## 3.2. Applications in Solvingl1-Norm Problems

In this subsection, we consider a kind of nonsmooth optimization problems withl1-norm. This kind of nonsmooth optimization problems can be solved by Algorithm 9. We consider(40)minx∈Rn12Ax-b22+τx1,where A∈Rm×n(m≪n), b∈Rm, and τ>0 is a parameter to trade off both terms for minimization. This problem is widely used in compressed sensing, signal reconstruction, and some related problems [18–22, 27–29]. In this subsection, we translate (40) into the absolute value equation problem based on the equivalence between the linear complementary problem and the absolute value equation problem [30] and then use Algorithm 9 to solve it.We first give the transformation form of (40). As in [19, 21], let(41)ui=xi+,vi=-xi+,i=1,2,…,n, where (xi)+=maxxi,0. ∀x∈Rn, we set(42)x=u-v,u≥0,v≥0.Due to the definitionx1=∑i=1nxi, we get that(43)x1=enTu+enTv, where en=[1,1,…,1]T is an n-dimensional vector. Therefore, as in [19, 21], problem (40) can be rewritten as follows:(44)minz=u,vT≥012b-Az22+τenTu+τenTv. Then, the above problem can be transformed into(45)minz≥012zTHz+cTz,where z=(u,v)T,c=τe2n+-c¯c¯,c=ATb,H=ATA-ATA-ATAATA,e2n is a 2n-dimensional vector. Solving (45) is equivalent to solving the following linear complementary problem.To findz∈R2n, such that(46)z≥0,Hz+c≥0,zTHz+c=0,then (46) can be transformed into the following absolute value equation problem(47)H+Iz+c=H-Iz+c, that is,(48)minz∈R2nfz=12H+Iz+c-H-Iz+c2.By the smoothing approximation function of|(H-I)z+c|, i.e.,(49)Φiz,μ=H-Iz+ci2+μ2,μ∈R+,i=1,2,…,2n, then we get(50)minz∈R2nf~z,μ=12∑i=12nf~i2z,μ, where (51)f~iz,μ=H+Iz+ci-Φiz,μ,i=1,2,…,2n.Now, we give some numerical experiments of Algorithm9, which are also considered in [19, 21, 22, 27, 28]. The numerical results of all examples indicate that the modified three-term conjugate gradient method is also effective for solving the l1-norm minimization problem (40). In our numerical experiments, all codes run in Matlab R2014a. For Examples 13 and 14, the parameters used in Algorithm 9 are chosen as σ=σ1=0.2, r=0.5, ε=10-6, and ρ=0.4.Example 13.
Consider (40) with(52)A=111000⋯0001000111⋯0001......⋯..........⋯..........⋯....000000⋯1111m×n,τ=3,y=1,1,…,1T.In this example, we choose m=30,n=100. The numerical results are given in Figure 4.Figure 4
Numerical results for solving Example13 with Algorithm 9.Example 14.
Consider (40) with (53)A=4-10...0001⋯1-14-1......1⋯10-14......1⋯1........⋯.....4-10.⋯.....-14-1.⋯.000...0-141⋯1m×n,τ=10,y=1,1,…,1T.In this example, we take m=200,n=210. The numerical results are given in Figure 5.Figure 5
Numerical results for solving Example14 with Algorithm 9.Example 15.
Consider a typical compressed sensing problem with the form as (40), which is also considered in [21, 22, 27, 28]. We choose m=24, n=26, σ=0.5, ρ=0.4, r=0.5, ε=10-6, μ=5, and η=2. The original signal contains 520 randomly generated ±1 spikes. Further, the m×n matrix A is obtained by first filling it with independent samples of a standard Gaussian distribution and then orthogonalization of its rows. We choose σ2=10-4 and τ=0.1ATy∞. The numerical results are shown in Figure 6.Figure 6
Numerical results for solving Example15 with Algorithm 9.


## 4. Conclusion

In this paper, we propose a modified three-term conjugate gradient method and give the applications in solvingM-tensor systems and a kind of nonsmooth optimization problems with l1-norm. The global convergence of the proposed method is also given. Finally, we present some numerical experiments to demonstrate the efficiency of the proposed method.



---

*Source: 5976595-2019-04-17.xml*