# Convergence Rate Analysis of the Proximal Difference of the Convex Algorithm

Authors: Xueyong Wang; Ying Zhang; Haibin Chen; Xipeng Kou
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In this paper, we study the convergence rate of the proximal difference of the convex algorithm for the problem with a strong convex function and two convex functions. By making full use of the special structure of the difference of convex decomposition, we prove that the convergence rate of the proximal difference of the convex algorithm is linear, which is measured by the objective function value.


---

## Body

## 1. Introduction

Difference of convex programming (DCP) is a kind of important optimization problem that the objective function can be written as the difference of convex (DC) functions. The DCP problem has found many applications in assignment and power allocation [1], digital communication system [2], compressed sensing [3], and so on [4–6].Up to now, one of the classical algorithms for DCP is the DC algorithm (DCA) [7] in which the nonconvex part of the objective function is replaced by a linear approximation. By DCA, only a convex optimization subproblem needs to be solved at each iteration. After that, the DCA has been attracted by a lot of researchers. Le Thi et al. [8] proved the linear convergence rate of DCA by employing the Kurdyka–Lojasiewicz inequality. Assuming that the subproblem of DCA can be easily solved [6], Gotoh et al. [4] proposed the proximal DC algorithm (PDCA) for solving the DCP, in which not only the nonconvex part in the objective function is replaced by the same technique as in DCA but also the convex part is replaced by a quadratic approximal. The PDCA reduces to the classical proximal gradient algorithm for convex programming if the nonconvex part of the objective function is void [9]. To accelerate the PDCA, Wen et al. [10] introduced a new type of proximal algorithm (PDCAe) with the help of an extrapolation technique. Since the convergence rate of PDCAe heavily depends on the Kurdyka–Lojasiewicz inequality, PDCAe converges linearly in general [10].In this paper, we study the linear convergence rate of PDCA by the structure, which is different from the techniques in [8, 10]. Under conditions that the objection function can be divided into difference of a strong convex function and two convex functions with Lipschitz continuous gradient, we prove the linear convergence rate of PDCA, which is measured by the objective function value.The remainder of the paper is organized as follows. In Section2, several useful preliminaries are recalled. In Section 3, more details about the DC optimization problem are given, and the PDCA proposed in [4] is listed for the sake of simplicity. The linear convergence rate of the PDCA is established in Section 4. Final remarks are given in Section 5.


## 2. Preliminaries

In this section, we recall some useful definitions and properties.Letf:Rn⟶−∞,+∞ be an extended real function. The domain of f is denoted by(1)domf=x∈Rn:fx<+∞.Iffx never equals −∞ for all x∈domf and dom f≠∅, we say that f is a proper function. If the proper function is lower semicontinuous, then it is called a closed function. A proper closed function fx is said to be level bounded if the lower level set of f (i.e., x∈Rn|fx≤r,∀r∈R) is bounded.Letf:Rn⟶R∪+∞ be a proper closed function. Then, the limit subdifferential of f at x∈domf is defined as follows:(2)∂fx=v∈Rn:∃xt⟶fx,vt⟶vwithlim infy⟶xtfy−fxt−vt,y−xty−xt≥0,∀t,where z⟶fx denote z⟶x and fz⟶fx. Note that dom ∂f=x∈Rn:∂fx≠∅. It is well known that the limit subdifferential reduces to the classical subdifferential in convex analysis when fx is a convex function, that is,(3)∂fx=v∈Rn:fu−fx−v,u−x≥0,∀u∈Rn.Furthermore, iff is continuously differentiable, then the limit subdifferential reduces to the gradient of f denoted by ∇f.


## 3. DC Programming and PDCA

In this section, we begin to consider the DC programming problem:(4)minx∈RnFx≔fx+gx−hx,where f:Rn⟶R is a strong convex function with constant a>0 and g,h:Rn⟶R are convex functions, and their gradients are Lipschitz continuous with constants Lg>0 and Lh>0, respectively. Throughout the paper, we assumed that Fx is level bounded and a>1. Apparently, (4) is a DC optimization problem and can be solved by the following DCA Algorithm 1.Algorithm 1:DCA for problem (4).
(1)
Initial step: chooseε>0andx0∈Rn, and set k=0.(2)  Iterative step: compute the new point by the following formula:(3)
xk+1=arg minx∈Rnfx+gx−hxk−∇hxk,x−xk,(4)
untilxk+1−xk≤ε is satisfied.Although the subproblem (Algorithm2) is convex, it may not have closed solutions. To solve this drawback, Gotoh et al. proposed the following PDCA.Algorithm 2:PDCA for problem (4).
(1)
Initial step: choose0<μ<1/maxLg,Lh,ε>0,andx0∈Rn, and set k=0.(2)  Iterative step: compute the new point by the following formula:(3)
xk+1=arg minx∈Rnfx+gxk−hxk−∇gxk−∇hxk,x−xk+1/2μx−xk2,(4)untilxk+1−xk≤ε is satisfied.


## 4. The Convergence Rate of PDCA

In this section, we give the linear convergence rate of PDCA. To continue, the following lemma is useful.Lemma 1.
Letf:Rn⟶R be a continuous differentiable function with Lipschitz continuous gradient with Lipschitz constant L>0. Then, for any L′>L, it holds that(5)fx≤fy+∇fy,x−y+L′2x−y2,∀x,y∈Rn.By Lemma1, we have the following result.Lemma 2.
Letxk be generated in Algorithm 2. Then,(6)μFx−Fxk+1≥x−xk+12−x−xk2.Proof.
Sincef is strongly convex with parameter a>0, it holds that(7)fx≥fxk+1+ξk+1,x−xk+1+a2μx−xk+12,where ξk+1∈∂fxk+1.
Since∇hx is Lipschitz continuous with constant Lh>0, by (5), there exists 0<μ≤1/Lh such that(8)hx≤hxx+∇hxk,x−xk+12μx−xk2,that is,(9)−hx≥−hxk−∇hxk,x−xk−12μx−xk2.
Sinceg is a convex function, we have(10)gx≥gxk+∇gxk,x−xk.
Summing (7), (9), and (10), we get(11)fx+gx−hx≥fxk+1+gxk−hxk+ξk+1,x−xk+1+∇gxk−∇hxk,x−xk+a2μx−xk+12−12μx−xk2.
On the contrary, sinceh is a convex function, we have(12)hx≥hxk+∇hxk,x−xk,which is equivalent to the following form:(13)−hx≤−hxk−∇hxk,x−xk.
Since∇gx is Lipschitz continuous with constant Lg>0, by (5), there exists 0<μ≤1/Lg such that(14)gx≤gxk+∇gxk,x−xk+12μx−xk2.
Summing (13) and (14), we have(15)gx−hx≤gxk−hxk+∇gxk−∇hxk,x−xk+12μx−xk2.
Addingfx on both sides of (15), we get(16)fx+gx−hx≤fx+gxk−hxk+∇gxk−∇hxk,x−xk+12μx−xk2.
Takingx=xk+1, it follows that(17)fxk+1+gxk+1−hxk+1≤fxk+1+gxk−hxk+∇gxk−∇hxk,xk+1−xk+12μxk+1−xk2.
By optimality conditions of Algorithm2, we know that(18)ξk+1+∇gxk−∇hxk+1μxk+1−xk=0,where ξk+1∈∂fxk+1, which means that(19)−1μxk+1−xk=ξk+1+∇gxk−∇hxk.
By (11) and (17), it holds that(20)Fx−Fxk+1≥ξk+1,x−xk+1+∇gxk−∇hxk,x−xk+1+a2μx−xk+12−12μx−xk2−12μxk−xk+12=−1μxk+1−xk,x−xk+1+a2μx−xk+12−12μx−xk2−12μxk−xk+12=12μxk−xk+12+x−xk+12−x−xk2+a2μx−xk+12−12μx−xk2−12μxk−xk+12=12μ1+ax−xk+12−2x−xk2≥1μx−xk+12−x−xk2,where the first equality follows from (19) and the last inequality follows from a>1. The desired result follows.
Now, we are at a position to prove the main theorem as follows.Theorem 1.
Letxk be generated in Algorithm 2. Then,(21)Fxk−Fx∗≤x0−x∗2μk,where x∗ is the stationary point of (4).Proof.
By Lemma2, let x=xk, and we have that(22)μFxk−Fxk+1≥xk+1−xk2≥0.
Then, it follows fromμ>0 that Fxk≥Fxk+1, which means that the sequence Fxk is nonincreasing. Then, for any k0∈N, it follows that(23)∑k=0k0−1Fxk+1≥∑k=0k0−1Fxk0=k0Fxk0.
By Lemma2 again, let x=x∗, and we have that(24)μFx∗−Fxk+1≥xk+1−x∗2−xk−x∗2,which implies that(25)μk0Fx∗−∑k=0k0−1Fxk+1≥xk0−x∗2−x0−x∗2≥−x0−x∗2.
By (23) and (25), it yields that(26)μk0Fx∗−Fxk0≥−x∗−x02,and the desired result follows.


## 5. Conclusions

In this paper, we give the linear convergence rate of PDCA for the case that the objective function is divided into a strong convex function and two convex functions. Different from the method in [8, 10], which depends heavily on the Kurdyka–Lojasiewicz inequality, we give a simple proof by the special structure of the optimization problem. Actually, there may be some other potential applications about the proposed PDCA. We leave this work in the future. For example, we will study further applications of the PDCA algorithm to some nonconvex problems [11, 12], tensor optimization problems [13, 14], and so on [15–18].



---

*Source: 5629868-2021-01-04.xml*