# Convergence Analysis of Alternating Direction Method of Multipliers for a Class of Separable Convex Programming

Authors: Zehui Jia; Ke Guo; Xingju Cai
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

The purpose of this paper is extending the convergence analysis of Han and Yuan (2012) for alternating direction method of multipliers (ADMM) from the strongly convex to a more general case. Under the assumption that the individual functions are composites of strongly convex functions and linear functions, we prove that the classical ADMM for separable convex programming with two blocks can be extended to the case with more than three blocks. The problems, although still very special, arise naturally from some important applications, for example, route-based traffic assignment problems.


---

## Body

## 1. Introduction

In this paper, we consider the convex programming with separable functions:(1)min{∑i=1m‍fi(xi)∣∑i=1m‍Aixi=b,xi∈𝒳i,i=1,2,…,m∑i=1m‍},
where fi:ℛni→ℛ∪{+∞} (i=1,2,…,m) are closed proper convex functions (not necessarily smooth); Ai∈ℛl×ni (i=1,2,…,m); 𝒳i⊆ℛni (i=1,2,…,m) are closed convex sets; b∈ℛl and ∑i=1m‍ni=n. Throughout the paper, we assume that the solution set of (1) is nonempty.For the special case of (1) with m=2,
(2)min{f1(x1)+f2(x2)∣A1x1+A2x2=b,xi∈𝒳i,i=1,2},
the problem has been studied extensively. Among lots of numerical methods, one of the most popular methods is the alternating direction method of multipliers (ADMM) which was presented originally in [1, 2]. The iterative scheme of ADMM for (2) is as follows:
(3)x1k+1=argmin{vβ2f1(x1)-(λk)TA1x1+β2∥A1x1+A2x2k-b∥2∣x1∈𝒳i};x2k+1=argmin{12β2f2(x2)-(λk)TA2x2+β2∥A1x1k+1+A2x2-b∥2∣x2∈𝒳2};λk+1=λk-β(A1x1k+1+A2x2k+1-b),
where λk is Lagrange multiplier associated with the linear constraints and β>0 is the penalty parameter. The convergence of ADMM for (2) was also established under the condition that the involved functions are convex and the constrained sets are convex too.While there are diversified applications whose objective function is separable intom≥3 individual convex functions without coupled variables, such as traffic problems, the problem of recovering the low-rank, sparse components of matrices from incomplete and noisy observation in [3], the constrained total-variation image restoration and reconstruction problem in [4, 5], and the minimal surface PDE problem in [6], it is   thus natural to extend ADMM from 2 blocks to m blocks, resulting in the iterative scheme:
(4)x1k+1=argmin{f1(x1)-(λk)TA1x1+β2∥AmxmkA1x1+A2x2k+···+Amxmk-b∥2∣x1∈𝒳112};x2k+1=argmin{f2(x2)-(λk)TA2x2+β2∥A1x1k+1+A2x2+⋯+Amxmk-b∥2∣x2∈𝒳212};⋮xmk+1=argmin{fm(xm)-(λk)TAmxm+β2∥A1x1k+1+A2x2k+1⋯+Amxm-bA1x1k+1∥2∣xm∈𝒳m12};λk+1=λk-β(A1x1k+1+A2x2k+1+⋯+Amxmk+1-b).Unfortunately, the convergence of the natural extension is still open under convex assumption, and the recent convergence results [7] are under the assumption that all the functions involved in the objective functions are strongly convex. This lack of convergence has inspired some ADM-based methods, for example, prediction-correction type method [3, 8–11], that is, the iterate x1k+1,x2k+1,…,xmk+1 is regarded as a prediction, and the next iterate is a correction for it. However, the numerical results show that the algorithm (4) always performs better than these variants. Recently, Han and Yuan [7] show that the global convergence of the extension of ADMM for m≥3 is valid if the involved functions are further assumed to be strongly convex. This result does not answer the open problem regarding the convergence of the extension of ADMM under the convex assumption, but it makes a key progress towards this objective.In this paper, we consider the separable convex optimization problem (1) where each individual function fi is the combination of a strongly convex function gi and a linear transform Bi. That is, (1) takes the following form:
(5)min{∑i=1m‍gi(Bixi)∣∑i=1m‍Aixi=b,xi∈𝒳i,i=1,2,…,m},
where gi:ℛsi→ℛ∪{+∞} (i=1,2,…,m) are closed proper strongly convex function with the modulus μi (not necessarily smooth); Ai∈ℛl×ni (i=1,2,…,m); 𝒳i⊆ℛni (i=1,2,…,m) are closed convex sets; b∈ℛl and ∑i=1m‍ni=n; Bi∈ℛsi×ni (i=1,2,…,m), where Bi may not have full column rank (if Bi has full column rank, the composite function is strongly convex and reduces to the case considered in [7]). Note that although (5) is very special, it arises frequently from many applications. One example is under the route-based traffic assignment problem [12], where gi is the link traffic cost, Bi is the link-path incidence matrix, and x is the path follow vector.In the following, we abuse a little the notation and still writegi with fi; that is, the problem under consideration is
(6)min{∑i=1m‍fi(Bixi)∣∑i=1m‍Aixi=b,xi∈𝒳i,i=1,2,…,m},
where fi:ℛsi→ℛ∪{+∞} (i=1,2,…,m) are closed proper strongly convex function with the modulus μi (not necessarily smooth).The rest of the paper is organized as follows. In the next section, we list some necessary preliminary results that will be used in the rest of the paper. We then describe the algorithm formally and analyze its global convergence under reasonable conditions in Section3. We complete the paper with some conclusions in Section 4.


## 2. Preliminaries

In this section, we summarize some basic concepts and their properties that will be useful for further discussion.Let∥·∥p denote the standard definition of the lp-norm, and particularly, let ∥·∥=∥·∥2 denote the Euclidean norm. For a symmetric and positive definite matrix G, we denote ∥·∥G the G-norm, that is, ∥x∥G=xTGx. If G is the product of a positive parameter β and the identity matrix I, that is, G=βI, we use the simpler notation: ∥·∥G=∥·∥β.Letf:ℛn→ℛ∪{+∞}. If the domain of f denoted by domf={x∈ℛn∣f(x)<+∞} is not empty, then f is said to be proper. If for any x∈ℛn and y∈ℛn, we have
(7)f(tx+(1-t)y)≤tf(x)+(1-t)f(y),∀t∈[0,1],
then f is said to be convex. Furthermore, f is said to be strongly convex with the modulus μ>0 if and only if
(8)f(tx+(1-t)y)≤tf(x)+(1-t)f(y)-12μt(1-t)∥x-y∥2,∀t∈[0,1].A set-valued operatorT defined on ℛn is said to be monotone if and only if
(9)(u-u~)T(w-w~)≥0,∀w∈Tu,∀w~∈Tu~,
and T is said to be strongly monotone with modulus μ>0 if and only if
(10)(u-u~)T(w-w~)≥μ∥u-u~∥2,∀w∈Tu,∀w~∈Tu~.LetΓ0(ℛn) denote the set of closed proper convex functions from ℛn to ℛ∪{+∞}. For any f∈Γ0(ℛn), the subdifferential of f which is the set-valued operator, defined by
(11)∂f:x⟼{12ξ∈ℛn∣(y-x)Tξ+f(x)≤f(y),∀y∈domf12},
is monotone. Moreover, if f is strongly convex function with the modulus μ, ∂f is strongly monotone with the modulus μ.LetF be a mapping from a set Ω⊂ℛn→ℛn. Then F is said to be co-coercive on Ω with modulus γ>0, if
(12)(u-v)T(F(u)-F(v))≥γ∥F(u)-F(v)∥2,∀u,v∈Ω.Throughout the paper, we make the following assumptions.Assumption 1.
(i)ni∥Bixi∥≥∥Ai∥∥xi∥,  ∀xi∈ℛni, i∈{1,2,…,m}; (ii) the solution set of (1) is nonempty.Remark 2.
Assumption1 is a little restrictive. However, some problems can satisfy it. A remarkable one is the following route-based traffic assignment problem.
Consider a transportation networkG(𝒩,E), where 𝒩 is the set of nodes. We denote the set of links by 𝒜, and the number of the element of 𝒜 by N𝒜, respectively. Let RS denote the set of origin-destination (O-D) pairs. For an O-D pair rs∈RS, let qrs be its traffic demand; let Prs be the set of routes connecting rs, and p∈Prs; 𝒩rs denotes the number of the routes connecting rs; let hprs be the route flow on p. The feasible route flow vector h=(p∈Prs∣rs∈RS) is thus given by
(13)H={h∣∑p∈Prs‍hprs=qrs,hprs≥0,∀p∈Prs,rs∈RS}={12h∣eT(h1rs,h2rs,…,hNrsrs)=qrs,hprs≥0,∀p∈Prs,rs∈RS12(h1rs,h2rs,…,hNrsrs)}.
Define E as the link-route incidence matrix such that
(14)δpa={1,ifpcontainslinka0,otherwise.
Then, link flow fa can be written as
(15)fa=∑rs∈RS‍∑p∈Prs‍δpahprs,∀a∈𝒜,F=EH={f∣f=Eh,h∈H}.
By denoting the link cost function as Ca(f) and for the additive case, the route cost function as Cp(h), they can be related by
(16)Cph=∑a∈𝒜‍δpaCa(f).
The user equilibrium traffic assignment problem can be formulated as a VI: find f*∈F such that
(17)(f-f*)TC(f*)≥0,∀f∈F,
or equivalently, find h*∈H such that
(18)(h-h*)TETC(Eh*)≥0,∀h∈H,
where C={Ca} is the vector of the link cost function.
In general, it is easy to show thate is a row of E and E is not a full column rank (if E is, then the above variational inequality is strongly monotone).
For simplicity, in the following, we only consider the case form=3. Notice that for m≥3, it can be proved similarly following the processing of m=3.


## 3. The Method

In this section, we consider the following convex minimization problem with linear constraint, where the objective function is in the form of the sum of three individual functions without coupled variable:(19)minf1(B1x1)+f2(B2x2)+f3(B3x3)s.t.A1x1+A2x2+A3x3=b,xi∈𝒳i,i=1,2,3,
where fi:ℛsi→ℛ∪{+∞} (i=1,2,3) are closed proper strongly convex function with the modulus μi (not necessarily smooth); Bi∈ℛsi×ni (i=1,2,3), Ai∈ℛl×ni (i=1,2,3);  𝒳i⊆ℛni (i=1,2,3) are closed convex sets; b∈ℛl and ∑i=13‍ni=n.The iterative scheme of ADMM for problem (19) is as follows:
(20)x1k+1=argmin{f1(B1x1)-(λk)TA1x1+β2∥A2x2kA1x1+A2x2k+A3x3k-b∥2∣x1∈𝒳112},x2k+1=argmin{f2(B2x2)-(λk)TA2x2+β2∥A3x3kA1x1k+1+A2x2+A3x3k-b∥2∣x2∈𝒳212},x3k+1=argmin{f3(B3x3)-(λk)TA3x3+β2∥A1x1k+1+A2x2k+1+A3x3-b∥2∣x3∈𝒳312},λk+1=λk-β(A1x1k+1+A2x2k+1+A3x3k+1-b),
where λk is the Lagrangian multiplier associated with the linear constraints and β>0 is the penalty parameter.


## 4. Convergence

In this section, we prove the convergence of the extended ADMM for problem (19). As the assumptions aforementioned, by invoking the first-order necessary and sufficient condition for convex programming, we easily see that the problem (19) under the condition is characterized by the following variational inequality (VI): find u*∈𝒰 and ξi*∈∂fi(Bixi*) such that
(21)(u-u*)TQ(u*)≥0,∀u∈𝒰,
where
(22)u:=(x1x2x3λ),Q(u):=(B1Tξ1-A1TλB2Tξ2-A2TλB3Tξ3-A3TλA1x1+A2x2+A3x3-b),𝒰=𝒳1×𝒳2×𝒳3×ℛl.
We denote the VI (21)-(22) by MVI(𝒰,Q).Similarly, in [7], we propose an easily implementable stopping criterion for executing (20):
(23)max{max1≤i≤3∥Aixik-Aixik+1∥,∥∑i=13‍Aixik-b∥}≤ϵ,
and its rationale can be seen in the following lemma.Lemma 3 (see [7]).
If∑i=13‍Aixik-b=0 and Aixik=Aixik+1 (i=1,2,3), then (x1k+1,x2k+1,x3k+1,λk+1) is a solution of MVI(𝒰,Q).Lemma3 implies that the iterate {(x1k,x2k,x3k,λk)} is a solution of MVI(𝒰,Q) when the inequality (23) holds with ϵ=0. Some techniques of establishing the error bounds in [13] can help us analyze how precisely the iterate satisfies the optimality conditions when the proposed stopping criterion is satisfied with a tolerance ϵ>0.Lemma 4.
Let(x1*,x2*,x3*,λ*) be the solution of the problem (19), and let λ* be a corresponding Lagrange multiplier associated with the linear constraint. Then, the sequence {(x1k,x2k,x3k,λk)} generated by (20) satisfies
(24)(λk-λ*)T(∑i=13‍Aixik+1-b)≥∑i=13‍(xik+1-xi*)T(BiTξik+1-BiTξi*)+β∥∑i=13‍Aixik+1-b∥2+β(A1x1k+1-A1x1*)T×[A2x2k-A2x2k+1+(A3x3k-A3x3k+1)]+β(A2x2k+1-A2x2*)T(A3x3k-A3x3k+1).Proof.
By invoking the first-order optimality condition for thexik+1-related subproblem in (20), for any xi∈𝒳i, i=1,2,3, we get
(25)(x1-x1k+1)T{B1Tξ1k+1-A1T[λk-β(A1x1k+1+A2x2k+A3x3k-b)]}≥0,(x2-x2k+1)T{B2Tξ2k+1-A2T×[λk-β(A1x1k+1+A2x2k+1+A3x3k-b)]}≥0,(x3-x3k+1)T{B3Tξ3k+1-A3T×[λk-β(A1x1k+1+A2x2k+1+A3x3k+1-b)]}≥0.
Setting xi=xi* (i=1,2,3) in (25), we have
(26)(x1*-x1k+1)T{B1Tξ1k+1-A1T[λk-β(A1x1k+1+A2x2k+A3x3k-b)]}≥0,(x2*-x2k+1)T{B2Tξ2k+1-A2T×[λk-β(A1x1k+1+A2x2k+1+A3x3k-b)]}≥0,(x3*-x3k+1)T{B3Tξ3k+1-A3T×[λk-β(A1x1k+1+A2x2k+1+A3x3k+1-b)]}≥0.
On the other hand, setting (x1,x2,x3)=(x1k+1,x2k+1,x3k+1)  in (21), it follows that
(27)(x1k+1-x1*x2k+1-x2*x3k+1-x3*)T(B1Tξ1*-A1Tλ*B2Tξ2*-A2Tλ*B3Tξ3*-A3Tλ*)≥0.
Adding (26) and (27), we obtain
(28)(x1k+1-x1*)T{(B1Tξ1*-B1Tξ1k+1)-A1T(λ*-λk)-βA1T(A1x1k+1+A2x2k+A3x3k-b)}≥0,(x2k+1-x2*)T{(B2Tξ2*-B2Tξ2k+1)-A2T(λ*-λk)-βA2T(A1x1k+1+A2x2k+1+A3x3k-b)}≥0,(x3k+1-x3*)T{(B3Tξ3*-B3Tξ3k+1)-A3T(λ*-λk)-βA3T(A1x1k+1+A2x2k+1+A3x3k+1-b)}≥0.
With the rearrangement of the above inequalities, we derive that
(29)(x1k+1-x1*)TA1T(λk-λ*)≥(x1k+1-x1*)T(B1Tξ1k+1-B1Tξ1*)+β(A1x1k+1-A1x1*)T(∑i=13‍Aixik+1-b)+β(A1x1k+1-A1x1*)T×[(A2x2k-A2x2k+1)+(A3x3k-A3x3k+1)],(x2k+1-x2*)TA2T(λk-λ*)≥(x2k+1-x2*)T(B2Tξ2k+1-B2Tξ2*)+β(A2x2k+1-A2x2*)T(∑i=13‍Aixik+1-b)+β(A2x2k+1-A2x2*)T(A3x3k-A3x3k+1),(x3k+1-x3*)TA3T(λk-λ*)≥(x3k+1-x3*)T(B3Tξ3k+1-B3Tξ3*)+β(A3x3k+1-A3x3*)T(∑i=13‍Aixik+1-b).
Adding the above inequalities (29), we have
(30)(λk-λ*)T(∑i=13‍Aixik+1-b)≥∑i=13‍(xik+1-xi*)T(BiTξik+1-BiTξi*)+β∥∑i=13‍Aixik+1-b∥2+β(A1x1k+1-A1x1*)T[(A2x2k-A2x2k+1)+(A3x3k-A3x3k+1)]+β(A2x2k+1-A2x2*)T(A3x3k-A3x3k+1).
The proof is complete.Hereafter, we define a matrix which will make the notation of proof more succinct. More specifically, let(31)M=(2βA1TA100002βA2TA20002βA3TA300001βI).
Obviously, M is a positive semidefinite matrix, only for analysis convenience; we denote
(32)∥u∥M2=2β(∥A1x1∥2+∥A2x2∥2+∥A3x3∥2)+∥λ∥1/β2.Lemma 5.
Letu*=(x1*,x2*,x3*,λ*) be a solution of MVI(𝒰,Q), and let the sequence {(x1k,x2k,x3k,λk)} be generated by (20). Then, one has
(33)∥uk+1-u*∥M2≤∥uk-u*∥M2+∑i=13‍3β∥Aixik+1-Aixi*Aixik+1∥2-2∑i=13‍μi∥Bixik+1-Bixi*∥2.Proof.
From (20) and Lemma 4, we have
(34)∥λk+1-λ*∥1/β2=∥λk-λ*-β(∑i=13‍Aixik+1-b)∥1/β2=∥λk-λ*∥1/β2-2(λk-λ*)T(∑i=13‍Aixik+1-b)+β∥∑i=13‍Aixik+1-b∥2≤∥λk-λ*∥1/β2-2∑i=13‍(xik+1-xi*)T(BiTξik+1-BiTξi*)-β∥∑i=13‍Aixik+1-b∥2-2β(A1x1k+1-A1x1*)T×(∑i=23‍(Aixik-Aixik+1))-2β(A2x2k+1-A2x2*)T(A3x3k-A3x3k+1).
Since
(35)∥∑i=13‍(Aixik+1-Aixi*)∥2=∑i=13‍∥Ai(xik+1-xi*)∥2+∑i≠j‍(Ai(xik+1-xi*))TAj(xjk+1-xj*),
and A1x1*+A2x2*+A3x3*=b, we can get
(36)-β∥∑i=13‍Aixik+1-b∥2=-β∑i=13‍∥Ai(xik+1-xi*)∥2-β∑i≠j‍(Ai(xik+1-xi*))TAj(xjk+1-xj*).
Using Cauchy-Schwarz inequality, we have
(37)-2β(A1x1k+1-A1x1*)T(∑i=23‍(Aixik-Aixik+1))-2β(A2x2k+1-A2x2*)T(A3x3k-A3x3k+1)=-2β(A1x1k+1-A1x1*)T(A2x2k-A2x2*)+2β(A1x1k+1-A1x1*)T(A2x2k+1-A2x2*)-2β(A1x1k+1-A1x1*)T(A3x3k-A3x3*)+2β(A1x1k+1-A1x1*)T(A3x3k+1-A3x3*)-2β(A2x2k+1-A2x2*)T(A3x3k-A3x3*)+2β(A2x2k+1-A2x2*)T(A3x3k+1-A3x3*)≤2β∥A1x1k+1-A1x1*∥2+β∥A2x2k+1-A2x2*∥2+β∥A2(x2k-x2*)∥2+2β∥A3(x3k-x3*)∥2+β∑i≠j‍(Ai(xik+1-xi*))TAj(xjk+1-xj*).
Substituting (36) and (37) into (34), we get
(38)∥λk+1-λ*∥1/β2≤∥λk-λ*∥1/β2+2β∑i=13‍∥Ai(xik-xi*)∥2+β∑i=13‍∥Ai(xik+1-xi*)∥2-2∑i=13‍(xik+1-xi*)T(BiTξik+1-BiTξi*).
Sincefi is strongly convex, from the strong monotonicity of the subdifferential mapping ∂fi (with the modulus μi), then we have
(39)(xik+1-xi*)T(BiTξik+1-BiTξi*)=(Bixik+1-Bixi*)T(ξik+1-ξi*)≥μi∥Bixik+1-Bixi*∥2,
where ξi*∈∂fi(Bixi*), ξik+1∈∂fi(Bixik+1), for any i∈{1,2,3}.
By using the notion of∥uk+1-u*∥M2, from (38) we have
(40)∥uk+1-u*∥M2=∥λk+1-λ*∥1/β2+2β∑i=13‍∥Ai(xik+1-xi*)∥2≤∥λk-λ*∥1/β2+2β∑i=13‍∥Ai(xik-xi*)∥2+3β∑i=13‍∥Ai(xik+1-xi*)∥2-2∑i=13‍μi∥Bixik+1-Bixi*∥2≤∥uk-u*∥M2+∑i=13‍3β∥Aixik+1-Aixi*∥2-2∑i=13‍μi∥Bixik+1-Bixi*∥2.
The proof is complete.Theorem 6.
Under  Assumption1,   for any
(41)0<β<min1≤i≤3{2μi3ni2},
the sequence {(x1k,x2k,x3k,λk)} generated by (20) converges to a solution of MVI(𝒰,Q).Proof.
From Lemma5, we have
(42)∥uk+1-u*∥M2≤∥uk-u*∥M2+∑i=13‍3β∥Aixik+1-Aixi*∥2-2∑i=13‍μi∥Bixik+1-Bixi*∥2,
where
(43)0<β<min1≤i≤3{2μi3ni2}.
From Assumption 1, it follows that
(44)∥Aixik+1-Aixi*∥2≤∥Ai∥2∥xik+1-xi*∥2≤ni2∥Bixik+1-Bixi*∥2,i=1,2,3.
Consequently,
(45)∥uk+1-u*∥M2≤∥uk-u*∥M2+∑i=13‍(3β-2μini2)∥Aixik+1-Aixi*∥2.
From (45), we have
(46)∥uk+1-u*∥M2≤∥uk-u*∥M2≤⋯≤∥u0-u*∥M2<+∞,
which means that the generated sequence {uk} is bounded.
Furthermore, it follows that(47)∑k=0+∞‍{∑i=13‍(2μini2-3β)∥Aixik+1-Aixi*∥2}≤∑k=0+∞‍{∥uk-u*∥M-∥uk+1-u*∥M}<+∞,
which means that
(48)limk→+∞∑i=13‍∥Aixik+1-Aixi*∥2=0.
Therefore, we have
(49)limk→+∞∥∑i=13‍Aixik+1-b∥2=0.
Since ∥Ai∥ is nonzero and bounded, from (48) we have
(50)limk→+∞∥xik+1-xi*∥=0,∀i=1,2,3.
Since {uk} is bounded, {λk} has at least one cluster point, say λ-. Let {λkj} be the corresponding subsequence that converges to λ-. Taking a limit along this subsequence in (25) and (49), we obtain ξi*∈∂fi(Bixi*),
(51)(xi-xi*)T(BiTξi*-AiTλ-)≥0,∀xi∈𝒳i,i=1,2,3,∑i=13‍Aixi*-b=0,
which follows that λ- is an optimal Lagrange multiplier. Since λ* is arbitrary, we can set λ*=λ- in (46) and conclude that the whole generated sequence converges to a solution of MVI(𝒰,Q).


## 5. Conclusions

In this paper, we extend the convergence analysis of the ADMM for the separable convex optimization problem with strongly convex functions to the case in which the individual functions are composites of strongly convex functions with a linear transform. Under further assumptions, we established the global convergence of the algorithm.It should be admitted that although some problems arising from applications such as traffic assignment fall into our analysis, the problems considered here are too special. Thus, it is far away to solve the open problem of convergence of the ADMM with more than three blocks.



---

*Source: 680768-2013-09-24.xml*