# A Gradient Projection Algorithm with a New Stepsize for Nonnegative Sparsity-Constrained Optimization

Authors: Ye Li; Jun Sun; Biao Qu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Nonnegative sparsity-constrained optimization problem arises in many fields, such as the linear compressing sensing problem and the regularized logistic regression cost function. In this paper, we introduce a new stepsize rule and establish a gradient projection algorithm. We also obtain some convergence results under milder conditions.


---

## Body

## 1. Introduction

In this paper, we are mainly concerned with the nonnegative sparsity-constrained optimization problem (NN-SCO):(1)minfxs.t.x∈S∩R+n,where f:Rn⟶R is a continuously differential function with a lower bound. S:=x∈Rn:x0≤s is a sparse set, where s<n is a given integer regulating the sparsity level in x and R+n is the nonnegative orthant in Rn. x0 is the l0 norm of x, counting the number of nonzero elements in x. Many application problems can be translated into problem (1), such as the widely studied linear compressing sensing problem of fx=1/2Ax−b2 with A∈Rm×n being a sensing matrix, b∈Rm is the observation vector, and ⋅ is the Euclidean norm in Rn [1]. Problem (1) has also used to the regularized logistic regression cost function [2].Recently, a great deal of work has been devoted to algorithms for sparsity-constrained optimization problem. Beck and Eldar [3] established the IHT algorithm which converges to L-stationary under the Lipchitz continuity of the gradient of objective function. Beck and Hallak [4] generalized these results to sparse symmetric sets. Lu [5] designed a nonmonotone algorithm for symmetric set constraint problems. Pan, Xiu, and Zhou [6, 7] established the B-stationary, C-stationary, and α-stationary based on the Bouligand tangent cone and Clarke tangent. Recently, Pan, Zhou, and Xiu [8] established the improved IHT algorithm (IIHT) for problem (1) by using Armijo line search. They proved that any accumulation point converged to an α-stationary point under the restricted strong smoothness of objective function which is weaker than the Lipchitz continuity of the gradient.Inspired by the above literature studies, in this paper, we establish a gradient projection algorithm with a new stepsize. The new algorithm removes the condition of the restricted strong smoothness of objective function which makes it more applicable. Meanwhile, we prove the convergence of the algorithm.The rest of this paper is organized as follows. In Section2, we present some notations, definitions, and lemmas. In Section 3, we give the algorithm of (1) and prove the convergence properties.


## 2. Preliminaries

### 2.1. Notations

To make it easier to read, we give some used notations as follows:(2)S=x∈Rn:x0≤s,I1x≡i∈1,…,n:xi≠0,I1xy=I1x∪I1y,PS∩R+nx≔argminy∈S∩R+nx−y,I0x≡i∈1,…,n:xi=0,I1x:the cardinality ofI1x.


### 2.2. Definitions

Definition 1 (see [8]).
Letx∗∈S∩R+n be a given feasible point of (1). We say that x∗ is an α-stationary point, if there exists α>0 such that(3)x∗∈PS∩R+nx∗−α∇fx∗.Definition 2 (see [9]).
A functionf is called 2s-restricted strongly smooth (2s-RSS) with parameter L2s>0, and if for any x,y∈Rn satisfying I1xy<2s, it holds that(4)fy−fx−∇fx,y−x≤L2s2y−x2.Definition 3 (see [9]).
A functionf is called 2s-restricted strongly convex (2s-RSC) with parameter l2s>0, and if for any x,y∈Rn satisfying I1xy<2s, it holds that(5)fy−fx−∇fx,y−x≥l2s2y−x2.
If and only if for anyx,y∈Rn and I1xy≤2s, we have(6)∇fx−∇fyI1xy≥l2sx−y.
In particular, in (5), if l2s=0, the function f is called 2s-restricted convex (2s-RC).Definition 4 (see [10]).
The projected gradient∇S∩R+nfx of f is defined by(7)∇S∩R+nfx=PTS∩R+nC−∇fx,=argminv+∇fxv∈TS∩R+nC,=max−∇fxk,v,v=1.


### 2.3. Lemmas

Lemma 1 (see [8]).
Forα>0, vectorx∗∈S∩R+n is an α-stationary point if and only if(8)∇ifx∗=0,i∈I1x∗,≥αMsx∗,i∈I0x∗.In particular, whenx∗0=s,x∗≥0, ∇ifx∗=0,i∈I1x∗≥−αMsx∗,i∈I0x∗.Whenx∗0<s,x∗≥0, ∇ifx∗=0,i∈I1x∗∈R+n,i∈I0x∗.Lemma 2 (see [8]).
PS∩R+nx=PSPR+nx.Lemma 3 (see [8]).
For anyx∗∈S∩R+n, we have(9)TS∩R+nCxk=spanei,i∈I1xk,where ei∈Rn is a vector whose ith component is one and others are zeros.


## 2.1. Notations

To make it easier to read, we give some used notations as follows:(2)S=x∈Rn:x0≤s,I1x≡i∈1,…,n:xi≠0,I1xy=I1x∪I1y,PS∩R+nx≔argminy∈S∩R+nx−y,I0x≡i∈1,…,n:xi=0,I1x:the cardinality ofI1x.


## 2.2. Definitions

Definition 1 (see [8]).
Letx∗∈S∩R+n be a given feasible point of (1). We say that x∗ is an α-stationary point, if there exists α>0 such that(3)x∗∈PS∩R+nx∗−α∇fx∗.Definition 2 (see [9]).
A functionf is called 2s-restricted strongly smooth (2s-RSS) with parameter L2s>0, and if for any x,y∈Rn satisfying I1xy<2s, it holds that(4)fy−fx−∇fx,y−x≤L2s2y−x2.Definition 3 (see [9]).
A functionf is called 2s-restricted strongly convex (2s-RSC) with parameter l2s>0, and if for any x,y∈Rn satisfying I1xy<2s, it holds that(5)fy−fx−∇fx,y−x≥l2s2y−x2.
If and only if for anyx,y∈Rn and I1xy≤2s, we have(6)∇fx−∇fyI1xy≥l2sx−y.
In particular, in (5), if l2s=0, the function f is called 2s-restricted convex (2s-RC).Definition 4 (see [10]).
The projected gradient∇S∩R+nfx of f is defined by(7)∇S∩R+nfx=PTS∩R+nC−∇fx,=argminv+∇fxv∈TS∩R+nC,=max−∇fxk,v,v=1.


## 2.3. Lemmas

Lemma 1 (see [8]).
Forα>0, vectorx∗∈S∩R+n is an α-stationary point if and only if(8)∇ifx∗=0,i∈I1x∗,≥αMsx∗,i∈I0x∗.In particular, whenx∗0=s,x∗≥0, ∇ifx∗=0,i∈I1x∗≥−αMsx∗,i∈I0x∗.Whenx∗0<s,x∗≥0, ∇ifx∗=0,i∈I1x∗∈R+n,i∈I0x∗.Lemma 2 (see [8]).
PS∩R+nx=PSPR+nx.Lemma 3 (see [8]).
For anyx∗∈S∩R+n, we have(9)TS∩R+nCxk=spanei,i∈I1xk,where ei∈Rn is a vector whose ith component is one and others are zeros.


## 3. Main Results

In this section, we establish a new algorithm which improves the IIHT algorithm for (1) and then we analyze its convergence properties. At first, let us develop the gradient projection algorithm with a new stepsize rule.Algorithm 1.
Step 1. Initialize x0∈S∩R+n, 0≤θ≤1, and ε>0, and setk⟸0.Step 2. Compute Lk=supα>0∇fxk−∇fzkα,θ/xk−zkα,θ, where(10)zkα,θ=xk+θxkα−xk,xkα=PS∩R+nxk−α∇fxk.Step 3. Compute xk+1=PS∩R+nxk−αk∇fxk where αk satisfies 0≤αk≤1/3Lk.Step 4. If ∇Γkfxk≤ε, then stop; otherwise, set k⟸k+1 and go to Step 2.
Next, let us list the following assumptions for convenience:(1)
For anyk>0, Lk<+∞(2)
f is bounded below on S∩R+nLemma 4.
Let the sequencexk be generated by Algorithm 1, and set lk=3Lk. Then, we have(11)fxk≤hlkxk,xk+1,where hlkxk,xk+1=fxk+1+∇fxk+1,xk−xk+1+lk/2xk−xk+12.Proof.
Let(12)gt=fxk+1+txk−xk+1.
Then,(13)g0=fxk+1,g1=fxk,g′t=xk−xk+1T∇fxk+1+txk−xk+1.
Thus,(14)fxk−fxk+1=g1−g0,=∫01g′tdt,=∫01xk−xk+1T∇fxk+1+txk−xk+1dt,=∫01xk−xk+1T∇fxk+1dt+∫01xk−xk+1T∇fxk+1+txk−xk+1−∇fxk+1dt,=∫01xk−xk+1T∇fxk+1dt+∫01xk−xk+1T∇fxk+1+txk−xk+1−∇fxk+1+∇fxk−∇fxkdt,=∫01xk−xk+1T∇fxk+1dt+∫01xk−xk+1T∇fxk−∇fxk+1dt,+∫01xk−xk+1T∇fxk+1+txk−xk+1−∇fxkdt,≤∫01xk−xk+1T∇fxk+1dt+∫01xk−xk+1T∇fxk−∇fxk+1dt,+∫01xk−xk+1∇fxk+1+txk−xk+1−∇fxkdt,≤xk−xk+1T∇fxk+1+Lkxk−xk+12+xk−xk+1∫01Lk1−txk−xk+1dt,≤xk−xk+1T∇fxk+1+3Lk2xk−xk+12,=xk−xk+1T∇fxk+1+lk2xk−xk+12.
Then, (11) is tenable.Lemma 5.
We supposel≥lk. For xk∈S∩R+n and xk+1=PS∩R+nxk−1/l∇fxk, we have(15)fxk−fxk+1≥σxk−xk+12,where σ=l−lk/2.Proof.
Sincexk+1∈PS∩R+nxk−1/l∇fxk, by the definition of projection, we get(16)xk+1∈argminx∈S∩R+nx−xk−1l∇fxk2.
Moreover,(17)hlx,xk=fxk+∇fxk,x−xk+l2x−xk,=l2x−xk−l2∇fxk2+fxk−12l∇fxk2.
Becausefxk−1/2l∇fxk2 is a constant independent of x, we can get(18)xk+1∈argminx∈PS∩R+nhlx,xk.
Therefore,(19)hlxk+1,xk≥hlxk,xk=fxk.
By Lemma4, we get(20)fxk+1≥hlxk+1,xk.
Hence,(21)fxk−fxk+1≥fxk−hlkxk+1,xk,≥hlxk+1,xk−hlkxk+1,xk,=l−lk2xk+1−xk2.
Letσ=l−lk/2. We get(22)fxk−fxk+1≥σxk−xk+12.Lemma 6.
Let the sequencexk be generated by Algorithm 1. Then,(1)
fxk−fxk+1≥1/αk−lk/2xk−xk+12(2)
fxk is an increasing sequence, and when k⟶∞, fxk converges(3)
xk−xk+1⟶0(4)
for anyk=0,1,2,…, if xk≠xk+1, we have fxk+1<fxkProof.
(1)
Since0≤αk≤1/3Lk, we get(23)1αk≥3Lk=lk.Settingl=1/αk in (15), formula (1) can be obtained.(2)
We can easily get thatfxk is an increasing sequence by (15). Moreover, by the assumptions H2, we can get that fxk converges.(3)
Letμ=1/αk−lk/2 in (1). We can get(24)fxk−fxk+1≥μxk−xk+12.Summing over both sides of this inequality, we get(25)∑k=1∞xk−xk+12≤∑k=1∞2μfxk−fxk+1,=2μfx0−limk⟶+∞fxk.Sincef is bounded below, we get(26)xk−xk+1⟶0.(4)
It easily can be got by (2).Lemma 7.
Let the sequencexk be generated by Algorithm 1. Suppose that the function f is 2s-RC. We have(27)∇fxk+1−∇fxk≤lkxk+1−xk.Proof.
Because the sequencexk be generated by Algorithm 1, we get I1xy<2s. By Lemma 4 and Lemma 5 in reference [8], we can get(28)∇fxk+1−∇fxk≤lkxk+1−xk.Theorem 1.
Let the sequencexk be generated by Algorithm 1. Then, the following results hold:(1)
Any accumulation of sequencexk is an α-stationary point.(2)
Iff is 2s-RC, the projected gradient sequence converges to zero, i.e.,(29)limk⟶+∞∇Γkfxk=0.Proof.
(1)
Suppose thatx∗ is an accumulation point of sequence xk. Then, there exists a subsequence xkn converges to x∗.Because(30)xkn−xkn+1−xkn≤xkn+1=xkn+1−xkn+xkn≤xkn+xkn+1−xkn,we get(31)limn⟶+∞xkn+1=limn⟶+∞xkn=x∗.Moreover,(32)xkn+1=PS∩R+nRnxk−αkn∇fxkn,=PSPR+nxk−αkn∇fxkn.We consider the next two cases:Case 1.
Fori∈I1x∗, there must exist a sufficiently large index N and a constant c0>0 such that(33)minxikn,xikn+1≥c0>0.ByPS∩R+n=PSPR+n and (33), we can get(34)xikn+1=xik−αkn∇ifxkn.Since(35)limn⟶+∞infαkn>0,without loss of generality, we can supposelimk⟶+∞αkn>c. Let n⟶+∞. We get(36)xi∗=xi∗−c∇ifx∗,i.e.,(37)∇ifx∗=0,∀i∈I1x∗.Case 2.
Fori∈I0x∗, we consider two subcases.Subcase 1.
Whenx∗0=s, we get(38)0=x∗=limn⟶+∞xikn+1=PSPR+nxkn−αkn∇fxkni.Due to the property of the projectionsPS and PR+n, we have(39)maxxikn−αkn∇ifxkn,0≤Msx∗.Thus,(40)xikn−αkn∇ifxkn≤Msx∗.Taking limits on both sides, we obtain(41)∇ifx∗≥−1cMsx∗.Subcase 2.
Whenx∗0<s, suppose ∇ifx∗<0, and we have(42)limn⟶+∞xikn−αkn∇ifxkn=−c∇ifx∗>0.For all sufficiently largen, we have(43)PR+nxikn−αkn∇ifxkn=xikn−αkn∇ifxkn,=−c∇ifx∗>0.Sincex∗0<s, for all sufficiently large n, we have(44)xikn+1=PSPR+nxkn−αkn∇fxkni,=PR+nxkn−αkn∇fxkni>0.which contradicts withi∈I0x∗. Thus, ∇ifx∗≥0.Summarizing the two cases, we obtain(45)∇ifx∗=0,i∈I1x∗,≥−1cMsx∗,i∈I0x∗.Thus,x∗ is an α-stationary point of (1).(2)
SetΓk=I1xk. By Lemma 3, we have(46)TS∩R+nCxk=RΓkn,=spanei,i∈I1xk.
By Definition4, we have(47)PTS∩R+nC−∇fxk=max−∇fxk,v,v=1,=∇Γkfxk.
Moreover, the maximum value is taken atv=1. For any ε>0, there exists vk∈RΓkn and vk=1 satisfies(48)∇Γkfxk≤−∇fxk,vk+ε.
Becausexk+1=PS∩R+nxk−αk∇fxk and xΓk+1=yΓk+1,x∈PS∩R+ny, we get(49)xΓk+1k+1=xk−αk∇fxkΓk+1,i.e.,(50)xΓk+1k+1−xk−αk∇fxkΓk+1=0.
Thus, for anyϖk+1∈RΓk+1n, we get(51)xk+1−xk−αk∇fxk,ϖk+1−xk+1=0.
Takingϖk+1=xk+1+vk+1, we get(52)xk+1−xk+αk∇fxk,−vk+1=0.
By the Cauchy–Schwartz inequality, we get(53)αk∇fxk,−vk+1=xk+1−xk,vk+1≤xk+1−xk,i.e.,(54)−∇fxk,vk+1≤xk+1−xkαk.
By Lemma7, we get(55)−∇fxk+1,vk+1=−∇fxk+1−∇fxk,vk+1−∇fxk,vk+1,≤lkxk+1−xk+xk+1−xkαk.
Taking limits on both sides and using Lemma6, we have(56)limk⟶+∞sup−∇fxk,vk+1≤0.
By (32), we get(57)limk⟶+∞∇Γkfxk=0.Theorem 2.
Let the sequencexk be generated by Algorithm 1. x∗ is an accumulation point of the sequence xk. Suppose fx is 2s−RC, then the following results hold:(1)
Ifx∗0<s, then x∗ is a global minimizer of (1)(2)
Ifx∗0=s, then x∗ is a local minimizer of (1)Proof.
(1)
For∀x∈S∩R+n, we have I1xx∗=I1x∪I1x∗≤2s. Since fx is 2s−RC, by Definition 3, we have(58)fx≥fx∗+∇fx∗,x−x∗,=fx∗+∑i∈I1x∗∇ifx∗xi−xi∗+∑i∈I0x∗∇ifx∗xi−xi∗.Becausex∗ is an accumulation point of the sequence xk. By Theorem 1, x∗ is an α-stationary. By Lemma 1, we can get(59)fx≥fx∗.Thus,x∗ is a global minimizer of (1).(2)
Ifx∗0=s, then I1x∗=I1xk.In fact, for all sufficiently largek, taking 0<δ<minxi∗:i∈I1x∗, we get(60)xk−x∗≤δ.
For anyi∈I1x∗, we have(61)xik=xi∗−xi∗−xik≥xi∗−xi∗−xik>xi∗−δ>0.
Thus,(62)I1x∗⊂I1xk.
Byxk0=s and I1x∗=x∗0=s, we have(63)I1x∗=I1xk.
For anyxk∈S∩R+n satisfying xk−x∗≤δ, we have I1xkx∗=I1xk∪I1x∗≤2s. Since fx is 2s−RC, by Definition 3, Theorem 1, and Lemma 1, we have(64)fxk≥fx∗+∇fx∗,xk−x∗,=fx∗+∑i∈I1x∗∇ifx∗xik−xi∗+∑i∈I0x∗∇ifx∗xik−xi∗,≥fx∗.
Thus,x∗ is a local minimizer of (1).Theorem 3.
Let the sequencexk be generated by Algorithm 1. x∗ is a limit of the sequence xk. Suppose fx is 2s−RSC with parameter l2s and x∗0=s, for all sufficiently large k, and we have(65)xk+1−x∗2≤xk−x∗2,0<ρ<1,where ρ=1−−2l2s2αk/Lk+2l2s2αk2.Proof.
By Theorem2, we get xk⟶x∗. As fx is 2s−RSC with parameter l2s, for any x,y∈Rn and I1xy≤2s, we have(66)∇fx−∇fyI1xy≥l2sx−y.
SetΓk=I1xkandΓ∗=I1x∗. By Theorem 2, we get Γk=Γ∗. For all sufficiently large k, we have(67)∇Γ∗fx∗=limk⟶+∞∇Γkfxk=0,xΓk+1k+1=xk−αk∇fxkΓk+1.
For all sufficiently largek, we have(68)xk+1−x∗2=xΓ∗k−αk∇Γ∗fxk−xΓ∗∗+αk∇Γ∗fx∗2=xk−x∗2−2αkxk−x∗,∇fxk−∇fx∗+αk2∇fxk−∇fx∗Γ∗.
Becausexk−x∗≥Lk∇fxk−∇fx∗, we get(69)xk+1−x∗2≤xk−x∗2−2αkLk−αk2∇fxk−∇fx∗Γ∗,≤1−2l2s2αkLk+l2s2αk2xk−x∗2.
Since0≤αk≤1/3Lk and σ=l−lk/2=l−Lk/2, we have 0≤αk≤1/2σ+3Lk. Thus,(70)β2σ+3Lk≤infαk≤12σ+3Lk.
Settingα∗=β/2σ+3Lk, we get(71)α∗≤αk≤13Lk.
Thus,(72)1−2l2s2αkLk+l2s2αk2=1+l2s2αk−1Lk2−l2s2Lk2,≤1+l2s2α∗−1Lk2−l2s2Lk2,=1−2l2s2α∗Lk+l2s2α∗2,=ρ2.
Byl2s≤Lk and ρ2=1+l2s2α∗−1/Lk2−l2s2/Lk2, we get ρ>0.
From0<β<1 and ρ2=1−2l2s2α∗/Lk+l2s2α∗2, we have ρ<1.
Thus,(73)limk⟶+∞xk+1−x∗xk−x∗≤ρ,where 0<ρ<1. Thus, the sequence xk is Q-linear convergence to x∗.


## 4. Conclusions

In this paper, we are mainly concerned with the nonnegative sparsity-constrained optimization problem. We introduce a new stepsize rule and propose a new gradient projection algorithm to solve this problem. The new algorithm removes the condition of the restricted strong smoothness of objective function which makes the new algorithm more applicable. Meanwhile, we prove the convergence of the algorithm.



---

*Source: 6489190-2020-08-26.xml*