# A Proximal Alternating Direction Method of Multipliers with a Substitution Procedure

Authors: Miantao Chao; Yongxin Zhao; Dongying Liang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we considers the separable convex programming problem with linear constraints. Its objective function is the sum ofm individual blocks with nonoverlapping variables and each block consists of two functions: one is smooth convex and the other one is convex. For the general case m≥3, we present a gradient-based alternating direction method of multipliers with a substitution. For the proposed algorithm, we prove its convergence via the analytic framework of contractive-type methods and derive a worst-case O1/t convergence rate in nonergodic sense. Finally, some preliminary numerical results are reported to support the efficiency of the proposed algorithm.


---

## Body

## 1. Introduction

In this paper, we consider the following convex minimization model with linear constraints and separable objective function:(1)min∑i=1mfixi+gixi∑i=1mAixi=b,xi∈Xi,i=1,…,m,where fi:ℛni⟶ℛ∪+∞i=1,…,m are closed proper convex functions and gi:ℛni⟶ℛi=1,…,m are smooth convex functions, Xi⊆ℛnii=1,…,m are closed convex sets, Ai∈ℛl×nii=1,…,m are given matrices, and b∈ℛl is a given vector. Furthermore, we assume that each gi has Lipschitz-continuous gradient, i.e., there exists Li>0 such that(2)∇gix−∇giy≤Lix−y,for allx,y∈Xi.Throughout the paper, the solution set of (1) is assumed to be nonempty.A fundamental method for solving (1) in the case of m=2 is the alternating direction method of multipliers (ADMM), which was presented originally in [1, 2]. We refer to [3, 4] for some review papers on ADMM. There are many problems of form (1) with m≥3 in contemporary applications, such as the robust principal component analysis model [5], the total variation-based image restoration problem [6], the superresolution image reconstruction problem [7, 8], the multistage stochastic programming problem [9], the deblurring Poissonian images problem [10], the latent variable Gaussian graphical model selection [11], the quadratic discriminant analysis model [12], and the electrical engineering [13, 14]. Then, our discussion focuses on (1) in the case of m≥3.A natural idea for solving (1) is to extend the ADMM from the special case m=2 to the general case m≥3. This straightforward extension can be written as follows:(3)xik+1∈arg minxi∈Xifixi+gixi+12∑j=1i−1Ajxjk+1+Aixi+∑j=i+1mAjxjk−b−μλkH2,i=1,2,…,m,λk+1=λk−H∑j=1mAjxjk+1−b.The convergence of (3) is proved in some special cases (see [15–17]). Unfortunately, without further conditions, the direct extension of ADMM (3) for the general case m≥3 may fail to converge (see [18]). In [19, 20], the authors present two convergent semiproximal ADMM for two types of 3-block problems. Recently, He et al. [21] showed that if a new iterate is generated by correcting the output of (3) with a substitution procedure, then the sequence of iterates converges to a solution of (1). Since then, several variants of the ADMM were proposed for solving (1) (see [21–26]).In (3), all the xi-related subproblems are in the form of(4)minfixi+gixi+12Aixi−aiH2xi∈Xi,with a certain known ai∈ℛl and a symmetric positive definite matrix H. When Ai is not the identity matrix, problem (4) becomes complicated. A popular technique is to linearize the quadratic term of (4) (see [27, 28]), that is, one can solve the following problem instead of (4):(5)minfixi+gixi+12τixi−ci2xi∈Xiwith a certain known ci∈ℛl. In general, one can solve the following problem instead of (4):(6)minfixi+gixi+12Aixi−aiH2+12xi−xikGi2xi∈Xi,where xik is the current iteration. If Gi=τiIi−AiTHAi≻0, then (6) becomes the form of (5).Sincegi is smooth, the following problem is easier than (6):(7)minfixi+∇gixik,xi−xik+12Aixi−aiH2+12xi−xikGi2xi∈Xi.Now, we can give the gradient-based ADMM (G-ADMM) iterative scheme as follows:(8)x¯ik=arg minxi∈Xifixi+∇gixik,xi−xik+12∑j=1i−1Ajx¯jk+Aixi+∑j=i+1mAjxjk−b−H−1λkH2+12xi−xikGi2,i=1,…,m,λ¯k=λk−H∑j=1mAjx¯jk−b.In this paper, imal ADMM with a substitution based on (8). In Section 2, we provide some preliminaries for further analysis. Then, we present the gradient-based alternating direction method of multipliers with a substitution (G-ADMM-S) for solving (1) and its convergence is shown in Section 3. In Section 4, we estimate the worst-case iteration complexity for the proposed algorithm in nonergodic sense. In Section 5, some preliminary numerical results are reported to support the efficiency of the proposed algorithm. Finally, some conclusions are given in Section 6.


## 2. Preliminaries

In this section, we provide some preliminaries. Letx,y=xTy and x=x,x. G≻0≽0 denotes that G is a positive definite (semidefinite) matrix. For any positive definite matrix G, we denote ⋅G as the G-norm. If G is the product of a positive parameter β and the identity matrix I, i.e., G=βI, we use a simpler notation: ⋅G=⋅β. Let f:ℛn⟶−∞,+∞. The domain of f denoted by domf:=x∈ℛnfx<+∞. We say that f is convex if(9)ftx+1−ty≤tfx+1−tfy,∀x,y∈ℛn,∀t∈0,1.For convex functionf, the subdifferential of f is the set-valued operator defined by(10)∂fx≔ξ∈ℛnfy≥fx+y−x,ξ,∀y∈domf.


### 2.1. Variational Characterizations of (1)

LetΘixi=fixi+gixi, i=1,2,…,m, and W:=X1×X2×⋯×Xm×ℛl. Since all Θixi are convex functions, by invoking the first-order necessary and sufficient condition for convex programming, one can easily find out that problem (1) is characterized by the following variational inequality: we obtain w∗=x1∗,x2∗,…,xm∗,λ∗∈W and ξi∗∈∂fixi∗i=1,2,…,m such that(11)xi−xi∗,ξi∗+∇gixi∗−AiTλ∗≥0,λ−λ∗,∑i=1mAixi∗−b≥0,for all x1,x2,…,xm,λ∈W.The Lagrange function of (1) is given by(12)Lx1,x2,…,xm,λ=∑i=1mΘixi−λT∑i=1mAixi−b,x1,x2,…,xm,λ∈W.Letx1∗,x2∗,…,xm∗,λ∗ be a saddle point of the Lagrange function Lx1,x2,…,xm,λ. That is, for any λ∈ℛl and xi∈Xi i=1,2,…,m,(13)Lx1∗,x2∗,…,xm∗,λ≤Lx1∗,x2∗,…,xm∗,λ∗≤Lx1,x2,…,xm,λ∗.Finding a saddle point ofLx1,x2,…,xm,λ is equivalent to finding a w∗=x1∗,x2∗,…,xm∗,λ∗∈W such that(14)Θ1x1−Θ1x1∗+x1−x1∗T−A1Tλ∗≥0,∀x1∈X1,Θ2x2−Θ2x2∗+x2−x2∗T−A2Tλ∗≥0,∀x2∈X2,⋯Θmxm−Θmxm∗+xm−xm∗T−AmTλ∗≥0,∀xm∈Xm,λ−λ∗T∑i=1mAixi∗−b≥0,∀λ∈ℛl.Letx=x1,x2,…,xmT,w=x1,x2,…,xm,λT,Θx=∑i=1mΘixi, and(15)Gw=−A1Tλ,−A2Tλ,…,−AmTλ,∑i=1mAixi−bT.Then, (14) can be rewritten as the following variational inequality (VI): we obtain w∗=x1∗,x2∗,…,xm∗,λ∗∈W such that(16)VIW,G,Θ:Θx−Θx∗+w−w∗TGw∗≥0,∀w∈W.Let W∗ be the solution set of VIW,G,Θ. Since we have assumed that the solution set of (1) is nonempty, W∗ is also nonempty. It follows from the definition of Gw that(17)w′−w″TGw′=w′−w″TGw″,∀w′,w″∈W.


### 2.2. Some Notations

Letxk=x1k,x2k,…,xmkT, x¯k=x¯1k,x¯2k,…,x¯mkT, wk=x1k,…,xmk,λkT, w¯k=x¯1k,…,x¯mk,λ¯kT, and v=x2,…,xm,λT. Let H and Gi (i=1,2,…,m) be given positive definite matrices, A=A1,A2,…,Am. λmax⋅ denotes the maximum eigenvalue of one matrix, and λmin⋅ denotes the minimum eigenvalue of one matrix. The following notions will be used in the later analysis:(18)M=A2THA20⋯0A3THA2A3THA3⋯0⋮⋮⋱⋮AmTHA2AmTHA3⋯AmTHAm,M¯=A2THA20⋯00A3THA2A3THA3⋯00⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯AmTHAm000⋯0H−1,Q=A2THA2A2THA3⋯A2THAmA2TA3THA2A3THA3⋯A3THAmA3T⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯AmTHAmAmTA2A3⋯AmH−1,P=diagA2THA2,A3THA3,…,AmTHAm,H−1,Dk=G1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jkH−1λk−λ¯k,(19)bk=wk−w¯kTDk+λk−λ¯kT∑j=2mAjxjk−x¯jk.It is easy to see that(20)Q=A2TH1/2A3TH1/2⋮AmTH1/2H−1/2A2TH12,A3TH12,…,AmTH12,H−12≽0.


## 2.1. Variational Characterizations of (1)

LetΘixi=fixi+gixi, i=1,2,…,m, and W:=X1×X2×⋯×Xm×ℛl. Since all Θixi are convex functions, by invoking the first-order necessary and sufficient condition for convex programming, one can easily find out that problem (1) is characterized by the following variational inequality: we obtain w∗=x1∗,x2∗,…,xm∗,λ∗∈W and ξi∗∈∂fixi∗i=1,2,…,m such that(11)xi−xi∗,ξi∗+∇gixi∗−AiTλ∗≥0,λ−λ∗,∑i=1mAixi∗−b≥0,for all x1,x2,…,xm,λ∈W.The Lagrange function of (1) is given by(12)Lx1,x2,…,xm,λ=∑i=1mΘixi−λT∑i=1mAixi−b,x1,x2,…,xm,λ∈W.Letx1∗,x2∗,…,xm∗,λ∗ be a saddle point of the Lagrange function Lx1,x2,…,xm,λ. That is, for any λ∈ℛl and xi∈Xi i=1,2,…,m,(13)Lx1∗,x2∗,…,xm∗,λ≤Lx1∗,x2∗,…,xm∗,λ∗≤Lx1,x2,…,xm,λ∗.Finding a saddle point ofLx1,x2,…,xm,λ is equivalent to finding a w∗=x1∗,x2∗,…,xm∗,λ∗∈W such that(14)Θ1x1−Θ1x1∗+x1−x1∗T−A1Tλ∗≥0,∀x1∈X1,Θ2x2−Θ2x2∗+x2−x2∗T−A2Tλ∗≥0,∀x2∈X2,⋯Θmxm−Θmxm∗+xm−xm∗T−AmTλ∗≥0,∀xm∈Xm,λ−λ∗T∑i=1mAixi∗−b≥0,∀λ∈ℛl.Letx=x1,x2,…,xmT,w=x1,x2,…,xm,λT,Θx=∑i=1mΘixi, and(15)Gw=−A1Tλ,−A2Tλ,…,−AmTλ,∑i=1mAixi−bT.Then, (14) can be rewritten as the following variational inequality (VI): we obtain w∗=x1∗,x2∗,…,xm∗,λ∗∈W such that(16)VIW,G,Θ:Θx−Θx∗+w−w∗TGw∗≥0,∀w∈W.Let W∗ be the solution set of VIW,G,Θ. Since we have assumed that the solution set of (1) is nonempty, W∗ is also nonempty. It follows from the definition of Gw that(17)w′−w″TGw′=w′−w″TGw″,∀w′,w″∈W.


## 2.2. Some Notations

Letxk=x1k,x2k,…,xmkT, x¯k=x¯1k,x¯2k,…,x¯mkT, wk=x1k,…,xmk,λkT, w¯k=x¯1k,…,x¯mk,λ¯kT, and v=x2,…,xm,λT. Let H and Gi (i=1,2,…,m) be given positive definite matrices, A=A1,A2,…,Am. λmax⋅ denotes the maximum eigenvalue of one matrix, and λmin⋅ denotes the minimum eigenvalue of one matrix. The following notions will be used in the later analysis:(18)M=A2THA20⋯0A3THA2A3THA3⋯0⋮⋮⋱⋮AmTHA2AmTHA3⋯AmTHAm,M¯=A2THA20⋯00A3THA2A3THA3⋯00⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯AmTHAm000⋯0H−1,Q=A2THA2A2THA3⋯A2THAmA2TA3THA2A3THA3⋯A3THAmA3T⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯AmTHAmAmTA2A3⋯AmH−1,P=diagA2THA2,A3THA3,…,AmTHAm,H−1,Dk=G1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jkH−1λk−λ¯k,(19)bk=wk−w¯kTDk+λk−λ¯kT∑j=2mAjxjk−x¯jk.It is easy to see that(20)Q=A2TH1/2A3TH1/2⋮AmTH1/2H−1/2A2TH12,A3TH12,…,AmTH12,H−12≽0.


## 3. Algorithm and Convergence Analysis

In this section, we first describe G-ADMM-S and then prove its convergence via the analytic framework of the contractive-type method [29]. Throughout this section, we assume that λminGi>Li (i=1,2,…,m). We propose the iterative scheme of G-ADMM-S for solving (1) in Algorithm G-ADMM-S:Letγ∈0,2Dk and bk be defined in (18) and (19), respectively. Start with w0. With the given iterate wk, the new iterate wk+1 is given as follows:Step 1 (G-ADMM procedure). Execute scheme (8) to generate w¯k.Step 2 (substitution procedure). Generate the new iterate wk+1 via(21)wk+1=wk−αkDk,where(22)αk=γαkwithαk=bkDk2.Next, we establish the global convergence of Algorithm G-ADMM-S following the analytic framework of contractive-type methods. We outline the proof sketch as follows:(1)
Prove that−Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk whenever wk≠w¯k, where w¯k is generated by G-ADMM scheme (8) and w∗∈W∗(2)
Prove that the sequence generated by Algorithm G-ADMM-S is contractive with respect toW∗(3)
Establish the convergenceAccordingly, we divide the convergence analysis into three sections to address the claims listed above.


### 3.1. Verification of the Descent Direction

In this section, we show that−Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk whenever wk≠w¯k and w∗∈W∗. For this purpose, we first prove an important inequality for the output of G-ADMM procedure (8), which will be used often in our further discussion.Theorem 1.
w
¯
k
∈
W and(23)Θx−Θx¯k+w−w¯kTGw¯k+Pk≥w−w¯kTDk,∀w∈W,where Pk=w−w¯kTA1TA2T⋮AmT0H∑j=2mAjxjk−x¯jk.Proof.
By the optimality condition of thexi-related subproblem in (8), for i=1,2,…,m, we have x¯ik∈Xi and(24)0∈∂fix¯ik+∇gixik+AiTH∑j=1iAjx¯jk+∑j=i+1mAjxjk−b−H−1λk+Gix¯ik−xik+∂δx¯ikXi,where δXi is the indicator function of the set Xi. Thus, w¯k∈W and there exists η∈∂δXix¯ik such that(25)−η∈∂fix¯ik+∇gix¯ik+ρ=∂Θix¯ik+ρ,where ρ≔∇gixik−∇gix¯ik+AiTH∑j=1iAjx¯jk+∑j=i+1mAjxjk−b−H−1λk+Gix¯ik−xik. From the subgradient inequality, one has(26)Θixi−Θix¯ik≥xi−x¯ikT−η−ρ,∀xi∈Xi,Θixi−Θix¯ik+xi−x¯ikTρ≥−xi−x¯ikTη,∀xi∈Xi.
From the definition of∂δXix¯ik, one has(27)Θixi−Θix¯ik+xi−x¯ikTρ≥0,∀xi∈Xi.
That is,(28)0≤Θixi−Θix¯ik+xi−x¯ikT∇gixik−∇gix¯ik+AiTH∑j=1iAjx¯jk+∑j=i+1mAjxjk−b−H−1λk+Gix¯ik−xik,for all xi∈Xi. Substituting λ¯k=λk−H∑j=1mAjx¯jk−b (see (8)) in the above inequality, we obtain(29)0≤Θixi−Θix¯ik+xi−x¯ikT∇gixik−∇gix¯ik−AiTλ¯k+AiTH∑j=i+1mAjxjk−x¯jk+Gix¯ik−xik,for all xi∈Xi. Summing the above inequality over i=1,2,…,m, we obtain(30)Θx−Θx¯k+x−x¯kT−ATλ¯kCk≥0,where(31)Ck=G1x¯1k−x1k+∇g1x1k−∇g1x¯1k+A1TH∑j=2mAjxjk−x¯jk⋯Gix¯ik−xik+∇gixik−∇gix¯ik+AiTH∑j=i+1mAjxjk−x¯jk⋯Gmx¯mk−xmk+∇gmxmk−∇gmx¯mk.
Then, by adding the following term(32)x−x¯kTG1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jkto both sides of (30), we get(33)Θx−Θx¯k+x−x¯kT−ATλ¯k+A1TH∑j=2mAjxjk−x¯jk⋯AiTH∑j=2mAjxjk−x¯jk⋯AmTH∑j=2mAjxjk−x¯jk≥x−x¯kTG1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jk.
Sinceλ¯k=λk−H∑j=1mAjx¯jk−b, we have(34)∑j=1mAjx¯jk−b+H−1λ¯k−λk=0.
Combining the above two formulas, we have(35)Θx−Θx¯k+w−w¯kTGw¯k+Hk≥w−w¯kTQk,∀w∈W,where(36)Hk=A1TH∑j=2mAjxjk−x¯jk,A2TH∑j=2mAjxjk−x¯jk,…,AmTH∑j=2mAjxjk−x¯jk,0T,Qk=G1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jkH−1λk−λ¯k.
Using the notations ofGw¯k (see (15)) and Dk (see (18)), assertion (23) is proved.Based on assertion (23), we can get the following result.Corollary 1.
(37)
w
¯
k
−
w
∗
T
D
k
≥
λ
k
−
λ
¯
k
T
∑
j
=
2
m
A
j
x
j
k
−
x
¯
j
k
,
∀
w
∗
∈
W
∗
.Proof.
It follows from (23) that(38)w¯k−w∗TDk≥Θx¯k−Θx∗+w¯k−w∗TGw¯k+w¯k−w∗TA1TA2T⋮AmTH∑j=2mAjxjk−x¯jk.
Using (17) and the optimality ofw∗, we have(39)Θx¯k−Θx∗+w¯k−w∗TGw¯k=Θx¯k−Θx∗+w¯k−w∗TGw∗≥0.
Thus,(40)w¯k−w∗TDk≥H∑j=1mAjx¯jk−∑j=1mAjxj∗T∑j=2mAjxjk−x¯jk.
Since∑j=1mAjxj∗=b and H∑j=1mAjx¯jk−b=λk−λ¯k,(41)w¯k−w∗TDk≥λk−λ¯kT∑j=2mAjxjk−x¯jk.
The next theorem implies that−Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk whenever wk≠w¯k.Theorem 2.
For allw∗∈W∗,(42)wk−w∗TDk≥bk≥∑j=1mxjk−x¯jkGj2−Lixjk−x¯jk+12vk−v¯kP+Q2≥∑j=1mλminGj−Lixjk−x¯jk2+12λk−λ¯kH−12.Proof.
It follows from (37) that(43)wk−w∗TDk≥wk−w¯kTDk+λk−λ¯kT∑j=2mAjxjk−x¯jk.That is, wk−w∗TDk≥bk. Now, we treat the first term of the right-hand side of (43):(44)wk−w¯kTDk=∑i=1mxik−x¯ikGi2+xik−x¯ikT∇gix¯ik−∇gixik+vk−v¯kTM¯vk−v¯k≥∑i=1mxik−x¯ikGi2−Lixjk−x¯jk+vk−v¯kTM¯vk−v¯k≥∑i=1mλminGi−Lixik−x¯ik2+vk−v¯kTM¯vk−v¯k,where the first inequality follows from the Lipschitz continuous of ∇gi. Then, let us deal with the second term of the right-hand side of (43):(45)λk−λ¯kT∑j=2mAjxjk−x¯jk=vk−v¯kT00⋯0000⋯00⋮⋮⋱⋮⋮00⋯00A2A3⋯Am0vk−v¯k.
Thus,(46)vk−v¯kTM¯vk−v¯k+λk−λ¯kT∑j=2mAjxjk−x¯jk=vk−v¯kTM1vk−v¯k=12vk−v¯kTM2vk−v¯k=12vk−v¯kP2+12vk−v¯kQ2≥12λk−λ¯kH−12,where(47)M1=A2THA20⋯00A3THA2A3THA3⋯00⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯AmTHAm0A2A3⋯AmH−1,M2=2A2THA2A2THA3⋯A2THAmA2kA3THA22A3THA3⋯A3THAmA3k⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯2AmTHAmAmkA2A3⋯Am2H−1.The assertion follows from the above three formulas.SinceH≻0 and λminGi>Li, whenever wk−w¯k≠0, assertion (42) shows the positivity of the term wk−w∗TDk, and thus, the direction −Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk.


### 3.2. Contractive Property

In this section, we show that the sequencewk generated by Algorithm G-ADMM-S is contractive with respect to the set W∗.Since the direction−Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk, the new iterate wk+1 can be generated by(48)wk+1=wk−αDk.Thus,(49)wk−w∗2−wk+1−w∗2=wk−w∗2−wk−w∗−αDk2=2αwk−w∗TDk−α2Dk2≥2αbk−α2Dk2,∀w∗∈W∗,where the inequality follows from the first inequality of (42).Letqα=2αbk−α2Dk2. Note that right-hand side of (49), i.e., qα, is a quadratic function of α, and(50)qα>0⟺0<α<2bkDk2.In order to obtain the closest proximity to W∗, we are in the desire to maximize this quadratic function and this promotes us to take the optimal value of α as(51)α=αk≔bkDk2.With this choice of step size, it follows from (49) that(52)wk−w∗2≤wk−w∗2−bk2Dk2,∀w∗∈W∗.Let(53)T1=maxλmaxH−1,λmaxGi+Li,1≤i≤m+λmaxMTM>0,T2=minλminH−12,λminGi−Li,1≤i≤m>0.From the definition ofDk (see, (18)), one has(54)Dk≤G¯k+Mvk−v¯k≤maxλmaxH−1,λmaxGi+Li,1≤i≤m+λmaxMTMwk−w¯k≤T1wk−w¯k,where(55)G¯k=G1x1k−x¯1k+∇g1x¯1k−∇g1x1kG2x2k−x¯2k+∇g2x¯2k−∇g2x2k⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmkH−1λk−λ¯k.It follows from (19) and (42) that(56)bk≥minλminH−12,λminGi−Li,1≤i≤mwk−w¯k2≥T2wk−w¯k2.It is easy to see thatαk≥T2/T12.Next, we show that the sequencewk generated by Algorithm G-ADMM-S is contractive with respect to the set W∗.Theorem 3.
Let the sequencewk be generated by the proposed Algorithm G-ADMM-S. Then,(57)wk+1−w∗2≤wk−w∗2−γ2−γT22T12w¯k−wk2,∀w∗∈W∗.Proof.
Using (21) and (22), we obtain(58)wk+1−w∗2=wk−w∗2−2γαkwk−w∗TDk+γαk2Dk2≤wk−w∗2−2γαkbk−γαk2Dk2=wk−w∗2−γ2−γαkbk=wk−w∗2−γ2−γbk2Dk2≤wk−w∗2−γ2−γT22T12w¯k−wk2,where the first inequality follows from the first inequality of (42) and the second inequality follows from (54)–(56).


### 3.3. Convergence Result

In this section, we establish the global convergence for Algorithm G-ADMM-S based on the analytic framework of contraction methods in [29].Theorem 4(global convergence).
Let the sequencewk be generated by Algorithm G-ADMM-S. Then, there exists w∞∈W∗ such that(59)limk⟶∞wk=w∞.Proof.
It follows from (57) that the sequence wk is bounded and(60)γ2−γ∑k=0∞T22T12w¯k−wk2≤w0−w∗2,which implies that limk⟶∞w¯k−wk=0.
Sincewk is bounded, the sequence wk has at least one cluster point and we denote it by w∞=x1∞,x2∞,…,xm∞,λ∞. In addition, let wkj be the subsequence converging to w∞. Since limk⟶∞wk−w¯k=0, w¯kj converges to w∞.
By taking the limit overkj in (15), we have that(61)Θx−Θx∞+w−w∞Gw≥0,∀w∈W.
Therefore,w∞ is a solution point of VIW,G,Θ. By using (57), we have(62)wk+1−w∞2≤wk−w∞2−γ2−γT22T12w¯k−wk2,and thus, limk⟶∞wk=w∞.


## 3.1. Verification of the Descent Direction

In this section, we show that−Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk whenever wk≠w¯k and w∗∈W∗. For this purpose, we first prove an important inequality for the output of G-ADMM procedure (8), which will be used often in our further discussion.Theorem 1.
w
¯
k
∈
W and(23)Θx−Θx¯k+w−w¯kTGw¯k+Pk≥w−w¯kTDk,∀w∈W,where Pk=w−w¯kTA1TA2T⋮AmT0H∑j=2mAjxjk−x¯jk.Proof.
By the optimality condition of thexi-related subproblem in (8), for i=1,2,…,m, we have x¯ik∈Xi and(24)0∈∂fix¯ik+∇gixik+AiTH∑j=1iAjx¯jk+∑j=i+1mAjxjk−b−H−1λk+Gix¯ik−xik+∂δx¯ikXi,where δXi is the indicator function of the set Xi. Thus, w¯k∈W and there exists η∈∂δXix¯ik such that(25)−η∈∂fix¯ik+∇gix¯ik+ρ=∂Θix¯ik+ρ,where ρ≔∇gixik−∇gix¯ik+AiTH∑j=1iAjx¯jk+∑j=i+1mAjxjk−b−H−1λk+Gix¯ik−xik. From the subgradient inequality, one has(26)Θixi−Θix¯ik≥xi−x¯ikT−η−ρ,∀xi∈Xi,Θixi−Θix¯ik+xi−x¯ikTρ≥−xi−x¯ikTη,∀xi∈Xi.
From the definition of∂δXix¯ik, one has(27)Θixi−Θix¯ik+xi−x¯ikTρ≥0,∀xi∈Xi.
That is,(28)0≤Θixi−Θix¯ik+xi−x¯ikT∇gixik−∇gix¯ik+AiTH∑j=1iAjx¯jk+∑j=i+1mAjxjk−b−H−1λk+Gix¯ik−xik,for all xi∈Xi. Substituting λ¯k=λk−H∑j=1mAjx¯jk−b (see (8)) in the above inequality, we obtain(29)0≤Θixi−Θix¯ik+xi−x¯ikT∇gixik−∇gix¯ik−AiTλ¯k+AiTH∑j=i+1mAjxjk−x¯jk+Gix¯ik−xik,for all xi∈Xi. Summing the above inequality over i=1,2,…,m, we obtain(30)Θx−Θx¯k+x−x¯kT−ATλ¯kCk≥0,where(31)Ck=G1x¯1k−x1k+∇g1x1k−∇g1x¯1k+A1TH∑j=2mAjxjk−x¯jk⋯Gix¯ik−xik+∇gixik−∇gix¯ik+AiTH∑j=i+1mAjxjk−x¯jk⋯Gmx¯mk−xmk+∇gmxmk−∇gmx¯mk.
Then, by adding the following term(32)x−x¯kTG1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jkto both sides of (30), we get(33)Θx−Θx¯k+x−x¯kT−ATλ¯k+A1TH∑j=2mAjxjk−x¯jk⋯AiTH∑j=2mAjxjk−x¯jk⋯AmTH∑j=2mAjxjk−x¯jk≥x−x¯kTG1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jk.
Sinceλ¯k=λk−H∑j=1mAjx¯jk−b, we have(34)∑j=1mAjx¯jk−b+H−1λ¯k−λk=0.
Combining the above two formulas, we have(35)Θx−Θx¯k+w−w¯kTGw¯k+Hk≥w−w¯kTQk,∀w∈W,where(36)Hk=A1TH∑j=2mAjxjk−x¯jk,A2TH∑j=2mAjxjk−x¯jk,…,AmTH∑j=2mAjxjk−x¯jk,0T,Qk=G1x1k−x¯1k+∇g1x¯1k−∇g1x1k⋯Gixik−x¯ik+∇gix¯ik−∇gixik+AiTH∑j=2iAjxjk−x¯jk⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmk+AmTH∑j=2mAjxjk−x¯jkH−1λk−λ¯k.
Using the notations ofGw¯k (see (15)) and Dk (see (18)), assertion (23) is proved.Based on assertion (23), we can get the following result.Corollary 1.
(37)
w
¯
k
−
w
∗
T
D
k
≥
λ
k
−
λ
¯
k
T
∑
j
=
2
m
A
j
x
j
k
−
x
¯
j
k
,
∀
w
∗
∈
W
∗
.Proof.
It follows from (23) that(38)w¯k−w∗TDk≥Θx¯k−Θx∗+w¯k−w∗TGw¯k+w¯k−w∗TA1TA2T⋮AmTH∑j=2mAjxjk−x¯jk.
Using (17) and the optimality ofw∗, we have(39)Θx¯k−Θx∗+w¯k−w∗TGw¯k=Θx¯k−Θx∗+w¯k−w∗TGw∗≥0.
Thus,(40)w¯k−w∗TDk≥H∑j=1mAjx¯jk−∑j=1mAjxj∗T∑j=2mAjxjk−x¯jk.
Since∑j=1mAjxj∗=b and H∑j=1mAjx¯jk−b=λk−λ¯k,(41)w¯k−w∗TDk≥λk−λ¯kT∑j=2mAjxjk−x¯jk.
The next theorem implies that−Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk whenever wk≠w¯k.Theorem 2.
For allw∗∈W∗,(42)wk−w∗TDk≥bk≥∑j=1mxjk−x¯jkGj2−Lixjk−x¯jk+12vk−v¯kP+Q2≥∑j=1mλminGj−Lixjk−x¯jk2+12λk−λ¯kH−12.Proof.
It follows from (37) that(43)wk−w∗TDk≥wk−w¯kTDk+λk−λ¯kT∑j=2mAjxjk−x¯jk.That is, wk−w∗TDk≥bk. Now, we treat the first term of the right-hand side of (43):(44)wk−w¯kTDk=∑i=1mxik−x¯ikGi2+xik−x¯ikT∇gix¯ik−∇gixik+vk−v¯kTM¯vk−v¯k≥∑i=1mxik−x¯ikGi2−Lixjk−x¯jk+vk−v¯kTM¯vk−v¯k≥∑i=1mλminGi−Lixik−x¯ik2+vk−v¯kTM¯vk−v¯k,where the first inequality follows from the Lipschitz continuous of ∇gi. Then, let us deal with the second term of the right-hand side of (43):(45)λk−λ¯kT∑j=2mAjxjk−x¯jk=vk−v¯kT00⋯0000⋯00⋮⋮⋱⋮⋮00⋯00A2A3⋯Am0vk−v¯k.
Thus,(46)vk−v¯kTM¯vk−v¯k+λk−λ¯kT∑j=2mAjxjk−x¯jk=vk−v¯kTM1vk−v¯k=12vk−v¯kTM2vk−v¯k=12vk−v¯kP2+12vk−v¯kQ2≥12λk−λ¯kH−12,where(47)M1=A2THA20⋯00A3THA2A3THA3⋯00⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯AmTHAm0A2A3⋯AmH−1,M2=2A2THA2A2THA3⋯A2THAmA2kA3THA22A3THA3⋯A3THAmA3k⋮⋮⋱⋮⋮AmTHA2AmTHA3⋯2AmTHAmAmkA2A3⋯Am2H−1.The assertion follows from the above three formulas.SinceH≻0 and λminGi>Li, whenever wk−w¯k≠0, assertion (42) shows the positivity of the term wk−w∗TDk, and thus, the direction −Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk.


## 3.2. Contractive Property

In this section, we show that the sequencewk generated by Algorithm G-ADMM-S is contractive with respect to the set W∗.Since the direction−Dk is a descent direction of the function 1/2w−w∗2 at the point w=wk, the new iterate wk+1 can be generated by(48)wk+1=wk−αDk.Thus,(49)wk−w∗2−wk+1−w∗2=wk−w∗2−wk−w∗−αDk2=2αwk−w∗TDk−α2Dk2≥2αbk−α2Dk2,∀w∗∈W∗,where the inequality follows from the first inequality of (42).Letqα=2αbk−α2Dk2. Note that right-hand side of (49), i.e., qα, is a quadratic function of α, and(50)qα>0⟺0<α<2bkDk2.In order to obtain the closest proximity to W∗, we are in the desire to maximize this quadratic function and this promotes us to take the optimal value of α as(51)α=αk≔bkDk2.With this choice of step size, it follows from (49) that(52)wk−w∗2≤wk−w∗2−bk2Dk2,∀w∗∈W∗.Let(53)T1=maxλmaxH−1,λmaxGi+Li,1≤i≤m+λmaxMTM>0,T2=minλminH−12,λminGi−Li,1≤i≤m>0.From the definition ofDk (see, (18)), one has(54)Dk≤G¯k+Mvk−v¯k≤maxλmaxH−1,λmaxGi+Li,1≤i≤m+λmaxMTMwk−w¯k≤T1wk−w¯k,where(55)G¯k=G1x1k−x¯1k+∇g1x¯1k−∇g1x1kG2x2k−x¯2k+∇g2x¯2k−∇g2x2k⋯Gmxmk−x¯mk+∇gmx¯mk−∇gmxmkH−1λk−λ¯k.It follows from (19) and (42) that(56)bk≥minλminH−12,λminGi−Li,1≤i≤mwk−w¯k2≥T2wk−w¯k2.It is easy to see thatαk≥T2/T12.Next, we show that the sequencewk generated by Algorithm G-ADMM-S is contractive with respect to the set W∗.Theorem 3.
Let the sequencewk be generated by the proposed Algorithm G-ADMM-S. Then,(57)wk+1−w∗2≤wk−w∗2−γ2−γT22T12w¯k−wk2,∀w∗∈W∗.Proof.
Using (21) and (22), we obtain(58)wk+1−w∗2=wk−w∗2−2γαkwk−w∗TDk+γαk2Dk2≤wk−w∗2−2γαkbk−γαk2Dk2=wk−w∗2−γ2−γαkbk=wk−w∗2−γ2−γbk2Dk2≤wk−w∗2−γ2−γT22T12w¯k−wk2,where the first inequality follows from the first inequality of (42) and the second inequality follows from (54)–(56).


## 3.3. Convergence Result

In this section, we establish the global convergence for Algorithm G-ADMM-S based on the analytic framework of contraction methods in [29].Theorem 4(global convergence).
Let the sequencewk be generated by Algorithm G-ADMM-S. Then, there exists w∞∈W∗ such that(59)limk⟶∞wk=w∞.Proof.
It follows from (57) that the sequence wk is bounded and(60)γ2−γ∑k=0∞T22T12w¯k−wk2≤w0−w∗2,which implies that limk⟶∞w¯k−wk=0.
Sincewk is bounded, the sequence wk has at least one cluster point and we denote it by w∞=x1∞,x2∞,…,xm∞,λ∞. In addition, let wkj be the subsequence converging to w∞. Since limk⟶∞wk−w¯k=0, w¯kj converges to w∞.
By taking the limit overkj in (15), we have that(61)Θx−Θx∞+w−w∞Gw≥0,∀w∈W.
Therefore,w∞ is a solution point of VIW,G,Θ. By using (57), we have(62)wk+1−w∞2≤wk−w∞2−γ2−γT22T12w¯k−wk2,and thus, limk⟶∞wk=w∞.


## 4. Iteration Complexity

In this section, we will show that aftert iterations of Algorithm G-ADMM-S, we can ensure that(63)min0≤k≤twk−wk2≤ε,where ε=O1/t. Thus, a worst-case O1/ε iteration complexity is established in nonergodic sense for Algorithm G-ADMM-S.Theorem 5.
Let the sequencewk be generated by Algorithm G-ADMM-S. Then,(64)min0≤k≤tw¯k−wk2≤1ct+1w0−w∗2,∀w∗∈W∗,where cγ2−γT22/T12.Proof.
It follows from (57) that(65)c∑k=0∞w¯k−wk2≤w0−w∗2,∀w∗∈W∗.
Thus, for any integert>0, we obtain(66)c∑k=0tw¯k−wk2≤w0−w∗2,∀w∗∈W∗,and consequently, we obtain assertion (64).Recall thatW∗ is convex and closed under our assumptions (see, Theorem 2.3.5 in [30]). Let(67)d≔infw0−w∗2w∗∈W∗.For any given ε>0, inequality (64) indicates that Algorithm G-ADMM-S requires at most ⌊d/cε⌋ iterations to fulfill the requirement w¯k−wk2≤ε.


## 5. Numerical Results

To investigate the numerical performance of the proposed algorithm, we apply it to solve a convex quadratic programming and a nonlinear convex programming with separable structure and report some preliminary numerical results. All codes were written by Matlab 2016a, and all the numerical experiments were conducted on a Dell desktop computer with Intel Pentium Intel (R) Core processor 3.30 GHz and 4 GB memory.


### 5.1. Quadratic Programming Problem

First, we consider the following quadratic programming problem:(68)min∑i=1312xiTMixi+qiTxis.t.A1x1+x2+A3x3=b,x1∈ℛn1,BL≤x1≤BU,x2∈ℛn2,x2≤r,x3∈ℛ+n3.In the experiments, we set fixi=q1Txi and gix1=1/2xiTMixi, (i=1,2,3). We set the matrix M1=In1×n1 and construct the rest of matrices Mii=2,3 in a way similar to [25, 31]. That is, Mi=ViTVi+τIni, where Vi are random matrices and(69)τ=λmaxViTVi−t⋅λminViTVit−1.In our tests, we set t=103 and generate the matrices Vi=randni/5,ni in Matlab function. In the experiments, we set BL,BU=0,10 and the radius r=10. For the linear constraint, the entries of Ai∈ℛl×ni (i=1,3) are uniformly distributed in 0,1 with the density 0.1 and l=n2. xi∗’s are given generated by xi∗=sprandni,1,0.5 (i=1,2,3) in the Matlab function. In order to guarantee the feasibility of the problem, we set qi=−Mixi∗, (i=1,2,3) and b=A1x1∗+x2∗+A3x3∗. Thus, x1∗,x2∗,x3∗ is an optimal solution of (68). The Algorithm G-ADMM-S is compared with the PPSM-C in [25]. The initial iteration points are the zero vectors xi0=0ni×1 (i=1,2,3) and λ0=0l×1 for all tested algorithms. We set a maximal number of 20000 for iteration of the proposed algorithms with a modified stopping criterion as follows:(70)maxi=1,2,3xik−x¯ikxik,λk−λ¯kλk≤10−2.Now, we specify the choices of parameters to implement these algorithms. First, we setH=βI with β=0.01 and the relaxation parameter γ=1.8 for all tested algorithms. For “PPSM-C″, we set ri=MiF+0.15AiTAi (i=1,2,3), where ⋅F represents the Frobenius norm. For G-ADMM-S, we consider two cases of the matrices Gi (i=1,2,3):Case 1:Gi=riIni×ni−βAiTAi with ri=MiF+0.15AiTAiFCase 2:Gi=riIni×ni−βAiTAi with ri=MiF+βAiTAiFIn order to investigate the stability and efficiency of our algorithms, we test 16 groups of problems with random data. Some preliminary numerical results are reported in Table1. Since they are synthetic examples with random date, for each scenario, we test 10 times and report the average performance. Specifically, we report the number of iterations (“Iter.”) and the computing time in seconds (“Time”) for all the tested methods. The data in Table 1 show that Algorithm G-ADMM-S (Gi=riIni×ni−βAiTAi with ri=MiF+βAiTAiF) is more efficient than the rest of algorithms for the test problems.Table 1
Numerical results.
n
1
,
n
2
,
n
3
PPSM-C
G-ADMM-S
Case 1
Case 2
Iter.
Time
Iter.
Time
Iter.
Time
(500, 500, 500)
1253
6.065
1589
6.290
1340
5.302
(500, 600, 500)
1057
5.483
1744
7.628
1523
6.671
(600, 500, 600)
1560
9.296
1825
8.589
1445
6.753
(600, 600, 600)
1580
10.307
1915
10.142
1642
8.625
(600, 700, 600)
1641
11.432
2042
11.817
1782
10.313
(700, 600, 700)
1745
13.129
2223
13.157
1871
11.087
(700, 700, 700)
2036
16.875
2357
16.304
1998
13.820
(700, 800, 700)
2857
25.090
2628
19.335
2308
17.168
(800, 700, 800)
2428
23.296
2634
19.875
2210
16.638
(800, 800, 800)
2809
28.659
2804
23.453
2381
19.620
(800, 900, 800)
4048
43.482
3016
28.678
2592
24.695
(900, 800, 900)
3204
41.398
3178
31.030
2675
26.080
(900, 900, 900)
3881
47.465
3332
36.036
2820
30.255
(900, 1000, 900)
10000
129.147
3790
44.253
3224
37.557
(1000, 900, 1000)
4547
71.910
3771
46.183
3140
38.250
(1000, 1000, 1000)
10000
151.273
4131
53.813
3482
45.660


### 5.2. Nonlinear Convex Programming Problem

In this section, we consider the following nonlinear convex programming problem:(71)minx11−12lnx12+1+qTx2+12x2TMx2+12x32−∑i=1n3cosx3,is.t.A1x1+A2x2+A3x3=b,x1∈ℛn1,0≤x1,x2∈ℛn2,x3∈ℛn3,x3,i≤π2,i=,1,…,n3,where x1=∑i=1nxi and M is a positive matrix. In the experiments, we set f1x1=x11,g1x1=−1/2lnx12+1,f2x2=qTx2,g2x2=1/2x2TMx2,f3x3=1/2x32,andg3x3=−∑i=1n3cosx3,i. It is easy to see that, when the PPSM-C in [25] solves (71), there is no explicit solution to the subproblems. In this section, we only use the Algorithm G-ADMM-S to solve (71). In the experiments, the entries of Ai∈ℛl×ni (i=1,3) are uniformly distributed in 0,1 with the density 0.1 and l=n2. x1∗=0n1×1, x3∗=0n3×1, and x2∗ is given generated by x2∗=sprandn2,1,0.5 in the Matlab function. We set the matrix M in a way similar to [25, 31]. In order to guarantee the feasibility of the problem, we set q=−Mx2∗ and b=A1x1∗+A2x2∗+A3x3∗. Thus, x1∗,x2∗,x3∗ is an optimal solution of (71). The initial iteration points are the zero vectors xi0=0ni×1 (i=1,2,3) and λ0=0l×1 for all tested algorithms. We set a maximal number of 20000 for iteration of the proposed algorithms with a modified stopping criterion as follows:(72)maxx1k,x2k−x¯2kx2k,x3k,A1x1k+A2x2k+A3x3k−b≤10−3.Now, we specify the choices of parameters to implement these algorithms. We setH=βI with β=0.01, the relaxation parameter γ=1.8, r1=n1+βA1TA1, r2=MF+βA2TA2, r3=n3+βA3TA3, and Gi=riIni×ni−μAiTAi (i=1,2,3). We consider two cases of the parameter μ: Case 1: μ=β; Case 2: μ=0.15.We test 7 groups of problems with random data. Numerical results are reported in Table2. For each scenario, we test 5 times and report the average performance. Specifically, we report the number of iterations (“Iter.”), the computing time in seconds (“Time”), and the absolute error of function value (“f-error”). The numerical results show that Algorithm G-ADMM-S is effective.Table 2
Numerical results.
n
1
,
n
2
,
n
3
Case 1 (μ=β)
Case 2 (μ=0.15)
Iter.
Time
f-error
Iter.
Time
f-error
(600, 600, 600)
3760.0
42.487
0.000211
3535.6
39.895
0.000207
(600, 700, 600)
5036.0
68.516
0.000196
5205.0
71.399
0.000200
(800, 700, 800)
3598.0
59.179
0.000211
3842.8
64.059
0.000211
(800, 800, 800)
5620.0
109.576
0.000202
5114.4
99.910
0.000206
(800, 900, 800)
7206.0
170.436
0.000192
7015.2
158.227
0.000199
(1000, 900, 1000)
5655.0
148.923
0.000203
5351.4
140.452
0.000205
(1000, 1000, 1000)
7577.0
223.832
0.000202
7529.2
229.729
0.000198


## 5.1. Quadratic Programming Problem

First, we consider the following quadratic programming problem:(68)min∑i=1312xiTMixi+qiTxis.t.A1x1+x2+A3x3=b,x1∈ℛn1,BL≤x1≤BU,x2∈ℛn2,x2≤r,x3∈ℛ+n3.In the experiments, we set fixi=q1Txi and gix1=1/2xiTMixi, (i=1,2,3). We set the matrix M1=In1×n1 and construct the rest of matrices Mii=2,3 in a way similar to [25, 31]. That is, Mi=ViTVi+τIni, where Vi are random matrices and(69)τ=λmaxViTVi−t⋅λminViTVit−1.In our tests, we set t=103 and generate the matrices Vi=randni/5,ni in Matlab function. In the experiments, we set BL,BU=0,10 and the radius r=10. For the linear constraint, the entries of Ai∈ℛl×ni (i=1,3) are uniformly distributed in 0,1 with the density 0.1 and l=n2. xi∗’s are given generated by xi∗=sprandni,1,0.5 (i=1,2,3) in the Matlab function. In order to guarantee the feasibility of the problem, we set qi=−Mixi∗, (i=1,2,3) and b=A1x1∗+x2∗+A3x3∗. Thus, x1∗,x2∗,x3∗ is an optimal solution of (68). The Algorithm G-ADMM-S is compared with the PPSM-C in [25]. The initial iteration points are the zero vectors xi0=0ni×1 (i=1,2,3) and λ0=0l×1 for all tested algorithms. We set a maximal number of 20000 for iteration of the proposed algorithms with a modified stopping criterion as follows:(70)maxi=1,2,3xik−x¯ikxik,λk−λ¯kλk≤10−2.Now, we specify the choices of parameters to implement these algorithms. First, we setH=βI with β=0.01 and the relaxation parameter γ=1.8 for all tested algorithms. For “PPSM-C″, we set ri=MiF+0.15AiTAi (i=1,2,3), where ⋅F represents the Frobenius norm. For G-ADMM-S, we consider two cases of the matrices Gi (i=1,2,3):Case 1:Gi=riIni×ni−βAiTAi with ri=MiF+0.15AiTAiFCase 2:Gi=riIni×ni−βAiTAi with ri=MiF+βAiTAiFIn order to investigate the stability and efficiency of our algorithms, we test 16 groups of problems with random data. Some preliminary numerical results are reported in Table1. Since they are synthetic examples with random date, for each scenario, we test 10 times and report the average performance. Specifically, we report the number of iterations (“Iter.”) and the computing time in seconds (“Time”) for all the tested methods. The data in Table 1 show that Algorithm G-ADMM-S (Gi=riIni×ni−βAiTAi with ri=MiF+βAiTAiF) is more efficient than the rest of algorithms for the test problems.Table 1
Numerical results.
n
1
,
n
2
,
n
3
PPSM-C
G-ADMM-S
Case 1
Case 2
Iter.
Time
Iter.
Time
Iter.
Time
(500, 500, 500)
1253
6.065
1589
6.290
1340
5.302
(500, 600, 500)
1057
5.483
1744
7.628
1523
6.671
(600, 500, 600)
1560
9.296
1825
8.589
1445
6.753
(600, 600, 600)
1580
10.307
1915
10.142
1642
8.625
(600, 700, 600)
1641
11.432
2042
11.817
1782
10.313
(700, 600, 700)
1745
13.129
2223
13.157
1871
11.087
(700, 700, 700)
2036
16.875
2357
16.304
1998
13.820
(700, 800, 700)
2857
25.090
2628
19.335
2308
17.168
(800, 700, 800)
2428
23.296
2634
19.875
2210
16.638
(800, 800, 800)
2809
28.659
2804
23.453
2381
19.620
(800, 900, 800)
4048
43.482
3016
28.678
2592
24.695
(900, 800, 900)
3204
41.398
3178
31.030
2675
26.080
(900, 900, 900)
3881
47.465
3332
36.036
2820
30.255
(900, 1000, 900)
10000
129.147
3790
44.253
3224
37.557
(1000, 900, 1000)
4547
71.910
3771
46.183
3140
38.250
(1000, 1000, 1000)
10000
151.273
4131
53.813
3482
45.660


## 5.2. Nonlinear Convex Programming Problem

In this section, we consider the following nonlinear convex programming problem:(71)minx11−12lnx12+1+qTx2+12x2TMx2+12x32−∑i=1n3cosx3,is.t.A1x1+A2x2+A3x3=b,x1∈ℛn1,0≤x1,x2∈ℛn2,x3∈ℛn3,x3,i≤π2,i=,1,…,n3,where x1=∑i=1nxi and M is a positive matrix. In the experiments, we set f1x1=x11,g1x1=−1/2lnx12+1,f2x2=qTx2,g2x2=1/2x2TMx2,f3x3=1/2x32,andg3x3=−∑i=1n3cosx3,i. It is easy to see that, when the PPSM-C in [25] solves (71), there is no explicit solution to the subproblems. In this section, we only use the Algorithm G-ADMM-S to solve (71). In the experiments, the entries of Ai∈ℛl×ni (i=1,3) are uniformly distributed in 0,1 with the density 0.1 and l=n2. x1∗=0n1×1, x3∗=0n3×1, and x2∗ is given generated by x2∗=sprandn2,1,0.5 in the Matlab function. We set the matrix M in a way similar to [25, 31]. In order to guarantee the feasibility of the problem, we set q=−Mx2∗ and b=A1x1∗+A2x2∗+A3x3∗. Thus, x1∗,x2∗,x3∗ is an optimal solution of (71). The initial iteration points are the zero vectors xi0=0ni×1 (i=1,2,3) and λ0=0l×1 for all tested algorithms. We set a maximal number of 20000 for iteration of the proposed algorithms with a modified stopping criterion as follows:(72)maxx1k,x2k−x¯2kx2k,x3k,A1x1k+A2x2k+A3x3k−b≤10−3.Now, we specify the choices of parameters to implement these algorithms. We setH=βI with β=0.01, the relaxation parameter γ=1.8, r1=n1+βA1TA1, r2=MF+βA2TA2, r3=n3+βA3TA3, and Gi=riIni×ni−μAiTAi (i=1,2,3). We consider two cases of the parameter μ: Case 1: μ=β; Case 2: μ=0.15.We test 7 groups of problems with random data. Numerical results are reported in Table2. For each scenario, we test 5 times and report the average performance. Specifically, we report the number of iterations (“Iter.”), the computing time in seconds (“Time”), and the absolute error of function value (“f-error”). The numerical results show that Algorithm G-ADMM-S is effective.Table 2
Numerical results.
n
1
,
n
2
,
n
3
Case 1 (μ=β)
Case 2 (μ=0.15)
Iter.
Time
f-error
Iter.
Time
f-error
(600, 600, 600)
3760.0
42.487
0.000211
3535.6
39.895
0.000207
(600, 700, 600)
5036.0
68.516
0.000196
5205.0
71.399
0.000200
(800, 700, 800)
3598.0
59.179
0.000211
3842.8
64.059
0.000211
(800, 800, 800)
5620.0
109.576
0.000202
5114.4
99.910
0.000206
(800, 900, 800)
7206.0
170.436
0.000192
7015.2
158.227
0.000199
(1000, 900, 1000)
5655.0
148.923
0.000203
5351.4
140.452
0.000205
(1000, 1000, 1000)
7577.0
223.832
0.000202
7529.2
229.729
0.000198


## 6. Conclusion

In this paper, for the linearly constrained separable convex programming, whose objective function is the sum ofm individual blocks with nonoverlapping variables and each block is convex, we present a gradient-based ADMM with a substitution in the case m≥3. We have analysed its convergence and iteration complexity. The preliminary numerical results have shown the efficiency of the proposed algorithm.



---

*Source: 7876949-2020-04-27.xml*