On the linear convergence of the alternating direction method of multipliers

Abstract

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth $\ell _1$ regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.

Appendix

1.1 Proof of dual error bound (2.8)

The augmented Lagrangian dual function can be expressed as

$$\begin{aligned} d(y)=\min _{x\in X} \langle y,q-Ex\rangle +\frac{\rho }{2}\Vert q-Ex\Vert ^2+g(Ax)+h(x). \end{aligned}$$

(6.1)

For convenience, define $p(Ex):=\frac{\rho }{2}\Vert q-Ex\Vert ^2$, and let $\ell (x):=p(Ex)+g(Ax)+h(x)$. For simplicity, in this proof we further restrict ourselves to the case where the nonsmooth part has polyhedral level sets, i.e., $\{x: h(x)\le \xi \}$ is polyhedral for each $\xi$. More general cases can be shown along similar lines, but the arguments become more involved.

Let us define

$$\begin{aligned} x(y)\in \arg \min _{x\in X} \ell (x)+\langle y, q-Ex\rangle . \end{aligned}$$

Let $(x^*, y^*)$ denote a primal and dual optimal solution pair. Let $X^*$ and $Y^*$ denote the primal and dual optimal solution set. The following properties will be useful in our subsequent analysis.

• (a) There exist positive scalars $\sigma _g$, $L_g$ such that $\forall ~x(y),x(y')\in X$

  • a-1) $\langle A^T \nabla g(A x(y'))-A^T \nabla g(A x(y)), x(y')-x(y)\rangle \ge \sigma _g\Vert A x(y')-A x(y)\Vert ^2$.

  • a-2) $g(A x(y'))-g(Ax(y))-\langle A^T \nabla g(A x(y)), x(y')-x(y)\rangle \ge \frac{\sigma _g}{2}\Vert A x(y')-Ax(y)\Vert ^2.$

  • a-3) $\Vert A^T\nabla g(Ax(y'))-A^T\nabla g(A x(y))\Vert \le L_g\Vert Ax(y')-Ax(y)\Vert .$

• (b) All a-1)–a-3) are true for $p(\cdot )$ as well, with some constants $\sigma _p$ and $L_p$.

• (c) $\nabla d(y)=q-Ex(y)$, and $\Vert \nabla d(y')-\nabla d(y)\Vert \le \frac{1}{\rho }\Vert y'-y\Vert .$

Part (a) is true due to the assumed Lipchitz continuity and strong convexity of the function $g(\cdot )$. Part (b) is from the Lipchitz continuity and strong convexity of the quadratic penalization $p(\cdot )$. Part (c) has been shown in Lemmas 2.1 and 2.2.

To proceed, let us rewrite the primal problem equivalently as

$$\begin{aligned} d(y)=\min _{(x,s): x\in X, h(x)\le s} \langle y, q-Ex\rangle + p(Ex)+g(Ax)+s. \end{aligned}$$

(6.2)

Let us write the polyhedral set $\{(x,s): x\in X, h(x)\le s\}$ compactly as $C_x x+ C_s s \ge c$ for some matrices $C_x\in \mathbb {R}^{j\times n}$, $C_s\in \mathbb {R}^{j\times 1}$ and $c\in \mathbb {R}^{j\times 1}$, where $j\ge 0$ is some integer. For any fixed y, let (x(y), s(y)) denote one optimal solution for (6.2), note we must have $h(x(y))=s(y)$. Due to equivalence, if $y^*\in Y^*$, we must also have $x(y^*)\in X^*$.

Define a set-valued function $\mathcal {M}$ that assigns the vector $(d, e)\in \mathbb {R}^{n}\times \mathbb {R}^{m}$ to the set of vectors $(x,s,y,\lambda )\in \mathbb {R}^n\times \mathbb {R}\times \mathbb {R}^m\times \mathbb {R}^j$ that satisfy the following system of equations

$$\begin{aligned}&E^Ty + C_x^T\lambda =d,\\&C^T_s\lambda =1,\\&q-Ex=e,\\&\lambda \ge 0, \ (C_x x+C_s s)\ge c, \ \langle C_x x+C_s s-c,\lambda \rangle =0. \end{aligned}$$

It is easy to verify by using the optimality condition for problem (6.2) that

$$\begin{aligned} (x,s,y,\lambda )\in \mathcal {M}(E^T\nabla p(Ex)+A^T\nabla g(Ax), e)~\hbox {for some} \ \lambda \nonumber \\ \quad \quad \quad \hbox {if and only if}\ x=x(y), \ e=\nabla d(y). \end{aligned}$$

(6.3)

We can take $e=0$, and use the fact that $x(y^*)\in X^*$, we see that $(x,s,y,\lambda )\in \mathcal {M}(E^T\nabla p(Ex)+A^T\nabla g(Ax), 0)$ if and only if $x\in X^*$ and $y\in Y^*$.

The following result states a well-known local upper Lipschitzian continuity property for the polyhedral multifunction $\mathcal {M}$; see [26, 33, 34].

Proposition 6.1

There exists a positive scalar $\theta$ that depends on $A, E, C_x, C_s$ only, such that for each $({\bar{d}}, {\bar{e}})$ there is a positive scalar $\delta '$ satisfying

$$\begin{aligned} \mathcal {M}(d, e)\subseteq \mathcal {M}({\bar{d}}, {\bar{e}})+\theta \Vert (d, e)-({\bar{d}}, {\bar{e}})\Vert {\mathcal {B}}, \end{aligned}$$

(6.4)

$$\begin{aligned} \quad \quad \quad \hbox {whenever} \ \Vert (d, e)-({\bar{d}}, {\bar{e}})\Vert \le \delta '. \end{aligned}$$

(6.5)

where ${\mathcal {B}}$ denotes the unit Euclidean ball in $\mathbb {R}^n\times \mathbb {R}^{m}\times \mathbb {R}\times \mathbb {R}^j$.

The following is the main result for this appendix. Note that the scalar $\tau$ in the claim is independent the choice of y, x, s, and is independent on the coefficients of the linear term s.

Claim 6.1

Suppose all the assumptions in Assumption A are satisfied. Then there exist positive scalars $\delta$, $\tau$ such that $\mathrm{dist}(y, Y^*)\le \tau \Vert \nabla d(y)\Vert$ for all $y\in \mathcal U$ with $\Vert \nabla d(y)\Vert \le \delta$.

Proof

By the previous claim, $\mathcal {M}$ is locally Lipschitzian with modulus $\theta$ at $(\nabla \ell (x^*), 0)=(E^T\nabla p(Ex^*)+A^T\nabla g(Ax^*), 0)$.

Let $\delta \le \delta '/2$. We first show that if $\Vert \nabla d(y)\Vert \le \delta$, then we must have $\Vert \nabla \ell (x(y))-\nabla \ell (x^*)\Vert \le \delta '/2$. To this end, take a sequence $y^1,y^2,\ldots$, such that $e^r:=\nabla d(y^r)\rightarrow 0$. By Assumption (g) $\{x(y^r)\}$ lies in a compact set. Due to the fact that $s(y^r)=h(x(y^r))$, so the sequence $\{s(y^r)\}$ also lies in a compact set (cf. Assumption s(e)). By passing to a subsequence if necessary, let $(x^{\infty },s^{\infty })$ be a cluster point of $\{x(y^r), s(y^r)\}$. In light of the continuity of $\nabla \ell (\cdot )$, we have $(\nabla \ell (x(y^r)), e^r)\rightarrow (\nabla \ell (x^{\infty }),0)$. Now for all r, $\{(x(y^r), s(y^r), \nabla \ell (x(y^r)), e^r)\}$ lies in the set

$$\begin{aligned} \left\{ (x, s, d, e)\mid (x,s,y,\lambda )\in \mathcal {M}(d, e)~\hbox {for some}~ (y,\lambda )\right\} \end{aligned}$$

which is polyhedral and thus is closed. Then we can pass limit to it and conclude (cf. Proposition 6.1)

$$\begin{aligned} (x^\infty , s^{\infty }, y^{\infty }, \lambda ^{\infty })\in \mathcal {M}(\nabla \ell (x^{\infty }), 0) \end{aligned}$$

for some $(y^{\infty }, \lambda ^{\infty })\in \mathbb {R}^{m}\times \mathbb {R}^j$. Thus by (6.3) and the discussions that follow, we have $x^\infty \in X^*$ and $y^{\infty }\in Y^*$. By Lemma 2.1, we have $\nabla \ell (x^*)=\nabla \ell (x^\infty )$, which further implies that $\nabla \ell (x(y^r))\rightarrow \nabla \ell (x^*)$. This shows that the desired $\delta$ exists.

Then we let $e= \nabla d(y)$, and suppose $\Vert e\Vert \le \delta$. From the previous argument we have

$$\begin{aligned} \Vert \nabla \ell (x(y))-\nabla \ell (x^*)\Vert +\Vert e\Vert \le \delta '/2+\delta '/2=\delta '. \end{aligned}$$

Using the results in Proposition 6.1, we have that there exists $(x^*,s^*, y^*, \lambda ^*)\in \mathcal {M}(\nabla \ell (x^*), 0)$ satisfying

$$\begin{aligned} \Vert (x(y), s, y, \lambda )-(x^*,s^*, y^*, \lambda ^*)\Vert&\le \theta \left( \Vert \nabla \ell (x^*)-\nabla \ell (x(y))\Vert +\Vert e\Vert \right) . \end{aligned}$$

Since $(x(y),s,y,\lambda )\in \mathcal {M}(\nabla \ell (x(y)), e)$, it follows from the definition of $\mathcal {M}$ that

$$\begin{aligned}&E^Ty + C_x^T\lambda =\nabla \ell (x(y)), \end{aligned}$$

(6.6)

$$\begin{aligned}&C^T_s\lambda =1, \end{aligned}$$

(6.7)

$$\begin{aligned}&q-Ex(y)=e, \end{aligned}$$

(6.8)

$$\begin{aligned}&\lambda \ge 0, \ (C_x x(y)+C_s s(y))\ge c, \ \langle C_x x(y)+C_s s(y)-c,\lambda \rangle =0. \end{aligned}$$

(6.9)

Since $(x^*,s^*,y^*,\lambda ^*)\in \mathcal {M}(\nabla \ell (x^*), 0)$, we have from the definition of $\mathcal {M}$

$$\begin{aligned}&E^Ty^* + C_x^T\lambda ^* =\nabla \ell (x^*),\end{aligned}$$

(6.10)

$$\begin{aligned}&C^T_s\lambda ^*=1, \end{aligned}$$

(6.11)

$$\begin{aligned}&q-Ex^{*} =0, \end{aligned}$$

(6.12)

$$\begin{aligned}&\lambda ^*\ge 0, \ (C_x x^*+C_s s^*)\ge c, \ \langle C_x x^*+C_s s^*-c,\lambda ^*\rangle =0. \end{aligned}$$

(6.13)

Moreover, we have

$$\begin{aligned}&\sigma _g\Vert A(x(y)-x^*)\Vert ^2+\sigma _p\Vert E(x(y)-x^*)\Vert ^2\\&\qquad \le \langle A^T\nabla g(Ax(y))-A^T\nabla g(Ax(y^*)), x(y)-x(y^*)\rangle \\&\qquad \quad +\langle E^T\nabla p(Ex(y))-E^T\nabla p(Ex(y^*)), x(y)-x(y^*)\rangle \\&\qquad =\langle \nabla \ell (x(y))-\nabla \ell (x(y^*)), x(y)-x(y^*)\rangle \\&\qquad =\langle \lambda -\lambda ^*, C_x x(y)-C_x x^*\rangle +\langle y-y^*, E x(y)-E x^*\rangle \end{aligned}$$

where the first inequality comes from the strong convexity of $g(\cdot )$ and $p(\cdot )$; the last equality is from (6.6) and (6.10). Moreover, we have

$$\begin{aligned}&\langle \lambda -\lambda ^*, C_x x(y)-C_x x^*\rangle \nonumber \\&\qquad =\langle \lambda -\lambda ^*, C_x x(y)-C_x x^*\rangle +\langle \lambda -\lambda ^*, C_s s-C_s s^*\rangle \nonumber \\&\qquad =\langle \lambda -\lambda ^*, (C_x x(y)+C_s s)-(C_x x^*+C_s s^*)\rangle \nonumber \\&\qquad =-\langle \lambda ^*, C_x x(y)+C_s s-c\rangle -\langle \lambda , C_x x^*+C_s s^*-c\rangle \le 0 \end{aligned}$$

(6.14)

where in the first equality we have used the fact that $C^T_s\lambda -C^T_s\lambda ^*=0$; see (6.7) (6.11); in the third equality and in the last inequality we have used the complementary conditions (6.13) and (6.9). As a result, we have

$$\begin{aligned}&\sigma _g\Vert A(x(y)-x^*)\Vert ^2+\sigma _p\Vert E(x(y)-x^*)\Vert ^2\nonumber \\&\le \langle y-y^*, (Ex(y)-q)-(Ex^*-q)\rangle \le \Vert y-y^*\Vert \Vert e\Vert , \end{aligned}$$

(6.15)

where the last step is due to $\nabla d(y)=Ex(y)-q$ and $\nabla d(y^*)=Ex^*-q=0$. Finally we have from Proposition 6.1

$$\begin{aligned}&\Vert (x(y), s, y, \lambda )-(x^*,s^*, y^*, \lambda ^*)\Vert ^2\\&\qquad \le \theta ^2\left( \Vert \nabla \ell (x^*)-\nabla \ell (x(y))\Vert +\Vert e\Vert \right) ^2\\&\qquad \le \theta ^2\left( 2\Vert \nabla \ell (x^*)-\nabla \ell (x(y))\Vert ^2+2\Vert e\Vert ^2\right) \\&\qquad \le 2\theta ^2\left( 2\Vert \nabla g(x^*)-\nabla g(x(y))\Vert ^2+2\Vert \nabla p(x^*)-\nabla p(x(y))\Vert ^2+\Vert e\Vert ^2\right) \\&\qquad \le 2\theta ^2\left( L^2_g\Vert A^T(x(y)-x^*)\Vert ^2+L^2_p\Vert E^T(x(y)-x^*)\Vert ^2+\Vert e\Vert ^2\right) \\&\qquad \le 2\theta ^2\max \left( \frac{2L^2_g}{\sigma _g}, \frac{2L^2_p}{\sigma _p},1\right) \left( \sigma _g\Vert A^T(x(y)-x^*)\Vert ^2 +\sigma _p\Vert E^T(x(y)-x^*)\Vert ^2+\Vert e\Vert ^2\right) \\&\qquad \le 2\theta ^2\max \left( \frac{2L^2_g}{\sigma _g}, \frac{2L^2_p}{\sigma _p},1\right) \left( \Vert e\Vert \Vert y-y^*\Vert +\Vert e\Vert ^2\right) \\&\qquad \le 2\theta ^2\max \left( \frac{2L^2_g}{\sigma _g}, \frac{2L^2_p}{\sigma _p},1\right) \left( \Vert e\Vert \Vert (x(y), s,y, \lambda )-(x^*, s^*, y^*, \lambda ^*)\Vert +\Vert e\Vert ^2\right) , \end{aligned}$$

where the second inequality is due to $\nabla \ell (x)=\nabla g(x)+\nabla p(x)$ and the fourth step follows from properties a-3) and b).

We see that the above inequality is quadratic in $\Vert (x(y), s, y, \lambda )-(x^*, s^*, y^*, \lambda ^*)\Vert /$ $\Vert e\Vert$, so we have

$$\begin{aligned} \Vert (x(y),s, y, \lambda )-(x^*, s^*, y^*, \lambda ^*)\Vert /\Vert e\Vert \le \tau \end{aligned}$$

for some scalar $\tau$ depending on $\theta$, $L_g$, $L_p$, $\sigma _g$, $\sigma _p$. It is worth noting that $\tau$ does not depend on the choice of the coefficients of the linear term s. We conclude $\mathrm{dist}(y, Y^*)\le \tau \Vert \nabla d(y)\Vert$. $\square$