# Two Improved Conjugate Gradient Methods with Application in Compressive Sensing and Motion Control

Authors: Min Sun; Jing Liu; Yaru Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

To solve the monotone equations with convex constraints, a novel multiparameterized conjugate gradient method (MPCGM) is designed and analyzed. This kind of conjugate gradient method is derivative-free and can be viewed as a modified version of the famous Fletcher–Reeves (FR) conjugate gradient method. Under approximate conditions, we show that the proposed method has global convergence property. Furthermore, we generalize the MPCGM to solve unconstrained optimization problem and offer another novel conjugate gradient method (NCGM), which satisfies the sufficient descent property without any line search. Global convergence of the NCGM is also proved. Finally, we report some numerical results to show the efficiency of two novel methods. Specifically, their practical applications in compressive sensing and motion control of robot manipulator are also investigated.


---

## Body

## 1. Introduction

Letℛ,ℛn, and ℛm×n be the sets of real numbers, n dimensional real column vectors, and m × n dimensional real matrices, respectively. This paper is concerned with the following two active subjects in numerical analysis.(i)
Monotone equations with convex constraints: finding a vectorx∗∈X such that(1)Fx∗=0,x∗∈X,whereF:ℛn⟶ℛn is a continuous nonlinear mapping (not necessarily smooth) and X⊆ℛn is a nonempty convex set.(ii)
Unconstrained optimization problem: finding a vectorx∗∈ℛn such that(2)x∗∈argminx∈ℛnfx,where f:ℛn⟶ℛ is a continuously differentiable function whose gradient is denoted by gx.Problems (1) and (2) are interchangeable in some sense. In fact, setting fx=1/2Fx2, problem (1) with X=ℛn can be transformed into problem (2). Similarly, the necessary condition of problem (2), i.e., gx∗ = 0, is a special case of problem (1). Therefore, the design of numerical methods for the two problems often inspires each other and gives each other inspiration. For example, the first conjugate gradient method was developed by Hestenes and Stiefel to solve the system of linear equations [1], and then this method was generalized to solve the unconstrained optimization problem by Fletcher and Reeves [2].Problems (1) and (2) appear frequently in many areas of applied mathematics and play important roles in many applications, such as compressive sensing, image processing, control theory, and motion control of robot manipulator [3–8]. For example, in the numerical solution theory of partial differential equations, the finite difference schemes of elliptic equations can be transformed into the following Sylvester equations:(3)AX+XB=C,where A∈ℛp×m,B∈ℛn×q,andC∈ℛp×q are given matrices and X∈ℛm×n is the unknown matrix. Then, using the Kronecker product ⊗ and the vectorization operator vec(·), we can transform the above Sylvester equations into a linear system of equations as follows [9]:(4)In⊗A+B⊤⊗ImvecX=vecC,which is a special case of problem (1) with(5)x:=vecX,Fx:=In⊗A+B⊤⊗ImvecX−vecC,X=ℛmn.Due to the numerous applications in diverse scientific areas, problems (1) and (2) have been extensively studied during the past few decades and many numerical methods have been proposed. The numerical methods for problem (1) can be roughly divided into two categories: the iterative methods for smooth case and the iterative methods for nonsmooth case. More specifically, the methods in the first category need to assume that the mapping F(x) is smooth, which includes the Newton method, quasi-Newton method, Levenberg–Marquardt method, and their variants [10–13]. The methods in this category often need to solve a linear system of equations at each iteration, which indicates that they are not suitable to solve large-scale problem (1). The methods in the second category remove this restriction. For example, based on the spectral gradient method for unconstrained optimization problem, Cruz et al. [14, 15], Zhang and Zhou [16], and Liu and Duan [17] have successively proposed some spectral gradient projection methods or spectral residual methods for solving problem (1) with X=ℛn. Motivated by the studies in [14–16], Cheng [18] extended the Polak–Ribiére–Polyak (PRP) method to solve problem (1) with X=ℛn. Other similar methods include the two-term PRP-based method [19], the CG−DESCENT method [3], the Hestenes–Stiefel projection method [20], and the hybrid conjugate gradient projection method [21]. After careful analysis and comparison, we find that the above methods mainly consist of the following three steps at each iteration: (i) a sufficient descent direction is first generated, along which a step size is obtained by Armijo-like line search; (ii) a temporal iterate zk is generated, and then a hyperplane(6)ℋk=x∈ℛn|Fzk,x−zk=0,is defined, which strictly separates the current iterate xk and the solution set X∗ of problem (1); (iii) the next iterate xk+1 is defined by the projection of xk onto the hyperplane ℋk.On the other hand, the conjugate gradient method is one of the most efficient solvers for large-scale problem (2), whose iteration sequence {xk} is generated by(7)xk+1=xk+αkdk,k=0,1,…,where αk > 0 is the step size and dk is the search direction defined by(8)dk=−gk,ifk=0,−gk+βkdk−1,ifk≥1,in which βk is the so-called conjugate gradient formula which is the main difference in conjugate gradient methods. Since 1952, many conjugate gradient methods have been offered, such as the Hestenes–Stiefel (HS) method [1], the Fletcher–Reeves (FR) conjugate gradient method [2], the Polak–Ribiére–Polyak (PRP) conjugate gradient method [22], the Liu–Storey (LS) conjugate gradient method [23], and the Dai–Yuan (DY) conjugate gradient method [24]. During the last two decades, many conjugate gradient methods with sufficient descent property were proposed, and the first one is that proposed by Shi and Shen [25], which has not aroused continuing concern. Lately, the CG−DESCENT method designed by Hager and Zhang [26] is another one with sufficient descent property, which has inspired to benefit much research and design in this direction, and many efficient conjugate gradient methods have been developed, such as the modified FR in [27], the modified PRP in [28], and the descent memory gradient method in [29], in which the modified FR in [27] accomplished a theoretical breakthrough of great significance.In this paper, based on the Fletcher–Reeves (FR) conjugate gradient method, we firstly propose a multiparameterized conjugate gradient method (MPCGM) for problem (1), which is derivative-free and thus only needs to compute the value of mapping F(x) at each iteration. Then, the method is generalized to solve problem (2), and a novel conjugate gradient method (NCGM) is obtained. Both methods’ convergence property is analyzed under traditional conditions and their practical application in compressive sensing and motion control of robot manipulator is investigated.The remainder of this paper is organized as follows. In Section2, we describe the MPCGM for nonsmooth problem (1). Moreover, the proof of its global convergence is also presented. In Section 3, we generalize MPCGM to solve nonconvex problem (2) and analyze the convergence property of the generalized method. In Section 4, some numerical results and comparisons are presented, and finally a brief conclusion is drawn in Section 5. Before ending this section, it is worth pointing out the main contributions of this paper as below.(i)
A multiparameterized conjugate gradient method is proposed for nonsmooth problem (1), which is used to solve compressive sensing.(ii)
A novel conjugate gradient method is proposed for nonconvex problem (2), which is used to solve motion control of robot manipulator.(iii)
Global convergence property of two novel methods is proved under mild conditions.


## 2. Multiparameterized Conjugate Gradient Method

Projection operatorPΩ[x] is defined as a mapping from the n dimensional Euclidean space ℛn to a nonempty closed convex subset Ω⊆ℛn:(9)PΩx:=argminy−xy∈Ω,∀x∈ℛn,which satisfies the following property [30].Lemma 1.
Let Ω be a closed convex subset ofℛn. For any x,y∈ℛn, we have(10)PΩx−PΩy≤x−y.Assumption 1.
(1)
The solution set of problem (1), denoted by X∗, is nonempty.
(2)
The mappingF(x) is monotone on ℛn, i.e.,
(11)
x
−
y
,
F
x
−
F
y
≥
0
,
∀
x
,
y
∈
ℛ
n
.
(3)
The mappingF(x) is Lipschitz continuous on X, i.e., there exists a constant L > 0 such that
(12)
F
x
−
F
y
≤
L
x
−
y
,
∀
x
,
y
∈
X
.
Based on the research in [27, 29], we present a multiparameterized conjugate gradient method for nonsmooth problem (1) as follows.Algorithm 1.
Multiparameterized conjugate gradient method (MPCGM).Step 0: choose constants 0 <ρ < 1, c > 0, σ > 0, v≥0, β > 0, 0 < γ < 2, and tolerance error ɛ > 0. Set an initial point x0∈X, and let k = 0.Step 1: ifFxk<ε, then stop; otherwise, go to step 2.Step 2: computedk by(13)dk=−Fxk,ifk=0,−θkFxk+βkdk−1,ifk≥1,whereθk and βk are two parameters defined by(14)θk=c+Fxk⊤dk−1dk−12,∀k≥1,βk=Fxk2dk−12,∀k≥1.Step 3: compute a temporal iteratezk = xk + αkdk, where αk=βρmk with mk being the smallest nonnegative integer m such that(15)−Fxk+βρmdk,dk≥σβρmvFxk+Fxk+βρmdkdk2.Step 4: ifzk∈X and Fzk<ε, then stop; otherwise, compute the new iterate xk+1 by(16)xk+1=PXxk−γξkvFxk+Fzk,where(17)ξk=Fzk,xk−zkvFxk+Fzk2.Setk = k + 1 and go to Step 1.Remark 1.
Parameterβk is obtained by replacing the denominator Fxk−12 of βk in the classical FR conjugate gradient method by dk−12, and parameter θk makes the generated direction dk satisfy sufficient descent property, which is proved in the next lemma.Lemma 2.
Forc > 0 and any k ≥ 0, the direction dk defined by (13) satisfies(18)Fxk⊤dk≤−CFxk2,where C = min{1, c} > 0.Proof.
Ifk = 0, from (13), it holds that(19)Fx0⊤d0=−Fx02≤−CFxk2.
Ifk ≥ 1, from (13) again, we have(20)Fxk⊤dk=Fxk⊤−θkFxk+βkdk−1=−c+Fxk⊤dk−1dk−12Fxk2+Fxk2dk−12Fxk⊤dk−1=−cFxk2≤−CFxk2.
Therefore, for allk ≥ 0, inequality (18) always holds. This completes the proof.Remark 2.
By Cauchy–Schwarz inequality, it holds that(21)dk≥CFxk.Remark 3.
Parameterξk in Step 4 of MPCGM is well defined, which is analyzed as follows.(i)
Forv=0: if Fzk=0, from the line search (15), we have dk=0, which together with (21) implies Fxk=0. This indicates that vFxk+Fzk=Fzk≠0 if ‖F(xk)‖ ≠ 0.(ii)
Forv>0: if vFxk+Fzk=0, we have F(zk) = −vF(xk). This together with the line search (15) gives vFxk,dk≥σαkdk2. From this inequality and (18), we have(22)−CvFxk2≥σαkdk2,i.e.,(23)Fxk2≤−σαkCvdk2,which indicates ‖F(xk)‖ = 0. Therefore, we again get ‖vF(xk) + F(zk)‖ ≠ 0 if ‖F(xk)‖ ≠ 0.
The following lemma indicates that the Armijo-type line search (15) is well defined.Lemma 3.
For eachk ≥ 0, there exists a nonnegative integer mk satisfying inequality (15).Proof.
If the Armijo line search (15) is executed, then ‖F(xk)‖ ≥ ɛ > 0. Assume that there exists an integer k0 ≥ 0 such that inequality (15) does not hold for any nonnegative integer m, i.e.,(24)−Fxk0+βk0ρmdk0,dk0<σβk0ρmvFxk0+Fxk0+βρmdk0dk02,∀m≥1.
Settingm ⟶ +∞ and taking limits on both sides of the above inequality, we get(25)−Fxk0,dk0≤0.
This together with inequality (18) gives Fxk02≤0, i.e., Fxk0=0 which contradicts Fxk0≥ε. This completes the proof.Lemma 4.
Let {xk} be the sequence generated by MPCGM. Then, for any fixed k ≥ 0, the step size αk is bigger than a positive number, i.e., there exists ck > 0, such that(26)αk≥ck.
Furthermore, we can deduce that(27)ck=minβ,ρCFxk2L+σvFxk+Fxk+αkρ−1dkdk2.Proof.
Ifαk ≠ β, then according to principle of the Armijo line search (15), the positive number αk′ = αk/ρ does not satisfy the following inequality:(28)−Fxk+αk′dk,dk<σαk′vFxk+Fxk+αk′dkdk2.
So, by (15) and (18), we get(29)CFxk2≤−Fxk⊤dk=Fxk+αk′dk−Fxk,dk−Fxk+αk′dk,dk≤Lαk′dk2+σαk′vFxk+Fxk+αk′dkdk2=L+σvFxk+Fxk+αkρ−1dkαkρ−1dk2,from which we get inequality (26). This completes the proof.Lemma 5.
Let {xk} and {zk} be two sequences generated by MPCGM. Then {xk} and {zk} are both bounded, and(30)limk⟶∞αkdk=0.Proof.
From inequality (15), we have(31)Fzk,xk−zk=−αkFzk,dk≥σαk2vFxk+Fzkdk2=σvFxk+Fzkxk−zk2.
Choosex∗∈X∗; from the monotonicity of F(x), we get(32)Fzk,zk−x∗≥Fx∗,zk−x∗=0,which together with (10) and (16) implies(33)xk+1−x∗2≤xk−γξkvFxk+Fzk−x∗2=xk−x∗2−2γξkvFxk+Fzk,xk−x∗+γ2ξk2vFxk+Fzk2≤xk−x∗2−2γξkFzk,xk−x∗+γ2ξk2vFxk+Fzk2≤xk−x∗2−2γξkFzk,xk−zk+γ2ξk2vFxk+Fzk2=xk−x∗2−γ2−γFzk,xk−zk2vFxk+Fzk2≤xk−x∗2−σ2γ2−γxk−zk4,where the last inequality follows from (31). Therefore, the sequence xk−x∗ is decreasing and convergent, and thus the sequence {xk} is bounded. From (33), we have(34)σ2γ2−γ∑k=0∞xk−zk4≤∑k=0∞xk−x∗2−xk+1−x∗2=x0−x∗2<∞.
Then,(35)limk⟶∞αkdk=limk⟶∞xk−zk=0.
By the above inequality and the boundedness of the sequence {xk}, it holds that the sequence {zk} is also bounded. The proof is completed.
Now, we are ready to establish the global convergence of MPCGM.Theorem 1.
Let {xk} be the sequence generated by MPCGM. Then, we have(36)limk⟶∞Fxk=0.Proof.
We prove (36) by using reduction to absurdity. Suppose that (36) is not true. Then, there is a constant ɛ0 > 0 such that(37)Fxk≥ε0,∀k≥0.
By (21), we have(38)dk≥CFxk≥Cε0,∀k≥0.
Combining this with (30), it holds that(39)limk⟶∞αk=0.
On the other hand, by the boundedness of {xk}, there exists a constant M1 > 0 such that(40)Fxk≤M1,∀k≥0.
Furthermore, by (39) and the continuity of F(x), there exists M2 > 0, such that(41)vFxk+Fxk+αkρ−1dk≤vFxk+Fxk+αkρ−1dk≤vM1+M2,∀k≥0.
Then, by the definition of search directiondk defined by (13), we have(42)dk≤cFxk+dk−1⊤Fxkdk−12Fxk+Fxk2dk−12dk−1≤c+2M1dk−1Fxk≤c+2M1CFxk−1Fxk≤c+2M1Cε0Fxk.
This together with (26) implies that(43)αk≥minβ,ρCε02L+σvM1+M2ε0+2M12>0,∀k≥0,which contradicts (39). Therefore, conclusion (36) holds and the proof is completed.


## 3. Novel Conjugate Gradient Method

In this section, we will generalized MPCGM to solve problem (2) and prove its global convergence. Firstly, we make the following standard assumption.Assumption 2.
(1)
The solution set of problem (2), denoted by X∗, is nonempty.
(2)
The level setL0 = {x|f(x) ≤ f(x0)} is bounded, where x0∈ℛn in an initial point.
(3)
The gradientgx is assumed to be Lipschitz continuous on ℛn, i.e., there exists a constant L > 0 such that
(44)
g
x
−
g
y
≤
L
x
−
y
,
∀
x
,
y
∈
ℛ
n
.Algorithm 1.
Novel conjugate gradient method (NCGM).Step 0: given an initial pointx0∈ℛn, three constants c > 0, 0 < ρ, γ < 1, and set k = 0.Step 1: ifgk=0, then stop; otherwise, go to step 2.Step 2: computedk by(45)dk=−gk,ifk=0,−θkgk+βkdk−1,ifk≥1,whereθk and βk are two parameters defined by(46)θk=c+gk⊤dk−1dk−12,∀k≥1,βk=gk2dk−12,∀k≥1.Determine the step sizeαk=ρmk with mk being the smallest nonnegative integer m such that(47)fxk+ρmdk−fxk≤γρmgk⊤dk.Step 3: setxk+1 = xk + αkdk and k = k + 1; go to Step 1.
Similar to Lemma2, it holds that(48)gk⊤dk≤−Cgk2,where C = min{1, c}. From inequality (48), it is easy to prove that the Armijo line search (47) is well defined. Moreover, from the Cauchy–Schwarz inequality and (48), it holds that(49)Cgk≤dk.
The next theorem indicates that NCGM is globally convergent.Theorem 2.
If Assumption2 holds and NCGM generates an infinite sequence {xk}, we have(50)liminfk⟶∞gk=0.Proof.
First, we prove that there exists a constantc1 > 0 such that the following inequality holds for all k:(51)αk≥c1gk2dk2.
The proof of (51) is divided into the following two cases.Case (I): ifαk = 1, then from (49), we have αk=1≥C2gk2/dk2.Case (II): ifαk < 1, then by the Armijo line search condition, ρ−1αk does not satisfy inequality (47). That is,(52)fxk+ρ−1αkdk−fxk>γρ−1αkgk⊤dk.
By the mean-value theorem of the continuous function, there exists a constanttk ∈ (0, 1) such that(53)fxk+ρ−1αkdk−fxk=ρ−1αkgxk+tkρ−1αkdk⊤dk=ρ−1αkgk⊤dk+ρ−1αkgxk+tkρ−1αkdk−gk⊤dk≤ρ−1αkgk⊤dk+Lρ−2αk2dk2.
Substituting the last inequality into the left-hand side of (52), we get(54)αk≥1−γρC2Lgk2dk2.
Settingc1=minC2,1−δρC2/L, we can get inequality (51). From (47), (48), and Assumption 2, it is easy to deduce that(55)∑k=0∞αkgk2<∞.
Substituting (51) into the left-hand side of (55), we can derive the famous Zoutendijk condition(56)∑k=0∞gk4dk2<∞.
Suppose that conclusion (50) is not true, so there is a constant ɛ0 > 0 such that(57)gk≥ε0,∀k≥0.
By the definition ofdk, we have(58)dk≤cgk+gk⊤dk−1dk−12gk+gk2dk−12dk−1≤c+2M2dk−1gk≤c+2M2Cgk−1gk≤c+2M2Cε0gk,where M2 > 0 is the upper bound of f(x) in the level set L0. From this inequality and (56), we get(59)dk2gk4≤c+2M2Cε021gk2≤c+2M2Cε021ε02.
Thus,(60)∑k=0∞gk4dk2≥∑k=0∞ε02c+2M2Cε0−2=∞,which contradicts (56). Therefore, conclusion (50) holds. The proof is completed.


## 4. Numerical Results

In this section, to show the efficiency of MPCGM and NCGM, we apply them to solve problems (1) and (2). Furthermore, we compare the performance of MPCGM with the spectral gradient projection method in [31] (SGPM) and the conjugate gradient method in [3] (CGM). All codes were written in MATLAB R2014a, and run on a notebook computer with Intel Core 2 CPU 2.10 GHZ and RAM 2.00 GM.


### 4.1. Numerical Test of MPCGM

We consider two synthesized problems and one practical problem, which are drawn from [3, 32, 33].Problem 1.
SetFx=f1x,f2x,…,fnx⊤, where(61)fix=exi−1,fori=1,2,…,n,and X=R+n. This problem has a unique solution x∗ = (0, 0, …, 0)⊤.Problem 2.
SetFx=f1x,f2x,…,fnx⊤, where(62)fix=xi−sinxi−1,fori=1,2,…,n,and X=x∈ℛn∑i=1nxi≤n,xi≥0,i=1,2,…,n. This problem is nonsmooth at the point (1, 1, …, 1)⊤.
It is easy to prove that the above two mappings are monotone. The parameters in the three tested methods for Problem1 and Problem 2 are set as follows:SGPM:r = 0.01, σ = 0.01, β = 0.5.CGM:ρ = 0.39, σ = 10−4, β = 1.MPCGM:ρ = 0.2, c = 1, σ = 0.01, β = 1, γ = 1.7.
In the experiment, we use the following termination condition:(63)Fxk≤10−6.
In MPCGM, we have introduced two new parametersγ and v. Now, we conduct some sensitivity tests on the two parameters to determine their optimal choices. Here, we use the tentative method and analyze the fluctuation of the number of iterations with respect to different values of γ and v. Specifically, we set γ or v as abscissa and we set the number of iterations as ordinate.(i)
We use Problem1 with x0 = (1, 1, …, 1) and n = 10000 to analyze the influence of γ on the number of iterations. Moreover, we set v=0 and choose different values of γ ∈ {0.5, 0.6, …, 1.9}.(ii)
We use Problem2 with x0 = (1, 1, …, 1) and n = 10000 to analyze the influence of v on the number of iterations. Moreover, we set γ = 1.7 and choose different values of v∈0,0.01,…,0.1.
The numerical results are graphically shown in Figure1, from which we can see that for Problem 1, larger values of γ can accelerate the convergence of MPCGM, and for Problem 2, the positive values of v can also accelerate the convergence of MPCGM. Therefore, the advantage of incorporating the parameters γ and v into MPCGM is verified. In the following, we set γ = 1.7 and v=0.07.Figure 1
Sensitivity test onγ and v. (a) Sensitivity test on the parameter γ. (b) Sensitivity test on the parameter v.
(a)
(b)Now, we give more numerical results about Problem1 and Problem 2 with the number of variables n = 1000, 2000, 5000, 10000, 20000, 50000, 100000, 1000000, and the initial point is set as x0 = (1, 1, …, 1). The numerical results are reported in Tables 1 and 2, which contain the dimension of the problem (Dim), the number of iterations (Iter), the CPU time required in seconds (Time), and the final norm of equations (Fn) when the termination condition is satisfied. It is well known that when a set is a polyhedral, that is, all the constraint functions defining the set are linear, then computing the projection on it reduces to solving a quadratic problem. Here, we use the quadratic program solver quadprog.m from the MATLAB optimization toolbox to perform the projection operator.Table 1
Numerical results of Problem1.
Dim
SGPM
CGM
MPCGM
Iter
Time
Fn
Iter
Time
Fn
Iter
Time
Fn
1000
13
0.02
5.62314e − 07
13
0.01
4.76573e − 07
1
0.01
0.00000e + 00
2000
13
0.03
7.95231e − 07
13
0.01
6.73977e − 07
1
0.01
0.00000e + 00
5000
14
0.07
8.85789e − 08
14
0.02
4.36958e − 07
1
0.01
0.00000e + 00
10000
14
0.13
1.25269e − 07
14
0.04
6.17952e − 07
2
0.02
0.00000e + 00
20000
14
0.26
1.77161e − 07
14
0.08
8.73916e − 07
2
0.02
0.00000e + 00
50000
14
0.68
2.80126e − 07
15
0.23
3.56664e − 07
2
0.03
0.00000e + 00
100000
14
1.35
3.96172e − 07
15
0.44
5.04400e − 07
4
0.11
0.00000e + 00
1000000
15
17.70
2.30082e − 07
16
5.97
8.61927e − 07
12
3.92
0.00000e + 00Table 2
Numerical results of Problem2.
Dim
SGPM
CGM
MPCGM
Iter
Time
Fn
Iter
Time
Fn
Iter
Time
Fn
1000
11
0.01
1.53710e − 08
13
0.01
2.36758e − 07
8
0.01
4.29514e − 07
2000
11
0.01
2.17380e − 08
13
0.01
3.34826e − 07
8
0.01
6.07424e − 07
5000
11
0.02
3.43707e − 08
13
0.01
5.29406e − 07
8
0.01
9.60422e − 07
10000
11
0.03
4.86070e − 08
13
0.02
7.48694e − 07
9
0.01
7.05926e − 07
20000
11
0.05
6.87439e − 08
14
0.04
4.65956e − 07
9
0.02
9.98330e − 07
50000
11
0.11
1.08699e − 07
14
0.09
7.36741e − 07
14
0.07
8.57326e − 08
100000
11
0.24
1.53719e − 07
15
0.19
5.16018e − 07
14
0.12
1.21244e − 07
1000000
11
3.23
4.85879e − 07
16
2.36
8.99942e − 07
21
2.35
6.98408e − 07The numerical results in Tables1 and 2 verify that the gradient methods perform well on the large-scale constrained monotone equations. For Problem 1, the performance of CGM and MPCGM is obviously better than that of SGPM, and the performance of MPCGM is obviously better than that of CGM. That is, MPCGM performs the best among the three tested methods. As the dimension increased, the advantage on the required CPU time of MPCGM becomes prominent gradually. For Problem 2, there seems to be not much difference among the performance of the three tested methods, and MPCGM still performs a little better than the other two methods because it is the fastest for most scenarios. In a word, the numerical experiments show that the proposed method provides an efficient tool to solve nonlinear constrained equations.Problem 3.
Consider the compressive sensing (CS):(64)minx∈ℛn12Ax−b22+μx1,where A∈ℛm×nm≪n is a linear operator, b∈ℛm is an observation, is the unknown vector, x1=∑i=1nxi is the ℓ1-norm of x, and parameter μ > 0 is used to trade off both terms of the objective function of (64). Following the procedure of Figueiredo et al. [33], we can set x=u−v, u ≥ 0, v≥0, where u∈ℛn,v∈ℛn, and ui=xi+,vi=−xi+ for all i = 1, 2, …, n with (⋅)+ = max{0, ⋅}. Then, CS can be rewritten as(65)minu,v12b−Au−v22+μen⊤u+μen⊤vs.t.u≥0,v≥0.
That is,(66)minu,v12z⊤Hz+c⊤zs.t.z≥0,where(67)z=uv,y=A⊤b,c=μe2n+−yy,H=A⊤A−A⊤A−A⊤AA⊤A.
Then, Xiao et al. [3] further transformed the above optimization problem as the constrained nonlinear equations:(68)Fz=minz,Hz+c=0,z≥0.
The following relative error (RelErr) to the original signalx˜ is used to measure the quality of restoration:(69)RelErr=x˜−x∗2x˜2,where x∗ is the restored signal. In the experiment, our goal is to reconstruct a length-n sparse signal from m observation. Here, we set n = 2048 and m = 512, and the original signal contains 64 randomly placed spikes. The m × n matrix A is obtained by first filling it with independent samples of a standard Gaussian distribution and then orthonormalizing the rows. The observation b is generated by b=Ax˜+ω, where ω is the Gaussian noise distributed as N(0, δ2I) with δ = 10−3. We set μ = 0.01‖A⊤b‖∞ and use fx=μx1+Ax−b22/2 as the merit function and stop the tested methods if ‖fk‖ ≤ 10−2. The parameters in the three tested methods for Problem 3 are listed as follows:SGPM:r = 10, σ = 0.01, β = 0.3.CGM:ρ = 0.39, σ = 10−4, β = 1.MPCGM:ρ = 0.4, c = 1, σ = 0, β = 1, γ = 1.9.
The numerical results generated by the three tested methods are given in Figure2.Figure 2
The original signal, noisy measurement, and recovered results. (a) Original signal. (b) Noisy measurement. (c) SGPM (RelErr = 3.91%, Iter = 347, Time = 3.04 s). (d) CGM (RelErr = 4.40%, Iter = 287, Time = 3.71 s). (e) MPCGM (RelErr = 3.81%, Iter = 156, Time = 1.48 s).
(a)
(b)
(c)
(d)
(e)From Figures2(c)–2(e), we can see that the three tested methods recover the original signal with high precision, and MPCGM still performs the best among the three methods because it takes the least number of iterations and CPU time.


### 4.2. Numerical Test of NCGM

In this section, the motion control of a two-joint planar robotic manipulator is solved by NCGM. As stated in [34], the discrete-time kinematics equation of two-joint planar robot manipulator at the position level is given as(70)fθk=rk,where f(⋅) is the kinematics mapping function with known structure and defined as(71)fθ=l1c1+l2c2l1s1+l2s2,in which li is the length of the i-th rod, c1 = cos(θ1), s1 = sin(θ1), c2 = cos(θ1 + θ2), and s2 = sin(θ1 + θ2). Besides, θk∈ℛ2 is the joint angle vector and rk∈ℛ2 is the end effector position vector. Then, we need to solve a series of optimization problem defined at each time instant tk ∈ [0, tf] as follows:(72)minrk∈ℛ212rk−rdk2.In this experiment, we setli = 1(i = 1, 2) and the end effector is controlled to track a Lissajous curve, which is expressed as [34](73)rdk=1.5+0.2sinπtk53/2+0.2sin2πtk5+π3.For NCGM, we setc = 0.01, ρ = 0.2, and γ = 0.08. The initial point is set as θ0 = [0,π/3]⊤, the length of rod li = 1(i = 1, 2), the end of task duration tf = 10s, and the task duration [0, 10] is divided into 200 equal parts. The numerical results generated by NCGM are plotted in Figure 3. Specifically, Figure 3(a) shows robot trajectories synthesized by NCGM. Figure 3(b) plots end effector trajectory and desired path. Figures 3(c) and 3(d) show the error of NCGM on x-axis and y-axis, respectively. From Figures 3(a) and 3(b), it is clear that NCGM successfully completes the given task. Furthermore, Figures 3(c) and 3(d) indicate that the generated error is about 10−3.Figure 3
Numerical results generated by NCGM. (a) Manipulator trajectories. (b) End effector trajectory and desired path. (c) Tracking errors on the horizontalx-axis. (d) Tracking errors on the vertical y-axis.
(a)
(b)
(c)
(d)


## 4.1. Numerical Test of MPCGM

We consider two synthesized problems and one practical problem, which are drawn from [3, 32, 33].Problem 1.
SetFx=f1x,f2x,…,fnx⊤, where(61)fix=exi−1,fori=1,2,…,n,and X=R+n. This problem has a unique solution x∗ = (0, 0, …, 0)⊤.Problem 2.
SetFx=f1x,f2x,…,fnx⊤, where(62)fix=xi−sinxi−1,fori=1,2,…,n,and X=x∈ℛn∑i=1nxi≤n,xi≥0,i=1,2,…,n. This problem is nonsmooth at the point (1, 1, …, 1)⊤.
It is easy to prove that the above two mappings are monotone. The parameters in the three tested methods for Problem1 and Problem 2 are set as follows:SGPM:r = 0.01, σ = 0.01, β = 0.5.CGM:ρ = 0.39, σ = 10−4, β = 1.MPCGM:ρ = 0.2, c = 1, σ = 0.01, β = 1, γ = 1.7.
In the experiment, we use the following termination condition:(63)Fxk≤10−6.
In MPCGM, we have introduced two new parametersγ and v. Now, we conduct some sensitivity tests on the two parameters to determine their optimal choices. Here, we use the tentative method and analyze the fluctuation of the number of iterations with respect to different values of γ and v. Specifically, we set γ or v as abscissa and we set the number of iterations as ordinate.(i)
We use Problem1 with x0 = (1, 1, …, 1) and n = 10000 to analyze the influence of γ on the number of iterations. Moreover, we set v=0 and choose different values of γ ∈ {0.5, 0.6, …, 1.9}.(ii)
We use Problem2 with x0 = (1, 1, …, 1) and n = 10000 to analyze the influence of v on the number of iterations. Moreover, we set γ = 1.7 and choose different values of v∈0,0.01,…,0.1.
The numerical results are graphically shown in Figure1, from which we can see that for Problem 1, larger values of γ can accelerate the convergence of MPCGM, and for Problem 2, the positive values of v can also accelerate the convergence of MPCGM. Therefore, the advantage of incorporating the parameters γ and v into MPCGM is verified. In the following, we set γ = 1.7 and v=0.07.Figure 1
Sensitivity test onγ and v. (a) Sensitivity test on the parameter γ. (b) Sensitivity test on the parameter v.
(a)
(b)Now, we give more numerical results about Problem1 and Problem 2 with the number of variables n = 1000, 2000, 5000, 10000, 20000, 50000, 100000, 1000000, and the initial point is set as x0 = (1, 1, …, 1). The numerical results are reported in Tables 1 and 2, which contain the dimension of the problem (Dim), the number of iterations (Iter), the CPU time required in seconds (Time), and the final norm of equations (Fn) when the termination condition is satisfied. It is well known that when a set is a polyhedral, that is, all the constraint functions defining the set are linear, then computing the projection on it reduces to solving a quadratic problem. Here, we use the quadratic program solver quadprog.m from the MATLAB optimization toolbox to perform the projection operator.Table 1
Numerical results of Problem1.
Dim
SGPM
CGM
MPCGM
Iter
Time
Fn
Iter
Time
Fn
Iter
Time
Fn
1000
13
0.02
5.62314e − 07
13
0.01
4.76573e − 07
1
0.01
0.00000e + 00
2000
13
0.03
7.95231e − 07
13
0.01
6.73977e − 07
1
0.01
0.00000e + 00
5000
14
0.07
8.85789e − 08
14
0.02
4.36958e − 07
1
0.01
0.00000e + 00
10000
14
0.13
1.25269e − 07
14
0.04
6.17952e − 07
2
0.02
0.00000e + 00
20000
14
0.26
1.77161e − 07
14
0.08
8.73916e − 07
2
0.02
0.00000e + 00
50000
14
0.68
2.80126e − 07
15
0.23
3.56664e − 07
2
0.03
0.00000e + 00
100000
14
1.35
3.96172e − 07
15
0.44
5.04400e − 07
4
0.11
0.00000e + 00
1000000
15
17.70
2.30082e − 07
16
5.97
8.61927e − 07
12
3.92
0.00000e + 00Table 2
Numerical results of Problem2.
Dim
SGPM
CGM
MPCGM
Iter
Time
Fn
Iter
Time
Fn
Iter
Time
Fn
1000
11
0.01
1.53710e − 08
13
0.01
2.36758e − 07
8
0.01
4.29514e − 07
2000
11
0.01
2.17380e − 08
13
0.01
3.34826e − 07
8
0.01
6.07424e − 07
5000
11
0.02
3.43707e − 08
13
0.01
5.29406e − 07
8
0.01
9.60422e − 07
10000
11
0.03
4.86070e − 08
13
0.02
7.48694e − 07
9
0.01
7.05926e − 07
20000
11
0.05
6.87439e − 08
14
0.04
4.65956e − 07
9
0.02
9.98330e − 07
50000
11
0.11
1.08699e − 07
14
0.09
7.36741e − 07
14
0.07
8.57326e − 08
100000
11
0.24
1.53719e − 07
15
0.19
5.16018e − 07
14
0.12
1.21244e − 07
1000000
11
3.23
4.85879e − 07
16
2.36
8.99942e − 07
21
2.35
6.98408e − 07The numerical results in Tables1 and 2 verify that the gradient methods perform well on the large-scale constrained monotone equations. For Problem 1, the performance of CGM and MPCGM is obviously better than that of SGPM, and the performance of MPCGM is obviously better than that of CGM. That is, MPCGM performs the best among the three tested methods. As the dimension increased, the advantage on the required CPU time of MPCGM becomes prominent gradually. For Problem 2, there seems to be not much difference among the performance of the three tested methods, and MPCGM still performs a little better than the other two methods because it is the fastest for most scenarios. In a word, the numerical experiments show that the proposed method provides an efficient tool to solve nonlinear constrained equations.Problem 3.
Consider the compressive sensing (CS):(64)minx∈ℛn12Ax−b22+μx1,where A∈ℛm×nm≪n is a linear operator, b∈ℛm is an observation, is the unknown vector, x1=∑i=1nxi is the ℓ1-norm of x, and parameter μ > 0 is used to trade off both terms of the objective function of (64). Following the procedure of Figueiredo et al. [33], we can set x=u−v, u ≥ 0, v≥0, where u∈ℛn,v∈ℛn, and ui=xi+,vi=−xi+ for all i = 1, 2, …, n with (⋅)+ = max{0, ⋅}. Then, CS can be rewritten as(65)minu,v12b−Au−v22+μen⊤u+μen⊤vs.t.u≥0,v≥0.
That is,(66)minu,v12z⊤Hz+c⊤zs.t.z≥0,where(67)z=uv,y=A⊤b,c=μe2n+−yy,H=A⊤A−A⊤A−A⊤AA⊤A.
Then, Xiao et al. [3] further transformed the above optimization problem as the constrained nonlinear equations:(68)Fz=minz,Hz+c=0,z≥0.
The following relative error (RelErr) to the original signalx˜ is used to measure the quality of restoration:(69)RelErr=x˜−x∗2x˜2,where x∗ is the restored signal. In the experiment, our goal is to reconstruct a length-n sparse signal from m observation. Here, we set n = 2048 and m = 512, and the original signal contains 64 randomly placed spikes. The m × n matrix A is obtained by first filling it with independent samples of a standard Gaussian distribution and then orthonormalizing the rows. The observation b is generated by b=Ax˜+ω, where ω is the Gaussian noise distributed as N(0, δ2I) with δ = 10−3. We set μ = 0.01‖A⊤b‖∞ and use fx=μx1+Ax−b22/2 as the merit function and stop the tested methods if ‖fk‖ ≤ 10−2. The parameters in the three tested methods for Problem 3 are listed as follows:SGPM:r = 10, σ = 0.01, β = 0.3.CGM:ρ = 0.39, σ = 10−4, β = 1.MPCGM:ρ = 0.4, c = 1, σ = 0, β = 1, γ = 1.9.
The numerical results generated by the three tested methods are given in Figure2.Figure 2
The original signal, noisy measurement, and recovered results. (a) Original signal. (b) Noisy measurement. (c) SGPM (RelErr = 3.91%, Iter = 347, Time = 3.04 s). (d) CGM (RelErr = 4.40%, Iter = 287, Time = 3.71 s). (e) MPCGM (RelErr = 3.81%, Iter = 156, Time = 1.48 s).
(a)
(b)
(c)
(d)
(e)From Figures2(c)–2(e), we can see that the three tested methods recover the original signal with high precision, and MPCGM still performs the best among the three methods because it takes the least number of iterations and CPU time.


## 4.2. Numerical Test of NCGM

In this section, the motion control of a two-joint planar robotic manipulator is solved by NCGM. As stated in [34], the discrete-time kinematics equation of two-joint planar robot manipulator at the position level is given as(70)fθk=rk,where f(⋅) is the kinematics mapping function with known structure and defined as(71)fθ=l1c1+l2c2l1s1+l2s2,in which li is the length of the i-th rod, c1 = cos(θ1), s1 = sin(θ1), c2 = cos(θ1 + θ2), and s2 = sin(θ1 + θ2). Besides, θk∈ℛ2 is the joint angle vector and rk∈ℛ2 is the end effector position vector. Then, we need to solve a series of optimization problem defined at each time instant tk ∈ [0, tf] as follows:(72)minrk∈ℛ212rk−rdk2.In this experiment, we setli = 1(i = 1, 2) and the end effector is controlled to track a Lissajous curve, which is expressed as [34](73)rdk=1.5+0.2sinπtk53/2+0.2sin2πtk5+π3.For NCGM, we setc = 0.01, ρ = 0.2, and γ = 0.08. The initial point is set as θ0 = [0,π/3]⊤, the length of rod li = 1(i = 1, 2), the end of task duration tf = 10s, and the task duration [0, 10] is divided into 200 equal parts. The numerical results generated by NCGM are plotted in Figure 3. Specifically, Figure 3(a) shows robot trajectories synthesized by NCGM. Figure 3(b) plots end effector trajectory and desired path. Figures 3(c) and 3(d) show the error of NCGM on x-axis and y-axis, respectively. From Figures 3(a) and 3(b), it is clear that NCGM successfully completes the given task. Furthermore, Figures 3(c) and 3(d) indicate that the generated error is about 10−3.Figure 3
Numerical results generated by NCGM. (a) Manipulator trajectories. (b) End effector trajectory and desired path. (c) Tracking errors on the horizontalx-axis. (d) Tracking errors on the vertical y-axis.
(a)
(b)
(c)
(d)


## 5. Conclusion

In this paper, we have proposed a multiparameterized conjugate gradient method for nonlinear equations with convex constraints. Under the condition that the underlying mapping is monotone and Lipschitz continuous, we have established its global convergence. Furthermore, we have generalized this method to solve unconstrained optimization and get a new conjugate gradient method, whose global convergence is analyzed under mild conditions. Preliminary numerical results are reported which indicate that the proposed methods perform better than some well-developed methods.



---

*Source: 9175496-2020-05-05.xml*