# An Accelerated Proximal Algorithm for the Difference of Convex Programming

Authors: Feichao Shen; Ying Zhang; Xueyong Wang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In this paper, we propose an accelerated proximal point algorithm for the difference of convex (DC) optimization problem by combining the extrapolation technique with the proximal difference of convex algorithm. By making full use of the special structure of DC decomposition and the information of stepsize, we prove that the proposed algorithm converges at rate ofO1/k2 under milder conditions. The given numerical experiments show the superiority of the proposed algorithm to some existing algorithms.


---

## Body

## 1. Introduction

Difference of convex problem (DCP) is an important kind of nonlinear programming problems in which the objective function is described as the difference of convex (DC) functions. It finds numerous applications in digital communication system [1], assignment and power allocation [2], compressed sensing [3–6], and so on [7–13].It is well known that the method to solve the DCP is the so-called difference of the convex algorithm (DCA) [14] in which the concave part is replaced by a linear majorant in the objective function and a convex optimization subproblem needs to be solved at each iteration. Note that the difficulty of the involved subproblem relies heavily on the DC decomposition of the objective function, and it can be easily solved when the objective function can be written as the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function, and a continuous concave function [15]. Motivated by this, Gotoh et al. [16] proposed the so-called proximal difference of the convex algorithm (PDCA) for solving DCP, in which not only the concave part is replaced by a linear majorant in each iteration but also the smooth convex part is replaced by some techniques. Furthermore, if the proximal mapping of the proper closed convex function can be easily computed, then the subproblem involved in the PDCA can be solved efficiently. However, when the concave part of the objective is void, the PDCA reduces to the proximal gradient algorithm which may be slow in computing [17]. In fact, since the convergence rate of the PDCA heavily depends on the Lojasiewicz exponent of the objective function, the PDCA converges linearly in general [18, 19]. To accelerate the convergence rate of the proximal difference of the convex algorithm, researchers recall the well-known extrapolation technique to design some efficient algorithms [20–24]. This technique has been extensively used in accelerating the proximal type algorithms for convex programming [25, 26], and the convergence rate of the algorithms can be improved from O1/k to O1/k2. Motivated by this, Wen et al. [27] proposed the proximal difference of the convex algorithm with extrapolation (PDCAE) for solving the DCP. The numerical experiments [27] show that the PDCAE has a better performance although it converges linearly in theory [27]. Now, a question is posed naturally: can we propose new type of the PDCA in which the convergence rate can be improved in theory? This constitutes the motivation of the paper.In this paper, inspired by the work in [20–23, 27], we establish an accelerated proximal DC programming algorithm (APDCA) for the DCP by combining the extrapolation technique and the PDCA. In the algorithm, the current iteration point is replaced by a linear combination of the previous two points, and extrapolation technique is involved in the stepsize. By making full use of the special structure of DC decomposition and the information of stepsize, we prove that the APDCA converges at rate of O1/k2 under milder conditions. The given numerical experiments show the superiority to some existing algorithms.The remainder of the paper is organized as follows. In Section2, we describe the DC optimization problem considered in this paper and present our new designed algorithm. In Section 3, we establish the global convergence and the quadratic convergence rate of the new designed algorithm. Some numerical experiments are provided in Section 4. Some conclusions are drawn in Section 5.To end this section, we recall some definitions used in the subsequent analysis [28–30].For an extended real valued functionf:Rn⟶−∞,+∞, we denote its domain by dom f=x∈Rn:fx<+∞. The function f is said to be strongly convex if there exists an a>0 such that ∇2fx≽aI for all x∈S, where S is a convex set and I is a identity matrix. The function f is said to be proper if it never equals −∞ and dom f≠∅. Moreover, a proper function is closed if it is lower semicontinuous. A proper closed function f is said to be level-bounded if the lower level sets of f are bounded; that is, x∈Rn:fx≥r are bounded for any r∈R. Given a proper closed function f:Rn⟶R∪+∞, the limiting subdifferential of f at x∈domf is given as follows:(1)∂fx=v∈Rn:∃xk⟶fx,vk⟶vwith liminfy⟶xkfy−fxk−vk,y−xky−xk≥0,k,where z⟶fx mean z⟶x and fz⟶fx. Note that dom ∂f=x∈Rn:∂fx≠∅. It is well known that the (limiting) subdifferential reduces to the classical subdifferential in convex analysis when f is a convex function; that is,(2)∂fx=v∈Rn:fu−fx−v,u−x≥0,u∈Rn.Furthermore, iff is continuously differentiable, then the (limiting) subdifferential reduces to the gradient of f and denoted by ∇f.


## 2. Algorithms for DC Programming

Consider the following difference of convex programming:(3)minx∈RnFx≔fx+gx−hx,where f:Rn⟶R is a strongly convex function with a>0, g:Rn⟶R is a smooth convex function, ∇g is Lipschitz continuous with Lg>0, h:Rn⟶R is a continuous convex function, and ∇h is Lipschitz continuous with Lh>0.For the DCP, the following is a classical DCA which takes the following iterative scheme [14]:(4)xk+1∈argminx∈Rnfx+gx−∇hxk,x−xk.By replacing the concave part in the objective function by a linear majorant and replacing the smooth convex part by a quadratic majorant, Gotoh et al. [16] proposed a proximal DCA for the DCP. For the sake of completeness, we list Algorithm 1 as follows.Algorithm 1: PDCA.
Initial step. Take ε>0, μ=1/Lg, and x0∈domf.Iterative step. Compute the new iterate by the following iterative scheme:xk+1∈argminx∈Rnfx+gxk−hxk−∇gxk−∇hxk,x−xk+1/2μx−xk2untilxk+1−xk≤ε is satisfiedwhereLg>0 is the Lipschitz constant of ∇g.Despite a simple subproblem is involved in the algorithm, the PDCA is potentially slow [19, 27]. To accelerate the convergence rate of the PDCA, we incorporate extrapolation technique into the PDCA to obtain the following algorithm (Algorithm 2).Algorithm 2: APDCA.
Initial step. Take 0<μ≤1/maxLg,Lh, βk⊂0,1 with 0≤supkβk<1, ε>0, t0=t1=1, and x1=x0∈domf.Iterative step. Compute the new iterate by the following iterative scheme:βk=tk−1/tk+1andtk+1=1+1+4tk2/2yk=xk+βkxk−xk−1,xk+1=argminx∈Rnfx+gyk−hyk+∇gyk−∇hyk,x−yk+1/2μx−yk2untilxk+1−xk≤ε is satisfied.


## 3. Convergence Analysis of the APDCA

In this section, we establish the global convergence of the algorithm and its convergence rate. To continue, we first recall the following conclusions.Lemma 1.
(see [25]). Let f be a continuously differentiable function with Lipschitz continuity gradient whose Lipschitz constant Lf>0. Then, for any L≥Lf, it holds that(5)fx≤fy+∇fy,x−y+L2x−y2,x,y∈Rn.Lemma 2.
Letμ≥1/2a. For the sequence xk,yk generated by the APDCA, it holds that(6)μFx−Fxk+1≥x−xk+12−x−yk2,k≥1.Proof.
Sincef is strong convex function, there exists constant a>0 such that(7)fx≥fxk+1+ξk+1,x−xk+1+ax−xk+12,where ξk+1∈∂fxk+1.
Connecting the fact that∇hx is Lipschitz continuous with constant Lh>0 with Lemma 1, we have(8)hx≤hyk+∇hyk,x−yk+12μx−yk2,where 0<μ≤1/Lh, which means that(9)−hx≥−hyk−∇hyk,x−yk−12μx−yk2.
It follows fromg is convex function that(10)gx≥gyk+∇gyk,x−yk.
Connecting (7) and (9) with (10), we have(11)fx+gx−hx≥fxk+1+gyk−hyk+ξk+1,x−xk+1+∇gyk−∇hyk,x−yk+ax−xk+12−12μx−yk2.
On the other hand, sinceh is convex, it follows that(12)hx≥hyk+∇hyk,x−yk,which means that(13)−hx≤−hyk−∇hyk,x−yk.
Connecting the fact that∇gx is Lipschitz continuous with constant Lh>0 with Lemma 1, we have(14)gx≤gyk+∇gyk,x−yk+12μx−yk2,where 0<μ≤1/Lg. Summing (13) and (14), we have(15)gx−hx≤gyk−hyk+∇gyk−∇hyk,x−yk+12μx−yk2.
Addingfx to both sides of (15) yields(16)fx+gx−hx≤fx+gyk−hyk+∇gyk−∇hyk,x−yk+12μx−yk2.
By takingx=xk+1, (16) yields that(17)fxk+1+gxk+1−hxk+1≤fxk+1+gyk−hyk+∇gyk−∇hyk,xk+1−yk+12μxk+1−yk2.
By the optimality conditions of (8), one has(18)ξk+1+∇gyk−∇hyk+1μxk+1−yk=0,that is,(19)−1μxk+1−yk=ξk+1+∇gyk−∇hyk.
Then, for0<μ≤1/maxLg,Lh, it follows from (11) and (17) that(20)Fx−Fxk+1≥ξk+1+∇gyk−∇hyk,x−xk+1+ax−xk+12−12μx−yk2−12μyk−xk+12=−1μxk+1−yk,x−xk+1+ax−xk+12−12μx−yk2−12μyk−xk+12=12μyk−xk+12+x−xk+12−x−yk2+ax−xk+12−12μx−yk2−12μyk−xk+12=12μ1+2aμx−xk+12−2x−yk2≥1μx−xk+12−x−yk2,where the first equality follows from (19), the second equality follows from the fact that 2a−b,a−c=a−c2+a−b2−b−c2,a,b,c∈Rn, and the last inequality follows from 2aμ≥1. We have conclusion (6).
Before proceeding further, we need the following conclusions.Lemma 3.
(see [25, 31]). Let t0=t1=1. Then, the sequence tk generated by (6) is increasing, and tk≥k+1/2.Lemma 4.
Letxk,yk be a sequence generated by the APDCA. Then,(21)μtk2vk−tk+12vk+1≥uk+12−uk2,where uk=tkxk−tk−1xk−1−x∗, vk=Fxk−Fx∗, and x∗ is the critical point of problem (3).Proof.
From (7) and (6), we have yk=xk+tk−1/tk+1xk−xk−1. Then, it follows that(22)uk+12−uk2=tk+1xk+1−tk+1−1xk−x∗2−tkxk−tk−1xk−1−x∗2=tk+1xk+1−tk+1−1xk−x∗2−tk+1yk−tk+1−1xk−x∗2.
Hence, to show the assertion, we only need to show that(23)μtk2vk−tk+12vk+1≥tk+1xk+1−tk+1−1xk−x∗2−tk+1yk−tk+1−1xk−x∗2.
In fact, by takingx=xk, one has from Lemma 2 that(24)μFxk−Fxk+1≥xk+1−xk2−xk−yk2.
Hence,(25)μvk−vk+1≥xk+1−xk2−xk−yk2.
Using Lemma2 again, one has from x=x∗ that(26)μFx∗−Fxk+1≥xk+1−x∗2−yk−x∗2,that is,(27)−μvk+1≥xk+1−x∗2−yk−x∗2.
Multiplying (25) by tk2 and (27) by tk+1, respectively, and summing them yield(28)μtk2vk−tk+12vk+1=μtk2vk−tk2+tk+1vk+1≥tk2xk+1−xk2−xk−yk2+tk+1xk+1−x∗2−yk−x∗2=tk+12−tk+1xk+1−xk2−xk−yk2+tk+1xk+1−x∗2−yk−x∗2=tk+1xk+1−tk+1−1xk−x∗2−tk+1yk−tk+1−1xk−x∗2,where the first equality follows from the fact that tk+12=tk2+tk+1 and the last equality follows by some manipulation. The desired result follows.
Now, we are ready to show the convergence rate of the APDCA.Theorem 1.
For the sequencexk generated by the APDCA, it holds that(29)Fxk−Fx∗≤4x0−x∗2μk+12,where x∗ is a stationary point of (3).Proof.
Using the notations used in Lemma4, let k=0, and it follows from (27) that(30)−μv1≥x1−x∗2−y0−x∗2.
Hence,(31)μv1+x1−x∗2≤y0−x∗2.
Then, from Lemma4, we know that the sequence μtk2vk+uk2 is nonincreasing. Therefore,(32)μtk2vk≤μtk2vk+uk2≤μt12v1+x1−x∗2≤y0−x∗2=x0−x∗2,where the second inequation follows from t1=1 and u1=x1−x∗, and the last equation follows from t1=1.
Then, it follows from Lemma3 that(33)Fxk−Fx∗≤4x0−x∗2μk+12.
The desired result follows.


## 4. Numerical Experiments

In this section, we evaluate the performance of the APDCA by applying it to the DC regularized least squares problem. We will compare the performance of the APDCA with the algorithm in [15] (PDCA) and GIST in [32].On APDCA and PDCA, we set1/μ=Lg=λmaxATA and c=Lg/2. On GIST, we set σ=10−5,m=5,η=2,and1/αmin=αmax=1030. We initialize the three algorithms at the origin point and terminate the algorithms when(34)xk−xk−1max1,xk<10−5.Furthermore, we terminate PDCA when the number of iteration is more than 5000 (denoted by “max” on the report).Example 1.
Least squares problems withl1−2 regularizer are as follows:(35)minx∈Rn12Ax−b2+cx2+λx1−cx2−λx,where A∈Rm×n,b∈Rm,c>0, and λ>0 is the regularization parameter.
This problem takes the form of (3) with fx=cx2+λx1, gx=1/2Ax−b2, and hx=cx2+λx. Note that the purpose of adding cx2 is to ensure strong convexity of fx.
To compare the performance of the three algorithms, we report the number of iterations (denoted by Iter), CPU times in seconds (denoted by CPU time), the sparsity of the solution (denoted by sparsity), and the function values at termination (denoted by fval), averaged over the 30 random instances. The numerical results are reported in Tables1 and 2, from which we can see that the APDCA always outperforms PDCA and GIST. Specifically, from Table 1, we can see that the APDCA is about 2.5 times faster than GIST and is about 5.2 times faster than PDCA for the parameter λ=5×e−4. From Table 2, we can see that the APDCA is about 2.1 times faster than GIST and is about 8.4 times faster than PDCA for the parameter λ=1×e−3. Tables 1 and 2 also show that the APDCA requires fewer iteration steps than the other two algorithms. Specifically, from Table 1, the iteration step of APDCA is about 53% of GIST for the parameter λ=5×e−4. From Table 2, the iteration step of APDCA is about 64% of GIST for the parameter λ=1×e−3. Meanwhile, Tables 1 and 2 also show that the solution given by APDCA is more sparse than that given by GIST and PDCA.Table 1
Solving (35) on random instances, λ=5×e−4.
IterCPU timemnGISTAPDCAPDCAGISTAPDCAPDCA72025601750909Max3.571.387.37144051201629802Max13.75.031.8216076801724802Max28.510.062.228801024017421002Max52.822.3112.236001280017991002Max83.834.3174.743201536017391002Max113.748.9246.550401792017781002Max160.766.9334.557602048018261002Max178.371.5366.16480230401778975Max244.3100.5524.17200256001752975Max317.4130.9692.6SparsityFvalmnGISTAPDCAPDCAGISTAPDCAPDCA720256078376111322.9755e−22.9743e−24.5442e−2144051201575161422406.1144e−26.1122e−29.4466e−2216076802367242434259.4648e−29.4612e−21.4594e−12880102403117291044961.2312e−11.2308e−11.8319e−13600128003889364457071.5896e−11.5890e−12.4309e−14320153604766437667201.8879e−11.8869e−12.8401e−15040179205497514179112.2523e−12.2512e−13.4175e−15760204806327593191812.6870e−12.6859e−14.1224e−164802304070656716101842.9070e−12.9098e−14.3889e−172002560078657449112863.2206e−13.2191e−14.8588e−1Table 2
Solving (35) on random instances, λ=1×e−3.
IterCPU timemnGISTAPDCAPDCAGISTAPDCAPDCA7202560972591Max1.50.75.414405120968602Max6.12.823.221607680993602Max13.66.150.2288010240835602Max19.810.688.6360012800973602Max36.116.7139.8432015360931602Max49.223.5202.5504017920941602Max67.532.6296.4576020480979602Max100.743.5354.9648023040992602Max116.354.9449.8720025600939602Max138.067.4558.5SparsityFvalmnGISTAPDCAPDCAGISTAPDCAPDCA72025607287039276.2438e−26.2430e−27.6433e−2144051201449138118381.3160e−11.3159e−11.6346e−1216076802168208628102.0060e−12.0058ee−12.5146e−12880102402853274536182.3976e−12.3973e−12.7654e−13600128003675355746073.0264e−13.0260e−13.5620e−14320153604368419555233.9802e−13.9798e−14.7740e−15040179205132492565014.7413e−14.7407e−15.7676e−15760204805825565673585.3208e−15.3202e−16.3891e−16480230406597631183615.7707e−15.7699e−16.9385e−17200256007270705292696.4648e−16.4640e−17.7325e−1Example 2.
Least squares problems with logarithmic regularizer are as follows:(36)minx∈Rn12Ax−b2+cx2+∑i=1nλlogxi+ε−λlogε−cx2,where A∈Rm×n,b∈Rm,ε>0 is a constant, and λ>0 is the regularization parameter.
This problem takes the form of (3) with fx=cx2+λ/εx1, gx=1/2Ax−b2, and hx=cx2+∑i=1nλxi/ε−logxi+ε+logε. Note that the purpose of adding cx2 is to ensure strong convexity of fx. For this example, we set ϵ=0.5.
To compare the performance of the three algorithms, we report the number of iterations (denoted by Iter), CPU times in seconds (denoted by CPU time), the sparsity of the solution (denoted by sparsity), and the function values at termination (denoted by fval), averaged over the 30 random instances. The numerical results are reported in Tables3 and 4, from which we can see that the APDCA always outperforms PDCA and GIST. Specifically, from Table 3, we can see that the APDCA is about 1.9 times faster than GIST and is about 8.3 times faster than PDCA for the parameter λ=5×e−4. From Table 4, we can see that the APDCA is about 1.6 times faster than GIST and is about 11.3 times faster than PDCA for the parameter λ=1×e−3. Tables 3 and 4 also show that the APDCA requires fewer iteration steps than the other two algorithms. Specifically, from Table 3, the iteration step of APDCA is about 72% of GIST for the parameter λ=5×e−4. From Table 4, the iteration step of APDCA is about 83% of GIST and is about 8.6% of PDCA for the parameter λ=1×e−3. Meanwhile, Tables 3 and 4 also show that the solution given by APDCA is more sparse than that given by GIST and PDCA.Table 3
Solving (35) on random instances, λ=5×e−4.
IterCPU timemnGISTAPDCAPDCAGISTAPDCAPDCA7202560843596Max1.60.75.514405120672602Max5.63.022.321607680873602Max12.46.149.5288010240876602Max21.210.687.4360012800871602Max32.716.6138.0432015360845602Max45.123.4194.8504017920872602Max62.532.0265.6576020480846602Max79.441.4345.3648023040877602Max104.152.8441.0720025600816602Max120.466.0547.5SparsityFvalmnGISTAPDCAPDCAGISTAPDCAPDCA72025607056619313.8979e−23.8973e−25.6815e−2144051201395134517947.1306e−27.1293e−29.3006e−2216076802123201127101.1455e−11.1453e−11.5861e−12880102402809270535971.4878e−11.4876e−12.0601e−13600128003570341845031.9187e−11.9182e−12.7236e−14320153604277410353702.3163e−12.3159e−13.1699e−15040179205042472962872.6491e−12.6486e−13.6295e−15760204805689550171993.0649e−13.0643e−14.3049e−16480230406353609380573.4115e−13.4110e−14.7749e−17200256007139608989243.7435e−13.7427e−15.1004e−1Table 4
Solving (40) on random instances, λ=1×e−3.
IterCPU timemnGISTAPDCAPDCAGISTAPDCAPDCA720256049732946580.90.45.21440512046840245823.11.920.52160768049640247396.84.046.8288010240472402452711.17.079.5360012800494402460118.311.1126.5432015360505402460226.616.5179.0504017920451402442831.821.3234.7576020480448402444641.227.7304.2648023040459402460252.835.0403.6720025600487402466870.744.0510.4SparsityFvalmnGISTAPDCAPDCAGISTAPDCAPDCA72025606286356587.5032e−27.5032e−27.5053e−2144051201300124813371.4892e−11.4891e−11.4896e−1216076801987186519652.3348e−12.3347e−12.3354e−12880102402543246226273.0410e−13.0410e−13.0416e−13600128003156307232523.8829e−13.8828e−13.8837e−14320153603831370339734.5346e−14.5344e−14.5348e−15040179204460430046055.2664e−15.2662e−15.2676e−15760204805124499152685.9404e−15.9402e−15.9417e−16480230405761554059196.8740e−16.8737e−16.8756e−17200256006365623166327.6681e−17.6678e−17.6700e−1


## 5. Conclusions

In this paper, we propose an accelerated proximal point algorithm for the difference of convex optimization problem by combining the extrapolation technique with the proximal difference of the convex algorithm. By making full use of the special structure of difference of convex decomposition and the information of stepsize, we prove that the proposed algorithm converges at rate ofO1/k2 under milder conditions. The given numerical experiments show the superiority of the proposed algorithm to some existing algorithms.



---

*Source: 9994015-2021-04-26.xml*