# Convergence of Linear Bregman ADMM for Nonconvex and Nonsmooth Problems with Nonseparable Structure

Authors: Miantao Chao; Zhao Deng; Jinbao Jian
Journal: Complexity
 (2020)

---

## Abstract

The alternating direction method of multipliers (ADMM) is an effective method for solving two-block separable convex problems and its convergence is well understood. When either the involved number of blocks is more than two, or there is a nonconvex function, or there is a nonseparable structure, ADMM or its directly extend version may not converge. In this paper, we proposed an ADMM-based algorithm for nonconvex multiblock optimization problems with a nonseparable structure. We show that any cluster point of the iterative sequence generated by the proposed algorithm is a critical point, under mild condition. Furthermore, we establish the strong convergence of the whole sequence, under the condition that the potential function satisfies the Kurdyka–Łojasiewicz property. This provides the theoretical basis for the application of the proposed ADMM in the practice. Finally, we give some preliminary numerical results to show the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

In this paper, we consider the following possibly nonconvex and nonsmooth optimization problem:(1)min∑i=1N−1fixi+gx1,⋯,xN−1,y,s.t.∑i=1N−1Aixi+By=b,where xi∈ℝnii=1,2,…,N−1,y∈ℝn are variables vectors, g:ℝl⟶ℝl=n1+n2+⋯+nN−1+n is differentiable, and each fi:ℝni⟶ℝ∪+∞ is proper and lower semicontinuous, Ai∈ℝm×nii=1,2,…,N−1,B∈ℝm×n are given matrix, and b∈ℝm.The alternating direction method of multipliers (ADMM) is a very effective method for solving the convex two-block optimization problem [1, 2]. A natural idea is to extend ADMM to solve problem (1). However, ADMM or its directly extend version may not converge, when either the involved number of blocks is more than two, or there is a nonconvex function, or there is a nonseparable structure. Recently, there have been a few developments on it, e.g., [3–13].Hong et al. [6] considered the sharing and consensus problem and showed that the classical ADMM converges to the set of stationary solutions, only provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. Li and Pong [8] studied the convergence of ADMM for some special two-block nonconvex models, where one of the matrices A and B is an identity matrix. Wang et al. [9, 10] studied the convergence of the nonconvex Bregman ADMM algorithm, which includes ADMM as a special case. Wang et al. [11] studied the convergence of the ADMM for nonconvex nonsmooth optimization with a nonseparable structure. Guo et al. [4, 5]studied the convergence of classical ADMM for two-block and multiblock nonconvex models where one of the matrices is an identity matrix. Yang et al. [13] studied the convergence of the ADMM for a nonconvex optimization model which come from the background/foreground extraction.The purpose and the main contribution of this paper is to propose and prove the convergence of a new variant ADMM for nonconvex coupled problems (1). The novelty of this paper can be summarized as follows:(1)
Compared to the existing literature, the model in this paper is more general. There is no nonseparable structure in the models considered by [4–10, 12, 13]. Wang et al. [11] considered two scenarios. If gx1,…,xN−1,y=g1x1,…,xN−1+hy, then (1) is the scenario 1 in [11]. If fix≡0, for i=1,2,…,N−1, then (1) becomes the scenario 2 in [11]. Furthermore, in this paper, the matrices Aii=1,2,…,N−1 and B are possibly not full column or row rank.(2)
The proposed algorithm combines linearization technology with regularization technology. Linearization technology and regularization technology can effectively reduce the difficulty of the solving subproblems.The rest of this paper is organized as follows. In Section2, some basic concepts and necessary preliminaries for further analysis are summarized. In Section 3, we propose the algorithm and analyze the convergence of it for 3-block nonconvex and nonsmooth coupled problems. Finally, some conclusions are made in Section 4.


## 2. Preliminaries

ℝ
n denotes the n-dimensional Euclidean space, ℝ∪+∞ denotes the extended real number set, and ℕ denotes the natural number set. The image space of a matrix Q∈ℛm×n is defined as ImQ:=Qx:x∈ℛn. PQ⋅ denotes the Euclidean projection onto ImQ. If matrix Q≠0, let μQ denote the smallest positive singular value of the matrix QQT. ⋅ represents the Euclidean norm. domf:=x∈ℝn:fx<+∞ is the domain of a function f:ℝn⟶ℝ∪+∞. x,y=xTy=∑i=1nxiyi. η1<f<η2:=x:η1<fx<η2. For a set S⊂Rn and a point x∈ℝn, let dx,S=infy∈Sy−x2. If S=∅, we set dx,S=+∞ for all x∈ℝn. For a point-to-set mapping F, its graph is defined by GraphF:=x,y:y∈Fx.Definition 1 (see [14]).
Letf:ℝn⟶ℝ∪+∞ be a proper function. If there exists δ>0 such that(2)fλx+1−λy≤λfx+1−λfy−δλ1−λ2x−y2,for all λ∈0,1 and x,y∈domf, then f is called strongly convex with modulus δ.Definition 2 (see [15]).
For a convex differential functionϕ:ℝn⟶ℝ, the associated Bregman distance is defined as(3)Δϕx,y=ϕx−ϕy−<∇ϕy,x−y>,for allx,y∈ℝn.
The Bregman distance plays an important role in iterative algorithms. The Bregman distance share many similar nice properties of the Euclidean distance. However, the Bregman distance is not a metric, since it does not satisfy the triangle inequality nor symmetry. Some examples of Bregman distance include [16](i)
Classical Euclidean distance: ifϕx=x2, then Δϕx,y=x−y2(ii)
Itakura–Saito distance: ifϕx=∑i=1mxilogxi, then Δϕx,y=∑i=1mxilogxi/yi−∑i=1mxi−yi(iii)
Mahalanobis distance: ifϕx=xQ2=xTQx with Q a symmetric positive definite matrix, then Δϕx,y=x−yQ2
Let us now collect some useful properties about Bregman distance.Proposition 1 (see [15]).
Let ϕ be differentiable and strongly convex function with modulusδ, then(i)
Δϕx,y≥0 and Δϕx,y=0 if and only if x=y(ii)
Δϕx,y≥δ/2x−y2 for all xandy
The following notations and definitions are quite standard and can be founded in [14, 17].Definition 3.
Letf:ℝn⟶ℝ∪+∞ be a proper lower semicontinuous function.(i)
TheFrėchet subdifferential, or regular subdifferential, of f at x∈domf is(4)∂^fx=x∗:limy≠xinfy⟶xfy−fx−<x∗,y−x>y−x≥0.Whenx∉domf, we set ∂^fx=∅.(ii)
The limiting subdifferential, or simply the subdifferential, off at x∈domf, written ∂fx, is defined as(5)∂fx=ν∈ℝn:∃xk⟶x,s.t.fxk⟶fx,νk∈∂^fxk,νk⟶ν.(iii)
A point that satisfies0∈∂fx is called a critical point or a stationary point of the function f. The set of critical points of f is denoted by critf.
The following proposition collects some properties of the subdifferential.Proposition 2 (see [17]).
Letf:ℝn⟶ℝ∪+∞ and g:ℝn⟶ℝ∪+∞ be proper lower semicontinuous functions. Then, the following holds:(i)
∂^fx⊆∂fx for each x∈domf. Moreover, the first set is closed and convex, while the second is closed and not necessarily convex.(ii)
Letxk,uk⊂Graph∂f be a sequence such that it converges to x∗,u∗. If limk⟶+∞fxk=fx∗, then x∗,u∗∈Graph∂f.(iii)
Ifx∈ℝn is a local minimizer of f then 0∈∂^fx⊂∂fx.(iv)
Ifg:ℝn⟶ℝ is continuous differentiable, then ∂f+gx=∂fx+∇gx.The Lagrangian function of (1), with multiplier λ∈ℝm, is defined as(6)Lx1,…,xN−1,y,λ=f1x1+⋯+fN−1xN−1+gx1,…,xN−1,y−<λ,A1x1+⋯+AN−1xN−1+By−b>.Definition 4.
Ifw∗=x1∗,…,xN−1∗,y∗,λ∗T such that(7)AiTλ∗∈∂fixi∗+∇xigx1∗,⋯,xN−1∗,y∗,i=1,2,…,N−1,BTλ∗=∇ygx1∗,⋯,xN−1∗,y∗,A1x1∗+⋯+AN−1xN−1∗+By∗−b=0,then w∗ is called a critical point or stationary point of the Lagrange function Lx1,⋯,xN−1,y,λ.
A very important technique to prove the strong convergence of the ADMM for nonconvex optimization problems relies on the assumption that the benefit function satisfying Kurdyka-Łojasiewicz property (KL property) [18–21]. There are many functions which satisfy this inequality. Especially, when the function belongs to some functional classes, e.g., semialgebraic, real subanalytic, and log-exp (see [22–24]). It is often elementary to check that such an inequality holds.
For notational simplicity, we useΦηη>0 to denote the set of concave functions φ:0,η⟶0,+∞ such that(i)
φ0=0(ii)
φ is continuous differentiable on 0,η and continuous at 0(iii)
φ′s>0,∀s∈0,η.
The KL property can be described as follows.Definition 5.
(see [18–21]) (KL property). Let f:ℝn⟶ℝ∪+∞ be a proper lower semicontinuous function. If there exists η∈0,+∞, a neighborhood U of x∗, and a function φ∈Φη, such that for all x∈U∩fx∗<f<fx∗+η, it holds that(8)φ′fx−fx∗d0,∂fx≥1,then f is said to have the KL property at x∗.Lemma 1 (see [22]) (uniformized KL property).
Suppose thatf:ℝn⟶ℝ∪+∞ is a proper lower semicontinuous function and Ω is a compact set. If fx≡f∗ for all x∈Ω and satisfies the KL property at each point of Ω. Then, there exist ε>0,η>0, and φ∈Φη such that(9)φ′fx−f∗d0,∂fx≥1,for all x∈x∈ℝn:dx,Ω<ε∩f∗<f<f∗+η.Lemma 2 (see [25]) (Descent lemma).
Leth:ℝn⟶ℝ be a continuous differentiable function where gradient ∇h is Lipschitz continuous with the modulus lh>0, then for any x,y∈ℝn, we have(10)hy−hx−<∇hx,y−x>≤lh2y−x2.Lemma 3 (see [26]).
LetQ∈Rr×p be a nonzero matrix and let μQ denote the smallest positive eigenvalue of QQT. Then, for every u∈Rp, there holds(11)PQTu≤1μQQu.


## 3. Algorithm and Convergence

For the convenience of analysis, we only consider the case ofN=2. The obtained results could naturally be generalized to the case of N>2. Thus, in the rest of this paper, we consider the following nonconvex and nonsmooth 3-block optimization problem:(12)minf1x1+f2x2+gx1,x2,y,s.t.A1x1+A2x2+By=b,where fi:ℝni⟶ℝ∪+∞i=1,2 is proper and lower semicontinuous but possibly nonconvex, g:ℝn1+n2+n⟶ℝ is differentiable, Ai∈ℝm×nii=1,2, and b∈ℝm.In this paper, we present the following algorithm for (12).Algorithm 1.
LBADMM: start withx10,,x20,y0T and λ0. With the given iteration point wk=x1k,x2k,yk,λkT, the new iteration point wk+1=x1k+1,x2k+1,yk+1,λk+1T is given as follows:(13)x1k+1∈argminf1x1+x1−x1kT∇x1gx1k,x2k,yk+β2A1x1+A2x2k+Byk−b−λkβ2+△φ1x1,x1k,x2k+1∈argminf2x2+x2−x2kT∇x2gx1k,x2k,yk+β2A1x1k+1+A2x2+Byk−b−λkβ2+△φ2x2,x2k,yk+1=argmingx1k+1,x2k+1,y+β2A1x1k+1+A2x2k+1+By−b−λkβ2+△ϕy,yk,λk+1=λk−βA1x1k+1+A2x2k+1+Byk+1−b,where △φ1x1,x1k, △φ2x2,x2k, and △ϕy,yk are the Bregman distances associated with φ1, φ2, and ϕ, respectively.Remark 1.
Due to the different structures of the problem, the algorithm in this paper is different from the existing algorithms. In order to make use of the properties of differentiable blocks and simplify the calculation of each iteration, we linearize the differentiable part in thex1 and x2 subproblems. If the function gx1,x2,y is only related to the variable y, that is, gx1,x2,y=hy, then the algorithm LBADMM will become the Bregman ADMM in [9, 10]. Different from [9, 10], we do not assume B is full row rank.
In this section, we always assume that the sequencewk=x1k,x2k,yk,λkT is generated by algorithm LBADMM. Let μ=1/μBT, where μBT denotes the smallest positive eigenvalue of BTB.Assumption 1.
(i)
∇g is lg-Lipschitz continuous, i.e., ∇gu−∇gv≤lgu−v for all u,v∈Rn(ii)
B≠0 and ImB⊃b∪ImA(iii)
∇φ1,∇φ2,∇ϕ are Lipshitz continuous with the modulus lφ1,lφ2,lϕ, respectively(iv)
φ1,φ2,ϕ strongly convex with the modulus δφ1,δφ2,δϕ, and δφ1,δφ2>lg(v)
β>max6μ22lϕ2+lg2/δϕ,6μ2lg2/δφ1−lg,6μ2lg2/δφ2−lg
The following lemma establishes the relationship between the dual variable and the original variables.Lemma 4.
For eachk∈ℕ,(14)λk+1−λk2≤3μ2lg2x1k+1−x1k2+x2k+1−x2k2+3μ2lg2+lϕ2yk+1−yk2+3μ2lϕ2yk−yk−12.Proof.
By Assumption1 (ii) and Lemma 3, we have(15)λk+1−λk≤1μBTBTλk+1−λk.
From the optimality condition ofy-subproblem in (14) yields(16)0=∇ygx1k+1,x2k+1,yk+1−BTλk+βBTA1x1k+1+A2x2k+1+Byk+1−b+∇ϕyk+1−∇ϕyk.
Taking into accountλk+1=λk−βA1x1k+1+A2x2k+1+Byk+1−b, one has(17)BTλk+1=∇ygx1k+1,x2k+1,yk+1+∇ϕyk+1−∇ϕyk.
Thus,(18)BTλk+1−BTλk2=∇ygx1k+1,x2k+1,yk+1−∇ygx1k,x2k,yk+∇ϕyk+1−∇ϕyk+∇ϕyk−1−∇ϕyk2≤∇ygx1k+1,x2k+1,yk+1−∇ygx1k,x2k,yk+∇ϕyk−1−∇ϕyk+∇ϕyk−1−∇ϕyk2≤3∇ygx1k+1,x2k+1,yk+1−∇yx1k,x2k,yk2+∇ϕyk−1−∇ϕyk2+∇ϕyk−1−∇ϕyk2≤3lg2x1k+1,x2k+1,yk+1−x1k,x2k,yk2+lϕ2yk+1−yk2+lϕ2yk−1−yk2.
It follows from the abovementioned formula and (17) that(19)λk+1−λk2≤μ2BTλk+1−λk2≤3μ2lg2x1k+1,x2k+1,yk+1−x1k,x2k,yk2+lϕ2yk+1−yk2+lϕ2yk−1−yk2≤3μ2lg2x1k+1−x1k2+x2k+1−x2k2+3μ2lg2+lϕ2yk+1−yk2+3μ2lϕ2yk−yk−12.
The proof is completed.
The augmented Lagrangian function with multiplierλ of (12) is defined as(20)Lβx1,x2,y,λ=Lx1,x2,y,λ+β2A1x1+A2x2+By−b2,where Lx1,x2,y,λ is the Lagrangian function of (12). Let(21)L^x1,x2,y,λ,y^=Lβx1,x2,y,λ+3μ2lϕ2βy−y^2.
Let(22)w^k=x1k,x2k,yk,λk,yk−1,wk=x1k,x2k,yk,λk,uk=x1k,x2k,ykT,rk=A1x1k+A2x2k+Byk−b.
The following lemma implies the monotonicity of the sequenceL^w^kk∈N.Lemma 5.
For eachk∈ℕ,(23)L^w^k+1≤L^w^k−σx1k+1−x1k2+x2k+1−x2k2+yk+1−yk2,where(24)σ=minδϕ2−3μ22lϕ2+lg2β,δφ1−lg2−3μ2lg2β,δφ2−lg2−3μ2lg2β.Proof.
From (17), we have(25)f1x1k+1+x1k+1−x1k,∇x1guk−λk,A1x1k+1+A2x2k+Byk−b+β2A1x1k+1+A2x2k+Byk−b2≤f1x1k−λk,rk+β2rk2−△φ1x1k+1,x1k,f2x2k+1+x2k+1−x2k,∇x2guk−λk,A1x1k+1+A2x2k+1+Byk−b+β2A1x1k+1+A2x2k+1+Byk−b2≤f2x2k−λk,A1x1k+1+A2x2k+Byk−b+β2A1x1k+1+A2x2k+Byk−b2−△φ2x2k+1,x2k,guk+1−λk,rk+1+β2rk+12+△ϕyk+1,yk≤gx1k+1,x2k+1,yk−λk,A1x1k+1+A2x2k+1+Byk−b+β2A1x1k+1+A2x2k+1+Byk−b2.
Adding up the abovementioned three formulas, we have(26)f1x1k+1+f2x2k+1+guk+1−λk,rk+1+β2rk+12≤f1x1k+f2x2k+x1k+1,x2k+1,ykg−λk,rk+β2rk2−x1k+1−x1k,∇x1guk+x2k+1−x2k,∇x2guk−△φ1x1k+1,x1k−△φ2x2k+1,x2k−△ϕyk+1,yk,and hence(27)f1x1k+1+f2x2k+1+guk+1−λk,rk+1+β2rk+12≤f1x1k+f2x2k+guk−λk,rk+β2rk2+gx1k+1,x2k+1,yk−guk−x1k+1−x1k,x2k+1−x2k,0,∇guk−△φ1x1k+1,x1k−△φ2x2k+1,x2k−△ϕyk+1,yk,that is,(28)Lβx1k+1,x2k+1,yk+1,λk≤Lβwk+gx1k+1,x2k+1,yk−guk−x1k+1−x1k,x2k+1−x2k,0,∇guk−△φ1x1k+1,x1k−△φ2x2k+1,x2k−△ϕyk+1,yk.
From Lemma2, Assumption 1 (iv), and Proposition 1, we obtain(29)Lβx1k+1,x2k+1,yk+1,λk≤Lβwk−δφ1−lg2x1k+1−x1k2−δφ2−lg2x2k+1−x2k2−δϕ2yk+1−yk2.
Recall that(30)Lβwk+1=Lβx1k+1,x2k+1,yk+1,λk+λk−λk+1,rk+1=Lβx1k+1,x2k+1,yk+1,λk+1βλk−λk+12.
Adding up (71) and (72), we have(31)Lβwk+1≤Lβwk−δφ1−lg2x1k+1−x1k2−δφ2−lg2x2k+1−x2k2−δϕ2yk+1−yk2+1βλk−λk+12.
Together with (14), we obtain(32)Lβwk+1≤Lβwk−δφ1−lg2x1k+1−x1k2−δφ2−lg2x2k+1−x2k2−δϕ2yk+1−yk2+3μ2lϕ2+lg2βyk+1−yk2+3μ2lϕ2βyk−yk−12+3μ2lg2βx1k+1−x1k2+3μ2lg2βx2k+1−x2k2≤Lβwk−δφ1−lg2−3μ2lg2βx1k+1−x1k2−δφ2−lg2−3μ2lg2βx2k+1−x2k2−δϕ2−3μ2lϕ2+lg2βyk+1−yk2+3μ2lϕ2βyk−yk−12,which implies that(33)Lβwk+1+3μ2lϕ2βyk+1−yk2≤Lβwk+3μ2lϕ2βyk−yk−12−δφ1−lg2−3μ2lg2βx1k+1−x1k2−δφ2−lg2−3μ2lg2βx2k+1−x2k2−δϕ2−3μ22lϕ2+lg2βyk+1−yk2.
That is, (23) holds.Remark 2.
From Assumption1 (iv), we have δϕ−lg>0 and δφ1−lg>0. Furthermore, from Assumption 1 (v), we have σ>0.Lemma 6.
If the sequencewk=x1k,x2k,yk,λkT is bounded, then(34)∑k=0+∞wk+1−wk2<+∞.Proof.
Sincewk is bounded, the sequence w^k is bounded and there exists a subsequence w^kj such that limj⟶+∞w^kjw^∗. Since f1,f2 are lower semicontinuous and g is Lipschitz differentiable, the function L^⋅ is lower semicontinuous, which leads to(35)lim  infj⟶+∞L^w^kj≥L^w^∗.
Thus,L^w^kj is bounded from below. From Lemma 5, L^w^kj is nonincreasing. Thus, L^w^kj is convergent. Furthermore, L^w^k is also convergent and L^w^k≥L^w^∗ for each k. By Lemma 5, we have(36)σx1k+1−x1k2+x2k+1−x2k2+yk+1−yk2≤L^w^k−L^w^k+1.
From the abovementioned formula, we obtain(37)σ∑k=1tx1k+1−x1k2+x2k+1−x2k2+yk+1−yk2≤L^w^1−L^w^t+1.
Note thatσ>0 and the arbitrariness of t, we obtain(38)∑k=1+∞uk+1−uk2<+∞.
In view of (14), we have(39)∑k=0+∞λk+1−λk2<+∞.
Thus,(40)∑k=0+∞wk+1−wk2<+∞.Lemma 7.
There existsδ>0 such that(41)d0,∂L^w^k+1≤δak,for allk∈ℕ,where(42)ak=x1k+1−x1k+x2k+1−x2k+yk+1−yk+x1k−x1k−1+x2k−x2k−1+yk−yk−1.Proof.
From the definition ofL^w^, we have(43)∂x1L^w^k+1=∂f1x1k+1+∇x1guk+1−A1Tλk+1+βA1Trk+1,∂x2L^w^k+1=∂f2x2k+1+∇x2guk+1−A2Tλk+1+βA2Trk+1,∂yL^w^k+1=∇yguk+1−BTλk+1+βBTrk+1+6μ2lϕ2βyk+1−yk,∂y^L^w^k+1=−6μ2lϕ2βyk+1−yk,∂λL^w^k+1=1βλk+1−λk.
From (14) and the optimality conditions, one has(44)0∈∂f1x1k+1+∇x1guk−A1Tλk+βA1TA1x1k+1+A2x2k+Byk−b+∇φ1x1k+1−∇φ1x1k,0∈∂f2x2k+1+∇x2guk−A2Tλk+βA2TA1x1k+1+A2x2k+1+Byk−b+∇φ2x2k+1−∇φ2x2k,0=∇yguk+1−BTλk+βBTA1x1k+1+A2x2k+1+Byk+1−b+∇ϕyk+1−∇ϕyk,λk+1=λk−βA1x1k+1+A2x2k+1+Byk+1−b.
That is,(45)A1Tλk+1−∇x1guk+βA1TA2x2k−x2k+1+βA1TByk−yk+1+∇φ1x1k−∇φ1x1k+1∈∂f1x1k+1,A2Tλk+1−∇x2guk+βA2TByk−yk+1+∇φ2x2k−∇φ2x2k+1∈∂f2x2k+1,∇yguk+1=BTλk+1+∇ϕyk−∇ϕyk+1,λk+1=λk−βA1x1k+1+A2x2k+1+Byk+1−b.
From (43) and (45), we have(46)ρ1k,ρ2k,ρ3k,ρ4k,ρ5kT∈∂L^w^k+1,where(47)ρ1=A1Tλk−λk+1+∇x1guk+1−∇x1guk+βA1TA2x2k−x2k+1+βA1TByk−yk+1+∇φ1x1k−∇φ1x1k+1,ρ2=A2Tλk−λk+1−∇x2guk+βA2TByk−yk+1+∇φ2x2k−∇φ2x2k+1+∇x2guk+1,ρ3k=βBTλk−λk+1+6μ2lϕ2βyk+1−yk+∇ϕyk−∇ϕyk+1,ρ4k=−6μ2lϕ2βyk+1−yk,ρ5k=1βλk−λk+1.
Thus,(48)d0,∂L^w^k+1≤ρ1k,ρ2k,ρ3k,ρ4k,ρ5kT.
It follows from Assumption1 and Lemma 4 that there exists a δ>0 such that(49)d0,∂L^w^k+1≤δak,for allk∈ℕ.
The following theorem shows that the algorithm LBADMM has global convergence.Theorem 1.
LetSw^k denote the cluster point set of w^k, then(i)
Sw^k is a nonempty compact set, and limk⟶+∞dw^k,Sw^k=0(ii)
Ifx1∗,x2∗,yd,λ∗,y^∗T∈Sw^k, then x1∗,x2∗,y∗,λ∗T∈critL⋅;(iii)
L^⋅ is finite and constant on Sw^k and equal to infk∈NL^βw^k=limk⟶+∞L^βw^k.Proof.
(i)
By the definition ofSw^k, it is trivial.(ii)
Letw^∗=x1∗,x2∗,y∗,λ∗,y^∗T∈Sw^k, then there exists a subsequence w^kj of w^k converging to w^∗. Since wk+1−wk⟶0k⟶+∞, limj⟶+∞w^kj+1=w^∗. Since λkj+1=λkj−βA1x1k+1+A2x2k+1+Byk+1−b and β>0, A1x1∗+A2x2∗+By∗−b=0Let(50)hkx1=f1x1+x1−x1kT∇x1gx1k,x2k,yk+β2A1x1+A2x2k+Byk−b−λkβ2+△φ1x1,x1k,θkx2=f2x2+x2−x2kT∇x2gx1k,x2k,yk+β2A1x1k+1+A2x2+Byk−b−λkβ2+△φ2x2,x2k.It follows from (14) that hkjx1kj+1≤hkjx1∗ and θkjx2kj+1≤θkjx2∗. Thus,(51)lim supj⟶+∞hkjx1kj+1=lim supj⟶+∞f1x1kj+1+λ∗22β≤lim supj⟶+∞hkjx1∗=f1x1∗+λ∗22β,lim supj⟶+∞θkjx2kj+1=lim supj⟶+∞f2x2kj+1+λ∗22β≤lim supj⟶+∞θkjx2∗=f2x2∗+λ∗22β.Noting thatf1 and f2 are lower semicontinuous, we have(52)lim  infj⟶+∞f1x1kj+1≥f1x1∗,lim infj⟶+∞f2x2kj+1≥f2x2∗.It follows form the abovementioned four formulas that(53)limj⟶+∞f1x1kj+1=f1x1∗,limj⟶+∞f2x2kj+1=f2x2∗.Together with the continuity of∇g and the closeness of ∂f, by taking limit in (45) along the subsequence w^kj+1 and w^kj yields(54)−∇x1gx1∗,x2∗,y∗+A1Tλ∗∈∂f1x1∗,−∇x2gx1∗,x2∗,y∗+A2Tλ∗∈∂f2x2∗,∇ygx1∗,x2∗,y∗=BTλ∗,A1x1∗+A2x2∗+By∗−b=0.That is,w∗ is a critical point of the Lagrange function L of (12).(iii)
From (53) and Lemma 5, we have(55)limj⟶+∞L^w^kj+1=L^w^∗=Lw∗.
From (55) and the descent of L^w^kk∈N, we obtain(56)limk⟶+∞L^w^k=Lw^∗.
Therefore,L^⋅ is constant on Sw^k. Moreover, infk∈NL^w^k=limk⟶+∞L^w^k.
The following theorem is the main result of this paper.Theorem 2 (strong convergence).
Suppose that Assumption1 holds, L^w^ satisfies the KL property at each point of Sw^k, then(i)
∑k=0+∞wk+1−wk<+∞,(ii)
wk converges to a critical point of L⋅Proof.
From Theorem1, we have limk⟶+∞L^w^k=L^w^∗ for all w^∗∈Sw^k. We consider two cases.(i)
If there exists an integerk0 such that L^w^k0=L^w^∗. From Lemma 5, we have(57)σx1k+1−x1k2+x2k+1−x2k2+yk+1−yk2≤L^w^k−L^w^k+1≤Lβw^k0−Lβw^∗=0,for allk>k0.Thus, for anyk>k0, we have x1k+1=x1k,x2k+1=x2k,yk+1=yk. Hence, for any k>k0+1, it follows that w^k+1=w^k and the assertion holds.(ii)
Assume thatL^w^k>L^w^∗ for all k∈ℕ. Since limk⟶+∞dw^k,Sw^k=0, it follows that for any given ε>0, there exists k1>0, such that dw^k,Sw^k<ε, for all k>k1. Since limk⟶+∞L^w^k=L^w^∗, for given η>0, there exists k2>0, such that L^w^k<L^w^∗+η, for all k>k2. Consequently, when k>k˜:=maxk1,k2,(58)dw^k,Sw^k<ε,L^w^∗<L^w^k<L^w^∗+η.
SinceSw^k is a nonempty compact set and L^⋅ is constant on Sw^k, applying Lemma 1, we have(59)φ′L^w^k−L^w^∗d0,∂L^w^k≥1,for allk>k˜.
From Lemma7, one has(60)1φ′L^w^k−L^w^∗≤d0,∂L^w^k≤δak,for allk>k˜.
From the concavity ofφ, we have(61)φL^w^k−L^w^∗−φL^w^k+1−L^w^∗≥φ′L^w^k−L^w^∗L^w^k−L^w^k+1,
Thus, associating with Lemma5 and φ′L^w^k−L^w^∗>0, we have(62)σx1k+1−x1k2+x2k+1−x2k2+yk+1−yk2≤L^w^k−L^w^k+1≤φL^w^k−L^w^∗−φL^w^k+1−L^w^∗φ′L^w^k−L^w^∗≤δakφL^w^k−L^w^∗−φL^w^k+1−L^w^∗,∀k>k˜.
For convenience, we setΔp,q=φL^w^p−L^w^∗−φL^w^q−L^w^∗. Thus,(63)x1k+1−x1k2+x2k+1−x2k2+yk+1−yk2≤δσakΔk,k+1,for allk>k˜.
That is,(64)3x1k+1−x1k+x2k+1−x2k+yk+1−yk≤33x1k+1−x1k2+x2k+1−x2k2+yk+1−yk21/2≤2ak27δ4σΔk,k+1,for allk>k˜.
By the fact2αβ≤α+βα,β>0, we obtain(65)2ak27δ4σΔk,k+1≤ak+27δ4σΔk,k+1,which along with (64) yields(66)3x1k+1−x1k+x2k+1−x2k+yk+1−yk≤ak+27δ4σΔk,k+1.
Summing up the abovementioned formula fork=k˜+1,…,m yields(67)∑k=k˜+1m3x1k+1−x1k+x2k+1−x2k+yk+1−yk≤∑k=k˜+1mak+27δ4σΔk,k+1.
Notice thatφL^βw^m+1−L^βw^∗>0,; thus,(68)∑k=k˜+1mx1k+1−x1k+x2k+1−x2k+yk+1−yk≤bk+27δ4σφL^w^k˜+1−L^w^∗−φL^w^m+1−L^w^∗≤bk+27δ4σφL^w^k˜+1−L^w^∗,where(69)bk=x1k˜+1−x1k˜+x2k˜+1−x2k˜+yk˜+1−yk˜.Thus,(70)∑k=0+∞x1k+1−x1k+x2k+1−x2k+yk+1−yk<+∞.By Lemma 4, one has ∑k=0+∞λk+1−λk<+∞. Furthermore, ∑k=0+∞wk+1−wk<+∞. Consequently wk is a Cauchy sequence. The assertion then follows immediately from Theorem 1.Remark 3.
In this section, the main conclusions are based on the boundedness assumption of the sequenceswk=x1k,x2k,yk,λkT. The following conclusion shows that we only need to assume that the sequence uk=x1k,x2k,ykT is bounded.Proposition 3.
Ifλ0∈ImB and the sequence uk=x1k,x2k,ykT is bounded, then λk is bounded.Proof.
From (17), one has(71)BTλk+12=∇ygx1k,x2k,yk+∇ϕyk+1−∇ϕyk2≤∇ygx1k,x2k,yk+lϕyk+1−yk2≤2∇ygx1k,x2k,yk2+lϕ2yk+1−yk2.
Sinceuk=x1k,x2k,ykT is bounded, BTλk is bounded. By Assumption 1 (ii) and Lemma 3, we have(72)λk+1≤1μBTBTλk+1.
Thus,λk is bounded.
Next, we present a sufficient condition of boundedness of the sequenceuk, which is similar with Lemma 8 in [4].Lemma 8.
Letwk:=x1k,x2k,yk,λk be the sequence generated by Algorithm 1. Suppose that λ0∈ImB and there exists θ>0 such that(73)infugu−θ∇ygu2≔g¯>−∞.If(74)lim  infu⟶+∞f1x1+f2x2+gu=+∞,lglϕ,β2μ2θ,then wk is bounded.Proof.
From Lemma5, we know that(75)L^x1k,x2k,yk,λk,yk−1≤L^x12,x22,y2,λ2,y1.
Then, combining withBTλk=∇yguk−1+∇ϕyk−∇ϕyk−1, we obtain(76)L^x12,x22,y2,λ2,y1≥f1x1kf2x2k+guk−λk,rk+β2rk2+3μ2lg2βyk−yk−12=f1x1k+f2x2k+guk−12βλk2+β2rk−λkβ2+3μ2lg2βyk−yk−12.
Note thatλk2≤μ2BTλk2≤2μ2∇yguk2+lϕ2yk−yk−12, we have(77)L^x12,x22,y2,λ2,y1≥12f1x1k+f2x2k+guk+12f1x1k+f2x2k+guk−12θ∇yguk2μ2β−12θ∇yguk2+β2rk−λkβ2+3μ2lg2−lϕ2βyk−yk−12.
Under the assumptions, one can easily observe thatx1k,x2k,yk,∇yguk2, and β/2rk−λk/β2 are all bounded. Boundedness of λk follows from Proposition 3. Therefore, wk is bounded.


## 4. Numerical Results

In compressed sensing, a fundamental problem is recovering ann-dimensional sparse signal x from a set of m incomplete measurements. In such a case one needs to find the sparsest solution of a linear system, which can be modeled as(78)minx0,s.t.Dx=b,where D∈ℛm×n is the measurement matrix, b∈ℛm is the observed data, c>0 is a regularization parameter, and x0 denotes the number of nonzero elements of x. In general, the abovementioned models are NP-hard. In order to overcome such a difficulty, one can relax the l0 regularization to l1/2 regularization. And, some scholars generally solve the following problems instead of solving problem (78) [10, 27]:(79)mincx1/21/2+12y2,s.t.Dx−y=b,where(80)x1/2=∑i=1nxi1/22Based on (79), we construct the following problems:(81)mincx11/21/2+12x22+12B1x1+B2x2+y2s.t.A1x1+A2x2+y=b.In order to verify the effectiveness of the algorithm LBADMM, we now focus on applying the algorithm LBADMM to solve the nonconvex optimization problem (81). Applying the algorithm LBADMM to problem (81) with φixi=1/2xiμiIi−βAiTAi2i=1,2 and ϕy=μ3/2y2, we have(82)x1k+1=H1μ1G1x1k−B1TB1x1k+B2x2k+yk+βA1TA2x2k+yk−b−λkβ;2cμ1,x2k+1=11+μ2G2x2k−B2TB1x1k+B2x2k+yk+βA2TA1x1k+1+yk−b−λkβ,yk+1=11+β+μ3μ3yk−B1x1k+1+B2x2k+1+βA1x1k+1+A2x2k+1−b−λkβ,λk+1=λk−βA1x1k+1+A2x2k+1+Byk+1−b,where H⋅;⋅ is the half shrinkage operator [27] defined as Hx;τ=hτx1,hτx2,…,hτxn⊤ with(83)hτxi=2xi31+cos23π−φxi,xi>5434τ2/3;0,otherwise,with(84)φxi=arccosτ8xi3−3/2.In the experiment, we chooseAi∼N0,1, to normalize the columns to have unit L1/2 norm. The variable xi0i=1,2 are generated with 100 nonzero entries, each sample from an Gaussian distribution. The variables x10, x20, y0, and λ0 were initialized to be zero. The vector b=A1x10+A2x20+y0+v, where v∼N0,10−3I. We set μ1=30, μ2=30, μ3=1, and β=20, and the regularization parameter c=1. It is easy to verify that the parameters meet Assumption 1 (v). Defining the residual at iteration k as rk=A1x1k+A2kx2k+y−b, a reasonable termination criterion is that the residual must be small, so we choose the stop criterion as(85)rk2≤m10−4.The numerical results are reported in Table1. The codes were written by matlab R2016a, the computer running the program is configured as Windows 10 system, Inter (R) Core (TM) i7-6500U 2.5 GHz CPU, 8 GB memory. We report the number of iterations (“Iter”.), the computing time in seconds (“Time”) and the objective function value (“f-val”). Numerical results show that the Algorithm LBADMM is stable and effective.Table 1
Numerical results.
Data
IPPRSM
n1
n2
m
Iter
Time (s)
f-val
1500
1500
1500
94
3.942479
402.69
1500
1500
2000
76
4.031269
650.11
2000
1500
2000
84
5.359473
636.09
1500
2000
2000
78
5.213782
523.09
2000
2000
1500
95
5.904308
346.26
2000
2000
2000
95
7.222839
514.67
3000
3000
3000
92
17.289544
727.81
3000
3000
4000
99
21.769152
1242.77
4000
4000
4000
96
32.752034
924.24
5000
5000
5000
106
58.176851
1138.52
6000
6000
5000
114
84.718137
1035.05
6000
6000
6000
113
104.601905
1366.83A part of computational results are presented in Figures1–3. In each figure, we plot the trend of the objective value (“objective-value”) and the trend of the residual defined by rk=A1x1k+A2kx2k+yk−b (“r2”).Figure 1
n1 = 1500, n2 = 1500, and m = 2000.
(a)
(b)Figure 2
n1 = 3000, n2 = 300, and m = 3000.
(a)
(b)Figure 3
n1 = 6000, n2 = 6000, and m = 6000.
(a)
(b)


## 5. Conclusions

We propose a new algorithm called linear Bregman ADMM for the three-blocks optimization problem with the nonseparable structure. The proposed algorithm integrates the basic ideas of the linearization technology and regularization technology. We show that any cluster point of the sequence generated by the proposed algorithm is a critical point. Under the condition that the potential function satisfies the Kurdyka-Łojasiewicz property and the penalty parameter is larger than a constant, the strong convergence of the algorithm is proved. Preliminary numerical results show that the algorithm LBADMM is stable and effective.



---

*Source: 6237942-2020-02-26.xml*