On the Linear Convergence of the Alternating Direction Method of Multipliers\thanks{The research is supported by the National Science Foundation, grant number DMS-1015346.}
{ Mingyi Hong\ \ and\ \ Zhi-Quan Luo}\thanks{ Department of Electrical and Computer Engineering
Minneapolis
MN 55455
[20pt] Dedicated to the fond memories of a close friend and collaborator, Paul Y. Tseng
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 linear convergence of the ADMM for minimizing the sum of any number of convex separable functions. This result settles a key question regarding the convergence of the ADMM when the number of blocks is more than two or if the strong convexity is absent. It also implies the linear convergence of the ADMM for several contemporary applications including LASSO, Group LASSO and Sparse Group LASSO without any strong convexity assumption. Our proof is based on estimating the distance from a dual feasible solution to the optimal dual solution set by the norm of a certain proximal residual, and by requiring the dual stepsize to be sufficiently small.
1208.3922.tex
\documentclass[11pt]{article}
\usepackage{psfrag,cite,amsmath,graphicx,epsfig,latexsym,subfigure,color}
%\usepackage[active]{srcltx}
\usepackage[scriptsize,bf]{caption}
\usepackage{color}
\usepackage{amssymb}
\setlength{\captionmargin}{40pt}%
%\input{../../../slides/Singapore/defs.tex}
%\input{../../../slides/preamble2e}
%\input{head.tex}

% ===================================================================
% ============================ head.tex =============================
% ===================================================================

\DeclareMathOperator{\argmin}{\mbox{argmin}}
\def\bn{\hfill \\ \smallskip\noindent}
\def\argmin{\mathop{\rm argmin}}
\def\sgn{\mathop{\rm sgn}}
\def \la {\langle}
\def \ra {\rangle}
\def\vx{x}
\def\vy {y}
\def\vz{z}
\def\dom{\mbox{dom\,}}
\def\proj{\mbox{proj}}
\def\prox{\mbox{prox}}
\def\R{\Re}
\def\dist{\mbox{dist\,}}
%\DeclareMathOperator{\prox}{\mbox{prox}}
%\DeclareMathOperator{\proj}{\mbox{proj}}
%\def\prox{\mathop{\rm prox}}
%\def\proj{\mathop{\rm proj}}
% Things defined by amsmath:
% \newcommand{\implies}{\Longrightarrow}
% \newcommand{\Vec}{{\rm \;vec\; }}

% ===================================================================
% ========================= end of head.tex =========================
% ===================================================================
%\usepackage{subfigure}

%\renewcommand{\thesection}{\arabic{section}}
%\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\newcommand{\newsection}{\setcounter{equation}{0}\section}

\textheight 8.5truein
\parskip 0.1in
\topmargin -0.05truein \textwidth 6.5truein
\oddsidemargin -0.05in %
\evensidemargin -0.05in %
\renewcommand{\baselinestretch}{1.2}   %line space adjusted here
\setcounter{footnote}{0} \sloppy

\newcommand{\namelistlabel}[1]{\mbox{#1}\hfill}
\newenvironment{namelist}[1]{%
\begin{list}{}
{
\let\makelabel\namelistlabel
\settowidth{\labelwidth}{#1}
%\setlength{\leftmargin}{1.1\labelwidth}
\leftmargin +2.0truein }
}{%
\end{list}}

\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}


\begin{document}


\bigskip
\def\theequation {\thesection.\arabic{equation}}
\def\pn {\par\smallskip\noindent}
\def \bn {\hfill \\ \smallskip\noindent}
\newcommand{\fs}{f_1,\ldots,f_s}
\newcommand{\f}{\vec{f}}
\newcommand{\vecx}{x_1,\ldots,x_m}
\newcommand{\xoy}{x\rightarrow y}
\newcommand{\barx}{{\bar x}}
\newcommand{\bary}{{\bar y}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{claim}{Claim}[section]

\newcommand{\newsection}{\setcounter{equation}{0}\section}

\def\br{\break}
\def\smskip{\par\vskip 5 pt}
\def\proof{\bn {\bf Proof.} }
\def\QED{\hfill{\bf Q.E.D.}\smskip}
\def\qed{\quad{\bf q.e.d.}\smskip}

\newcommand{\cM}{\mathcal{M}}



%% PUT YOUR TITLE PAGE INFORMATION HERE %%%
\begin{titlepage}
\title{\bf On the Linear Convergence of the Alternating Direction Method of Multipliers\thanks{The research is supported  by the National Science Foundation, grant number DMS-1015346.}
} \vskip 0.5cm
\author{{ Mingyi Hong\ \ and\ \ Zhi-Quan Luo}\thanks{ Department of Electrical and
Computer Engineering, University of Minnesota, Minneapolis, MN
55455, USA. Email: \texttt{\{mhong, luozq\}@umn.edu} }
\\[20pt]
\emph{Dedicated to the fond memories of a close friend and
collaborator, Paul Y. Tseng}}
\date{August 13, 2012; Revised March 20, 2013}
\maketitle
\vskip 1.0cm

\begin{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 \emph{two} convex functions defined on
\emph{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 linear convergence of the ADMM for
minimizing the sum of \emph{any} number of convex separable
functions. This result settles a key question regarding the
convergence of the ADMM when the number of blocks is more than two
or if the strong convexity is absent. It also implies the linear
convergence of the ADMM for several contemporary applications
including LASSO, Group LASSO and Sparse Group LASSO without any
strong convexity assumption. Our proof is based on estimating the
distance from a dual feasible solution to the optimal dual solution
set by the norm of a certain proximal residual, and by requiring
 the dual stepsize to be sufficiently small.
\end{abstract}

\vspace*{\fill}

\noindent {\bf KEY WORDS:} Linear convergence, alternating directions of multipliers, error bound,  dual ascent.
\pn
\noindent {\bf AMS(MOS) Subject Classifications:}  49, 90.

\end{titlepage}

%%SO MUCH FOR THE TITLE PAGE

\newsection{\bf Introduction}


Consider the problem of minimizing a separable nonsmooth convex function subject to linear equality constraints:
\begin{equation}\label{eq:1}
\begin{array}{ll}
\mbox{minimize} & f(x)=f_1(x_1)+f_2(x_2)+\cdots+f_K(x_K)\\ [10pt]
\mbox{subject to} & \displaystyle Ex=E_1x_1+E_2x_2+\cdots+E_Kx_K=q\\
& x_k\in X_k,\quad k=1,2,...,K,
\end{array}
\end{equation}
where each $f_k$ is a nonsmooth convex function (possibly with
extended values), $x=(x_1^T,...,x_K^T)^T\in\Re^n$ is a partition of
the optimization variable $x$, $X=\prod_{k=1}^{K}X_k$ is the
feasible set for $x$, and $E=(E_1,E_2,...,E_K)\in\Re^{m\times n}$ is
an appropriate partition of matrix $E$ (consistent with the
partition of $x$) and $q\in\Re^m$ is a vector. Notice that the model
\eqref{eq:1} can easily accommodate general linear inequality
constraints $Ex\ge q$ by adding one extra block. In particular, we
can introduce a slack variable $x_{K+1}\ge0$ and rewrite the
inequality constraint as $Ex-x_{k+1}=q$. The constraint
$x_{K+1}\ge0$ can be enforced by adding a new convex component
function $f_{K+1}(x_{K+1})=i_{\Re^m_+}(x_{K+1})$ to the objective
function $f(x)$, where $i_{\Re^m_+}(x_{K+1})$ is the indicator
function for the nonnegative orthant $\Re^m_+$
\[
i_{\Re^{m}_+}(x_{K+1})=\left\{\begin{array}{ll}
0,& \mbox{if $x_{K+1}\ge 0$ (entry wise),}\\
\infty, & \mbox{otherwise}.
\end{array}
\right.
\]
In this way, the inequality constrained problem with $K$ blocks is reformulated as an equivalent equality constrained convex minimization problem with $K+1$ blocks.

Optimization problems of the form \eqref{eq:1} arise in many emerging applications involving structured convex optimization. For instance, in compressive sensing applications, we are given an observation matrix $A$ and a noisy observation vector $b\approx Ax$. The goal is to estimate the sparse vector $x$ by solving the following $\ell_1$ regularized linear least squares problem:
\[
\begin{array}{ll}
\mbox{minimize}& \|y\|^2+\lambda\|x\|_1\\
\mbox{subject to} &Ax+y=b,
\end{array}
\]
where $\lambda>0$ is a penalty parameter. Clearly, this is a
structured convex optimization problem of the form \eqref{eq:1} with
$K=2$. If the variable $x$ is further constrained to be nonnegative,
then the corresponding compressive sensing problem can be formulated
as a three block ($K=3$) convex separable optimization problem
\eqref{eq:1} by introducing a slack variable. Similarly, in the
stable version of robust principal component analysis (PCA)
\cite{rpca}, we are given an observation matrix $M\in\Re^{m\times
n}$ which is a noise-corrupted sum of a low rank matrix $L$ and a
sparse matrix $S$. The goal is recover $L$ and $S$ by solving the
following nonsmooth convex optimization problem
\[
\begin{array}{ll}
\mbox{minimize}& \|L\|_*+\rho\|S\|_1 +\lambda\|Z\|_F^2\\
\mbox{subject to} &L+S+Z=M
\end{array}
\]
where $\|\cdot\|_*$ denotes the matrix nuclear norm (defined as the sum of the matrix singular eigenvalues), while $\|\cdot\|_1$ and $\|\cdot\|_F$ denote, respectively, the $\ell_1$ and the Frobenius norm of a matrix (equal to the standard $\ell_1$ and $\ell_2$ vector norms when the matrix is viewed as a vector). In the above formulation, $Z$ denotes the noise matrix, and $\rho,\;\lambda$ are some fixed penalty parameters. It is easily seen that the stable robust PCA problem corresponds to the three block case $K=3$ in the problem \eqref{eq:1} with $x=(L,S,Z)$ and
\begin{equation}\label{eq:fs}
f_1(L)=\|L\|_*,\quad f_2(S)=\|S\|_1,\quad f_3(Z)=\|Z\|_F^2,
\end{equation}
while the coupling linear constraint is given $L+S+Z=M$. In image processing applications where the low rank matrix $L$ is additionally constrained to be nonnegative, then the above problem can be reformulated as
\[
\begin{array}{ll}
\mbox{minimize}& \|L\|_*+\rho\|S\|_1 +\lambda\|Z\|_F^2+i_{\Re^{mn}_+}(C)\\
\mbox{subject to} &L+S+Z=M,\ L-C=0,
\end{array}
\]
where $C$ is a slack matrix variable of the same size as $L$, and $i_{\Re^{mn}_+}(\cdot)$ is the indicator function for the nonnegative orthant $\Re_+^{mn}$.
In this case, the stable robust PCA problem is again in the form of \eqref{eq:1}. In particular, it has 4 block variables $(L,S,Z,C)$ and the first three convex functions are the same as in \eqref{eq:fs}, while the fourth convex function is given by $f_4(C)=i_{\Re^{mn}_+}(C)$. The coupling linear constraints are $L+S+Z=M,\ L-C=0$.
Other applications of the form \eqref{eq:1} include the latent variable Gaussian graphical model selection problem, see \cite{latent}.

A popular approach to solving the separable convex optimization problem \eqref{eq:1} is to attach a Lagrange multiplier vector $y$ to the linear constraints $Ex =q$ and add a quadratic penalty, thus obtaining an augmented Lagrangian function of the form
\begin{equation}\label{eq:aug-lagrangian}
%d(y) = \min_{x\in X} \ \langle y, q - Ex \rangle + f(x)+\frac{\rho}{2}\|[q-Ex]_+\|^2,
L(x;y) =  f(x)+ \langle y, q - Ex \rangle +\frac{\rho}{2}\|q-Ex\|^2,
\end{equation}
where  $\rho\ge0$ is a constant.
The augmented dual function is given by
\begin{equation}\label{1.1.1}
d(y) = \min_{x} \ f(x)+ \langle y, q - Ex \rangle +\frac{\rho}{2}\|q-Ex\|^2
\end{equation}
and the dual problem (equivalent to \eqref{eq:1} under mild conditions) is
\begin{equation}\label{2.3}
\max_y d(y).
\end{equation}
Moreover, if $\rho>0$, then $Ex$ is constant over the set of minimizers of \eqref{1.1.1} (see Lemma~\ref{lm:const-derivative} in Section 2). This implies that the dual function $d(y)$ is differentiable with
\[
\nabla d(y)=q-Ex(y)
\]
where $x(y)$ is a minimizer of \eqref{1.1.1}. Given the differentiability of $d(y)$, it is natural to consider the following dual ascent method to solve the primal problem \eqref{eq:1}
\begin{equation}\label{eq:dual-ascent}
y:=y+\alpha \nabla d(y)=y+\alpha(q-Ex(y)),
\end{equation}
where $\alpha>0$ is a suitably chosen stepsize.
Such a dual ascent strategy is  well suited
for structured convex optimization problems that are amenable to decomposition.  For example, if the objective function $f$ is separable (i.e., of the form given in \eqref{eq:1}) and if we select $\rho=0$, then the minimization in (\ref{1.1.1}) decomposes into $K$ independent minimizations whose solutions frequently can be obtained in a simple form. In addition, the iterations can be implemented in a manner that exploits the sparsity structure of the problem and, in certain network cases, achieve a high degree of parallelism.   Popular choices for the ascent methods include (single) coordinate ascent (see \cite{[3], [6], [7], [19], [14], [21], [28], [29], [32]}), gradient ascent (see \cite{[14], [21], [31]}) and gradient projection \cite{[Gol64],[LeP65]}. (See \cite{[5], [14], [30]} for additional references.)

For large scale optimization problems, it is numerically advantageous to select $\rho>0$. Unfortunately, this also introduces variable coupling in the augmented Lagrangian \eqref{eq:aug-lagrangian}, which makes the exact minimization step in \eqref{1.1.1} no longer decomposable across variable blocks even if $f$ has a separable structure. In this case, it is more economical to minimize \eqref{1.1.1} inexactly by updating the components of $x$ cyclically via the coordinate descent method. In particular, we can apply the Gauss-Seidel strategy to inexactly minimize \eqref{1.1.1}, and then update the multiplier $y$ using an approximate optimal solution of \eqref{1.1.1} in a manner similar to \eqref{eq:dual-ascent}. The resulting algorithm is called the Alternating Direction Method of Multipliers (ADMM) and is summarized as follows (see \cite{Gab76,Ga83,Glow84,Glt89}). In the general context of sums of
monotone operators, the work of \cite{eckstein10} describes a large family of splitting methods for $K\ge 3$ blocks which, when applied to the dual, result in similar but not identical methods to the ADMM algorithm \eqref{eq:admm} below.
\begin{center}
\fbox{
\begin{minipage}{5.2in}
\smallskip
\centerline{\bf Alternating Direction Method of Multipliers (ADMM)}
\smallskip
At each iteration $r\ge 1$, we first update the primal variable blocks in the Gauss-Seidel fashion and then update the dual multiplier using the updated primal variables:
\begin{equation}\label{eq:admm}
\left\{\begin{array}{l}\displaystyle
x_k^{r+1}={\rm arg}\!\min_{x_k\in X_k}L(x_1^{r+1},...,x^{r+1}_{k-1},x_k,x^r_{k+1},...,x^r_K;y^r),\ k=1,2,...,K,\\[10pt]
\displaystyle y^{r+1}=y^r+\alpha(q-Ex^{r+1})=y^r+\alpha\left(q-\sum_{k=1}^KE_kx_k^{r+1}\right),
\end{array}
\right.
\end{equation}
where $\alpha>0$ is the step size for the dual update.
\end{minipage}
}
\end{center}

Notice that if there is only one block ($K=1$), then the ADMM
reduces to the standard augmented Lagrangian method of multipliers
for which the global convergence is well understood (see e.g.,
\cite{bertsekas}). In particular, it is known that, under mild
assumptions on the problem, this type of dual gradient ascent
methods generate a sequence of iterates whose limit points must be
optimal solutions of the original problem (see \cite{[6], [28],
[30]}).  For the special case of ordinary network flow problems, it
is further known that an associated sequence of dual iterates
converges to an optimal solution of the dual (see \cite{[3]}).  The
rate of convergence of dual ascent methods has been studied in the
reference \cite{luo-tseng} which showed that, under mild assumptions
on the problem, the distance to the optimal dual solution set from
any $y \in \Re^m$ near the set is bounded above by the dual optimality
`residual' $\|\nabla d(y)\|$. By using this bound, it can be
shown that a number of ascent methods, including coordinate ascent
methods and a gradient projection method, converge at least linearly
when applied to solve the dual problem (see \cite{[15],[16]}; also
see \cite{[2],[8],[11]} for related analysis).   (Throughout this
paper, by `linear convergence' we mean root--linear convergence
(denoted by R-linear convergence) in the sense of Ortega and
Rheinboldt \cite{[20]}.)

When there are two blocks ($K=2$), the convergence of the ADMM was
studied in the context of  Douglas-Rachford splitting method
\cite{douglas-rachford,eckstein,eckstein-bertsekas} for finding a
zero of the sum of two maximal monotone operators. It is known that
in this case every limit point of the iterates is an optimal
solution of the problem. The recent work of
\cite{goldfarb-ma,goldfarb-ma-scheinberg,HeYuan12} have shown that,
under some additional assumptions, the objective values generated by
the ADMM algorithm and its accelerated version (which performs some
additional line search steps for the dual update) converge at a rate
of $O(1/r)$ and $O(1/r^2)$ respectively. Moreover, if the objective
function $f(x)$ is strongly convex and the constraint matrix $E$ is
row independent, then the ADMM is known to converge linearly to the
unique minimizer of \eqref{eq:1} \cite{LionsMercier}.  [One notable
exception to the strong convexity requirement is in the special case
of linear programming for which the ADMM is linearly convergent
\cite{eckstein}.] More recent convergence rate analysis of the ADMM
still requires at least one of the component functions ($f_1$ or
$f_2$) to be strongly convex and have a Lipschitz continuous
gradient. Under these and additional rank conditions on the
constraint matrix $E$, some linear convergence rate results can be
obtained for a subset of primal and dual variables in the ADMM
algorithm (or its variant); see \cite{Yin,UCLA,Boley}. However, when
there are more than two blocks involved ($K\ge3$), the convergence
(or the rate of convergence) of the ADMM method is unknown, and this
has been a key open question for several decades. The recent work
\cite{mashiqian} describes a list of novel applications of the ADMM
with $K\ge 3$ and motivates strongly for the need to analyze the
convergence of the ADMM in the multi-block case.  The recent
monograph \cite{boyd} contains more details of the history,
convergence analysis and applications of the ADMM and related
methods.

A main contribution of this paper is to establish the global (linear) convergence of the ADMM method for a class of convex objective functions involving any number of blocks ($K$ is arbitrary). The key requirement for the global (linear) convergence is the satisfaction of a certain error bound condition that is similar to that used in the analysis of \cite{luo-tseng}. This error bound estimates the distance from an iterate to the optimal solution set in terms of a certain proximity residual. The class of objective functions that are known to satisfy this error bound condition include many of the compressive sensing applications, such as LASSO \cite{lasso}, Group LASSO \cite{group-lasso} or Sparse Group LASSO \cite{luo-zhang}.



%dual problem of maximizing $d(y)$, subject to $y \ge 0$.
%
%
%In this paper, we extend the above results  to the case where $X$ is any polyhedral set (instead of the entire space).  We show that, under mild assumptions on the problem, the local error bound cited above still holds (see Theorem 4.1).  By using this bound, we then prove a general linear convergence result for a class of dual ascent methods, included in which are the methods proposed in [3], [6], [21], [28], [29], [32].  To our knowledge, this is the first general rate of convergence result for these methods.  As a consequence, we show, also for the first time, that the methods proposed in [7] and [19] converge at least linearly (see Section 5).  We remark that, owing to the presence of $X$, the analysis here is quite more complex than those in [15] and [16].  For example, in proving the local error bound, a sensitivity result of Robinson is applied {\it simultaneously} to a primal--dual pair of linear systems (see Lemma 4.1), instead of to, say, the dual linear system alone.
%
%This paper proceeds as follows: In Section 2, we describe
%the primal problem and its  dual.  In Section 3, we prove two technical lemmas characterizing this pair of problems. In Section 4, we use these lemmas to establish our local error bound.  This bound, in turn, is used in Sections 5--7 to prove  linear convergence for a number of dual ascent methods.  In Section 8, we give our conclusion and discuss extensions.
%


%In our notation, all vectors are column vectors and $\Re^n$ denotes
%the $n$--dimensional Euclidean space. For any vector $x \in \Re^n$,
%we denote by $x_i$ the $i$th coordinate of $x$ and, for any $I
%\subseteq \{1,...,n\}$, by $x_I$ the vector obtained after removing
%from $x$ those $x_i$ with $i\not\in I$.  We also denote by $\|x\|$
%the usual Euclidean norm of $x$, i.e., $\|x\| = \sqrt{\langle x , x
%\rangle }$ with $\langle x, y \rangle = \sum_i x_i y_i$. For any
%$h\times k$ matrix $A$, we denote by $A_i$ the $i$th row of $A$, and
%by $A_I$ the submatrix of $A$ obtained by removing all rows $A_i$
%with $i\not\in I$.  For any function $h$ with gradient $\nabla h$,
%the notations $\nabla_i h$ and $\nabla_I h$ carry analogous meaning.
%For any closed convex set $X$ and any vector $x$ in the same space,
%we denote by $[x]^+_X$ the orthogonal projection of $x$ onto $X$.


\newsection{ Technical Preliminaries}

Let $f$ be a closed proper convex function in $\Re^n$, let $E$ be an
$m \times n$  matrix,  let $q$ be a vector in $\Re^m$.
%We associate with $f$, $E$, $q$ and $Y$ the  following \underbar{primal functional} $p$, given by
%\begin{equation}\label{2.4}
%p(x) = \max_{y\in Y}\  \langle y , q - Ex \rangle  + f(x).
%\end{equation}
%We  study the convex program:
%\begin{equation} \label{2.5}
%\min_{x\in X} p(x),
%\end{equation}
%where $X$ is a polyhedral set in $\Re^n$.
%
Let ${\rm dom}\ f$ denote the effective domain of $f$ and let
$\hbox{int}(\hbox{dom } f)$ denote the interior of ${\rm dom}\ f$.
We make the following standing assumptions regarding $f$: \pn {\bf
Assumption A.}
\begin{itemize}
\item [(a)] The global minimum of \eqref{eq:1} is attained and so is its dual optimal value.
The intersection $X\cap \hbox{int}(\hbox{dom } f)\cap \{x\mid
Ex=q\}$ is nonempty.
\item
[(b)] $f=f_1(x_1)+f_2(x_2)+\cdots+f_K(x_K)$, with each $f_k$ further decomposable as
\[
f_k(x_k)=g_k(A_kx_k)+h_k(x_k)
\]
where $g_k$ and $h_k$ are both convex and continuous over their
domains, and $A_k$'s are some given matrices (not necessarily full
column rank, and can be zero).
\item
[(c)] Each $g_k$ is strictly convex and continuously differentiable
on $\hbox{int}(\hbox{dom } g_k)$ with a uniform Lipschitz continuous
gradient
\begin{align}
&\|\nabla A_k^T g_k(Ax_k)-A^T_k\nabla g_k(Ax_k')\|\le
L\|x_k-x_k'\|,~\quad\quad\forall~x_k,x_k'\in X_k\nonumber
\end{align}
where $L>0$ is a constant. %Moreover, $\|\nabla g_k(z_k)\|\to \infty$
%whenever $z_k$ approaches the boundary of $\hbox{int}(\hbox{dom }
%f)$ or $\|z_k\|\to\infty$.

\item [(d)] Each $h_k$ satisfies either one of the following
conditions
\begin{enumerate}
\item The epigraph of $h_k(x_k)$ is a polyhedral set.
\item $h_k(x_k)=\lambda_k\|x_k\|_1+\sum_{J}w_J\|x_{k,J}\|_2$, where
$x_k=(\cdots, x_{k,J},\cdots)$ is a partition of $x_k$ with $J$
being the partition index.
\item Each $h_k(x_k)$ is the sum of the functions described in the previous
two items.
\end{enumerate}
\item [(e)] For any fixed and finite $y$ and $\xi$, $\sum_k h_k(x_k)$ is finite for all $x\in\{x: L(x;y)\le \xi\}\cap  X$.
\item [(f)] Each submatrix $E_k$ has full column rank.
\item [(g)] The feasible sets $X_k$,
$k=1,\cdots,K$ are compact polyhedral sets.
\end{itemize}

%We remark that the inclusion of a linear term $\langle
%b_k,x_k\rangle$ in Assumption A(b) is needed to cover cases where
%$b_k$ lies outside the row span of $A_k$.
%In the subsequent
%analysis, however, we shall assume $b_k=0$ for all $k$ to simplify
%the notations. All the ensuing proofs and results will remain true
%with trivial modifications for $b_k\neq 0$ case.
We have the following remarks regarding to the assumptions made.
\begin{enumerate}
\item Each $f_k$ may only contain convex function $h_k$. That is, the strongly convex
part $g_k$ can be absent. Also, since the matrices $A_k$'s are not required to have full column rank,
the overall objective function $f(x)$ is not necessarily strongly convex. In fact, under Assumption A,
the optimization problem \eqref{eq:1} can still have
multiple primal or dual optimal solutions. This makes the convergence (and rate of convergence) analysis of ADMM difficult.
%\item We have required that the feasible sets $X_k$'s are polyhedral
%and compact.  Later we will elaborate on how this assumption can be
%relaxed.
\item Assumption $(e)$ does allow $h_k(\cdot)$ to be an
indicator function, as in this case the set $\{x_k\mid \sum_k
h_k(x_k)=\infty\}\cap X$ is not a subset of $\{x: L(x;y)\le
\xi\}\cap X$ for any given $y$ and $\xi$.

\item Linear term of the form $\langle b_k,x_k\rangle$ is already
included in $h_k$, as its ephigraph is polyhedral. Moreover, from
the assumption that $X_k$ is polyhedral, the feasibility constraint
$x_k\in X_k$ can be absorbed into $h_k$ by adding to it an indicator
function ${i}_{X_k} (x_k)$. To simplify notations,
we will not explicitly write $x_k\in X_k$ in the ADMM update
\eqref{eq:admm} from now on.

\item Assumption (f) is made to ensure that the subproblems for each
$x_k$ is strongly convex. This assumption will be relaxed later when
the subproblems are solved inexactly; see Section \ref{subProximal}.

\item Assumption (g) requires the feasible set of the variables to
be compact, which is needed to ensure that certain error bounds of
the primal and dual problems of \eqref{eq:1} hold. This assumption
is usually satisfied in practical applications (e.g. the consensus
problems) whenever {\it a priori} knowledge on the variable
domain is available. This assumption can be further relaxed; see the
discussion at the end of Section \ref{secMain}.
\end{enumerate}
Under Assumption A, both the primal optimum and the dual optimum values of \eqref{eq:1} are attained and are equal (i.e., the strong duality holds for \eqref{eq:1}) so that
\[
d^*=\max_yL(x;y)=\max_y\left(f(x)+\langle y,q-Ex\rangle + \frac{\rho}{2}\|Ex-q\|^2\right)=\min_{Ex=q}f(x),
\]
where $d^*$ is the optimal value of the dual of \eqref{eq:1}.
%
%\bn
%(a) $f$ is co--finite, essentially smooth.
%\bn
%(b) $\nabla f$ is strongly monotone and Lipschitz continuous on any compact convex subset of $\hbox{int}(\hbox{dom } f)$.
%\bn
%(c) $f$ is continuous on $\hbox{dom } f$.

% Roughly speaking, Assumption A requires that the smooth part of $f$ (i.e., the $g_k$'s), in addition to satisfying certain regularity conditions, be a co--finite, strictly convex essentially smooth function or, in the terminology of Rockafellar \cite[Sec.\ 26]{[25]}, a co--finite convex function of the Legendre type.  In general,  Assumption A(c) is satisfied whenever the smooth part of $f$ is strongly convex twice differentiable or whenever its Hessian is positive definite everywhere on the interior of its effective domain.
%
%Although Assumption A may seem restrictive, there are a number of important special cases that satisfy this assumption.  These include (i) strictly convex quadratic programs (see \cite{[14]}), (ii) certain problems of matrix balancing and image reconstruction, where $f(x)$ is the entropy function  $\sum_{j=1}^n x_j \ln x_j$ (see \cite{[10], [12], [26]}), (iii) a  problem of optimal routing on data networks, where $f(x)$ is the inverse barrier function $\sum_{j=1}^n 1/(c_j - x_j)$ with $c_j > 0$ (see [4]), and (iv) the Hazen--Williams' model of flow through pipe networks, where $f(x)$ is the power function $\sum_{j=1}^n a_j (x_j)^c$ with $a_j > 0$ and $c \approx 2.85$ (see \cite{[27]}).

%We make the following standing assumption regarding  (\ref{2.4})--(\ref{2.5}):
%\pn
%{\bf Assumption B.} The feasible set for (\ref{2.5}), namely $\hbox{dom } p \cap X$, makes a nonempty intersection with $\hbox{int}(\hbox{dom } f)$.
%
%
%Assumption B is the usual feasibility assumption plus a constraint qualification condition.  To see this, consider the special case where $Y = \Re^m$ (respectively, $Y = [0,\infty)^m$).  In this case, (\ref{2.4})--(\ref{2.5}) reduces to the problem:
%\[
%\hbox{minimize $f(x)$ subject to $x \in X$ and $Ex = q$ (respectively, $Ex \ge q$)}
%\]
% and Assumption B reduces to the standard constraint qualification condition that $\{\ x\ |\ Ex = q\ \}$ (respectively, $\{\ x\ |\ Ex \ge q\ \}$) makes a nonempty intersection with  $X\cap \hbox{int}(\hbox{dom } f)$.
%
%By Assumption A, $f$ is proper and the interior of
%its effective domain is nonempty. Moreover, because $f$ is essentially smooth (so its graph `curves upwards' at the boundary of its effective domain) and has compact level sets, this implies that optimal solutions of \eqref{eq:1} must lie in $\hbox{int}(\hbox{dom }f)$.

%By Assumption A, $f$ is proper and the interior of
%its effective domain is nonempty.  Since $f$ is the sum of a closed co--finite strictly convex function (namely  $f$) with a convex polyhedral function (cf.\ (\ref{2.4})), then $p$ itself is closed co--finite strictly convex.  Since $p$ is closed co--finite, its level sets are compact, so the feasibility of (\ref{2.5}) (cf.\ Assumption B) implies that (\ref{2.5}) has an optimal solution.  Since $p$ is strictly convex, this optimal solution is unique, which we denote by $x^*$.  Moreover, because $f$ is essentially smooth (so its graph `curves upwards' at the boundary of its effective domain), the constraint qualification condition embodied by Assumption B implies that $x^*$ lies in $\hbox{int}(\hbox{dom }f)$.

%
%By reversing the order of `$\max$' and
%`$\min$' in the primal problem
%(\ref{2.4})--(\ref{2.5}), we obtain  the following  concave program, called the \underbar{dual problem}:
%\begin{equation} \label{2.3}
% \max_{y\in Y} d(y),
%\end{equation}
%where $d$ is the \underbar{dual functional} given by (cf.\ (\ref{2.4}))
%\begin{equation}\label{2.2}
%d(y) =
% \min_{x\in X} \ \langle y , q - Ex \rangle  + f(x).
%\end{equation}
%Since $f$ is co--finite and (cf.\ Assumption A(b)) essentially strictly convex,  it follows from Corollary 13.3.1 and Theorem 26.3 in [25] that $d$ is concave differentiable.  Moreover, Assumption B implies that  strong duality holds, i.e., the respective optimal values of (\ref{2.5}) and (\ref{2.3}) are equal,
%and  that (\ref{2.3}) has at least one optimal solution.  (This can be seen, for example, by rewriting (\ref{2.4})--(\ref{2.5}) as an ordinary convex program and then verifying that Theorem 28.2 in [25] applies to the latter.) Let $Y^*$ denote the set of optimal solutions of (\ref{2.3}). Then, $Y^*$ is  nonempty closed convex and $y^*\in Y^*$ if and only if $y^* \in Y$ and $d(y^*) = f(x^*)$.
%Notice that $Y^*$ need not be bounded (such as when $[E\ \vdots\ q]$ lacks full row rank).


%\vfill
%\eject


Under Assumption A, there may still be multiple optimal solutions for both the primal problem \eqref{eq:1} and its dual problem. We first claim that the dual functional
\begin{equation}\label{eq:dual}
d(y)=\min_xL(x;y)=\min_{x} \ f(x)+ \langle y, q - Ex \rangle +\frac{\rho}{2}\|q-Ex\|^2,
\end{equation}
is differentiable everywhere. Let $X(y)$ denote the set of optimal solutions for \eqref{eq:dual}.
\begin{lemma}\label{lm:const-derivative}
For any $y\in \Re^m$, both $Ex$ and $A_kx_k$, $k=1,2,...,K$, are constant over $X(y)$. Moreover, the dual function $d(y)$ is differentiable everywhere and
\[
\nabla d(y)=q-Ex(y),
\]
where $x(y)\in X(y)$ is any minimizer of \eqref{eq:dual}.
\end{lemma}
\proof
Fix $y\in\Re^m$. We first show that $Ex$ is invariant over $X(y)$. Suppose the contrary, so that there exist two optimal solutions $x$ and $x'$ from $X(y)$ with the property that $Ex\neq Ex'$. Then, we have
\[
d(y)=L(x;y)=L(x';y).
\]
Due to the convexity of $L(x;y)$ with respect to the variable $x$, the solution set $X(y)$ must be convex, implying ${\bar x}=(x+x')/2\in X(y)$. By the convexity of $f(x)$, we have
\[
\frac{1}{2}\left[(f(x)+\langle y,q-Ex\rangle)+(f(x')+\langle y,q-Ex'\rangle)\right]\ge f(\barx)+\langle y,q-E\barx\rangle.
\]
Moreover, by the strict convexity of $\|\cdot\|^2$ and the assumption $Ex\neq Ex'$, we have
\[
\frac{1}{2}\left(\|Ex-q\|^2+\|Ex'-q\|^2\right)>\|E\barx-q\|^2.
\]
Multiplying this inequality by $\rho/2$ and adding it to the previous inequality yields
\[
\frac{1}{2}\left[L(x;y)+L(x';y)\right]>L(\barx;y),
\]
which further implies
\[
d(y)>L(\barx;y).
\]
This contradicts the definition $d(y)=\min_xL(x;y)$. Thus, $Ex$ is
invariant over $X(y)$. Notice that $d(y)$ is a concave function and
its subdifferential is given by \cite{bertsekas}
$$
\partial d(y)=\mbox{Closure of the convex hull}\;\{\;q-Ex(y)\mid x(y)\in X(y)\;\}.
$$
Since $Ex(y)$ is invariant over $X(y)$, the subdifferential $\partial d(y)$ is a singleton. By Danskin's Theorem, this implies that $d(y)$ is differentiable and the gradient is given by $\nabla d(y)=q-Ex(y)$, for any $x(y)\in X(y)$.

A similar argument (and using the strict convexity of $g_k$) shows that $A_kx_k$ is also invariant over $X(y)$. The proof is complete.
\QED

By using Lemma~\ref{lm:const-derivative}, we show below
%Lemma 3.1, we show below a boundedness property of $x(y)$, a strong monotonicity property of $\nabla f(x(y))$ and
a Lipschitz continuity property of $\nabla d(y)$, for $y$ over any
level set of $d$. \pn
\begin{lemma}\label{lm:3.2}
Fix any scalar $\eta \le f^*$ and let ${\cal U} = \{\ y\in \Re^m\ |\
d(y) \ge \eta \ \}$.
%The following holds:
%\bn
%(a) The closure of $\{\ x(y)\ |\ y \in {\cal U} \ \}$ is a compact subset of $\hbox{int}(\hbox{dom }f)$.
%\bn
%(b) There exist positive scalars $\sigma_\eta$ and $L_\eta $ such that
%\begin{eqnarray}
%\langle \nabla f(x(y'))-\nabla f(x(y)),x(y')-x(y) \rangle
%&\ge& \sigma_\eta \|x(y') - x(y)\|^2
%\quad \forall y' \in {\cal U}, \ y \in {\cal U}, \label{4.11v}\\
%f(x(y')) - f(x(y)) - \langle \nabla f(x(y)),x(y')-x(y) \rangle
%&\ge& {\sigma_\eta \over 2} \|x(y') - x(y)\|^2
%\quad \forall y' \in {\cal U}, \ y \in {\cal U}, \label{4.11w}\\
%\|\nabla f(x(y')) - \nabla f(x(y))\|
%&\le& L_\eta \|x(y') - x(y)\|
%\quad \forall y' \in {\cal U},
%\ y \in {\cal U}.  \nonumber
%\end{eqnarray}
%\bn
%(c)
Then there holds %exists a positive scalar $M_\eta$ such that
\[
 \|\nabla d(y') - \nabla d(y)\|
\le \frac{1}{\rho}\|y' - y\|, \quad \forall\; y' \in {\cal U}, \ y
\in {\cal U}.
\]
%where $M_\eta=\frac{\|E\|}{\rho}$.
\end{lemma}
\proof
%(a)  Fix  $y^*$ to be any optimal solution of (\ref{2.3}). Then, $x(y^*) = x^*$ and, by (\ref{x(y)}) and the definition of $d(y)$, we have $ d(y) = f(x(y)) +  \langle q - Ex(y) , y \rangle$ for all $y$.  Thus, for any $y \in {\cal U}$,
%\[
%d(y^*) - \eta \ge
% d(y^*) - d(y) =
%f(x^*) - f(x(y)) - \langle q - E x^* , y - y^* \rangle
%- \langle  E^T y , x^* - x(y) \rangle.
%\]
%Since $x(y^*) = x^*$, we also have from (\ref{2.6}) and the fact that $y^*$ maximizes $d$ over $Y$ that
%\[
%\langle q - E x^* , y - y^* \rangle
%= \langle \nabla d(y^*) , y - y^* \rangle \le 0.
%\]
%Finally, since $x^*\in X$ we have from (\ref{2.7}) that
%\[
%\langle \nabla f(x(y)) - E^T y , x^* - x(y) \rangle \ge 0. \]
%Combining the above three relations yields, for any $y \in {\cal U}$,
%\[
%d(y^*) - \eta \ge
%f(x^*) - f(x(y)) -
%\langle \nabla f(x(y)) ,x^* - x(y) \rangle.
%\]
%Since $d(y^*)=f(x^*)$, it follows that
%\[f(x(y))+
%\langle \nabla f(x(y)) ,x^* - x(y)\ge \eta\qquad \forall y\in{\cal U}.\]
%This together with the earlier observation $x(y) \in \hbox{int}(\hbox{dom }f)$ implies (cf.\ Lemma 3.1) that $\{\ x(y)\ |\ y\in {\cal U}\ \}$ lies in a compact subset of $\hbox{int}(\hbox{dom }f)$.
%
%(b) By part (a), the closure of
%$\{\ x(y) \ |\ y \in {\cal U} \ \}$ is a compact subset of $\hbox{int}(\hbox{dom }f)$.  The convex hull of this subset is also a compact subset of $\hbox{int}(\hbox{dom }f)$. By Assumption A(b), $\nabla f$ is strongly monotone (with $\sigma_\eta$ denoting the modulus) and Lipschitz continuous (with $L_\eta$ denoting the Lipschitz constant) on this convex hull.  Thus, for any $x'$ and $x$ in this convex hull,
%\begin{eqnarray*}
%f(x') - f(x) - \langle \nabla f(x) ,
%x' - x \rangle
%&=& \int_0^1 \langle \nabla f(x +\theta (x' -x)) - \nabla f(x) , x' - x \rangle \ d \theta \\
%&\ge&  \int_0^1 \sigma_\eta \theta  \|x' - x\|^2   \ d \theta \\
%&=& {\sigma_\eta \over 2} \|x' - x\|^2.
%\end{eqnarray*}
%
%(c)
Fix any $y$ and $y'$ in ${\cal U}$. Let $x = x(y)$ and $x' = x(y')$
be two minimizers of $L(x;y)$ and $L(x;y')$ respectively. By
convexity, we have
$$z - E^Ty +\rho E^T(Ex-q)= 0\ \ \mbox{ and }\ \
z' - E^Ty'+\rho E^T(Ex'-q)= 0,$$ where $z$ and $z'$ are some
subgradient vectors in the subdifferential $\partial f(x)$ and
$\partial f(x')$ respectively. Thus, we have
\[
\langle z - E^Ty +\rho E^T(Ex-q),x'-x\rangle = 0\] { and }
\[
\langle z' - E^Ty'+\rho E^T(Ex'-q),x-x'\rangle= 0.
\]
Adding the above two equalities yields
\[
\langle z - z' + E^T(y' - y)-\rho E^TE(x'-x) , x' - x \rangle = 0.
\]
Upon rearranging terms and using the convexity property
\[
\langle  z' - z, x' - x \rangle\ge 0,
\]
we get
\[
\langle y' - y , E(x' - x) \rangle = \langle  z' - z, x' - x
\rangle+\rho \|E(x'-x)\|^2 \ge \rho\|E(x' - x)\|^2.
\]
Thus, $\rho \|E(x' - x)\| \le \|y' - y\|$ which together with
$\nabla d(y') - \nabla d(y) = E(x - x')$ (cf.\
Lemma~\ref{lm:const-derivative})  yields
\[
\|\nabla d(y') - \nabla d(y)\|=\|E(x' - x)\| \le {1 \over \rho }\|y
- y'\|.
\]
The proof is complete. \QED


To show the linear convergence of the ADMM method, we need certain
local error bounds around the optimal solution set $X(y)$ as well as
around the dual optimal solution set $Y^*$. To describe these local
error bounds, we first define the notion of a proximity operator.
%The \emph{Moreau envelope} of $f$ is defined as
%\[ %\begin{equation}
%%\label{e:prox1}
%e_h(\vx)={\min_{\vy\in\R^n}}\;\;f(\vy)+\frac12\|\vx-\vy\|^2
%\] %\end{equation}
%and is convex differentiable.
Let $h:\dom(h)\mapsto \Re$ be a (possibly nonsmooth) convex
function. For every $\vx\in\dom(h)$, the \emph{proximity operator}
of $h$ is defined as \cite{[25]}
\[ %\begin{equation}
%\label{e:prox1}
\prox_{h}(\vx)={\argmin_{u\in\Re^n}}\;\;h(u)+\frac12\|\vx-u\|^2.
\] %\end{equation}
Notice that if $h(\vx)$ is the indicator function of a closed convex set $X$, then
$$
\prox_h(\vx)=\proj_X(\vx),
$$
so the proximity operator is a generalization of the projection operator. In particular, it is known that the proximity operator satisfies the nonexpansiveness property:
\begin{equation}\label{eq:nonexpansiveness}
\|\prox_h(x)-\prox_h(x')\|\le \|x-x'\|,\quad \forall\ x,x'.
\end{equation}

The proximity operator can be used to characterize the optimality condition for a nonsmooth convex optimization problem. Suppose a convex function $f$ is decomposed as $f(x)=g(Ax)+h(x)$ where $g$ is  strongly convex and differentiable, $h$ is a convex (possibly nonsmooth) function, then we can define the \textit{proximal gradient} of $f$ with respect to $h$ as
\[
\tilde \nabla f(\vx):=\vx-\prox_{h}(\vx-\nabla (f(\vx)-h(x)))=\vx-\prox_{h}(\vx-A^T\nabla g(A\vx)).
\]
%where
%\[
%\prox_{h}(\vz):={\argmin_{u\in \Re^n}}\;\;h(u)+\frac12\|\vz-u\|^2.
%\]
If $h\equiv 0$, then the proximal gradient $\tilde \nabla f(\vx)=\nabla f(\vx)$.
In general, $\tilde\nabla f(\vx)$ can be used as the (standard) gradient of $f$ for the nonsmooth minimization  $\min_{\vx\in X}f(\vx)$.
For example, $\tilde \nabla f(\vx^*)=0$ iff $\vx^*$ is a global minimizer.

For the Lagrangian minimization problem \eqref{eq:dual} and
under Assumption A,
the work of \cite{tseng09,luo-tseng,luo-zhang} suggests that the size of the proximal gradient
\begin{eqnarray}
\tilde \nabla_xL(x;y)&:=&x-\prox_h\left(x-\nabla_x(L(x;y)-h(x))\right)\nonumber \\
&=&x-\prox_h\left(x-A^T\nabla g(Ax)+E^Ty-\rho E^T(Ex-q)\right)\label{eq:prox-grad}
\end{eqnarray}
can be used to upper bound the distance to the optimal solution set
$X(y)$ of \eqref{eq:dual}. Here $$h(x):=\sum_{k=1}^Kh_k(x_k),\quad
g(Ax):=\sum_{k=1}^Kg_k(A_kx_k)$$ represent the nonsmooth and the
smooth parts of $f(x)$ respectively.
%We make the following local error bound assumption for the Lagrangian minimization problem \eqref{eq:dual}.


In our analysis of ADMM, we will also need an error bound for the
dual function $d(y)$. Notice that a $y \in\Re^m$ solves (\ref{2.3})
if and only if $ y$ satisfies the system of nonlinear equations
\[
\nabla d(y)=0.
\]
This suggests that the norm of the `residual' $\|\nabla d(y)\|$ may
be a good estimate of  how close $y$ is from solving (\ref{2.3}).
The next lemma says if the nonsmooth part of $f_k$ takes certain
forms, then the distance to the primal and dual optimal solution
sets can indeed be bounded.

\begin{lemma}\label{lm:eb}
Suppose assumptions A(a)---A(e) hold.
\begin{enumerate}
\item If in addition $X$ is a polyhedral set, then
there exists a positive scalar $\tau$ and $\delta$ such that the following error bound holds
%For any $y$ and scalar $\eta\ge f(x(y))$, there exist positive scalars $\delta $ and $\tau$ such that, for any $x \in \Re^n$ satisfying $L(x;y) \le \eta$ and $\|\tilde\nabla_x L(x;y)\| \le \delta$, the following error bounds hold
\begin{equation}\label{eq:primaleb}
\dist(x,X(y))\le \tau \|\tilde\nabla_x L(x;y)\|,\quad
%=\tau\left\|x-\prox_h\left(x-\nabla_x (L(x;y)-h(x))\right)\right\|,
\end{equation}
for all $(x,y)$ such that $\|\tilde\nabla_x L(x;y)\|\le \delta$, where the proximal gradient $\tilde \nabla_x L(x;y)$ is given by
\eqref{eq:prox-grad}.  Furthermore, if $X$ is also a compact set, then there exists some $\tau>0$ such that
the error bound \eqref{eq:primaleb} holds for all $x\in X\cap {\rm dom}(h)$.
\item
Similarly, if assumption A-(g) also holds, then for any scalar $\zeta$, there exist
positive scalars $\delta$ and $\tau$ such that
\begin{equation}\label{eq:dualeb}
\dist(y,Y^*)=\|y-y^*\|\le \tau\|\nabla d(y)\|,~\mbox{whenever}~
d(y)\ge \zeta~\mbox{and}~\|\nabla d(y)\|\le \delta.
\end{equation}
\end{enumerate}
%and
%\[
%L(x;y)-L(x(y);y) \le \tau \left(\dist(x,X(y))\right)^2, %\|\nabla_x L(x;y)\|^2=\tau \left\|x-\prox_h\left(x-\nabla A^Tg(Ax)+E^Ty\right)\right\|^2.
%\]
Moreover, in both cases the constant $\tau$ is \emph{independent} of
the choice of $y$ and $x$.
\end{lemma}

%\begin{lemma}\label{lm:eb}
%Suppose Assumption A holds. Then
%the local error bounds in Assumption B hold if the nonsmooth component functions $h_k(x_k)$ of the objective function satisfy one of the following properties:
%\begin{itemize}
%\item [(1)] Either the epi-graph of $h_k(x_k)$ is a polyhedral set;
%\item [(2)] Or $h_k(x_k)=\lambda_k\|x_k\|_1+\sum_J\omega_J\|x_{k,J}\|_2$, where $x_k=(\cdots,x_{k,J},\cdots)$ is a  partition of $x_k$ with $J$ being the partition index.
%\end{itemize}

%For any $y\in \Re^m$, let $\partial_xL(x;y)$ denote the subdifferential of the Lagrangian function
%$L(x;y)$ with respect to the variable $x$.

%\end{lemma}

For any fixed $y$, the proof for the first part of Lemma~\ref{lm:eb}
is identical to those of \cite{tseng09,luo-tseng,luo-zhang}, each of
which shows the error bound with different assumptions on the
objective function $f$. In particular, it was shown that
\eqref{eq:primaleb} holds for all $x$ with $\|\tilde\nabla_x
L(x;y)\|\le \delta$ (i.e., sufficiently close to $X(y)$). An
important new ingredient is the claim that the error bound holds
over the compact set $X\cap{\rm dom}(h)$. This can be seen in two
steps as follows: (1) for all $x\in X\cap{\rm dom}(h)$ such that
$\|\tilde\nabla_x L(x;y)\|\le \delta$, the error bound
\eqref{eq:primaleb} is already known to hold; (2) for all $x\in
X\cap {\rm dom}(h)$ such that $\|\tilde\nabla_x L(x;y)\|\ge \delta$,
the ratio
\[
\frac{\dist(x,X(y))}{ \|\tilde\nabla_x L(x;y)\|}
\]
is a continuous function and well defined over the compact set
$X\cap {\rm dom}(h)\cap\left\{x\mid \|\tilde\nabla_x L(x;y)\|\ge
\delta\right\}.$ Thus, the above ratio must be bounded from  above
by a constant $\tau'$ (independent of $y$). Combining (1) and (2)
yields the desired error bound over the set $X\cap {\rm dom}(h)$.

Another new ingredient in Lemma~\ref{lm:eb}
is the additional claim that the constants $\delta$, $\tau$ are both
independent of the choice of $y$. This property follows directly
from a similar property of Hoffman's error bound \cite{Hoffman} (on
which the error bounds of \cite{tseng09,luo-tseng,luo-zhang} are
based) for a feasible linear system $P:=\{x\mid Ax\le b\}$:
\[
\dist(x,P) \le \tau \|[Ax-b]_+\|,\quad \forall\ x\in \Re^n,
\]
where $\tau$ is independent of $b$. In fact, a careful checking of
the proofs of \cite{tseng09,luo-tseng,luo-zhang} shows that the
corresponding error constants $\delta$ and $\tau$ for the augmented
Lagrangian function $L(x;y)$ can be indeed made \emph{independent}
of $y$. We omit the proof of the first part of Lemma~\ref{lm:eb} for
space consideration.


Dual error bounds like the one stated in the second part of the
lemma have been studied previously by Pang \cite{[22]} and by
Mangasarian and Shiau \cite{[17]}, though in different contexts. The
above error bound is `local' in that it holds only for those $y$
that are bounded or near $Y^*$ (i.e., when $\|\nabla d(y)\|\le
\delta$ as opposed to a `global' error bound which would hold for
all $y$ in $\Re^m$). However if in addition $y$ also lies in some
compact set $Y$, then the dual error bound hold true for all $y\in
Y$ (using the same argument as in the preceding paragraph). In the appendix, we include a proof showing that the dual error
bound holds true, for the case where the epigraph of $h_k$ is
polyhedral (which includes $\ell_1$ norm and indicator function for
polyhedral sets). We note that from this proof it is clear that
indeed the value of $\tau$ in the dual error bound does not depend
on the choice of either $x$ or $y$.








%\begin{corollary}\label{co:cost-to-go}
%Let $d^*$ denote the dual optimal value. Then, Assumptions A and B imply that for any scalar $\delta>0$, there exists a positive scalar $\tau'$ such that  % and $\|\nabla d(y)\| \le \delta$,
%\begin{equation}\label{eq:d-gap}
%d^*-d(y) \le \tau' \|\nabla d(y)\|^2=\tau'\|Ex(y)-q\|^2,
%\end{equation}
%for any $y \in \Re^m$ with $\|y\|\le \delta$. Moreover, if
%$h(x)=\sum_{k=1}^Kh_k(x_k)=0$ (i.e., the objective function $f(x)$
%of \eqref{eq:1} is smooth), then for any $x\in \Re^n$, $y \in \Re^m$
%with $\|x\|+\|y\|\le \delta$, there holds
%\begin{equation}\label{eq:p-gap}
%L(x;y)-L(x(y);y)\le \tau'\left({\rm dist}(x,X(y))\right)^2,%\quad\mbox{for some $\tau>0$}
%\end{equation}
%for any $x(y)\in X(y)$.
%\end{corollary}
%
%\proof By Assumption A, the strong duality holds so that
%$f(x^*)=d(y^*)$ where $y^*$ is any dual optimal solution for
%\eqref{2.3}. Fix any $y$, and let $y^*$ be the optimal dual solution
%closest to $y$. Then it follows from the mean value theorem that
%there exists some $\tilde y$ in the line segment joining $y$ and
%$y^*$ such that
%\begin{eqnarray*}
%f(x^*)-d(y)&=&d(y^*)-d(y)\\
%&=&\langle \nabla d({\tilde y}),y^*-y\rangle\\
%&=&\langle \nabla d({\tilde y})-\nabla d(y^*),y^*-y\rangle\\
%&\le &\| \nabla d({\tilde y})-\nabla d(y^*)\|\|y^*-y\|\\
%&\le & \frac{1}{\rho}\|{\tilde y}-y^*\|\|y^*-y\|\\
%&\le & \frac{1}{\rho}\|y-y^*\|\|y^*-y\|\\
%&=&\frac{1}{\rho}\|y^*-y\|^2
%\end{eqnarray*}
%where the second inequality follows from Lemma~\ref{lm:3.2}. Recall
%from Assumption B that there exists some $\tau$ such that
%\[
%\dist(y,Y^*)=\|y-y^*\|\le \tau\|\nabla d(y)\|.
%\]
%Combining the above two inequalities yields
%\[
%d^*-d(y)=f(x^*)-d(y)\le \tau'\|\nabla d(y)\|^2,
%\]
%where $\tau'\ge\tau^2/\rho$ is a constant. This establishes the
%bound on the size of dual gap \eqref{eq:d-gap}.
%
%It remains to prove the bound on the primal-gap \eqref{eq:p-gap}. To
%this end, we fix any $x$ and $y$ with $\|x\|+\|y\|\le \delta$. Let
%$\barx$ be defined as
%\[
%\barx:=\argmin_{u\in X(y)}\|u-x\|
%\]
%so that $\dist(x,X(y))=\|x-\barx\|$. Since the nonsmooth part of
%$f(x)$ is absent, that is,
%\[
%h(x)=\sum_{k=1}^Kh_k(x_k)=0,
%\]
%it follows that the augmented Lagrangian function is differentiable.
%%\[
%%m(x;y)=\sum_{k=1}^Kg_k(A_kx_k)+\langle y,q-Ex\rangle +\frac{\rho}{2}\|Ex-q\|^2.
%%\]
%%Then, we can write $L(x;y)=h(x)+m(x;y)$.
%Since $\barx$ is a minimizer of $\min_uL(u;y)$, it follows from the
%optimality condition that
%\[
%\langle \nabla_xL(\barx;y),x-\barx\rangle = 0.
%\]
%Also, we have from the Mean Value theorem
%\[
%L(x;y)-L(\barx;y)=\langle \nabla_xL({\tilde x};y),x-\barx\rangle,
%\]
%where $\tilde x$ is a point lying in between $\barx$ and $x$.
%Combining the above two expressions yields
%\begin{eqnarray*}
%L(x;y)\!\!&-&\!\!L(\barx;y) \\
%&=&\langle \nabla_xL({\tilde x};y)-\nabla_xL(\barx;y),x-\barx\rangle\\
%&\le &\|\nabla_xL({\tilde x};y)-\nabla_xL(\barx;y)\| \|x-\barx\|\\
%&=& \left\|\sum_{k=1}^KA_k^T\nabla g_k(A_k{\tilde x}_k)+\rho E^T(E{\tilde x}-q)-\left(\sum_{k=1}^KA_k^T\nabla g_k(A_k{\bar x}_k)+\rho E^T(E{\bar x}-q)\right)\right\|\|x-\barx\|\\
%&\le &\left(\sum_{k=1}^KL\|A^T_k\|\|A_k\|+\rho\|E^TE\|\right)\|{\tilde x}-\barx\|\|x-\barx\|\\
%&\le
%&\left(\sum_{k=1}^KL\|A^T_k\|\|A_k\|+\rho\|E^TE\|\right)\|x-\barx\|^2,
%\end{eqnarray*}
%where the second inequality follows from the Lipschitz continuity of
%$\nabla g_k$ and the last step is due to the fact that $\tilde x$
%lies in the line segment joining $x$ and $\barx$ so that $\|{\tilde
%x}-\barx\|\le \|x-\barx\|$. Setting $\tau'>
%\left(\sum_{k=1}^KL\|A^T_k\|\|A_k\|+\rho\|E^TE\|\right)$ proves
%\eqref{eq:p-gap}.
%%
%%\begin{itemize}
%%\item Let $\bar\vx^r\in X^*$ be s.t.\ $\color{red}\dist_{X^*}(\vx^r)=\|\vx^r-\bar\vx^r\|$. The optimality of $\vx^{r+1}$ implies
%%\[
%%{\color{red}\begin{array}{l}
%%f_0(\bar\vx^r)+\langle \nabla f_1(\vx^r),\bar\vx^r-\vx^r\rangle +
%%\frac12\|\bar\vx^r-\vx^r\|^2\\ [5pt]
%%\quad\ge f_0(\vx^{r+1})+\langle \nabla f_1(\vx^r),\vx^{r+1}-\vx^r\rangle +
%%\frac12\|\vx^{r+1}-\vx^r\|^2
%%\end{array}
%%}
%%\]\\ [-10pt]
%%implying
%%\[
%%{\color{red}
%%\langle\nabla f_1(\vx^r),\vx^{r+1}\!-\!\bar\vx^r\rangle\!+\! f_0(\vx^{r+1})\!-\!f_0(\bar\vx^r)\le
%%\frac12\dist^2_{X^*}(\vx^r).}
%%\] \\ [-10pt]
%%\item Also, the mean value theorem shows
%%$$
%%{\color{red}f_1(\vx^{r+1})-f_1(\bar\vx^r)=\langle \nabla f_1(\xi),\vx^{r+1}-\bar\vx^r\rangle}
%%$$
%%for some $\xi^r$ in the line segment joining $\vx^{r+1}$ and $\bar\vx^r$.\\ [-10pt]
%%\item Combining the above two relations yields
%%{\color{red}
%%\[
%%\begin{array}{l}
%%\!\!\!\! f_0(\vx^{r+1})\!+\!f_1(\vx^{r+1})-f_0(\bar\vx^r)\!-\!f_1(\bar\vx^r) = \langle \nabla f_1(\xi^{r}),\vx^{r+1}\!-\!\bar\vx^r\rangle\!+\! f_0(\vx^{r+1})\!-\!f_0(\bar\vx^r) \\ [5pt]
%%\le\langle\nabla f_1(\vx^r),\vx^{r+1}\!-\!\bar\vx^r\rangle\!+L\|\vx^{r+1}-\bar\vx^r\|^2+\! f_0(\vx^{r+1})\!-\!f_0(\bar\vx^r) \\ [5pt]
%%\le \frac12\dist^2_{X^*}(\vx^r)+L\|\vx^{r+1}-\bar\vx^r\|^2 =O(\|\vx^{r+1}-\vx^r\|^2+\dist^2_{X^*}(\vx^r))
%%\end{array}
%%\]
%%}
%%\end{itemize}
%\QED


%\end{itemize}
%
%In this section we develop a number of technical facts about the primal problem (\ref{2.4})--(\ref{2.5}) and its dual (\ref{2.3})--(\ref{2.2}).  These facts will be used in Sections 4 to 7 to establish our local error bound and to study the rate of convergence of a number of dual ascent methods for solving (\ref{2.4})--(\ref{2.5}).
%
%By using parts (a) and (c) of Assumption A and invoking two lemmas from [29] (or see Lemma 1 in [30]), we show below that the level sets of a certain nonlinear function associated with $f$ have a compactness property.  This result will be used to prove Lemma 3.2(a).
%\pn
%{\bf Lemma 3.1.} For any scalar $\eta \le f(x^*)$, the set
%$\{\ x\in \hbox{int}(\hbox{dom }f)
% \ |\ f(x) + \langle \nabla f(x) , x^* - x \rangle
%\ge \eta\ \}$ is nonempty and compact.
%\pn
%{\bf Proof.}
%Fix any scalar $\eta \le f(x^*)$ and let $L$ denote the
%corresponding set given above.  Since $x^*\in \hbox{int}(\hbox{dom }f)$ so $x^* \in L$, $L$ is nonempty.  Below we show that $L$ is compact.
%
%Consider any sequence $x^1, x^2, ...$ in $L$.  Then, $x^r$ is in $\hbox{int}(\hbox{dom }f)$ so $f(x^r) + f'(x^r;x^* - x^r) = f(x^r) + \langle \nabla f(x^r),x^* - x^r \rangle \ge \eta$ for all $r$.
%  Since $f$ is co--finite and continuous on its
%effective domain (cf.\ Assumption A(a), (c)), Lemma 2 in [29] (equivalently, Lemma 1(a) in [30]) yields that both $\{x^r\}$ and $\{f(x^r)\}$ are bounded.  Thus, $L$ is bounded and $f$ is bounded on $L$.
%
%We claim that $L$ is closed.  If this were not true, then there would exist a sequence $x^1, x^2, ... $ in  $L$ converging to an $x^\infty \not\in L$.  Since $f$ and $\nabla f$ are continuous on $\hbox{int}(\hbox{dom }f)$, this can happen only if $x^\infty$ is a boundary point of $\hbox{dom }f$.  On the other hand, $f$ is bounded on $L$ and lower semicontinuous, so $x^\infty \in \hbox{dom }f$.  Thus  $f'(x^\infty;x^* - x^\infty)$ is well defined and, since $f$ is essentially smooth, we have (see [25, Lemma 26.2])
%\begin{equation}\label{3.5x}
%  f'(x^\infty;x^* - x^\infty) = -\infty.
%\end{equation}
%On the other hand, $f$ is continuous on $\hbox{dom }f$ and both $\{x^r\}$ and its limit $x^\infty$ are in $\hbox{dom }f$, so Lemma 1 in [29] (equivalently, Lemma 1(b) in [30]) yields
%\[
%\limsup_{r \to \infty}  f'(x^r; x^* - x^r)
%\le f'(x^\infty ; x^* - x^\infty).
%\]
%Since $x^r \in \hbox{int}(\hbox{dom }f)$ for all $r$, the quantity inside the limit supremum
%is exactly $\langle \nabla f(x^r) , x^* - x^r \rangle$ which, because $f$ is bounded on $L$ and $x^r \in L$,
%is bounded  below as $r \to \infty$.  Thus the limit supremum is not identically $-\infty$, a contradiction with (\ref{3.5x}).
%\QED
%
%\bigskip
%
%
%It can be seen that, for each $y\in \Re^m$, the minimization in (\ref{2.2}) is attained at a unique point inside $\hbox{int}(\hbox{dom }f)$.  [The argument is analogous to that for showing (\ref{2.5}) has a unique optimal solution inside $\hbox{int}(\hbox{dom }f)$.]    Let $x(y)$ denote this minimum point, i.e.,
%\begin{equation}\label{x(y)}
%x(y) = \arg\min_{x\in X} f(x) - \langle y , Ex \rangle
%\end{equation}
%or, equivalently, $x(y)$ is in $\hbox{int}(\hbox{dom }f)\cap X$ and satisfies
%\begin{equation}\label{2.7}
%\langle \nabla f(x(y)) - E^T y , x - x(y) \rangle \ge 0 \quad \forall x \in X.
%\end{equation}
%It is easily calculated using (\ref{2.2}) and [25,  Theorem 23.5] that
%\begin{equation}\label{2.6}
%\nabla d(y)=  q - E x(y).
%\end{equation}
%Also, it can be seen that $x(y^*) = x^*$ for all $y^*\in Y^*$.
%


%\pn
%{\bf Assumption C.}
%Each submatrix $E_k$ has full column rank.

Under Assumption A(f), the augmented Lagrangian function $L(x;y)$
(cf.\ \eqref{eq:aug-lagrangian}) is strongly convex with respect to
each subvector $x_k$. As a result, each alternating minimization
iteration of ADMM \eqref{eq:admm}
\[{\color{black}
\vx^{r+1}_k = \argmin_{x_k}
L(\vx^{r+1}_1, ..., \vx^{r+1}_{k-1}, \vx_k, \vx^r_{k+1}, ..., \vx^r_K;y^r), \quad k=1,...,K.
}\]
has a unique optimal solution. Thus the sequence of iterates $\{x^r\}$ of the ADMM are well defined.
%\begin{itemize}
%\item Recall the ADMM method \eqref{eq:admm}:
%\[{\color{black}
%\vx^{r+1}_k = {\arg\min}_{x_k }
%L(\vx^{r+1}_1, ..., \vx^{r+1}_{k-1}, \vx_k, \vx^r_{k+1}, ..., \vx^r_K;y^r), \quad k=1,...,K.
%}\]
%\item Fix any index $r$.  For each $k\in\{1,...,K\}$, %we have %from (\ref{5.10}) that
%%\[{\color{black}\abovedisplayskip 2.5pt
%%\nabla_i f(\vx^{r+1}_1, ..., \vx^{r+1}_i, \vx^r_{i+1}, ..., \vx^r_n)(\vx^{r+1}_i -\vx^r_i) \le 0.
%%\belowdisplayskip -15pt}\]
%%Then,
% the strong convexity (per variable) implies
%\[{\color{black}
%L(\vx^{r+1}_1, ..., \vx^r_k, \vx^r_{k+1}, ..., \vx^r_K;y^r) - L(\vx^{r+1}_1, ..., \vx^{r+1}_k, \vx^r_{k+1}, ..., \vx^r_K;y^r)
% \ge \gamma\|\vx^r_k - \vx^{r+1}_k\|^2.
%}\]
%where $\gamma$ is independent of $r$ and $y^r$.
%\item Summing this over $k$, we obtain the {\color{black} sufficient decrease} condition
%\[{\color{black}
%L(\vx^r;y^r) - L(\vx^{r+1};y^r) \ge \gamma\|\vx^r - \vx^{r+1}\|^2.
%}\]
%\item On the other hand, due to the Lipschitz continuity of $\nabla g_k$, the cost-to-go is upper bounded by $\|x^{r+1}_k-x^r_k\|^2$
%\[{\color{black}
%L(\vx^{r+1}_1, ..., \vx^r_k, \vx^r_{k+1}, ..., \vx^r_K;y^r) - L(\vx^{r+1}_1, ..., \vx^{r+1}_k, \vx^r_{k+1}, ..., \vx^r_K;y^r)
% \le \gamma'\|\vx^r_k - \vx^{r+1}_k\|^2
%}\]
%for some $\gamma'>0$ independent of $r$ and $y^r$.
%\item This further implies
%\[{\color{black}
%\gamma'\|x^r-x^{r+1}\|^2\le L(\vx^r;y^r) - L(\vx^{r+1};y^r) \ge \gamma\|\vx^r - \vx^{r+1}\|^2.
%}\]
%\end{itemize}
%
%\begin{itemize}
%\item
The following lemma shows that the alternating minimization of the Lagrangian function gives a sufficient descent of the Lagrangian function value.
\begin{lemma}\label{lm:p-descent}
Suppose Assumptions A(b) and A(f) hold.
Then fix any index $r$, we have %.  For each $k\in\{1,...,K\}$, we have %from (\ref{5.10}) that
%\[{\color{black}\abovedisplayskip 2.5pt
%\nabla_i f(\vx^{r+1}_1, ..., \vx^{r+1}_i, \vx^r_{i+1}, ..., \vx^r_n)(\vx^{r+1}_i -\vx^r_i) \le 0.
%\belowdisplayskip -15pt}\]
%Then,
\begin{equation}\label{eq:p-descent}
%\gamma'\left(\dist(x^r,X(y^r))\right)^2\ge
L(\vx^r;y^r)- L(\vx^{r+1};y^r) \ge \gamma\|\vx^r - \vx^{r+1}\|^2,
\end{equation}
where the constant $\gamma>0$ is independent of $r$ and $y^r$.
\end{lemma}
\proof By assumptions A(b) and A(f) , the augmented Lagrangian
function
$$
L(x;y)=\sum_{k=1}^K\left(f_k(x_k)+\langle y_k,q_k-E_kx_k\rangle\right) +\frac{\rho}{2}\left\|\sum_{k=1}^KE_kx_k-q\right\|^2
$$
is strongly convex in each variable $x_k$ and has a uniform modulus
$\rho \lambda_{\min}(E_k^TE_k)>0$. Here, the notation
$\lambda_{\min}(\cdot)$ denotes the smallest eigenvalue of a
symmetric matrix. This implies that, for each $k$, that
\begin{equation}\label{eq:strongcvx}
L(x;y)-L(x_1,..,x_{k-1},{\bar x}_k,x_{k+1},...,x_K;y)\ge \rho \lambda_{\min}(E_k^TE_k)\|x_k-{\bar x}_k\|^2,
\end{equation}
for all $x$, where $\bar x_k$ is the minimizer of $\min_{x_k}L(x;y)$ (when all other variables $\{x_j\}_{j\neq k}$ are fixed).

Fix any index $r$. For each $k\in\{1,...,K\}$, by ADMM
\eqref{eq:admm}, $x^{r+1}_{k}$ is the minimizer of
$L(x^{r+1}_1,...,x^{r+1}_{k-1},x_k,x^r_{k+1},x^r_{k+2},...,x^r_K;y^r)$.
It follows from  \eqref{eq:strongcvx}
\begin{equation}\label{eq:older}
L(\vx^{r+1}_1, ..., x_{k-1}^{r+1},\vx^r_k, ..., \vx^r_K;y^r)-L(\vx^{r+1}_1, ..., \vx^{r+1}_k, \vx^r_{k+1}, ..., \vx^r_K;y^r)\ge \gamma\|\vx^r_k - \vx^{r+1}_k\|^2,\ \ \forall \; k,
\end{equation}
where
$$\gamma=\rho \min_k\lambda_{\min}(E_k^TE_k)$$
is independent of $r$ and $y^r$.
Summing this over $k$, we obtain the {\color{black} sufficient decrease} condition
\[{\color{black}
L(\vx^r;y^r) - L(\vx^{r+1};y^r) \ge \gamma\|\vx^r - \vx^{r+1}\|^2.
}\]
This completes the proof of Lemma~\ref{lm:p-descent}.
%the second inequality.

%To establish the first inequality, we recall the definition of $x^{r+1}_k$:
%\[
%x^{r+1}_k=\argmin_{x_k}\left(h_k(x_k)+g_k(A_kx_k)+\langle y^r,q-E_kx_k\rangle+\frac{\rho}{2}\left\|E_kx_k+\sum_{j<k}E_jx_j^{r+1}+\sum_{j>k}x^r_j-q\right\|^2\right).
%\]
%The corresponding optimality condition can be written as
%\[
%x_k^{r+1}=\prox_{h_k}\left[x_k^{r+1}-A_k^T\nabla_{x_k}g_k(A_kx^{r+1}_k)+E_k^Ty^r+\rho E_k^T\left(\sum_{j\le k}E_jx_j^{r+1}+\sum_{j>k}x^r_j-q\right) \right].
%\]
%Notice that
%\begin{eqnarray*}
%L(\vx^r;y^r)-L(\vx^{r+1};y^r)&=&\sum_{k=1}^K[L(\vx^{r+1}_1, ...,x_{k-1}^{r+1}, \vx^r_k, \vx^r_{k+1}, ..., \vx^r_K;y^r)-L(\vx^{r+1}_1, ...,x_{k-1}^{r+1},\vx^{r+1}_k, \vx^r_{k+1}, ..., \vx^r_K;y^r)]\\
%&=&\sum_{k=1}^K\left[\left(h_k(x^r_k)+g_k(A_kx^r_k)+\langle y^r,q-E_kx^r_k\rangle +\frac{\rho}{2}\|\sum_{j<k}E_jx_j^{r+1}+\sum_{j\ge k}E_jx^r_j-q\|^2\right)\right.\\
%&&-\left.\left(h_k(x^{r+1}_k)+g_k(A_kx^{r+1}_k)+\langle y^r,q-E_kx^{r+1}_k\rangle +\frac{\rho}{2}\|\sum_{j\le k}E_jx_j^{r+1}+\sum_{j> k}E_jx^r_j-q\|^2\right)\right]
%\end{eqnarray*}
\QED

To prove the linear convergence of the ADMM algorithm, we also need the following lemma which bounds the size of the proximal gradient $\tilde\nabla L(x^r;y^r)$ at an iterate $x^r$.
\begin{lemma}\label{lm:estimate}
Suppose assumptions A(b)---A(c) hold. Let $\{x^r\}$ be generated by
the ADMM algorithm \eqref{eq:admm}. Then there exists some constant
$\sigma>0$ $($independent of $y^r$$)$ such that
\begin{equation}\label{eq:old-estimate}
\|\tilde\nabla L(x^r;y^r)\|\le \sigma\|x^{r+1}-x^r\|
\end{equation}
for all $r\ge1$.
\end{lemma}
\proof
Fix any $r\ge1$ and any $1\le k\le K$. According to the ADMM procedure \eqref{eq:admm}, the variable $x_k$ is updated as follows
\[
x^{r+1}_k=\argmin_{x_k}\left(h_k(x_k)+g_k(A_kx_k)-\langle y^r,E_kx_k\rangle+\frac{\rho}{2}\left\|E_kx_k+\sum_{j<k}E_jx_j^{r+1}+\sum_{j>k}E_jx^r_j-q\right\|^2\right).
\]
The corresponding optimality condition can be written as
\begin{equation}\label{eq:old}
\! x_k^{r+1}=\prox_{h_k}\left[x_k^{r+1}-A_k^T\nabla_{x_k}g_k(A_kx^{r+1}_k)+E_k^Ty^r-\rho E_k^T\left(\sum_{j\le k}E_jx_j^{r+1}+\sum_{j>k}E_jx^r_j-q\right) \right].
\end{equation}
Therefore, we have
\begin{eqnarray}\label{eq:error_norm}
&&\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\left\|x_k^{r+1}-\prox_{h_k}\left(x_k^{r}-A_k^T\nabla_{x_k}g_k(A_kx^{r}_k)+E_k^Ty^r-\rho E_k^T\left(Ex^r-q\right)\right)\right\|=\nonumber\\
&&\Bigg\|\prox_{h_k}\left[x_k^{r+1}-A_k^T\nabla_{x_k}g_k(A_kx^{r+1}_k)+E_k^Ty^r+\rho E_k^T\left(\sum_{j\le k}E_jx_j^{r+1}+\sum_{j>k}E_jx^r_j-q\right) \right]\nonumber\\
&&-\prox_{h_k}\left(x_k^{r}-A_k^T\nabla_{x_k}g_k(A_kx^{r}_k)+E_k^Ty^r+\rho E_k^T\left(Ex^r-q\right)\right)\Bigg\|\nonumber\\
&\le&\Big\|(x^{r+1}_k-x_k^r)-A_k^T(\nabla_{x_k}g_k(A_kx^{r+1}_k)-\nabla_{x_k}g_k(A_kx^{r}_k))+\rho E_k^T\sum_{j\le k}E_j(x_j^{r+1}-x_j^r)\Big\|\nonumber\\
&\le &\|x^{r+1}_k-x_k^r\|+L\|A_k^T\|\|A_k\|\|x^{r+1}_k-x_k^r\|+\rho\|E_k^T\|\sum_{j\le k}\|E_j\|\|x_j^{r+1}-x_j^r\|\nonumber\\
&\le &c\|x^{r+1}-x^r\|,\quad \mbox{for some $c>0$ independent of
$y^r$},
\end{eqnarray}
where the first inequality follows from the nonexpansive property of the prox operator \eqref{eq:nonexpansiveness}, and the second inequality is due to the Lipschitz property of the gradient vector $\nabla g_k$ (cf.\ Assumption~A-(c)).
Using this relation and the definition of the proximal gradient $\tilde\nabla L(x^r;y^r)$, we have
\begin{eqnarray*}
\|\tilde\nabla_{x_k} L(x^r;y^r)\|&=& \left\|x^r_k-\prox_{h_k}\left(x_k^{r}-A_k^T\nabla_{x_k}g_k(A_kx_k^r)+E_k^Ty^r-\rho E_k^T\left(Ex^r-q\right)\right)\right\|\\
&\le &\|x^r_k-x^{r+1}_k\|+ \left\|x_k^{r+1}-\prox_{h_k}\left(x_k^{r}-A_k^T\nabla_{x_k}g_k(A_kx_k^r)+E_k^Ty^r-\rho E_k^T\left(Ex^r-q\right)\right)\right\|\\
&\le & (c+1)\|x^{r+1}-x^r\|,\quad \forall \ k=1,2,...,K.
\end{eqnarray*}
This further implies that the entire proximal gradient vector can be bounded by $\|x^{r+1}-x^r\|$:
\[
\|\tilde\nabla L(x^r;y^r)\|\le (c+1)\sqrt{K}\|x^{r+1}-x^r\|.
\]
Setting $\sigma=(c+1)\sqrt{K}$ (which is independent of $y^r$) completes the proof.
\QED

%On the other hand, due to the Lipschitz continuity of $\nabla g_k$, the cost-to-go is upper bounded by $\|x^{r+1}_k-x^r_k\|^2$
%\[{\color{black}
%L(\vx^{r+1}_1, ..., \vx^r_k, \vx^r_{k+1}, ..., \vx^r_K;y^r) - L(\vx^{r+1}_1, ..., \vx^{r+1}_k, \vx^r_{k+1}, ..., \vx^r_K;y^r)
% \le \gamma'\|\vx^r_k - \vx^{r+1}_k\|^2
%}\]
%for some $\gamma'>0$ independent of $r$ and $y^r$.
%This further implies
%\[{\color{black}
%\gamma'\|x^r-x^{r+1}\|^2\ge L(\vx^r;y^r) - L(\vx^{r+1};y^r) \ge \gamma\|\vx^r - \vx^{r+1}\|^2.
%}\]


%Lemma 3.2 will be used in the proof of Theorem 4.1 and Lemma 5.1(a).


%\newsection{ Local Error Bound for the Dual}
%
%\indent
%
%Suppose the objective function $f(x)$ can be partitioned as the sum
%\[
%f(x)=h(Ax)+g(x)
%\]
%where $h: \Re^m\mapsto (-\infty,\infty]$ is a smooth convex function and $g$ is a nonsmooth convex function. In addition, we make the following assumption.
%\pn
%{\bf Assumption A.}
%\begin{enumerate}
%\item [(a)] $h$ is strongly convex differentiable on $\mbox{dom}(h)$, which is assumed to be convex and open.
%\item [(b)] The epi-graph of $g(x)$ is a polyhedral set, or $g(x)$ is given by $$g(x)=\lambda_1\|x\|_1+\lambda_2\sum_{k=1}^K\|x_k\|_2$$
%    where $\lambda_i\ge 0$.
%\end{enumerate}
%Under Assumption A, it has been shown \cite{tseng09,luo-zhang}

%It is well known that an $y \in\Re^m$ solves (\ref{2.3}) if and only if $ y$ satisfies the system of nonlinear equations
%\[
%y =  [ y +  \nabla d(y) ]^+_Y.
%\]
%This suggests that the norm of the `residual'
%$y - [ y + \nabla d(y) ]^+_Y$ may be a good estimate of  how close $y$ is from solving (\ref{2.3}). In this section we show that this is true in the sense that, for all $y \in Y$ such that the above residual is small and $d(y)$ is bounded below, the distance from $y$ to $Y^*$, defined by
%\[
%\phi(y)=\min_{y^*\in Y^*}\|y - y^*\|,
%\]
%is bounded above by the norm of this residual (see Theorem 4.1).  Bounds like this (called `error bounds') have been studied previously by Pang [22] and by Mangasarian and Shiau [17], though in different contexts.  The above error bound is `local' in that it holds only for those $y\in Y$ near $Y^*$ (as opposed to a `global' error bound which would hold for all $y$ in $Y$).  This local error bound in a sense complements that given in [16] (see Theorem 2.1 therein) which requires $X = \Re^n$ but does not require $f$ to be co--finite.
%
%To prove the above result, we first need an algebraic description of $x(\cdot)$ and the projection operator $[\cdot]^+_Y$.
%Let the polyhedral set $X$ be expressed as
%\begin{equation}\label{4.1}
%X = \{\ x\in\Re^n \ |\ Ax \ge a \ \},
%\end{equation}
%for some $h \times n$ matrix $A$ and some vector
%$a$ in $\Re^h$.  Similarly, let
%the polyhedral set $Y$ be expressed as
%\begin{equation}\label{4.2}
%Y = \{\ y\in\Re^m \ |\ By \ge b \ \}.
%\end{equation}
%for some $k\times m$ matrix $B$ and some vector
%$b$ in $\Re^k$.
%We define a set-valued function (or \underbar{multifunction}) ${\cal M}$ which assigns to each vector $(d,e)\in \Re^n\times\Re^m$ the set ${\cal M}(d,e)$ defined to be the set of vectors $(x,y,\lambda,\mu)\in \Re^n\times\Re^m\times \Re^h\times\Re^k$ satisfying the following system of equations and inequalities whose right-hand side is parameterized by $(d,e)$:
%\begin{eqnarray*}
% A^T\lambda + E^T y &=& d,   \\
%-B^T\mu + E x  &=& e + q,
%\end{eqnarray*}
%\[
%\lambda \ge 0, \qquad
%Ax \ge a, \qquad
%\langle A x - a , \lambda \rangle = 0,
%\]
%\[
%\mu \ge 0,\qquad
%By \ge b + Be, \qquad
%\langle B y - b - B e,  \mu \rangle = 0.
%\]
%It is easily verified using (\ref{4.1})--(\ref{4.2}) that $(x,y,\lambda,\mu)\in {\cal M}(d,e)$ for some $(\lambda,\mu)$ if and only if
%$\langle d - E^Ty, x' - x \rangle \ge 0$ for all $x'\in X$ and $e = y - [ y + q - Ex ]^+_Y$. Hence, by (\ref{2.7}) and (\ref{2.6}),
%\begin{equation}\label{4.21}
% (x,y,\lambda,\mu)\in {\cal M}(\nabla f(x),e)
%\hbox{ for some $(\lambda,\mu)$\ \ if and only if\ \ $x = x(y),\ e = y - [ y + \nabla d(y) ]^+_Y$.}
%\end{equation}
%Taking $e = 0$ in (\ref{4.21}) and using the fact $x(y) = x^*$ for all $y\in Y^*$, we see that $(x,y,\lambda,\mu)\in {\cal M}(\nabla f(x),0)$ for some $(\lambda,\mu)$ if and only if $x = x^*$, $y \in Y^*$.
%
%It is easily seen that ${\cal M}$ is a polyhedral multifunction; i.e., the graph of ${\cal M}$ is the union of a finitely many polyhedral convex sets.  Then, a result of Robinson [24, Proposition 1] states that ${\cal M}$ has a certain Lipschitzian behaviour around any point in $\Re^n\times\Re^m$.  (This result generalizes a classical result of Hoffman [Hof52] (also see [23], [17]) on the Lipschitzian behaviour of the solution set to a linear system as a multifunction of the right-hand side.)
%
%\pn {\bf Lemma 4.1}. There exists a positive scalar $\theta$ (depending on $A$, $B$, $E$ only) such that ${\cal M}$ is \underbar{locally upper Lipschitzian} with modulus $\theta$ at each $(\bar d,\bar e)\in \Re^n\times\Re^m$; that is, for each $(\bar d,\bar e)$ there is a positive scalar $\delta'$ satisfying
%\begin{equation}\label{4.20}
%{\cal M}(d,e) \subseteq {\cal M}(\bar d,\bar e) + \theta( \|(d,e)-(\bar d,\bar e)\|) {\cal B}\quad
%\hbox{whenever}\quad\|(d,e)-(\bar d,\bar e)\| \le \delta',
%\end{equation}
% where ${\cal B}$ denotes the unit Euclidean ball in $\Re^n \times\Re^m\times\Re^h\times\Re^k$. (When ${\cal M}(\bar d,\bar e) =\emptyset$, the inclusion interprets to mean ${\cal M}(d,e) =\emptyset$ whenever $\|(d,e)-(\bar d,\bar e)\| \le \delta'$.)

%\bigskip
%
%By using Lemmas 3.3 and 4.1, we now prove the main result of this section.  The idea of the proof is as follows: First, we use the compactness property of $x(\cdot)$ (cf.\ Lemma 3.2(a)) to show that $x(y) \approx x^*$ whenever $e = y - [y + \nabla d(y)]^+_Y \approx 0$.  Then, by invoking the locally upper Lipschitzian property of ${\cal M}$ (cf.\ Lemma 4.1), we demonstrate the existence of an $(x^*,y^*,\lambda^*,\mu^*)\in {\cal M}(\nabla f(x^*),0)$ whose distance to $(x,y,\lambda,\mu)\in {\cal M}(\nabla f(x),e)$ is bounded above by $\|\nabla f(x(y)) - \nabla f(x^*)\| + \|e\|$.  Using the strong convexity of $f$ (cf.\ Lemma 3.2(b)) and the Lipschitz continuity of $\nabla f$ (cf.\ Lemma 3.2(c)), we show that  $\|x(y) - x^*\|$ can be eliminated from the right-hand side of the above bound.
%
%\pn
%{\bf Theorem 4.1.}
% For any scalar $\eta\le f(x^*)$, there exist positive scalars $\delta $ and $\tau$ such that, for any $y \in Y$ with $d(y) \ge \eta$ and $\|y - [y + \nabla d(y)]^+_Y\| \le \delta$, there holds
%\[
%\|x(y)-x^*\|+\phi(y) \le \tau  \|y - [y + \nabla d(y)]^+_Y\|.
%\]
%{\bf Proof.}
%By Lemma 4.1, ${\cal M}$ is locally upper Lipschitzian with modulus $\theta$ at $(\nabla f(x^*),0)$ so there exists a positive scalar $\delta'$ such that (\ref{4.20}) holds with $(\bar d,\bar e) =(\nabla f(x^*),0)$.
%Fix any $\eta \le f(x^*)$.
%
% First we claim that there exists a positive scalar $\delta \le \delta'/2$ such that for all $y \in Y$ with $d(y) \ge \eta$ and
%$\| y - [ y + \nabla d(y) ]^+_Y \|\le \delta$, we have
%\[
%\|\nabla f(x(y))- \nabla f(x^*)\| \le \delta'/2.
%\]
%To see this, consider any sequence of vectors $y^1, y^2, ...$ in  $Y$ such that $d(y^r) \ge \eta$ and $e^r = y^r - [ y^r + \nabla d(y^r) ]^+_Y \rightarrow 0$.  For convenience, let $x^r = x(y^r)$ and $d^r = \nabla f(x^r)$ for all $r$.
%By Lemma 3.2(a),  $\{x^r\}$ lies in some compact subset of $\hbox{int}(\hbox{dom }f)$.  By passing into a subsequence if necessary, we can assume that $\{x^r\}$ converges to some $x^\infty \in \hbox{int}(\hbox{dom }f)$. Since $\nabla f$ is continuous on $\hbox{int}(\hbox{dom }f)$, it follows that $(d^r,e^r)\to (\nabla f(x^\infty),0)$.  Since for each $r$ there exists some $(\lambda^r,\mu^r)\in \Re^h\times \Re^k$ such that
%$(x^r,y^r,\lambda^r,\mu^r)\in {\cal M}(d^r,e^r)$ (cf.\ (\ref{4.21})) and, by Lemma 4.1,
%${\cal M}$ is locally upper Lipschitzian at $(\nabla f(x^\infty),0)$, this implies that there
%exists some $(\bar x^r,\bar y^r,\bar \lambda^r,\bar \mu^r)$ in ${\cal M}(\nabla f(x^\infty),0)$
%such that $\|x^r-\bar x^r\|\to 0$.  Since
%${\cal M}(\nabla f(x^\infty),0)$ consists of finitely many polyhedral sets and $\bar x^r\to x^\infty$
%(cf.\ $\|x^r-\bar x^r\|\to 0$ and $x^r\to x^\infty$),
%this further implies that ${\cal M}(\nabla f(x^\infty),0)$ contains an element of the form
%$(x^\infty, y^\infty, \lambda^\infty, \mu^\infty)$
%for some $( y^\infty, \lambda^\infty, \mu^\infty)\in\Re^m\times\Re^h\times\Re^k$. By the remark following (\ref{4.21}), $x^\infty = x^*$ and $y^\infty\in Y^*$.  Since the choice of the sequence $y^1, y^2, ...$ was arbitrary, this shows that the desired $\delta$ exists.
%
%Consider any $y \in Y$ satisfying $d(y) \ge \eta$ and
%$\| e \|\le \delta$, where for convenience we let $e = y - [y + \nabla d(y)]^+_Y$.
% Then the preceding claim together with $\delta \le \delta'/2$ implies $\|\nabla f(x(y))- \nabla f(x^*)\| + \|e\| \le \delta'/2 + \delta'/2 = \delta'$.  Since, by (\ref{4.21}), $(x(y),y)$ together with some $(\lambda,\mu) \in \Re^h\times \Re^k$ satisfies $(x(y),y,\lambda,\mu)\in {\cal M}(\nabla f(x(y)),e)$, the fact that (\ref{4.20}) holds with $(\bar d,\bar e) =(\nabla f(x^*),0)$ implies there exists an $(x^*,y^*,\lambda^*,\mu^*) \in {\cal M}(\nabla f(x^*),0)$ satisfying
%\begin{eqnarray}
%\|(x(y),y,\lambda,\mu) - (x^*,y^*,\lambda^*,\mu^*)\|
%&\le& \theta \Bigl(
%\|\nabla f(x(y)) - \nabla f(x^*)\| + \|e\| \Bigr)  \nonumber\\
%&\le& \theta \left( L_\eta \|x(y) - x^*\|+ \|e\| \right),
%\label{4.14c}
%\end{eqnarray}
%where the second inequality follows from the Lipschitz continuity property of $\nabla f$ (cf.\ Lemma 3.2(b)).
%By the remark following (\ref{4.21}), $y^*\in Y^*$.
%
%Since $(x(y),y,\lambda,\mu)\in {\cal M}(\nabla f(x(y)),e)$, the definition of ${\cal M}$ yields
%\begin{eqnarray}
%\nabla f(x(y)) &=&  A^T\lambda + E^T y ,  \label{4.14e} \\
%B^T\mu &=& E x(y)-q-e,  \label{4.14g}
%\end{eqnarray}
%\begin{equation}\label{4.14f}
%\lambda \ge 0, \qquad Ax(y) \ge a, \qquad
%\langle A x(y) - a , \lambda \rangle = 0,
%\end{equation}
%\begin{equation}\label{4.14h}
% \mu \ge 0,  \qquad By \ge b + Be, \qquad
%\langle B y - b - B e,  \mu \rangle = 0.
%\end{equation}
%Similarly, since $(x^*,y^*,\lambda^*,\mu^*) \in {\cal M}(\nabla f(x^*),0)$, we have
%\begin{eqnarray}
%\nabla f(x^*) &=& A^T\lambda^* + E^T y^*, \label{4.15e}\\
%B^T\mu^* &=& E x^* -q ,  \label{4.15g}
%\end{eqnarray}
%\begin{equation}\label{4.15f}
%\lambda^* \ge 0, \qquad
%Ax^* \ge a, \qquad
%\langle A x^* - a , \lambda^* \rangle = 0,
%\end{equation}
%\begin{equation}\label{4.15h}
% \mu^* \ge 0, \qquad By^* \ge b, \qquad
%\langle B y^* - b ,  \mu^* \rangle = 0.
%\end{equation}
%
%The strong monotonicity property of $\nabla f$ (cf.\ (\ref{4.11v})) together with (\ref{4.14e}) and (\ref{4.15e}) yields
%\begin{eqnarray*}
%\sigma_\eta \|x(y) - x^*\|^2
%&\le& \langle \nabla f(x(y)) - \nabla f(x^*) , x(y) - x^* \rangle \\
%&=&  \langle \lambda - \lambda^* , Ax(y) - Ax^* \rangle
%+ \langle y - y^* , Ex(y) - Ex^* \rangle .
%\end{eqnarray*}
%We bound the right-hand side below. Using (\ref{4.14f}) and (\ref{4.15f}), we  have
%\begin{eqnarray*}
%\langle \lambda - \lambda^* , Ax(y) - Ax^* \rangle
%&=& \langle \lambda - \lambda^* , Ax(y) - a \rangle
%- \langle \lambda - \lambda^* ,  Ax^* - a \rangle  \\
%&=& - \langle \lambda^* , Ax(y) - a \rangle
%- \langle \lambda ,  Ax^* - a \rangle \qquad \le\ \ 0.
%\end{eqnarray*}
%Also, (\ref{4.14g}) and (\ref{4.15g}) together yield
%\[
% \langle y - y^* , Ex(y) - Ex^* \rangle
%= \langle y - y^* , e \rangle
%+ \langle B y - By^* , \mu - \mu^* \rangle.
%\]
%Using (\ref{4.14h}) and (\ref{4.15h}), the rightmost term can be bounded above as follows:
%\begin{eqnarray*}
% \langle B y - By^* , \mu - \mu^* \rangle
%&=& \langle B y - b - Be  , \mu - \mu^* \rangle
%- \langle By^* - b , \mu - \mu^* \rangle
%+ \langle Be , \mu - \mu^* \rangle  \\
%&=& -\langle B y - b - Be , \mu^* \rangle
%- \langle By^* - b , \mu \rangle
%+ \langle Be , \mu - \mu^* \rangle \\
%&\le& \langle Be , \mu - \mu^* \rangle.
%\end{eqnarray*}
%Summing the preceding four inequalities yields
%\begin{equation}\label{4.add}
%\sigma_\eta \|x(y) - x^*\|^2
%\le
% \langle y - y^* , e \rangle  + \langle B e , \mu - \mu^* \rangle
%\le (1 + \|B\|)\|e\| \|(y,\mu) - (y^*,\mu^*)\|.
%\end{equation}
%
%Squaring both sides of (\ref{4.14c}) and then
%using (\ref{4.add}) to bound the right--hand side gives:
%\begin{eqnarray*}
%\|(x(y),y,\lambda,\mu) - (x^*,y^*,\lambda^*,\mu^*)\|^2
% &\le&
%\theta^2 \left(L_\eta\|x(y) - x^*\| + \|e\| \right)^2 \\
% &\le& 2 \theta^2 \left( L_\eta^2
%\|x(y) - x^*\|^2  + \|e\|^2
%\right) \\
% &\le& 2 \theta^2 \left( L_\eta^2
%{ 1 + \|B\|  \over \sigma_\eta } \|e\| \|(y,\mu) - (y^*,\mu^*)\|  + \|e\|^2
%\right) \\
%&\le& 2 \theta^2 \left( L_\eta^2
%{ 1 + \|B\|  \over \sigma_\eta } \|e\| \|(x(y),y,\lambda,\mu) - (x^*,y^*,\lambda^*,\mu^*)\|  + \|e\|^2
%\right).
%\end{eqnarray*}
%This is a quadratic inequality in $\|(x(y),y,\lambda,\mu) - (x^*,y^*,\lambda^*,\mu^*)\|/\|e\|$, so
%\[
% \|(x(y),y,\lambda,\mu) - (x^*,y^*,\lambda^*,\mu^*)\|/\|e\| \le \rho,
%\]
%for some scalar $\rho$ depending on $\theta$, $\|B\|$, $L_\eta$ and $\sigma_\eta$ only.  Since $y^*\in Y^*$ so clearly $\phi(y) \le \|y-y^*\|$, the above relation yields $\phi(y) \le \rho \|e\|$. The same relation also yields $\|x(y)-x^*\|\le \rho \|e\|$.
%Summing these two inequalities
%completes the proof.
%\QED
%
%Notice that the above argument shows that the distance from the multipliers $(\lambda,\mu)$ associated with $y$ to the set of optimal multipliers is also locally bounded above by $\|y - [y + \nabla d(y)]^+_Y\|$.
%It can also be shown that $\phi(y)$ is bounded {\it below} by this quantity.  However, this lower bound is not needed by the subsequent analysis and so,  for simplicity, is omitted.   Finally, we caution that the results embodied by Theorem 4.1 depend strongly on the special structure of $d$ (cf.\ (\ref{2.2}) and Assumption A) and do not hold if $d$ is any concave differentiable function.
%
%In the special case $Y =\Re^m$, we have, as a consequence of Theorem 4.1, the very useful result that the duality gap $f(x^*) - d(y)$ is bounded above by the residual at $y$ {\it squared}, provided that the latter is small and $d(y)$ is bounded.  This result will be used in Section 5 to analyze the rate of convergence of certain dual ascent methods.
%\pn
%{\bf Corollary 4.1.}  Suppose $Y = \Re^m$.
% For any scalar $\eta\le f(x^*)$, there exist positive scalars $\delta $ and $\tau'$ such that, for any $y \in \Re^m$ with $d(y) \ge \eta$ and $\|\nabla d(y)\| \le \delta$,
%\[
%f(x^*) - d(y) \le \tau' \|\nabla d(y)\|^2.
%\]
%{\bf Proof.}
%Fix any $\eta\le f(x^*)$ and let $\delta$ and $\tau$ be the corresponding scalars given in Theorem 4.1.  By Theorem 4.1, for any $y \in \Re^m$ with $d(y) \ge \eta$ and $\|\nabla d(y)\| \le \delta$, there is an $y^* \in Y^*$ with
%\[
%\|y - y^*\| \le \tau \|\nabla d(y)\|.
%\]
%By the Mean Value Theorem, there exists some
%$\psi$ lying on the line segment joining $y$ with $y^*$
%such that $d(y^*) - d(y) = \langle \nabla d(\psi) ,
%y^* - y \rangle$, which together with $\nabla d(y^*) = 0$ (cf.\ $y^* \in Y^*$ and $Y = \Re^m$) and the above relation yields
%\begin{eqnarray*}
%d(y^*) - d(y)
%&=& \langle \nabla d(\psi) - \nabla d(y^*) ,
%y^* - y \rangle \\
%&\le&
%\|\nabla d(\psi) - \nabla d(y^*) \| \| y^* - y \|  \\
%&\le & M_\eta \|\psi - y^*\| \| y^* -  y \|  \\
%&\le & M_\eta \| y^* -  y \|^2  \\
%&\le& M_\eta \tau^2  \|\nabla d(y)\|^2,
%\end{eqnarray*}
%where the second inequality follows from Lemma 3.2(c) and the third inequality is due to
%the fact $\psi$ lies on the line segment joining $y$ with $y^*$.  Now use the strong duality relation $d(y^*) = f(x^*)$.
%\QED



\newsection{Linear Convergence of ADMM}\label{secMain}

Let $d^*$ denote the dual optimal value and $\{x^r,y^r\}$ be the
sequence generated by the ADMM method \eqref{eq:admm}. Due to
assumption A(a), $d^*$ also equals to the primal optimal value.
Further we denote
\begin{equation}\label{eq:dd-gap}
\Delta_d^r=d^*-d(y^r)
\end{equation}
which represents the gap from dual optimality at the $r$-th iteration. The primal gap to optimality at iteration $r$ is defined as
\begin{equation}\label{eq:pp-gap}
\Delta_p^r=L(x^{r+1};y^{r})-d(y^r),\quad r\ge 1.
\end{equation}
Clearly, we have both $\Delta_d^r\ge0$ and $\Delta_p^r\ge0$ for all
$r$. To establish the linear convergence of ADMM, we need several
lemmas to estimate the sizes of the primal and dual optimality gaps
as well as their respective decrease.


Let $X(y^r)$ denote the set of optimal solutions for the following
optimization problem
\[
\min_x L(x;y^r)=\min_xf(x)+\langle y^r, q - Ex \rangle
+\frac{\rho}{2}\|Ex-q\|^2.
\]
We denote
\[
\barx^r=\argmin_{\barx\in X(y^r)}\|\barx-x^r\|.
\]


We first bound the sizes of the dual and primal optimality
gaps.


\begin{lemma}\label{lm:cost-to-go}
Suppose assumptions A(a)---A(e) and A(g) hold. Then for any scalar $\delta>0$, there exists a positive scalar $\tau'$ such that  % and $\|\nabla d(y)\| \le \delta$,
\begin{equation}\label{eq:d-gap}
\Delta_d^r\le \tau' \|\nabla d(y^r)\|^2=\tau'\|Ex(y^r)-q\|^2,
\end{equation}
for any $y^r \in \Re^m$ with $\|\nabla d(y^r)\|\le \delta$.
Moreover, there exist positive scalars $\zeta$ and $\zeta^{'}$
$($independent of $y^r)$ such that
\begin{equation}\label{eq:p-gap}
\Delta_p^r\le \zeta\|x^{r+1}-x^r\|^2+\zeta^{'}\|x^r-\bar{x}^r\|^2,\quad\mbox{for all $r\ge1$.}
\end{equation}
\end{lemma}

\proof %By Assumption A, the strong duality holds so that
%$f(x^*)=d(y^*)$ where $y^*$ is any dual optimal solution for
%\eqref{2.3}.
Fix any $y^r$, and let $y^*$ be the optimal dual solution closest to
$y^r$. Then it follows from the mean value theorem that there exists
some $\tilde y$ in the line segment joining $y^r$ and $y^*$ such
that
\begin{eqnarray*}
\Delta_d^r&=&d(y^*)-d(y^r)\\
&=&\langle \nabla d({\tilde y}),y^*-y^r\rangle\\
&=&\langle \nabla d({\tilde y})-\nabla d(y^*),y^*-y^r\rangle\\
&\le &\| \nabla d({\tilde y})-\nabla d(y^*)\|\|y^*-y^r\|\\
&\le & \frac{1}{\rho}\|{\tilde y}-y^*\|\|y^*-y^r\|\\
&\le & \frac{1}{\rho}\|y^r-y^*\|\|y^*-y^r\|\\
&=&\frac{1}{\rho}\|y^*-y^r\|^2
\end{eqnarray*}
where the second inequality follows from Lemma~\ref{lm:3.2}. Recall
from the second part in Lemma \ref{lm:eb} that there exists some
$\tau$ such that
\[
\dist(y^r,Y^*)=\|y^r-y^*\|\le \tau\|\nabla d(y^r)\|.
\]
Combining the above two inequalities yields
\[
\Delta^r_d=d(y^*)-d(y^r)\le \tau'\|\nabla d(y^r)\|^2,
\]
where $\tau'=\tau^2/\rho$ is a constant. This establishes the
bound on the size of dual gap \eqref{eq:d-gap}.

It remains to prove the bound on the primal gap \eqref{eq:p-gap}.
For notational simplicity, let us separate the smooth and nonsmooth
part of the augmented Lagrangian as follows
\begin{equation}\label{eq:Lbar}
L(x;y)=g(x)+h(x)+\langle y,
q-Ex\rangle+\frac{\rho}{2}\|q-Ex\|^2\nonumber:=\bar{L}(x;y)+h(x).
\end{equation}



Let  $x^{r+1}_{k}$ denote the $k$-th subvector of the primal vector
$x^{r+1}$. From the way that the variables are updated \eqref{eq:old}, we have
\begin{align}
x^{r+1}_k&={\rm
prox}_{h_k}\left[x^{r+1}_k-\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j\le
k}\}, \{x^r_{j}\}_{j>k}; y^r\right)\right]\nonumber\\
&={\rm
prox}_{h_k}\left[x^r_k-\nabla_{x_k}\bar{L}(x^r;y^r)-x^r_k+x^{r+1}_k-\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j\le
k}\}, \{x^r_{j}\}_{j>k};
y^r\right)+\nabla_{x_k}\bar{L}(x^r;y^r)\right]\nonumber\\
&:= {\rm
prox}_{h_k}\left[x^r_k-\nabla_{x_k}\bar{L}(x^r;y^r)-e^r_k\right]\label{eqAGP}
\end{align}
where the gradient vector $\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j\le
k}\}, \{x^r_{j}\}_{j>k}; y^r\right)$ can be explicitly expressed as
\[
\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j\le k}\}, \{x^r_{j}\}_{j>k};
y^r\right)=A^T_k\nabla_{x_k}g(A_k x^{r+1}_k)-E^T_k y^r+\rho
E^T_k\left(\sum_{j\le k}E_j x^{r+1}_j+\sum_{j>k}E_jx^r_j-q\right)\]
and the error vector $e^r_k$ is defined by
\begin{align}
e^r_k:=x^r_k-x^{r+1}_k+\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j\le
k}\}, \{x^r_{j}\}_{j>k}; y^r\right)-\nabla_{x_k}\bar{L}(x^r;y^r).
\label{eqDefe}
\end{align}

%
%Then we have
%\begin{align}
%&\|\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j\le k}\}, \{x^r_{j}\}_{j>k};
%y^r\right)-\nabla_{x_k}\bar{L}\left(x^r;y^r\right)\|\nonumber\\
%&= \left\|A^T_k\left(\nabla_{x_k}g(A_k x^{r+1}_k)-\nabla_{x_k}g(A_k
%x^{r}_k)\right)+\rho E^T_k\left(\sum_{j\le k}E_j
%(x^{r+1}_j-x^r_k)\right)\right\|\nonumber\\
%&\le c_3\|x^{r+1}-x^r\|, \ {\rm for~some~c_3>0}
%\end{align}

Note that we can bound the norm of $e^r_k$ as follows
\begin{align}\label{eq:error_norm_AGP}
\|e^r_k\|&\le
\|x^r_k-x^{r+1}_k\|+\|\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j\le k}\},
\{x^r_{j}\}_{j>k};
y^r\right)-\nabla_{x_k}\bar{L}(x^r;y^r)\|\nonumber\\
&\le \|x^r_k-x^{r+1}_k\|+\left\|A^T_k\left(\nabla_{x_k}g(A_k
x^{r+1}_k)-\nabla_{x_k}g(A_k x^{r}_k)\right)+\rho
E^T_k\left(\sum_{j\le k}E_j
(x^{r+1}_j-x^r_k)\right)\right\|\nonumber\\
&\le c\|x^r-x^{r+1}\|,
\end{align}
where the constant $c>0$ is independent of $y^r$, and can take the
same value as in \eqref{eq:error_norm}.


Using \eqref{eqAGP}, and by the definition of the proximity
operator, we have the following
\begin{align}
&h_k(x^{r+1}_k)+\langle x^{r+1}_k-x^r_k,
\nabla_{x_k}\bar{L}(x^r;y^r)+e^r_k\rangle+\frac{1}{2}\|x^{r+1}_k-x^r_k\|^2\nonumber\\
&\le h_k(\bar{x}^r_k)+\langle \bar{x}^r_k-x^r_k,
\nabla_{x_k}\bar{L}(x^r;
y^r)+e^r_k\rangle+\frac{1}{2}\|\bar{x}_k^r-x^r_k\|^2.
\end{align}
Summing over all $k=1,\cdots, K$, we obtain
\begin{align*}
&h(x^{r+1})+\langle x^{r+1}-x^r,
\nabla_{x}\bar{L}(x^r;y^r)+e^r\rangle+\frac{1}{2}\|x^{r+1}-x^r\|^2\nonumber\\
&\le h(\bar{x}^r)+\langle \bar{x}^r-x^r, \nabla_{x}\bar{L}(x^r;
y^r)+e^r\rangle+\frac{1}{2}\|\bar{x}^r-x^r\|^2.
\end{align*}
Upon rearranging terms, we obtain
\begin{align}
&h(x^{r+1})-h(\bar{x}^r)+\langle x^{r+1}-\bar{x}^r,
\nabla_{x}\bar{L}(x^r;y^r)\rangle\le
\frac{1}{2}\|\bar{x}^r-x^r\|^2-\langle x^{r+1}-\bar{x}^r,
e^r\rangle\label{eqBoundDifference}.
% &\le
%\frac{1}{2}\|\bar{x}^r-x^r\|^2+\| x^{r+1}-\bar{x}^r\|
%\|e^r\|\label{eqBoundDifference}.
\end{align}

Also, we have from the mean value theorem that there exists some
$\tilde{x}$ in the line segment joining $x^{r+1}$ and $\bar{x}^r$
such that
\[\bar{L}(x^{r+1};
y^r)-\bar{L}(\bar{x}^r; y^r)=\langle \nabla_x \bar{L}(\tilde{x};
y^r), x^{r+1}-\bar{x}^r\rangle. \]

Using the above results, we can bound $\Delta^r_p$ by
\begin{align}
\Delta^r_p&=L(x^{r+1}; y^r)-L(\bar{x}^r; y^r)\nonumber\\
&=\bar{L}(x^{r+1}; y^r)-\bar{L}(\bar{x}^r;
y^r)+h(x^{r+1})-h(\bar{x}^r)\nonumber\\
&=\langle \nabla_x \bar{L}(\tilde{x}; y^r),
x^{r+1}-\bar{x}^r\rangle+h(x^{r+1})-h(\bar{x}^r)\nonumber\\
&=\langle \nabla_x \bar{L}(\tilde{x}; y^r)-\nabla_x \bar{L}({x}^r;
y^r), x^{r+1}-\bar{x}\rangle+\langle \nabla_x \bar{L}({x}^r; y^r),
x^{r+1}-\bar{x}\rangle+h(x^{r+1})-h(\bar{x}^r)\nonumber\\
&\le\langle \nabla_x \bar{L}(\tilde{x}; y^r)-\nabla_x \bar{L}({x}^r;
y^r), x^{r+1}-\bar{x}\rangle+\frac{1}{2}\|\bar{x}^r-x^r\|^2+c\sqrt{K}\|x^{r+1}-x^r\|\|x^{r+1}-\bar{x}^r\| \quad \quad  \nonumber\\
&\le
\left(\sum_{k=1}^{K}L\|A_k\|^T\|A_k\|+\rho\|E^T E\|\right)\|\tilde{x}-x^r\|\|x^{r+1}-\bar{x}^r\|\nonumber\\
&\quad\quad\quad+\frac{1}{2}\|\bar{x}^r-x^r\|^2+c\sqrt{K}\|x^{r+1}-x^r\|\|x^{r+1}-\bar{x}^r\|\nonumber\\
&\le \left(\sum_{k=1}^{K}L\|A_k\|^T\|A_k\|+\rho\|E^T
E\|\right)\left(\|x^{r+1}-x^r\|+\|\bar{x}^{r}-x^r\|\right)^2\nonumber\\
&\quad\quad\quad+
\frac{1}{2}\|\bar{x}^r-x^r\|^2+c\sqrt{K}\|x^{r+1}-x^r\|\left(\|x^{r+1}-x^r\|
+\|\bar{x}^{r}-x^r\|\right)\nonumber\\
&\le \zeta\|x^{r+1}-x^r\|^2+\zeta^{'}\|\bar{x}^r-x^r\|^2,\quad \mbox{for some }\zeta,\ \zeta'>0, \nonumber
\end{align}
where the first inequality follows from \eqref{eqBoundDifference}
and \eqref{eq:error_norm_AGP}, the second inequality is due to the Cauchy-Schwartz inequality and
the Lipschitz continuity of $\nabla \bar L_x(x;y^r)$, while the third inequality follows from the
fact that $\tilde{x}$ lies in the line segment joining $x^{r+1}$ and
$\bar{x}^r$ so that $\|\tilde{x}-x^r\|\le
\|x^{r+1}-x^r\|+\|\bar{x}^r-x^r\|$. This completes the proof. \QED








We then bound the decrease of the dual optimality gap.
\begin{lemma}\label{lm:dual-gap}
For each $r\ge 1$, there holds
\begin{equation}
\Delta_d^r-\Delta_d^{r-1}\le -\alpha(Ex^{r}-q)^T(E\barx^{r}-q). \label{eq:dual-gap}
\end{equation}
\end{lemma}
\proof
%We again  Let $X(y^r)$ denote the set of optimal solutions for
%the following optimization problem
%\[
%\min_x L(x;y^r)=\min_xf(x)+\langle y^r, q - Ex \rangle +\frac{\rho}{2}\|Ex-q\|^2.
%\]
%We denote
%\[
%\barx^r=\argmin_{\barx\in X(y^r)}\|\barx-x^r\|.
%\]
The reduction of the optimality gap in the dual space can be bounded as follows:
\begin{eqnarray*}
\Delta_d^r-\Delta_d^{r-1}&=&[d^*-d(y^{r})]-[d^*-d(y^{r-1})]\nonumber\\
&=& d(y^{r-1})-d(y^{r})\nonumber\\
&=&L(\barx^{r-1};y^{r-1})-L(\barx^{r};y^{r})\nonumber\\
&=&[L(\barx^{r};y^{r-1})-L(\barx^{r};y^{r})] + [L(\barx^{r-1};y^{r-1})-L(\barx^{r};y^{r-1})]\nonumber \\
&=&(y^{r-1}-y^{r})^T(q-E\barx^{r})+[L(\barx^{r-1};y^{r-1})-L(\barx^{r};y^{r-1})]\nonumber\\
&= &-\alpha(Ex^{r}-q)^T(E\barx^{r}-q)+[L(\barx^{r-1};y^{r-1})-L(\barx^{r};y^{r-1})]\nonumber\\
&\le &-\alpha(Ex^{r}-q)^T(E\barx^{r}-q), \quad \forall\; r\ge 1,%\label{eq:dual-gap}
\end{eqnarray*}
where the last equality follows from the update of the dual variable
$y^{r-1}$, and the fact that $\bar{x}^{r-1}$ minimizes $L(\cdot,
y^{r-1})$. \QED

Lemma~\ref{lm:dual-gap} implies that if $q-Ex^r$ is close to the true dual gradient $\nabla d(y^r)=q-E\barx^r$, then the dual optimal gap is reduced after each ADMM iteration. However, since ADMM updates the primal variable by only one Gauss-Seidel sweep, the primal iterate $x^r$ is not necessarily close the minimizer $\barx^r$ of $L(x;y^r)$. Thus, unlike the method of multipliers (for which $x^r=\barx^r$ for all $r$), there is no guarantee that the dual optimality gap $\Delta_d^r$ is indeed reduced after each iteration of ADMM.

Next we proceed to bound the decrease in the primal gap $\Delta_p^r$.
\begin{lemma}\label{lm:primal-descent}
Suppose assumptions A(b) and A(f) hold. Then for each $r\ge1$, we
have
\begin{equation}
\Delta_p^{r}-\Delta_p^{r-1}\le \alpha\|Ex^r-q\|^2-\gamma\|x^{r+1}-x^r\|^2-\alpha(Ex^{r}-q)^T(E\barx^{r}-q)\label{eq:primal-gap}
\end{equation}
for some $\gamma$ independent of $y^r$.
\end{lemma}
\proof
Fix any $r\ge1$, we have
\[
L(x^r;y^{r-1})=f(x^r)+\langle y^{r-1}, q-Ex^r\rangle+\frac{\rho}{2}\|Ex^r-q\|^2\\
\]
and
\[
L(x^{r+1};y^r)=f(x^{r+1})+\langle y^r,q-Ex^{r+1}\rangle+\frac{\rho}{2}\|Ex^{r+1}-q\|^2.
\]
By the update rule of $y^r$ (cf.\ \eqref{eq:admm}), we have
\[
L(x^{r};y^r)=f(x^{r})+\langle y^{r-1}, q-Ex^{r}\rangle +\frac{\rho}{2}\|Ex^{r}-q\|^2+\alpha\|Ex^r-q\|^2.
\]
This implies
\[
L(x^r;y^r)=L(x^r;y^{r-1})+\alpha\|Ex^r-q\|^2.
\]
Recall from Lemma~\ref{lm:p-descent} that the alternating minimization of the Lagrangian function gives a sufficient descent. In particular, we have
\[
L(x^{r+1};y^r)-L(x^r;y^r)\le -\gamma\|x^{r+1}-x^r\|^2,
\]
for some $\gamma>0$ that is independent of $r$ and $y^r$. Therefore, we have
\[
L(x^{r+1};y^r)-L(x^r;y^{r-1})\le \alpha\|Ex^r-q\|^2-\gamma\|x^{r+1}-x^r\|^2, \quad \forall\; r\ge1.
\]
Hence, we have the following bound on the reduction of primal optimality gap
\begin{eqnarray*}
\Delta_p^{r}-\Delta_p^{r-1}&=&[L(x^{r+1};y^r)-d(y^r)]-[L(x^r;y^{r-1})-d(y^{r-1})]\nonumber\\
&=& [L(x^{r+1};y^r)-L(x^r;y^{r-1})]-[d(y^r)-d(y^{r-1})]\nonumber\\
&\le & \alpha\|Ex^r-q\|^2-\gamma\|x^{r+1}-x^r\|^2-\alpha(Ex^{r}-q)^T(E\barx^{r}-q), \quad \forall \; r\ge1,
\end{eqnarray*}
where the last step is due to Lemma~\ref{lm:dual-gap}. \QED

Notice that when $\alpha=0$ (i.e., no dual update in the ADMM algorithm), Lemma~\ref{lm:primal-descent} reduces to the sufficient decrease estimate \eqref{eq:p-descent} in Lemma~\ref{lm:p-descent}. When $\alpha>0$, the primal optimality gap is not necessarily reduced after each ADMM iteration due to the positive term $\alpha\|Ex^r-q\|^2$ in \eqref{eq:primal-gap}.
Thus, in general, we cannot guarantee a consistent decrease of either the dual optimality gap $\Delta_d^r$ or the primal optimality gap $\Delta_p^r$. However, somewhat surprisingly, the sum of the primal and dual optimality gaps decreases for all $r$, as long as the dual step size $\alpha$ is sufficiently small. This is used to establish the linear convergence of ADMM method.
\begin{theorem}\label{thm:main}
Suppose the conditions in Assumption A hold. %and that the level set of
%$\Delta_d+\Delta_p$ is bounded, i.e.,
%\begin{equation}\label{eq:bd}
%\delta:=\sup\left\{\;\|x\|+\|y\|\mid [L(x;y)-d(y)]+[d^*-d(y)]\le \Delta_p^0+\Delta^0_d\;\right\}<\infty.
%\end{equation}
Then %we have the following:
%\begin{itemize}
%\item [(a)] Every limit point of the sequence of iterates $\{x^r,y^r\}$ generated by the ADMM algorithm \eqref{eq:admm} is a primal-dual optimal solution pair for \eqref{eq:1}, provided the stepsize $\alpha$ is sufficiently small.
%\item [(b)]
the sequence of iterates $\{(x^r, y^r)\}$  generated by the ADMM
algorithm \eqref{eq:admm} converges linearly to an optimal
primal-dual solution for \eqref{eq:1}, provided the stepsize
$\alpha$ is sufficiently small. Moreover, the sequence of
feasibility violation $\{\|Ex^r-q\|\}$ also converges linearly.
%\end{itemize}
\end{theorem}
\proof %We first prove part (a).
We show by induction that the sum of optimality gaps $\Delta^r_d+\Delta^r_p$ is reduced after each ADMM iteration, as long as the stepsize $\alpha$ is chosen sufficiently small. For any $r\ge1$, we denote
\begin{equation}\label{eq:useful}
\barx^r=\argmin_{\barx\in X(y^r)}\|\barx-x^r\|.
\end{equation}
By induction, suppose $\Delta^{r-1}_d+\Delta^{r-1}_p\le
\Delta^0_d+\Delta^0_p$ for some $r\ge 1$.  Recall that each $X_k$ is compact
and that the indicator function $i_{X_k}(x_k)$ is included in $h_k(x_k)$ (see the discussion after Assumption A), it follows that
$x^r\in X$, implying the boundedness of $x^r$. Thus, we obtain from Lemma
\ref{lm:eb} that
\begin{equation}\label{eq:bds}
\|x^r-\barx^r\|\le \tau \|\tilde \nabla L(x^r;y^r)\|
\end{equation}
for some $\tau>0$ (independent of $y^r$).
To prove Theorem~\ref{thm:main},
we combine the two estimates \eqref{eq:dual-gap} and \eqref{eq:primal-gap} to obtain
\begin{eqnarray}
[\Delta_p^{r}+\Delta_d^{r}]-[\Delta_p^{r-1}+\Delta_d^{r-1}]&=&
[\Delta_p^{r}-\Delta_p^{r-1}]+[\Delta_d^{r}-\Delta_d^{r-1}]\nonumber\\
&\le & \alpha\|Ex^r-q\|^2-\gamma\|x^{r+1}-x^r\|^2-2\alpha(Ex^{r}-q)^T(E\barx^{r}-q)\nonumber\\
&=&\alpha\|Ex^r-E\barx^r\|^2-\alpha\|E\barx^r-q\|^2-\gamma\|x^{r+1}-x^r\|^2.\label{eq:estimate}
\end{eqnarray}
Now we invoke \eqref{eq:bds} and Lemma~\ref{lm:estimate} to lower bound $\|x^{r+1}-x^r\|$:
\begin{equation}\label{eq:nice}
\|x^r-\barx^r\|\le\tau\|\tilde \nabla L(x^r;y^r)\|\le\tau \sigma \|x^{r+1}-x^r\|.
\end{equation}
Substituting this bound into \eqref{eq:estimate} yields
\begin{equation}\label{eq:descent}
[\Delta_p^{r}+\Delta_d^{r}]-[\Delta_p^{r-1}+\Delta_d^{r-1}] \le
(\alpha\|E\|^2\tau^{2}\sigma^{2}-\gamma)\|x^{r+1}-x^r\|^2-\alpha\|E\barx^r-q\|^2.
\end{equation}
Thus, if we choose the stepsize $\alpha$ sufficiently small so that
\begin{equation}\label{eq:alpha}
0<\alpha<\gamma\tau^{-2}\sigma^{-2}\|E\|^{-2},
\end{equation}
then the above estimate shows that
\begin{equation}\label{eq:induction}
[\Delta_p^{r}+\Delta_d^{r}]\le [\Delta_p^{r-1}+\Delta_d^{r-1}],
\end{equation}
which completes the induction. Moreover, the induction argument shows that if the stepsize $\alpha$ satisfies the condition \eqref{eq:alpha}, then the descent condition \eqref{eq:descent} holds for all $r\ge1$.

%Now we argue that the sequence $\{x^r,y^r\}$ converge to a  primal-dual optimal solution pair for the
%original optimization problem \eqref{eq:1}.
By the descent estimate \eqref{eq:descent}, we have
\begin{equation}\label{eq:limit}
\|x^{r+1}-x^r\|\to 0,\quad \|\nabla d(y^r)\|=\|E\barx^r-q\|\to 0.
\end{equation}
%By the assumption of the compactness of $\{x^r\}$,  the sequence
%$\{x^r\}$ is bounded. Let $(\barx)$ be any limit point of the
%sequence $\{x^r\}$ so that
%$$\lim_{r\in {\cal R}, r\to\infty}x^r=\barx$$
%for some subsequence ${\cal R}$.
%By \eqref{eq:d-gap}, we obtain
%\[
%d^*-d(y^r)\le \tau'\|E\barx^r-q\|^2,\quad r\in {\cal R}.
%\]
%By taking limit along this subsequence ${\cal R}$, we have
%\[
%0\le \lim_{r\in {\cal R}, r\to\infty} (d^*-d(y^r))\le \tau'\lim_{r\in {\cal R}, r\to\infty} \|E\barx^r-q\|^2=0.
%\]
%This further implies that
%$$
%\lim_{r\in {\cal R}, r\to\infty} (d^*-d(y^r))=d^*-d(\bary)=0.
%$$
%Thus, each limit point of the sequence $\{y^r\}$ is a dual optimal solution.

%By taking limit in \eqref{eq:nice} and using \eqref{eq:limit}, we
%obtain
%\[
%\lim_{r\in{\cal R},r\to\infty}\|x^r-\barx^r\|=0.
%\]
%Thus, $\|\barx-\barx^r\|\le \|x^r-\barx\|+\|x^r-\barx^r\|\to 0$ as $r\to\infty$ and $r\in {\cal R}$. Since $\barx^r\in X(y^r)$, it follows that the limit point of $\{\barx^r\}_{r\in{\cal R}}$ must be an element of $X(\bary)$. Thus, $\barx\in X(\bary)$, implying that $\barx$ is a primal optimal solution for \eqref{eq:1}. % This completes the proof of part (a).

%Now we establish part (b).
We now show that the sum of optimality gaps $\Delta^r_d+\Delta^r_p$
in fact contracts geometrically after a finite number of ADMM
iterations. By \eqref{eq:limit}, for any $\delta>0$, there must
exist a finite integer $\bar{r}>0$ such that for all $r\ge
\bar{r}$, $\|\nabla d(y^r)\|\le\delta$. Since $\Delta_d^r$, $\Delta^r_p$ are nonnegative and bounded from
above (see \eqref{eq:induction}), it follows that $d(y^r)$ is bounded from below by a constant $\zeta$ independent of $r$.
Applying the second part of Lemma~\ref{lm:eb}, we have that for all $r\ge \bar{r}$, the dual error
bound ${\rm dist}(y^r, Y^*)\le \tau \|\nabla d(y^r)\|$ holds true.



%To this end, we first notice that %the
%%inequalities \eqref{eq:nice} and \eqref{eq:descent} imply
%%\begin{equation}\label{eq:descent1}
%%[\Delta_p^{r}+\Delta_d^{r}]-[\Delta_p^{r-1}+\Delta_d^{r-1}] \le
%%(\alpha\|E\|^2-\gamma\tau^{-2}\sigma^{-2})\|x^r-\barx^r\|^2-\alpha\|E\barx^r-q\|^2.
%%\end{equation}
%the condition
%\[
%[L(x^{r+1};y^r)-d(y^r)]+[d^*-d(y^r)]= \Delta^r_d+\Delta^r_p\le \Delta^0_d+\Delta^0_p
%\]
%implies $\|x^{r+1}\|+\|y^{r}\|\le \delta$ for all $r\ge0$.  This
%further implies $\|x^r\|\le \delta$ and $\|y^r\|\le \delta$ for all
%$r\ge1$.
Therefore, it follows from
%and Assumption B
Lemma~\ref{lm:cost-to-go} that we have the following cost-to-go
estimate
\begin{equation}\label{eq:11}
\Delta_d^r=d^*-d(y^r)%\le \frac{1}{\delta'}[\mbox{dist}(y^r,Y^*)]^2
\le  {\tau'}\|\nabla d(y^r)\|^2=  {\tau'}\|E\barx^r-q\|^2,%\quad\mbox{for some $\tau'>0$}
\end{equation}
%and
%\begin{equation}\label{eq:22}
%%\Delta^r_p=
%L(x^r;y^r)-L(\barx^r;y^r)\le \tau'\|x^{r}-\barx^r\|^2,%\quad\mbox{for some $\tau>0$}
%\end{equation}
for some $\tau'>0$ and for all $r\ge\bar{r}$.
%Using these two estimates in \eqref{eq:descent1}, we can bound the decrease of $\Delta^r_p+\Delta^r_d$ as follows:
%\begin{equation}\label{eq:fun}
%[\Delta_p^{r}+\Delta_d^{r}]-[\Delta_p^{r-1}+\Delta_d^{r-1}]\le (\alpha\|E\|^2-\tau^{-2}\sigma^{-2}\gamma)\|\barx^{r}-x^r\|^2-\alpha\|E\barx^r-q\|^2.
%\end{equation}
%where the
%second inequality is due to the error bound property (Lemma~\ref{lm:eb})
%\[
%\mbox{dist}(x^r_k,X_k^r)=\|\barx^r_k-x_k^r\|\le \tau\|x^r_k-\prox_{h_k}(x^r_k-\nabla_{x_k} L(x^r;y^r))\|\le \tau\|x_k^{r+1}-x_k^r\|,
%\]
%for some $\tau>0$ (independent of $r$ and $y^r$),
%%(Notice that $c$ is independent of the linear term or $y^r$.)
%while the

Moreover, we can use Lemma~\ref{lm:cost-to-go} to bound
$\|x^{r+1}-x^{r}\|^2$ from below by $\Delta^r_p$. In particular, we
have from \eqref{eq:nice} and Lemma~\ref{lm:cost-to-go}  that
\begin{align*}
\Delta^r_p&\le \zeta\|x^{r+1}-x^r\|^2+\zeta^{'}\|\bar{x}^r-x^r\|^2\\
&\le\zeta\|x^{r+1}-x^r\|^2+\zeta^{'}\tau^2\sigma^2\|{x}^{r+1}-x^r\|^2\\
&=\left(\zeta+\zeta^{'}\tau^2\sigma^2\right)\|{x}^{r+1}-x^r\|^2.
\end{align*}
%\begin{eqnarray*}
%\|x^r-\barx^r\|^2&\ge& \frac{1}{\tau'}\left( L(x^r;y^r)-L(\barx^r;y^r)\right)\\
%&=&\frac{1}{\tau'}\left(\Delta^r_p+L(x^r;y^r)-L(x^{r+1};y^r)\right)\\
%&\ge&\frac{1}{\tau'}\left(\Delta^r_p+\gamma\|x^r-x^{r+1}\|^2\right)\\
%&\ge &\frac{1}{\tau'}\Delta^r_p,%+\gamma\left(\frac{1}{\tau\sigma}\right)^2\|x^r-\barx^r\|^2\right),
%\end{eqnarray*}
%where the second step follows from the definition of $\Delta^r_p$ (cf.\ \eqref{eq:pp-gap}), while the third step is due to Lemma~\ref{lm:p-descent}. Rearranging the terms yields
%\[
%\|x^r-\barx^r\|^2\ge (\tau')^{-1} \Delta_p^r,\quad\forall\; r.
%\]
%where
%\[
%\mu:=\frac{1}{\tau'\left(1-\frac{1}{\tau'}\frac{\gamma}{\tau^2\sigma^2}\right)}.
%\]
Substituting this bound and \eqref{eq:11} into \eqref{eq:descent},
and assuming that $\alpha>0$ satisfies \eqref{eq:alpha}, we obtain
\begin{eqnarray*}
[\Delta_p^{r}+\Delta_d^{r}]-[\Delta_p^{r-1}+\Delta_d^{r-1}]&\le &
(\alpha\|E\|^2\tau^2\sigma^2-\gamma)\|x^{r+1}-x^r\|^2-\alpha\|E\barx^r-q\|^2\\
%\alpha\|E\|^2\|x^r-\barx^r\|^2-\alpha(\tau')^{-1}(d^*-d(y^r))-\beta\|x^{r+1}-x^r\|^2\\
%\!\!\!\!\!\!&\le & -(\tau^{-2}\gamma-\alpha\|E\|^2)\|x^{r}-\barx^r\|^2-\alpha(\tau')^{-1}(d^*-d(y^r))\\
&\le & -\frac{(\gamma-\alpha\|E\|^2\tau^2\sigma^2)}{\zeta+\zeta^{'}\tau^2\sigma^2}\Delta_p^r-\alpha(\tau')^{-1}\Delta_d^r\\
&\le & -{
\min\left\{\frac{(\gamma-\alpha\|E\|^2\tau^2\sigma^2)}{\zeta+\zeta^{'}\tau^2\sigma^2},\alpha(\tau')^{-1}\right\}}[\Delta_p^r
+\Delta_d^r].
\end{eqnarray*}
%where the second step follows from \eqref{eq:11} and \eqref{eq:22}.
Since $\alpha>0$ is chosen small enough such that \eqref{eq:alpha}
holds, we have
\[
\lambda:=\min\left\{\frac{\gamma-\alpha\|E\|^2\tau^2\sigma^2}{\zeta+\zeta^{'}\tau^2\sigma^2},\alpha(\tau')^{-1}\right\}>0.
\]
Consequently, we have
\[
[\Delta_p^{r}+\Delta_d^{r}]-[\Delta_p^{r-1}+\Delta_d^{r-1}]\le -\lambda[\Delta_p^{r}+\Delta_d^{r}]
\]
which further implies
\[
0\le [\Delta_p^{r}+\Delta_d^{r}]\le \frac{1}{1+\lambda}[\Delta_p^{r-1}+\Delta_d^{r-1}].
\]
This shows that the sequence $\{\Delta_p^{r}+\Delta_d^{r}\}_{r\ge
\bar{r}}$ converges to zero Q-linearly\footnote{A sequence
$\{x^r\}$ is said to converge $Q$-linearly to some  $\bar{x}$ if
$\|x^{r+1}-\bar{x}\|/\|x^{r}-\bar{x}\|\le \mu$ for all $r$, where
$\mu\in(0,1)$ is some constant. A sequence $\{x^r\}$ is said to converge to $\bar{x}$
$R$-linearly if $\|x^r-\bar{x}\|\le c\mu^r$ for all $r$ and for some $c>0$. }.
As a result, we conclude that
$\{\Delta_p^{r}+\Delta_d^{r}\}$ and hence both $\Delta_p^r$ and
$\Delta^r_d$ globally converge to zero R-linearly\footnote{To see
that such R-linear convergence is in fact global, note that
$\bar{r}>0$ is finite, and $\Delta_p^{r}+\Delta_d^{r}$ is Q-linearly
convergent for $r\ge \bar{r}$. Then one can always find an appropriate constant $c$
such that
$\Delta_p^{r}+\Delta_d^{r}\le c(1+\lambda)^{-r}$ for all $r=1, 2,\ldots.$}.

We next show that the dual sequence $\{y^r\}$ %as well as the dual objective values $\{d(y^r)\}$ are 
is also R-linearly convergent. To this end,
notice that the inequalities \eqref{eq:nice} and \eqref{eq:descent}
imply
\begin{equation}\label{eq:descent1}
[\Delta_p^{r}+\Delta_d^{r}]-[\Delta_p^{r-1}+\Delta_d^{r-1}] \le
(\alpha\|E\|^2-\gamma\tau^{-2}\sigma^{-2})\|x^r-\barx^r\|^2-\alpha\|E\barx^r-q\|^2.
\end{equation}
Then by \eqref{eq:descent1}, we see that both $\|x^r-\barx^r\|\to 0$
and $\|E\barx^r-q\|\to 0$ R-linearly. This implies that $Ex^r-q\to
0$ R-linearly and $\nabla d(y^r)\to 0$ R-linearly. Using the fact
that ${\rm dist}(y^r,Y^*)\le \tau\|\nabla d(y^r)\|$, we conclude
that $y^r$ converges R-linearly to an optimal dual solution.

We now argue that the primal iterates $\{x^r\}$ converge to an optimal solution of \eqref{eq:1}.
By the inequality
\eqref{eq:descent}, we can further conclude that
\[
\|x^{r+1}-x^r\|^2\to0,\quad \|E\barx^r-q\|\to 0
\]
R-linearly. Notice that the R-linear convergence of
$\|x^{r+1}-x^r\|^2\to0$ implies that $\|x^{r+1}-x^r\|\to0$
R-linearly. This further shows that $x^r\to x^\infty$ R-linearly for
some $x^\infty$. Denote the limit of dual sequence $\{y^r\}$ by
$y^\infty$. By the preceding argument, we know $y^\infty$ is a dual
optimal solution of \eqref{eq:1}. To show that $x^\infty$ is a
primal optimal solution of \eqref{eq:1}, it suffices to prove that
$x^\infty\in X(y^\infty)$. Using \eqref{eq:nice}, and the fact that
$\|x^r-\bar{x}^r\|\to 0$, we have
$$\|{x}^{\infty}-\bar{x}^r\|\le\|x^r-{x}^{\infty}\|+\|x^r-\bar{x}^r\|\to 0 .$$
Since $\bar{x}^r\in X(y^r)$, we have $L(\bar{x}^r,y^r)\le L(x, y^r)$
for all $x\in X$. Passing limit, we obtain
$L({x}^{\infty},{y}^{\infty})\le L(x, {y}^{\infty})$ for all $x\in
X$, that is, ${x}^{\infty}\in X({y}^{\infty})$. It then follows that
the sequence $\{x^r\}$ converges R-linearly to a primal optimal
solution.
%
%
%
%By Lemma~\ref{lm:p-descent}, we have
%\[
%\Delta_p^r\ge L(\vx^r;y^r)- L(\vx^{r+1};y^r) \ge \gamma\|\vx^r - \vx^{r+1}\|^2
%\]
%which further implies that the sequence $\{\|x^{r+1}-x^r\|^2\}$ converges to zero Q-linearly.
%
%
 %which
%further implies that
%$d(y^r)-d^*\to 0$ R-linearly. %By the
%ADMM dual update formula \eqref{eq:admm}, the linear convergence of
%$\|Ex^r-q\|\to 0$ implies that $\|y^{r+1}-y^r\|\to 0$ R-linearly.
%
%Since $\Delta^r_d=d^*-d(y^r)\to 0$, it follows that $\{y^r\}$ converges R-linearly to a dual optimal solution $y^*$. %Finally, by \eqref{eq:useful}, we have $\dist(x^r,X(y^r))=\|x^r-\barx^r\|\to0$. Since $y^r\to y^*$, it follows that $\dist(x^r,X(y^*))\to0$.
%Furthermore, by part (a), the limit of the iterate sequence $\{x^r,y^r\}$ must exist and it is primal-dual optimal solution pair for \eqref{eq:1}. %  $\{x^r\}$ converges Q-linearly to a primal optimal solution.
%
%Finally, since
%\begin{eqnarray*}
%f(x^{r+1})-d^*&=&[f(x^{r+1})-d(y^r)]+[d(y^r)-d^*]\\
%&=&[L(x^{r+1};y^r)-d(y^r)]-[d^*-d(y^r)]-\langle y^r,q-Ex^{r+1}\rangle -\frac{\rho}{2}\|Ex^{r+1}-q\|^2\\
%&=&\Delta_p^r-\Delta_d^r-\langle y^r,q-Ex^{r+1}\rangle -\frac{\rho}{2}\|Ex^{r+1}-q\|^2
%\end{eqnarray*}
%and
%\[
%\Delta_p^r\to 0,\quad \Delta_d^r\to 0,\quad \|q-Ex^r\|\to0
%\]
%linearly, it follows that $f(x^{r+1})-d^*\to 0$ R-linearly (recall that $y^r$ is bounded by $\delta$). The proof is complete.
\QED

The following corollary relaxes the compactness assumption of the feasible set $X$ (Assumption A-(g) in Theorem~\ref{thm:main}),
and replaces it by the boundedness of the primal-dual iterates.

\begin{corollary}\label{co:1}
Suppose assumptions A(a)---A(f) hold, and that $X$ is a polyhedral
set. Further assume that either one of the following two assumptions
holds true
\begin{enumerate}
\item The sequence of dual iterates $\{y^r\}$ lies in a compact set,
and that the set $\{x \mid L(x,y)\le \zeta\}$ is compact for any
finite $y$ and $\zeta$.
\item The sequence of primal-dual iterates $\{(x^r, y^r)\}$ lies in a
compact set.
\end{enumerate}
Then if $\alpha$ is chosen sufficiently small $($cf.
\eqref{eq:alpha}$)$, all the conclusions stated in Theorem
\ref{thm:main} still hold true. Moreover, the sequence of function
values $\{f(x^r)\}$ also converges linearly.
\end{corollary}

\proof Suppose the first assumption is true, so that all the
dual iterates $\{y^r\}$ lie in a compact set $\tilde{Y}$. Let us define
$$\delta:=\sup\left \{\|x\|\mid [L(x,y)-d(y)]+[d^*-d(y)]\le \Delta^0_p+\Delta^0_p, \forall~y\in\tilde{Y}\right\}.$$

Clearly we have $[d^*-d(y)]\ge 0$ and $[L(x,y)-d(y)]\ge 0$ for all
$y\in\tilde{Y}$. Moreover $\delta<\infty$ due to the compactness of
$\tilde{Y}$ as well as the compactness of the set $\{x \mid
L(x,y)\le \zeta\}$ for any finite $y$.

Again we show by induction that the sum of optimality gaps
$\Delta^r_d+\Delta^r_p$ is reduced after each ADMM iteration, as
long as the stepsize $\alpha$ is chosen sufficiently small. For any
$r\ge 1$, by induction we suppose $\Delta^{r-1}_d+\Delta^{r-1}_p\le
\Delta^0_d+\Delta^0_p$. Then $\|x^r\|\le \delta<\infty$, and by the
first part of Lemma \ref{lm:eb}, the primal error bound holds. Then
we can carry out exactly the same analysis as the proof of Theorem
\ref{thm:main} to arrive at the same conclusion.

Additionally, since
\begin{eqnarray*}
f(x^{r+1})-d^*&=&[f(x^{r+1})-d(y^r)]+[d(y^r)-d^*]\\
&=&[L(x^{r+1};y^r)-d(y^r)]-[d^*-d(y^r)]-\langle y^r,q-Ex^{r+1}\rangle -\frac{\rho}{2}\|Ex^{r+1}-q\|^2\\
&=&\Delta_p^r-\Delta_d^r-\langle y^r,q-Ex^{r+1}\rangle -\frac{\rho}{2}\|Ex^{r+1}-q\|^2
\end{eqnarray*}
and
\[
\Delta_p^r\to 0,\quad \Delta_d^r\to 0,\quad \|q-Ex^r\|\to0,
\]
linearly, it follows that $f(x^{r+1})-d^*\to 0$ R-linearly (recall
that $y^r$ is now in a compact set). The proof is complete.

Similarly, when the second assumption is true, then  the error bound condition
in Lemma \ref{lm:eb} again holds, and by using the same argument
above we arrive at the desired conclusion.
\QED

As a remark, we point out that the proof of Corollary~\ref{co:1} also shows that the same linear convergence of
$f(x^r)\to d^*$ also holds under the assumptions in Theorem~\ref{thm:main}.
%the assumption on the compactness of the %dual
%iterates is true for example when the subgradient $\partial
%f_K(x_K)$ is bounded, $E_K$ is full row rank, and $X_K=\R^n$ (note
%that the bounded of $\partial f_K(x_K)$ is satisfied for example
%when $f_K(\cdot)$ is $\ell_1$ or $\ell_2$ norm). In this case, we
%can verify that
%\begin{align}
%E^T_K(y^r+\beta(q-Ex^{r+1}))\in\partial f(x^{r+1}_K)
%\end{align}
%which means that $y^r+\beta(q-Ex^{r+1})$ is always bounded for all
%$r$. From the fact that both $\beta$ and $\alpha$ are positive and
%finite, we must have that $y^{r+1}=y^r+\alpha(q-Ex^{r+1})$ is
%bounded for all $r$ as well. Interestingly,


%An immediate corollary of Theorem~\ref{thm:main} and
%Lemma~\ref{lm:eb} is that the ADMM algorithm is globally linearly
%convergent if the objective function $f$ satisfies any of the two
%conditions of Lemma~\ref{lm:eb}.

We close this section by providing a few examples that satisfy the
assumptions in Theorem \ref{thm:main} and Corollary
\ref{co:1}. First consider the following $\ell_1$ minimization
problem
\begin{align}
\min_{x} \|x\|_1, \quad {\rm s.t.} \ Ex=b, \ a\le x_k\le b, \
k=1,\cdots, K
\end{align}
which can be equivalently written as a $K$-block problem
\begin{align}
\min_{\{x_k\}} \sum_{k=1}^{K} |x_k|, \quad {\rm s.t.} \
\sum_{k=1}^{K}e_k x_k=b, \ a\le x_k\le b, \ k=1,\cdots, K,
\end{align}
where $e_k$ is the $k$-th column of $E$, $a$ and $b$ are some
scalars. It is easy to verify that this problem meets all the
conditions listed in Assumption A, hence the linear convergence result in
Theorem~\ref{thm:main} applies. The same is true for the following mixed
$\ell_1/\ell_2$ minimization problem
\begin{align}
\min_{\{x_k\}} \sum_{k=1}^{K}\|x_k\|, \quad {\rm s.t.}\
\sum_{k=1}^{K}E_k x_k=b,\ a\le x_k\le b, \ k=1,\cdots, K,
\end{align}
where $x_k$, $a$ and $b$  are now $n$-dimensional vectors, and
$E_k\in\R^{m\times n}$ is some matrix with full column rank.

Furthermore, the boundedness assumption in Corollary \ref{co:1} is satisfied
by many examples of the two-block ADMM described in
\cite{boyd}. This is because when $K=2$,
$\alpha/\beta\in(0,\frac{1}{2}(1+\sqrt{5}))$ and $E_k$'s are full
column rank, it is known that both the primal and dual iterates
generated by the two-block ADMM algorithm indeed lie in a bounded
set \cite{Glow84}. Therefore the second assumption made in the
Corollary \ref{co:1} holds true, hence we only require assumptions
A(a)--A(f), which are in fact quite mild. For example, they are met
by the following instance of the consensus problem (see
\cite[Section 7]{boyd} for introduction of the consensus problem)
\begin{align}\label{consensus}
\min_{\{x_k\},z}\sum_{k=1,\cdots, K}\|Ax_k-b\|^2+w\|x_k\|_1\quad{\rm
s.t.} \ x_k-z=0, \ k=1,\cdots, K,
\end{align}
where $w>0$ is some constant. Thus, the two block ADMM algorithm converges
linearly for \eqref{consensus} regardless of the rank of $A$. Note that when $A$ is full column
rank, the objective is strongly convex. Consequently the error bound
condition in Lemma \ref{lm:eb} holds true globally, and the
coefficient $\tau$ can be at least greater than $\lambda_{\rm
min}(A^T A)$.


%It is easily seen that all assumptions A(a)---A(f) are satisfied.


%
%Theorem \ref{thm:main} and Corollary \ref{co:1} imply the linear
%convergence of the ADMM for several contemporary applications
%including LASSO, Group LASSO and Sparse Group LASSO without any
%strong convexity assumption.
%

%\begin{corollary}\label{co:2}
%Suppose Assumptions A(a)---A(f) hold. Further assume that the
%sequence of primal-dual iterates $\{x^r, y^r\}$ lies in a compact
%set. Then all the conclusions stated in Corollary \ref{co:1} still
%hold true.
%\end{corollary}

\newsection{Variants of ADMM}\label{secVariants}

The convergence analysis of Section 3 can be extended to some variants of the ADMM. We briefly describe two of them below.

\subsection{Proximal ADMM}\label{subProximal}

In the original ADMM \eqref{eq:admm}, each block $x_k$ is updated by solving a convex optimization subproblem \emph{exactly}. For large scale problems, this subproblem may not be easy to solve unless the matrix $E_k$ is unitary (i.e., $E^T_kE_k=I$) in which case the variables in $x_k$ can be further decoupled (assuming $f_k$ is separable). If the matrix $E_k$ is not unitary, we can still employ a simple proximal gradient step to \emph{inexactly} minimize $L(x^{r+1}_1,...,x^{r+1}_{k-1},x_k,x^r_{k+1},...,x^r_K)$. More specifically, we update each block of $x_k$ according to the following procedure
%\[
%x^{r+1}_k=\argmin_{x_k}
\begin{eqnarray}
    x_k^{r+1}\!\!& =&\!\! {\rm arg}\!\min_{x_k}\Big\{\;h_k(x_k)+\langle y^r,q-E_kx_k\rangle+\left\langle A_k^T\nabla g_k(A_kx^r_k),x_k-x^r_k\right\rangle +\frac{\beta}{2}\|x_k-x^r_k\|^2\nonumber\\[10pt]
    &&\!\!+\Big\langle \rho E_k^T\Big(\sum_{j<k}E_jx^{r+1}_j+\sum_{j\ge k}E_jx_j^r-q\Big),x_k-x^r_k\Big\rangle\Big\} \label{eq:linearized-admm}
    \end{eqnarray}
%\]
in which the smooth part of the objective function in the $k$-th subproblem, namely,
$$
g_k(A_kx_k)+\langle y^r,q-E_kx_k\rangle+
\frac{\rho}{2}\Big\|E_kx_k+\sum_{j< k}E_jx_j^{r+1}+\sum_{j>
k}E_jx_j^{r}-q\Big\|^2
$$
is linearized locally at $x^r_k$, and a proximal term
$\frac{\beta}{2}\|x_k-x_k^r\|^2$ is added. Here, $\beta>0$ is a
positive constant. With this change, updating $x_k$ is easy when
$h_k$ (the nonsmooth part of $f_k$) is separable. For example, this
is the case for compressive sensing applications where
$h_k(x_k)=\|x_k\|_1$, and the resulting subproblem admits a closed
form solution given by the component-wise soft thresholding (also
known as the shrinkage operator). We note that the proximal ADMM
algorithm described here is slightly more general than the proximal
ADMM algorithm seen in the literature, in which only the
penalization term $\frac{\rho}{2}\Big\|E_kx_k+\sum_{j<
k}E_jx_j^{r+1}+\sum_{j> k}E_jx_j^{r}-q\Big\|^2 $ is linearized
locally at $x^r_k$; see e.g., \cite{YangZhang2011, WangYuan2012}.

We claim that Theorem~\ref{thm:main} holds for the proximal ADMM
algorithm {\it without requiring assumption A-(f)} (the full rankness
of $E_k$'s). Indeed, to establish the (linear) convergence of the
proximal ADMM \eqref{eq:linearized-admm}, we can follow the same
proof steps as that for Theorem~\ref{thm:main}, with the only
changes being in the proof of
Lemmas~\ref{lm:p-descent}-\ref{lm:estimate} and Lemma
\ref{lm:cost-to-go}. We first show that Lemma~\ref{lm:p-descent}
holds without assumption A(f). Clearly subproblem
\eqref{eq:linearized-admm} is now {\it strongly convex} without the
full column rank assumption of $E_k$'s made in A(f). In the
following, we will show that as long as $\beta$ is large enough,
there is a sufficient descent:
\begin{equation}\label{eq:s-descent}
{\color{black}
L(\vx^{r+1};y^r)-L(\vx^{r};y^r)\le -\gamma\|\vx^{r+1} - \vx^{r}\|^2,\quad \mbox{for some $\gamma > 0$ independet of $y^r$.}
}
\end{equation}
This property can be seen by bounding the smooth part of $L(x^{r+1}_1,...,x^{r+1}_{k-1},x_k,x^r_{k+1},...,x^r_K)$, which is given by
\[
{\bar L}_k(x_k):=g_k(A_kx_k)+\langle y^r,q-E_kx_k\rangle +\frac{\rho}{2}\Big\|\sum_{j<k}E_jx^{r+1}_j+\sum_{j> k}E_jx_j^r+E_kx_k-q\Big\|^2,
\]
with the Taylor expansion at $x^r_k$:
\begin{equation}\label{eq:estimate1}
{\bar L}_k(x^{r+1}_k)\le {\bar L}_k(x^r_k)+\langle \nabla {\bar L}_k(x^r_k),x_k^{r+1}-x^r_k\rangle +\frac{\nu}{2}\|x^{r+1}_k-x^r_k\|^2
\end{equation}
where
$$\nu:=L\|A_k\|\|A^T_k\|+\rho\|E_k^TE_k\|$$
is the Lipschitz constant of ${\bar L}_k(\cdot)$ and $L$ is the Lipschitz constant of $\nabla g_k(\cdot)$. Making the above inequality more explicit yields
\begin{eqnarray}
&&\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!L(x^{r+1}_1,...,x^{r+1}_{k-1},x^{r+1}_k,x^r_{k+1},...,x^r_K;y^r)
-L(x^{r+1}_1,...,x^{r+1}_{k-1},x^r_k,x^r_{k+1},...,x^r_K;y^r)\nonumber
\\ [10pt]
&\le& h_k(\vx_k^{r+1})-h_k(\vx_k^r)+\langle y^r,E_k(x^r_k-x^{r+1}_k)\rangle+\left\langle A_k^T\nabla g_k(A_kx^r_k),x^{r+1}_k-x^r_k\right\rangle \nonumber\\
    &&\!\!+\left\langle \rho E_k^T\left(\sum_{j<k}E_jx^{r+1}_j+\sum_{j\ge k}E_jx_j^r-q\right),x^{r+1}_k-x^r_k\right\rangle +\frac{\nu}{2} \|\vx_k^{r+1}-\vx_k^r\|^2\nonumber\\ [10pt]
&\le& -\frac{\beta}{2}\|\vx_k^{r+1}-\vx_k^r\|^2 +\frac{\nu}{2}%(L\|A_k\|\|A^T_k\|+\rho\|E_k^TE_k\|)
\|\vx_k^{r+1}-\vx_k^r\|^2\nonumber\\ [10pt]
& =& -\gamma\|\vx^{r+1}_k-\vx^r_k\|^2, \quad \forall\; k,\label{eq:last-estimate}
\end{eqnarray}
provided the regularization parameter $\beta$ satisfies
$$
\gamma:=\frac{1}{2}\left(\beta-\nu\right)>0. %\frac{\beta}{2}-(L\|A_k\|\|A^T_k\|+\rho\|E_k^TE_k\|)\right)>0.
$$
In the above derivation of \eqref{eq:last-estimate}, the first step is due to  \eqref{eq:estimate1}, %that the gradient of the smooth part of $L(x^{r+1}_1,...,x^{r+1}_{k-1},x_k,x^r_{k+1},...,x^r_K;y^r)$ is Lipschitz continuous with a modulus of $\nu$, %$L\|A_k\|\|A^T_k\|+\rho\|E_k^TE_k\|$,
while the second inequality follows from the definition of $x^{r+1}_k$ (cf.\ \eqref{eq:linearized-admm}). Summing \eqref{eq:last-estimate} over all $k$ yields the desired estimate of sufficient descent \eqref{eq:s-descent}.
%This estimate can be used to replace \eqref{eq:strongcvx} in the proof of Lemma~\ref{lm:p-descent}.


To verify that Lemma~\ref{lm:estimate} still holds for the proximal
ADMM algorithm, we note from the corresponding optimality condition
for \eqref{eq:linearized-admm}
\[
x_k^{r+1}=\prox_{h_k}\left[x_k^{r+1}-A_k^T\nabla_{x_k}g_k(A_kx^{r}_k)+E_k^Ty^r-\rho E_k^T\left(\sum_{j< k}E_jx_j^{r+1}+\sum_{j\ge k}E_jx^r_j-q\right) -\beta(x_k^{r+1}-x_k^r)\right].
\]
Using this relation in place of \eqref{eq:old} and following the same proof steps, we can easily prove that the bound \eqref{eq:old-estimate} in Lemma~\ref{lm:estimate} can be extended to the proximal ADMM algorithm. Thus, the convergence results in Theorem~\ref{thm:main} remain true for the proximal ADMM algorithm \eqref{eq:linearized-admm}.

It remains to verify that Lemma~\ref{lm:cost-to-go} still holds
true. In fact the first part of Lemma~\ref{lm:cost-to-go} can be
shown to be independent of the iterates, thus it trivially holds
true for the proximal ADMM algorithm. To show that the second part
of Lemma~\ref{lm:cost-to-go} is true, note that the optimality
condition of the proximal ADMM algorithm implies that
\begin{align*}
x^{r+1}_k&={\rm
prox}_{h_k}\left[x^{r+1}_k-\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j<
k}\}, \{x^r_{j}\}_{j\ge k}; y^r\right)-\beta(x_k^{r+1}-x_k^r)\right]\\
&:= {\rm
prox}_{h_k}\left[x^r_k-\nabla_{x_k}\bar{L}(x^r;y^r)-e^r_k\right]
\end{align*}
where in this case $e^r_k$ is given as
\[
e^r_k:=x^r_k-x^{r+1}_k+\nabla_{x_k}\bar{L}\left(\{x^{r+1}_{j< k}\},
\{x^r_{j}\}_{j\ge k};
y^r\right)-\nabla_{x_k}\bar{L}(x^r;y^r)+\beta(x_k^{r+1}-x_k^r).\] It
is then straightforward to show that the norm of $e^r_k$ can be
bounded by $c^{'}\|x^r-x^{r+1}\|$ for some constant $c^{'}>0$. The
rest of the proof follows the same steps as in Lemma
\ref{lm:cost-to-go}.


\subsection{Jacobi Update}

Another popular variant of the ADMM algorithm is to use a Jacobi
iteration (instead of a Gauss-Seidel iteration) to update the primal
variable blocks $\{x_k\}$. In particular, the ADMM iteration
\eqref{eq:admm} is modified as follows:
\begin{equation}\label{eq:jacobi}
x^{r+1}_k=\argmin_{x_k}\left(h_k(x_k)+g_k(A_kx_k)-\langle y^r,E_kx_k\rangle+\frac{\rho}{2}\left\|E_kx_k+\sum_{j\neq k}E_jx_j^{r}-q\right\|^2\right),\quad \forall\; k.
\end{equation}

The convergence for this direct Jacobi scheme is unclear, % without an appropriate stepsize control,
as the augmented Lagrangian function may not decrease after each Jacobi update.
In the following, we consider a modified Jacobi
scheme with an explicit stepsize control. Specifically, let us introduce an intermediate variable $w=(w^T_1, \cdots,
w^T_K)^T\in \Re^n$. The modified Jacobi update is given as follows:
\begin{align}
w^{r+1}_k&=\argmin_{x_k}\left(h_k(x_k)+g_k(A_kx_k)-\langle
y^r,E_kx_k\rangle+\frac{\rho}{2}\left\|E_kx_k+\sum_{j\neq
k}E_jx_j^{r}-q\right\|^2\right),\quad \forall\;
k,\label{eq:jacobi_modif_w}\\
x^{r+1}_k&=x^r_k+\frac{1}{K}\left(w^{r+1}_k-x^r_k\right), \quad
\forall\; k. \label{eq:jacobi_modif_x}
\end{align}
where a stepsize of $1/K$ is used in the update of each variable block.

With this modification, we claim that
Lemmas~\ref{lm:p-descent}-\ref{lm:estimate} and Lemma
\ref{lm:cost-to-go} still hold.
In particular, Lemma~\ref{lm:p-descent} can be argued as follows.
The strong convexity of $L(x;y)$ with respect to the variable block
$x_k$ implies that
\begin{align}
&L\left(x^r_1, \cdots, x^r_{k-1}, x^r_k, x^r_{k+1}\cdots,x^r_K; y^r
\right)-L\left(x^r_1, \cdots, x^r_{k-1}, w^r_k,
x^r_{k+1}\cdots,x^r_K; y^r\right) \nonumber\\
&\ge \gamma\|w^{r+1}_k-x^r_k\|^2, \ \forall~k.\nonumber
\end{align}

Using this inequality we obtain
\begin{align*}
&L(x^r; y^r)-L(x^{r+1}; y^r)\\
&=L(x^r; y^r)-L\left(\frac{K-1}{K}x^r+\frac{1}{K}w^{r+1}; y^r\right)\nonumber\\
&= L(x^r; y^r)-L\left(\frac{1}{K}\sum_{k=1}^{K}(x^r_1, \cdots,
x^r_{k-1},
w^{r+1}_k, x^r_{k+1}\cdots,x^r_K); y^r\right)\\
&\ge L(x^r; y^r)-\frac{1}{K}\sum_{k=1}^{K}L\left(x^r_1, \cdots,
x^r_{k-1}, w^{r+1}_k, x^r_{k+1}\cdots,x^r_K; y^r\right)\\
&=\frac{1}{K}\sum_{k=1}^{K}\left(L(x^r; y^r)-L\left(x^r_1, \cdots,
x^r_{k-1}, w^{r+1}_k, x^r_{k+1}\cdots,x^r_K; y^r\right)\right)\\
&\ge\frac{\gamma}{K}\sum_{k=1}^{K}\|w^{r+1}_k-x^r_k\|^2\\
&=\frac{\gamma}{K}\|w^{r+1}-x^r\|^2.
\end{align*}
where the first inequality comes from the convexity of the augmented
Lagrangian function.

From the update rule \eqref{eq:jacobi_modif_x} we have
$K(x^{r+1}_k-x^r_k)=(w^{r+1}_k-x^r_k),$ which combined with the
previous inequality yields
\[L(x^r; y^r)-L(x^{r+1}; y^r)\ge \gamma K\|x^{r+1}-x^r\|^2.\]

The proof of Lemma~\ref{lm:estimate} also requires only minor
modifications. In particular, we have the following optimality
condition for \eqref{eq:jacobi}
\[
w_k^{r+1}=\prox_{h_k}\left[w_k^{r+1}-A_k^T\nabla_{x_k}g_k(A_kw^{r+1}_k)+E_k^Ty^r-\rho
E_k^T\left(\sum_{j\neq k}E_jx_j^{r}+E_kw^{r+1}_k-q\right) \right]
\]
Similar to the proof of Lemma~\ref{lm:estimate}, we have
\[
\left\|w_k^{r+1}-\prox_{h_k}\left[x^r_k-A_k^T\nabla_{x_k}g_k(A_kx^{r}_k)+E_k^Ty^r-\rho
E_k^T\left(E x^r-q\right) \right]\right\|\le c\|w^{r+1}-x^r\|.
\]
Utilizing the relationship $K(x^{r+1}_k-x^r_k)=(w^{r+1}_k-x^r_k)$, we can establish
Lemma~\ref{lm:estimate} by following similar proof steps (which we omit due to space reason).

Lemma \ref{lm:cost-to-go} can be shown as follows. We first
express $w_k^{r+1}$ as
\begin{align*}
w_k^{r+1}&=\prox_{h_k}\left[w_k^{r+1}-\nabla_{x_k}\bar{L}\left(\{x^{r}_{j\ne
k}\}, w^{r+1}_{k}; y^r\right)\right]\\
&=\prox_{h_k}\left[x_k^{r}-\nabla_{x_k}\bar{L}\left(x^{r};
y^r\right)-e^r_k\right]\\
\end{align*}
where we have defined
\[e^r_k:=\nabla_{x_k}\bar{L}\left(\{x^{r}_{j\ne
k}\}, w^{r+1}_{k}; y^r\right)-\nabla_{x_k}\bar{L}\left(x^{r};
y^r\right)+x^r_k-w_k^{r+1}.\] Again by using the relationship
$K(x^{r+1}_k-x^r_k)=(w^{r+1}_k-x^r_k)$, we can bound the norm of
$e^r_k$ by $c^{'}\|x^{r+1}-x^r\|$, for some $c^{'}>0$. The
remaining proof steps are similar to those in Lemma \ref{lm:cost-to-go}.


Since Lemmas~\ref{lm:p-descent}-\ref{lm:estimate} and Lemma
\ref{lm:cost-to-go} hold for the Jacobi version of the ADMM algorithm
with a step size control, we conclude that the convergence results of
Theorem~\ref{thm:main} remain true in this case.


\newsection{Concluding Remarks}

In this paper we have established the convergence and the rate of
convergence of the classical ADMM algorithm when the number of
variable blocks are more than two and in the absence of strong
convexity. Our analysis is a departure of the conventional analysis
of ADMM algorithm which relies on a contraction argument involving a weighted
(semi-)norm of $( x^r-x^*,y^r-y^*)$, see
\cite{Ga83,Gab76,Glow84,Glt89,HeTY12,HeYuan12,KoMe,TaoYuan}. In our
analysis, we require neither the strong convexity of the objective
function nor the row independence assumption of the constrained
matrix $E$. Instead, we use a local error bound to show that when
the stepsize of dual update is made sufficiently small, the sum of
the primal and the dual optimality gaps decreases after each ADMM
iteration, although separately they may individually increase. An
interesting issue for further research is to identify good practical stepsize
rules for dual update. While \eqref{eq:alpha} does suggest a dual  stepsize rule in terms of
error bound constants, it may be too conservative
and cumbersome to compute unless the objective function is strongly convex.
One possibility may be to use an adaptive dual stepsize rule to
guarantee the decrease of the sum of the primal and dual optimality
gaps.

\bigskip
\bigskip
\noindent {\bf Acknowledgement:} The authors are grateful to
Xiangfeng Wang and Dr.\ Min Tao of Nanjing University for their
constructive comments.

%An interesting issue for further research is whether and
%how we can relax the smoothness condition in the linear convergence
%analysis. In particular, it would be interesting to extend the
%convergence rate analysis to allow nonsmooth components in the
%objective function $f(x)$ of \eqref{eq:1}. The latter is important
%in several emerging applications of ADMM (e.g., the group LASSO or
%matrix completion). Notice that, when the nonsmooth components are
%present in $f(x)$, our current analysis does establish the global
%convergence of the ADMM algorithm and allows an arbitrary number of
%variable blocks. However, the convergence rate analysis requires the
%objective function to be smooth.

\newsection{Appendix}\label{secAppendix}

\subsection{Proof of Dual Error Bound \eqref{eq:dualeb}}\label{subProofDualEB}
The augmented Lagrangian dual function can be expressed as
\begin{align}
d(y)=\min_{x\in X}\langle
y,q-Ex\rangle+\frac{\rho}{2}\|q-Ex\|^2+g(Ax)+h(x).
\end{align}
For convenience, define $p(Ex):=\frac{\rho}{2}\|q-Ex\|^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
$$x(y)\in \arg\min_{x\in X} \ell(x)+\langle y, q-Ex\rangle.$$

Let $(x^*, y^*)$ denote a primal and dual optimal
solution pair. Let $X^*$ and $Y^*$ denote the primal and dual optimal
solution set. %From Assumption A-(a) we have that both primal and
%dual optimal values of \eqref{eq:MainProblem} are attained and are
%equal $d(y^*)=f(x^*)$. Moreover, there exist constants $t^*$ and
%$h^*$ such that $Ex^*=q$, $Ax^*=t^*$, $h(x^*)=h^*$ for all $x^*\in
%X^*$. Moreover $X^*$ is polyhedral.
The he following properties will be useful in our subsequent
analysis.
%\begin{claim}\label{claimProperties}
%Let $\cal U$ be a compact subset in $\mathbb{R}^m$. Then the
%following are true
\begin{itemize}
%\item [(a)] The closure of $\{x(y)| y\in\cal U\}$ is a compact
%subset of $X$.
\item[(a)] There exist positive scalars $\sigma_g$, $L_g$ such that $\forall~x(y),x(y')\in X$
\begin{enumerate}
\item[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\|A x(y')-A x(y)\|^2$.
\item[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}\|A x(y')-Ax(y)\|^2.$
\item[a-3)] $\|A^T\nabla g(Ax(y'))-A^T\nabla g(A x(y))\|\le
L_g\|Ax(y')-Ax(y)\|.$
\end{enumerate}
\item[b)] All a-1)--a-3) are true for $p(\cdot)$ as well, with some
constants $\sigma_p$ and $L_p$.
\item[c)] $\nabla d(y)=q-Ex(y)$, and $\|\nabla d(y')-\nabla d(y)\|\le\frac{1}{\rho}\|y'-y\|.$
\end{itemize}
%\end{claim}

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 Lemma
\ref{lm:const-derivative} and Lemma \ref{lm:3.2}.

To proceed, let us rewrite the primal problem equivalently as
\begin{align}
d(y)=\min_{(x,s): x\in X, h(x)\le s} \langle y, q-Ex\rangle+
p(Ex)+g(Ax)+s.\label{eq:problemPolyhedral}
\end{align}
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$ is some integer.
For any fixed $y$, let $(x(y), s(y))$ denote
one optimal solution for \eqref{eq:problemPolyhedral}, 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 $\cM$ 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{align*}
E^Ty + %\rho E^T (q-Ex)+
 C_x^T\lambda &=d,\nonumber \\
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{align*}
It is easy to verify by using the optimality condition for problem
\eqref{eq:problemPolyhedral} that
\begin{align}
(x,s,y,\lambda)\in\cM(E^T\nabla p(Ex)+A^T\nabla g(Ax),
e)~\mbox{for some} \ \lambda\nonumber\\
\quad\quad\quad \mbox{if and only if}\  x=x(y), \ e=\nabla
d(y).\label{eq:PolyHedronOPT}
\end{align}
We can take $e=0$, and use the fact that $x(y^*)\in X^*$, we see
that $(x,s,y,\lambda)\in\cM(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 $\cM$; see
\cite{Hoffman, [16], luo-tseng}.

\begin{proposition}\label{propLip}
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{align}
\cM(d, e)\subseteq \cM (\bar{d}, \bar{e})+\theta
\|(d, e)-(\bar{d}, \bar{e})\|\mathcal{B},\\
 \quad\quad\quad \mbox{whenever} \
\|(d, e)-(\bar{d}, \bar{e})\|\le \delta'.
\end{align}
where $\mathcal{B}$ denotes the unit Euclidean ball in
$\mathbb{R}^n\times\mathbb{R}^{m}\times \mathbb{R}\times
\mathbb{R}^j$.
\end{proposition}

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$.
\begin{claim}
Suppose all the assumptions in Assumption A are satisfied. Then
there exits positive scalars $\delta$, $\tau$ such that for all
$y\in \cal U$ and $\|\nabla d(y)\|\le \delta$, there holds ${\rm
dist}(y, Y^*)\le \tau \|\nabla d(y)\|$.
\end{claim}
\proof By the previous claim, $\cM$ 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 $\|\nabla d(y)\|\le
\delta$, then we must have $\|\nabla \ell(x(y))-\nabla
\ell(x^*)\|\le \delta'/2$. To this end, take a sequence
$y^1,y^2,\cdots,$ such that $e^r:=\nabla d(y^r)\to 0$. By assumption
A(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 A(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)\to
(\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
$$\left\{(x, s, d, e)\mid (x,s,y,\lambda)\in\cM(d, e)~\mbox{for some}~ (y,\lambda)\right\}$$
which is polyhedral and thus is closed. Then we can pass limit to it
and conclude (cf. Proposition \ref{propLip})
$$(x^\infty, s^{\infty}, y^{\infty}, \lambda^{\infty})\in\cM (\nabla\ell(x^{\infty}), 0)$$
for some $(y^{\infty}, \lambda^{\infty})\in\mathbb{R}^{m}\times
\mathbb{R}^j$. Thus by \eqref{eq:PolyHedronOPT} and the discussions
that follow, we have $x^\infty\in X^*$ and $y^{\infty}\in Y^*$. By Lemma~\ref{lm:const-derivative}, we have
$\nabla \ell(x^*)=\nabla\ell(x^\infty)$, which further implies that $\nabla \ell(x(y^r))\to \nabla \ell(x^*)$. This
shows that the desired $\delta$ exists.


Then we let $e= \nabla d(y)$, and suppose $\|e\|\le \delta$. From
the previous argument we have
$$\|\nabla\ell(x(y))-\nabla\ell(x^*)\|+\|e\|\le \delta'/2+\delta'/2=\delta'.$$

Using the results in Proposition~\ref{propLip}, we have that there exists $(x^*,s^*, y^*, \lambda^*)\in \cM(\nabla \ell(x^*), 0)$ satisfying
\begin{align}
\|(x(y), s, y, \lambda)-(x^*,s^*, y^*, \lambda^*)\|&\le
\theta\left(\|\nabla\ell(x^*)-\nabla\ell(x(y))\|+\|e\|\right)\nonumber.
\end{align}

Since $(x(y),s,y,\lambda)\in\cM(\nabla \ell (x(y)), e)$, it follows from the
definition of $\cM$ that
\begin{align}
E^Ty % + \rho E^T (q-Ex(y))
+ C_x^T\lambda &=\nabla\ell(x(y)),\label{eq:FirstOrderPrimal1} \\
C^T_s\lambda&=1, \label{eq:FirstOrderPrimal2} \\
q-Ex(y)&=e,\label{eq:FeaibilityPrimal} \\
\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. \label{eq:ComplementarityPrimal}
\end{align}
Since $(x^*,s^*,y^*,\lambda^*)\in\cM(\nabla \ell (x^*), 0)$, we have from
the definition of $\cM$
\begin{align}
E^Ty^* + %\rho E^T (q-Ex^*)+
C_x^T\lambda^* &=\nabla\ell(x^*),\label{eq:FirstOrderOPT1} \\
C^T_s\lambda^*&=1, \label{eq:FirstOrderOPT2}\\
q-Ex^*&=0,\label{eq:FeaibilityOPT}\\
\lambda^*\ge 0, \ (C_x x^*+C_s s^*)\ge c, \ \langle C_x x^*+C_s
s^*-c,\lambda^*\rangle&=0.\label{eq:ComplementarityOPT}
\end{align}

Moreover, we have
\begin{align}
&\sigma_g\|A(x(y)-x^*)\|^2+\sigma_p\|E(x(y)-x^*)\|^2\nonumber\\
&\le\langle A^T\nabla g(Ax(y))-A^T\nabla g(Ax(y^*)),
x(y)-x(y^*)\rangle+\langle E^T\nabla p(Ex(y))-E^T\nabla p(Ex(y^*)),
x(y)-x(y^*)\rangle\nonumber\\
&=\langle\nabla\ell(x(y))-\nabla\ell(x(y^*)),
x(y)-x(y^*)\rangle\nonumber\\
&=\langle \lambda-\lambda^*, C_x x(y)-C_x x^*\rangle+\langle y-y^*,
E x(y)-E x^*\rangle
%+\rho \langle x^*-x(y), E^T E(x(y)-x^*)\rangle
\nonumber
\end{align}
where the first inequality comes from the strong convexity of
$g(\cdot)$ and $p(\cdot)$; the last equality is from
\eqref{eq:FirstOrderPrimal1} and \eqref{eq:FirstOrderOPT1}.
%Clearly we have $\rho \langle x^*-x(y), E^T E (x(y)-x^*)\rangle\le0$.
Moreover, we have
\begin{align}
&\langle \lambda-\lambda^*, C_x x(y)-C_x
x^*\rangle\nonumber\\
&=\langle \lambda-\lambda^*, C_x x(y)-C_x
x^*\rangle+\langle\lambda-\lambda^*, C_s s-C_s s^*\rangle \nonumber\\
&=\langle \lambda-\lambda^*, (C_x x(y)+C_s s)-(C_x x^*+C_s
s^*)\rangle\nonumber\\
&=-\langle \lambda^*, C_x x(y)+C_s s-c\rangle-\langle \lambda, C_x
x^*+C_s s^*-c\rangle\le 0
\end{align}
where in the first equality we have used the fact that
$C^T_s\lambda-C^T_s\lambda^*=0$; see \eqref{eq:FirstOrderPrimal2}
\eqref{eq:FirstOrderOPT2}; in the third equality and in the last
inequality we have used the complementary conditions
\eqref{eq:ComplementarityOPT} and \eqref{eq:ComplementarityPrimal}.
As a result, we have
\begin{align}
&\sigma_g\|A(x(y)-x^*)\|^2+\sigma_p\|E(x(y)-x^*)\|^2\nonumber\\
&\le\langle y-y^*, (Ex(y)-q)-(Ex^*-q)\rangle\le \|y-y^*\|\|e\|,
\end{align}
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~\ref{propLip}
\begin{align*}
&\|(x(y), s, y, \lambda)-(x^*,s^*, y^*, \lambda^*)\|^2\\
&\le
\theta^2\left(\|\nabla\ell(x^*)-\nabla\ell(x(y))\|+\|e\|\right)^2\nonumber\\
&\le\theta^2\left(2\|\nabla\ell(x^*)-\nabla\ell(x(y))\|^2+2\|e\|^2\right)\nonumber\\
&\le 2\theta^2\left(2\|\nabla g(x^*)-\nabla g(x(y))\|^2+2\|\nabla p(x^*)-\nabla p(x(y))\|^2+\|e\|^2\right)\nonumber\\
&\le2\theta^2\left(L^2_g\|A^T(x(y)-x^*)\|^2+L^2_p\|E^T(x(y)-x^*)\|^2+\|e\|^2\right)\nonumber\\
&\le
2\theta^2\max\left(\frac{2L^2_g}{\sigma_g},\frac{2L^2_p}{\sigma_p},1\right)\left(\sigma_g\|A^T(x(y)-x^*)\|^2+\sigma_p\|E^T(x(y)-x^*)\|^2+\|e\|^2\right)\\
&\le
2\theta^2\max\left(\frac{2L^2_g}{\sigma_g},\frac{2L^2_p}{\sigma_p},1\right)\left(\|e\|\|y-y^*\|+\|e\|^2\right)\nonumber\\
&\le
2\theta^2\max\left(\frac{2L^2_g}{\sigma_g},\frac{2L^2_p}{\sigma_p},1\right)\left(\|e\|\|(x(y),
s,y, \lambda)-(x^*, s^*, y^*, \lambda^*)\|
+\|e\|^2\right)\nonumber,
\end{align*}
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 $\|(x(y), s, y,
\lambda)-(x^*, s^*, y^*, \lambda^*)\|/\|e\|$, so we have
$$\|(x(y),s, y, \lambda)-(x^*, s^*, y^*, \lambda^*)\|/\|e\|\le \tau$$ 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 ${\rm
dist}(y, Y^*)\le \tau\|\nabla d(y)\|$.
 \QED

%\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%
%As we noted in Section 2, an important special case of our problem arises when $Y$ is the entire space.  Then, the primal problem reduces to that of minimizing $f(x)$ subject to $Ex = q$ and $x\in X$, and the dual problem is obtained by dualizing the constraints $Ex = q$. In this section, we will apply the error bound of Section 4 (i.e., Corollary 4.1) to analyze the rate of convergence of a class of dual ascent methods for solving this special case.  Accordingly, we make the following assumption (in addition to Assumptions A and B) throughout:
%
%\pn
%{\bf Assumption C.}
% $Y = \Re^m$.
%
%\pn
%In subsequent sections we will study methods for the constrained case.
%
%  The special structure of $Y$ motivates the following method for solving this special case of (\ref{2.4})--(\ref{2.5}) and (\ref{2.3})--(\ref{2.2})  whereby, at each iteration, a subset of the coordinates of $y$ is adjusted (or `relaxed'), with the other coordinates held fixed, so as to increase $d(y)$.  We will call this the block coordinate relaxation method or, in short, the BCR method.
%
%\pn
%{\bf BCR Method} (Unconstrained Case)
%\bn
%Fix two parameters $\gamma \in(0,1]$ and $\rho \ge 0$.  Starting with any $y^0 \in \Re^m$, we generate a sequence $y^0, y^1, ...$ in $\Re^m$ according to the formula that, given $y^r$,  we choose
%a nonempty subset $I^r$ of $\{1,...,m\}$ and
%choose $y^{r+1}$ to be any vector in $ \Re^m$ satisfying
%\begin{eqnarray}
%y^{r+1}_i &=& y^r_i \quad \forall i\not\in I^r, \label{5.9a}\\
%(\gamma - 1)(d(y^{r+1})-d(y^r))
%&\le& \gamma\langle y^{r+1}-y^r,\nabla d(y^{r+1}) \rangle, \label{5.9b}\\
%\|\nabla_{I^r} d(y^{r+1})\|
%&\le& \rho \|\nabla d(y^{r+1}) - \nabla d(y^r)\|. \label{5.9c}
%\end{eqnarray}
%
%\bigskip
%
%Roughly speaking, (\ref{5.9a}) ensures that only coordinates with indices in $I^r$ change value; (\ref{5.9b}) ensures that a dual ascent occurs (with $\gamma$ acting as a stepsize of sorts); and (\ref{5.9c}) ensures that there is a change in $\nabla d$ whenever $y^{r+1}$ does not maximize exactly $d$ with respect to the coordinates indexed by $I^r$ (with $\rho$ controlling the accuracy of the maximization).  To see that an $y^{r+1}$ satisfying (\ref{5.9a})--(\ref{5.9c}) in fact exists, consider the restricted dual problem
%\begin{eqnarray*}
%\hbox{maximize\ }\ && d(y) \\
%\hbox{subject to}\ && y_i = y^r_i \quad \forall i\not\in I^r.
%\end{eqnarray*}
%Take $y^{r+1}$ to be any optimal solution of this problem (so that $\nabla_{I^r} d(y^{r+1}) = 0$ and $d(y^{r+1}) \ge d(y^r)$) and it is easily checked that $y^{r+1}$ satisfies (\ref{5.9a})--(\ref{5.9c}).
%[That the above problem has an optimal solution can be argued in a manner analogous to that for showing (\ref{2.2}) has an optimal solution, but with the following problem taken as the associated primal problem
%\begin{eqnarray*}
%\hbox{minimize\ }\ && \  f(x) - \sum_{i\not\in I^r} y^r_i (E_i x)  \\
%\hbox{subject to}\ && x\in X,\quad E_i x = q_i \ \ \ \forall i\in {I^r}.
%\end{eqnarray*}
%For a more detailed argument, see Proposition 3 in [30].]
%
%The BCR method need not converge unless the index sets $I^0, I^1,...$ are chosen according to some rule.  We will use either of the following two commonly used rules:
%\pn
%\pn
%{\bf Almost Cyclic Rule}.
%For some fixed integer $T \ge 1$, every coordinate is iterated upon at least once every $T$ successive iterations, i.e., $I^r \cup \cdots \cup I^{r+T-1}
%= \{1,...,m\}$ for all $r$.
%\pn
%\pn
%{\bf Gauss--Southwell Rule}.  Fix a scalar $\beta$ in the interval $(0,1]$ and choose a collection  ${\cal C}$ of nonempty subsets of $\{1,...,m\}$ whose union is $\{1,...,m\}$.  For each $r$,  choose $I^r$ to be any element of ${\cal C}$ satisfying
%\[
%\| \nabla_{I^r} d(y^{r})\| \ge \beta \max_{J\in {\cal C}} \|\nabla_J d(y^r)\|.
%\]
%\pn
%\pn
%An important special case of the almost cyclic rule is the \underbar{cyclic} rule, in which $I^r = \{ r (\hbox{mod }m) + 1 \}$ for all $r$.
%
%The BCR method was first proposed (in a more general form) in [30] as a unifying extension of dual coordinate ascent and dual gradient ascent methods.  It contains many known methods as special cases, including (i) single coordinate relaxation methods (see [6], [21], [28]):
%\[
%y^{new}_i \approx \arg\max_\zeta d(y_1,...,y_{i-1},\zeta, y_{i+1},...,y_m), \qquad
%y^{new}_j = y_j\ \ \ \forall j\not= i,
%\]
%with $i$ chosen according to either of the above two rules, (ii) their specialization to network flow problems (see [3], [7], [19], [32]), and (iii) dual gradient ascent methods of the form (see [14], [21]):
%\[
%y^{new} = y + \alpha H \nabla d(y),
%\]
%with $H$ a positive definite matrix and $\alpha$ a suitably chosen positive stepsize.  It is known that (under Assumptions A--C) if $\{y^r\}$ is a sequence generated by the BCR method using either the almost cyclic or the Gauss--Southwell rule, then $\{x(y^r)\}$ converges to $x^*$ [30, Proposition 1].  Below, we will use the local error bound of Section 4 (cf.\ Theorem 4.1 and Corollary 4.1) to show that this convergence is at least linear. The proof of this is quite intricate because, although $d$ is concave differentiable, it is not strictly concave and its level sets need not be bounded.
%
%First we give some properties of a sequence generated by the BCR method.  These properties follow from Lemma 3.2(b), Theorem 4.1 and Corollary 4.1, and will be used in the convergence proof both in the case where the almost cyclic rule is used and in the case where the Gauss--Southwell rule is used.
%\pn
%{\bf Lemma 5.1.}  For any sequence
%$\{y^r\}$ generated by the BCR method
%(\ref{5.9a})--(\ref{5.9c}), there is a positive scalar $\kappa $ such that the following hold for all $r$:
%\bn
%(a) $\|x(y^{r+1}) - x(y^r)\|^2 \le \kappa ( d(y^{r+1}) - d(y^r) )$.
%\bn
%(b) $\|\nabla d(y^{r+1}) - \nabla d(y^r)\|^2
%\le \kappa  ( d(y^{r+1}) - d(y^r) )$.
%\bn
%(c)
%$ \|\nabla_{I^r} d(y^{r+1})\|^2 \le
%\kappa( d(y^{r+1}) - d(y^r) )$.
%\bn
%(d) If there exist a positive scalar $\theta$ and a positive integer $R$ such that
%\begin{equation}\label{5.add}
%\|\nabla d(y^r)\|^2\le \theta (d(y^{r+R})-d(y^r))\qquad  \forall r\ge 0,
%\end{equation}
%then $\{d(y^r)\}$ converges at least linearly to $f(x^*)$  and $\{x(y^r)\}$ converges at least linearly to $x^*$.
%\pn
%{\bf Proof.}
%(a) For convenience, let $x^r = x(y^r)$ for all $r$.  Then, we have from (\ref{2.2}) and (\ref{x(y)}) that $d(y^r) = f(x^r) + \langle q - Ex^r , y^r \rangle$ for all $r$.  This together with $q -Ex^{r+1} = \nabla d(y^{r+1})$ for all $r$ (cf.\ (\ref{2.6})) yields, for any $r$,
%\begin{eqnarray*}
%d(y^{r+1}) - d(y^r) &=&
%f(x^{r+1}) - f(x^r) - \langle E^Ty^r , x^{r+1} - x^r \rangle + \langle y^{r+1} - y^r, \nabla d(y^{r+1}) \rangle.
%\end{eqnarray*}
%Using (\ref{5.9b}) to bound the last term on the right hand side, we obtain (after rearranging terms)
%\[d(y^{r+1}) - d(y^r)
%\ge  \gamma [ f(x^{r+1}) - f(x^r) - \langle E^Ty^r ,
%x^{r+1} - x^r \rangle ] .\]
%We now use (\ref{2.7}) with $y = y^r$ and $x = x^{r+1}$ to bound the right hand side to obtain
%\begin{equation}
%d(y^{r+1}) - d(y^r)
%\ge \gamma [ f(x^{r+1}) - f(x^r) - \langle \nabla f(x^r) , x^{r+1} - x^r \rangle ]. \label{5.4}
%\end{equation}
%Since $f$ is convex so the quantity inside the brackets is
%nonnegative, we obtain $d(y^{r+1}) \ge d(y^r)$ for all $r$.
% Thus,  $y^r$ lies in the set $\{\ y\in Y \ |\ d(y) \ge \eta\ \}$ for all $r$, where we let $\eta = d(y^0)$.  Then, for any $r$, we have from (\ref{5.4}) and applying (\ref{4.11w}) with $y' = y^{r+1}$ and $y = y^r$ that
%\[
%d(y^{r+1}) - d(y^r)
%\ge \gamma [ f(x^{r+1}) - f(x^r) - \langle \nabla f(x^r) ,
%x^{r+1} - x^r \rangle ]
%\ge {\gamma \sigma_\eta \over 2} \|x^{r+1} - x^r\|^2.
%\]
%
%\bn
%(b)  For any $r$,
%since $\nabla d(y^r) = q - Ex^r$ (cf.\ (\ref{2.6})) so
%$\|\nabla d(y^{r+1}) - \nabla d(y^r)\| \le \|E\| \|x^{r+1} - x^r\|$, the above relation yields
%\[
%d(y^{r+1}) - d(y^r)  \ge
%{ \gamma \sigma_\eta \over 2\|E\|^2 } \|\nabla d(y^{r+1}) - \nabla d(y^r)\|^2.
%\]
%
%\bn
%(c)  Combine (\ref{5.9c}) with part (b).
%
%\bn
%(d) By (a), $d(y^r) \le d(y^{r+1})$ for all $r \ge 0$.  Since $d(y^r)$ is bounded above (by, for example, $f(x^*)$) for all $r$, this implies $\{d(y^r)\}$ converges and so, by (\ref{5.add}), $\|\nabla d(y^r)\|\to 0$.  Then, by Corollary 4.1, there exist a positive scalar $\tau'$ and an index $\bar r$ such that
%\[
%f(x^*)-d(y^r)\le \tau' \|\nabla d(y^r)\|^2  \qquad \forall r \ge \bar r.
%\]
%Using (\ref{5.add}) to bound the right-hand side and rearranging terms yields
%\[
%f(x^*) - d(y^{r+R})
%\le (1 - {1 \over \tau'\theta}) (f(x^*) - d(y^r) )\quad \forall r \ge \bar r.
%\]
%Since $d(y^r) \le f(x^*)$ for all $r$,  this shows that $d(y^r) \to f(x^*)$ at least linearly.  Then $d(y^{r+R})-d(y^r)\to 0$ at least linearly and, by (\ref{5.add}), $\|\nabla d(y^r)\|\to 0$ at least linearly. Upon invoking Theorem 4.1 and using $Y = \Re^m$, we conclude that $x(y^r) \to x^*$ at least linearly.
%\QED
%\bigskip
%
%By using Lemma 5.1, we can now prove the first main result of this section.
%\pn
%{\bf Theorem 5.1.} Let $\{y^r\}$ be a sequence
%generated by the BCR method
%(\ref{5.9a})--(\ref{5.9c}), using the Gauss--Southwell rule.  Then $\{d(y^r)\}$ converges at least linearly to $f(x^*)$ and $\{x(y^r)\}$ converges at least linearly to $x^*$.
%\pn
%{\bf Proof.}  By Lemma 5.1(d), it suffices to verify that (\ref{5.add}) holds for some $\theta$ and $R$.  For any index $r\ge 0$ we have
%\begin{eqnarray*}
%\|\nabla d(y^{r})\|^2
%&\le& {1\over \beta^2} \|\nabla_{I^r} d(y^r)\|^2 \\
%&\le& {2 \over \beta^2}\left( \|\nabla_{I^r} d(y^{r+1})\|^2 + \|\nabla_{I^r} d(y^{r+1})-\nabla_{I^r} d(y^{r})\|^2\right)\\
%&\le& {4 \kappa \over \beta^2}
%(d(y^{r+1}) - d(y^{r})),
%\end{eqnarray*}
%where the first inequality follows from the Gauss--Southwell rule; the second inequality follows
%from using the triangle inequality and the inequality $(a+b)^2\le 2(a^2+b^2)$ (with $a$, $b$ any two numbers); and the last inequality follows from Lemma 5.1(b)--(c). Hence (\ref{5.add}) holds with $\theta = 4\kappa/\beta^2$ and  $R=1$.
%\QED
%
%\bigskip
%
%By using Lemma 5.1, we now prove the second  main result of this section.
%\pn
%{\bf Theorem 5.2.} Let $\{y^r\}$ be a sequence
%generated by the BCR method
%(\ref{5.9a})--(\ref{5.9c}), using the almost cyclic rule.
%Then $\{d(y^r)\}$ converges at least linearly to $f(x^*)$ and $\{x(y^r)\}$ converges at least linearly to $x^*$.
%\pn
%{\bf Proof.}  By Lemma 5.1(d), it suffices to verify that (\ref{5.add}) holds for some $\theta$ and $R$.
%Fix any index $r \ge 0$ and any $i\in \{1,...,m\}$.  Let $k$ be the smallest integer greater than or equal to $r$ such that $i \in I^k$.  By the almost cyclic rule, we have $k \le r+T-1$, so
%\begin{eqnarray*}
%|\nabla_i d(y^r)|
%&\le& |\nabla_i d(y^{k +1})| + \sum_{l=r}^{k}
%|\nabla_i d(y^{l+1}) - \nabla_i d(y^l)|   \\
%&\le& \|\nabla_{I^k} d(y^{k+1})\| + \sum_{l=r}^{k}\|\nabla d(y^{l+1}) - \nabla d(y^l)\| \\
%&\le& \sum_{l=r}^{r+T-1} \Bigl(\|\nabla_{I^{l}} d(y^{l+1})\| + \|\nabla d(y^{l+1}) - \nabla d(y^l)\|\Bigr),
%\end{eqnarray*}
%where the first inequality follows from telescoping $\nabla_i d(y^r)$ as $\nabla_i d(y^{k+1}) + \sum_{l=r}^{k} (\nabla_i d(y^l) - \nabla_i d(y^{l+1}))$ and then using the triangle inequality.
%Since our choice of $i$ was arbitrary, the above relation holds for all $i$. Squaring both sides of this relation and summing over all $i$ yields
%\begin{eqnarray*}
%\|\nabla d(y^r)\|^2
%&\le&  m\left( \sum_{l=r }^{r+T-1} \Bigl(\|\nabla_{I^l} d(y^{l+1})\| + \|\nabla d(y^{l+1}) - \nabla d(y^l)\|\Bigr) \right)^2 \\
%&\le& 2T m \sum_{l=r}^{r+T-1} \Bigl(\|\nabla_{I^l} d(y^{l+1})\|^2 + \|\nabla d(y^{l+1}) - \nabla d(y^l)\|^2 \Bigr) \\
%&\le& 2T m (2\kappa) \sum_{l=r}^{r+T-1} \Bigl(d(y^{l+1}) - d(y^l)\Bigr)   \\
%&=& 4T m\kappa  \Bigl( d(y^{r+T}) - d(y^{r}) \Bigr),
%\end{eqnarray*}
%where the second inequality follows from the relation
%$(a_1 + \cdots + a_{2T})^2 \le 2T ((a_1)^2 + \cdots +  (a_{2T})^2)$ for any numbers $a_1, ..., a_{2T}$, and
%the third inequality follows from Lemma 5.1(b)--(c).
%Since our choice of $r$ was also arbitrary, the above relation holds for all $r \ge 0$.
%Hence (\ref{5.add}) holds with $\theta=4 T m \kappa$ and $R=T$.
%\QED
%
%\bigskip
%
%As an immediate consequence of Theorem 5.2, we have that the network methods proposed in [7] and [19] converge at least linearly.  This is because these methods are special cases of the BCR method (with $\rho = 0$) using the cyclic rule, applied to the special case of (\ref{2.4})--(\ref{2.5}) in which $f$ is a separable strictly convex quadratic function, $X$ is a box, and $E$ is the node--arc incidence matrix for a directed network.  Similar rate of convergence results can be obtained for the other methods mentioned earlier in this section, though some care must be exercised in translating our assumptions (i.e., Assumptions A--C) to the respective problem setting.
%
%
%Notice that Theorems 5.1 and 5.2 do not assert
%the convergence of the dual sequence $\{y^r\}$.
%This is not surprising for, in general, $\{y^r\}$ need not converge.  As an example, take $y^0, y^1, ...$ to be any sequence of points in $Y^*$.  This sequence satisfies (\ref{5.9a})--(\ref{5.9c}) for all $r$ (with $I^r$ set to $\{1,...,m\}$ and $\gamma$ and $\rho$ chosen arbitrarily), but it certainly need not converge.
%
%
%\newsection{Linear Convergence of an Exact Block Coordinate Relaxation Method for the Box-Constrained Case}
%
%\indent
%
%As we noted in Sections 1 and 2, an important special case of our problem arises when $Y$ is the nonnegative orthant or, more generally, the Cartesian product of closed intervals (a `box').  In this box case, it is still possible to use a block coordinate ascent method to solve the dual problem as in Section 5 but, to attain linear convergence, the method must in addition be able to identify constraints which are active at the optimal solution set.   In this section, we consider such a method and we apply the error bound of Section 4 to show that it converges at least linearly.  Accordingly, we make the following assumption, in addition to Assumptions A and B, throughout:
%
%\pn
%{\bf Assumption E.}
% $Y = [l_1,c_1] \times [l_2,c_2] \times \cdots \times [l_m,c_m]$, for some  $-\infty \le l_i \le c_i \le \infty$,  $i=1,...,m$.
%
%
%For any $y \in \Re^m$ and any nonempty $I \subseteq \{1,...,m\}$, let $[y]^+_I$ denote the vector with components $\max\{l_i,\min\{c_i,y_i\}\}$, $i \in I$, arranged in the order of their indices.  Then, it is readily seen that $y \in Y^*$ if and only if $y_I = [y + \nabla d(y)]^+_I$ for every nonempty $I \subseteq \{1,...,m\}$.   This observation motivates the following extension of the BCR method of Section 5 for solving this special case of (\ref{2.4})--(\ref{2.5}) and (\ref{2.3})--(\ref{2.2})  whereby, at each iteration, a subset of the coordinates of $y$ is adjusted (or `relaxed'), with the other coordinates held fixed, so as to maximize $d(y)$ over the box $Y$ {\it exactly}.  As we shall see, exact maximization is essential for the method to have the constraint identification property mentioned above.   We will call this the exact block coordinate relaxation method or, in short, the exact BCR method.
%
%\pn
%{\bf Exact BCR Method} (Box--Constrained Case)
%\bn
%Starting with any $y^0 \in Y$, we generate a sequence $y^0, y^1, ...$ in $Y$ according to the formula that, given $y^r$,  we choose a nonempty subset $I^r$ of $\{1,...,m\}$ and choose $y^{r+1}$ to be any vector in $ Y$ satisfying
%\begin{eqnarray}
%y^{r+1}_i &=& y^r_i \qquad\qquad \forall i\not\in I^r, \label{6.9a}\\
% y^{r+1}_{I^r} &=& [y^{r+1} + \nabla d(y^{r+1})]^{+}_{I^r}. \label{6.9b}
%\end{eqnarray}
%
%That the above iterations are well defined can be shown by modifying the argument in Section 5 showing that the BCR iterations are well defined.  Analogous to the BCR method,  the index sets $I^0, I^1, ...$ are chosen according to either the almost cyclic  rule:
%\[
%I^r \cup \cdots \cup I^{r+T-1} = \{1,...,m\}
%\qquad \forall r,
%\]
%or the Gauss--Southwell Rule:
%\[
%I^r \in {\cal C} \quad \mbox{and} \quad
%\| y^r_{I^r} - [y^r + \nabla d(y^r)]^+_{I^r}\| \ge \beta \max_{J\in {\cal C}} \|y^r_J - [y^r + \nabla d(y^r)]^+_J\|
%\qquad \forall r,
%\]
%where $\beta$ is any scalar in $(0,1]$ and  ${\cal C}$ is any collection of nonempty subsets of $\{1,...,m\}$ whose union is $\{1,...,m\}$.
%
%Special cases of the exact BCR method include a number of dual coordinate ascent algorithms for quadratic programming and for entropy optimization (see Section 5 and [14], [30] for discussions).
%In the case where $Y$ is the nonnegative orthant in $\Re^m$, it is known that if $\{y^r\}$ is a sequence generated by the exact BCR method using either the almost cyclic or the Gauss--Southwell rule, then $\{x(y^r)\}$ converges to $x^*$ [30, Proposition 1].  However, no rate of convergence result was known previously.  Below we show that the rate of convergence for this method is at least linear.  A key step in the analysis is to show that the exact BCR method eventually identifies all bounds $l_i > -\infty$ or $c_i <\infty$ which are active (i.e., binding)  on $Y^*$.   This together with Theorem 4.1 then yields an estimate of the optimality gap $f(x^*) - d(y^r)$  analogous to that given in Corollary 4.1 (see (\ref{6.3})). Combining this estimate with an estimate of $d(y^r) - d(y^{r+R})$ analogous to (\ref{5.add}) (see (\ref{6.9c})), with $R$ some fixed integer, completes the proof.
%
%\pn
%{\bf Theorem 6.1.}
%Let $\{y^r\}$ be a sequence generated by the exact BCR method (\ref{6.9a})--(\ref{6.9b}), using either the Gauss--Southwell rule or the almost cyclic rule.  Then $\{d(y^r)\}$ converges at least linearly to $f(x^*)$ and $\{x(y^r)\}$ converges at least linearly to $x^*$.
%\pn
%{\bf Proof}.
%It is not difficult to see by using the box structure of $Y$ and (\ref{6.9a})--(\ref{6.9b}) that
%\[
%\langle y^{r+1} - y^r , \nabla d(y^{r+1}) \rangle \ge 0
%\]
%for all $r$.  Using this inequality, the proof of Lemma 5.1 can be easily modified to show that parts (a)--(b) of Lemma 5.1 still hold for all $r$.  Moreover, by (\ref{6.9b}) and $d(y^{r+1}) \ge d(y^r)$, the following extension of part (c) holds for all $r$:
%\[
%\| y^{r+1}_{I^r} - [y^{r+1} + \nabla d(y^{r+1})]^+_{I^r}\|^2
%\le \kappa (d(y^{r+1}) - d(y^r) ),
%\]
%with $\kappa$ some positive scalar.
%Then, proceeding as in the proof of Theorems 5.1 and 5.2, except with $\|\nabla d(y^r)\|$ and $\|\nabla_{I^l} d(y^{l+1})\|$ therein replaced everywhere by, respectively, $\|y^r - [y^r + \nabla d(y^r)]^+_Y\|$ and $\|y^{l+1}_{I^l} - [y^{l+1} + \nabla d(y^{l+1})]^+_{I^l}\|$, we obtain
%\begin{equation}\label{6.9c}
%\| y^{r }  - [y^{r} + \nabla d(y^{r})]^+_Y\|^2
%\le \theta (d(y^{r+R}) - d(y^r) )\quad \forall r,
%\end{equation}
%where $\theta$ is a positive scalar depending on the
%problem data only and $R$ equals $1$ if the Gauss--Southwell rule is used and equals $T$ if the almost cyclic rule is used.
%
%Next we show that
%there exists a positive scalar $\tau'$ and an index $\bar r$ such that
%\begin{equation} \label{6.3}
%f(x^*) - d(y^r) \le \tau' \|y^r - [y^r + \nabla d(y^r)]^+_Y\|^2  \qquad \forall r \ge \bar r.
%\end{equation}
%Since $d(y^r)$ is bounded above (by, for example, $f(x^*)$) and is monotonically nondecreasing, $\{d(y^r)\}$ is bounded and, by
%(\ref{6.9c}), $\| y^{r }  - [y^{r} + \nabla d(y^{r })]^+_Y\|\to 0$.  Then, by Theorem 4.1, there exists a positive scalar $\tau$ such that
%\begin{equation}\label{6.4}
%\|x(y^r)-x^*\|+ \|y^r - \bar y^r\|
%\le \tau \|y^r - [y^r + \nabla d(y^r)]^+_Y\|
%\end{equation}
%for all $r$ sufficiently large,
%where $\bar y^r$ denotes the element of $Y^*$ nearest to $y^r$ in the $L_2$-norm.  Since $\| y^{r }  - [y^{r} + \nabla d(y^{r })]^+_Y\|\to 0$, (\ref{6.4}) implies $x(y^r) \to x^*$ so (cf.\ (\ref{2.6})) $\nabla d(y^r) \to q - Ex^*$.
% By using (\ref{6.9a})--(\ref{6.9b}) and properties of the
%Gauss--Southwell or the almost cyclic rule, it can be seen that, for all $r$ sufficiently large,
%$y^r_i$ equals $l_i$ ($c_i$) whenever the $i$th component of $q - Ex^*$ is negative (positive).
%Fix any $r$ sufficiently large so that (\ref{6.4}) and the preceding condition hold.  Since $\nabla d(\bar y^r) = q - Ex^*$ (cf.\ (\ref{2.6}) and $x(\bar y^r) = x^*$) so $\bar y^r_i$ equals $l_i$ ($c_i$) whenever the $i$th component of $q - Ex^*$ is negative (positive), we have $\bar y^r_i = y^r_i$ whenever the $i$th component of $\nabla d(\bar y^r)$ is nonzero, implying $\langle \nabla d(\bar y^r),\bar y^r - y^r \rangle = 0$.  Combining this with the Mean Value Theorem, which states that there exists a $\psi^r$ lying on the line segment joining $y$ with $\bar y^r$ such that $d(\bar y^r) - d(y) = \langle \nabla d(\psi^r) , \bar y^r - y^r \rangle$, yields
%\begin{eqnarray*}
%d(\bar y^r) - d(y^r)
%&=& \langle \nabla d(\psi^r) - \nabla d(\bar y^r),  \bar y^r - y^r \rangle \\
%&\le& \|\nabla d(\psi^r) - \nabla d(\bar y^r)\| \| \bar y^r - y^r\| \\
%&\le& M_{\eta} \|\psi^r - \bar y^r\| \| \bar y^r - y^r\| \\
%&\le& M_{\eta} \|y^r - \bar y^r\|^2,
%\end{eqnarray*}
%where $\eta = d(y^0)$ and the second inequality follows from $d(y^r) \ge \eta$ and Lemma 3.2(c).  Combining this with (\ref{6.4}) and the strong duality relation $f(x^*) = d(\bar y^r)$ shows that (\ref{6.3}) indeed holds for some $\bar r$, with $\tau' = M_\eta \tau^2$.
%
%Upon combining (\ref{6.9c}) with (\ref{6.3}) and then rearranging terms, we obtain
%\[
%f(x^*) - d(y^{r+R}) \le \left(1 - {1\over \tau'\theta} \right) (f(x^*)-d(y^r))\qquad \forall r \ge \bar r.
%\]
% Since
%$f(x^*) \ge d(y^r)$ for all $r$, this implies
%$d(y^r)\to f(x^*)$ at least linearly.  Then $d(y^{r+1})-d(y^r)\to 0$ at least linearly so, by (\ref{6.9c}), $\|y^r-[y^r+\nabla d(y^r)]^+_Y\|\to 0$ at least linearly. The latter together with (\ref{6.4}) shows  that $x(y^r) \to x^*$ at least linearly.
%\QED
%
%
%
%\newsection{Linear Convergence of a Dual Gradient Projection Algorithm}
%
%\indent
%
%For the general case where $Y$ is any polyhedral set, the previous (block) coordinate ascent approach no longer applies.  Instead, we  will apply the gradient projection algorithm of Goldstein \cite{[Gol64]} and of Levitin and Polyak \cite{[LeP65]} (also see \cite{[1], [9], [18]}) to solve the dual problem. This latter algorithm is well suited for a problem with simple constraint set (e.g., a box or a simplex), and its use of projections lends itself well to an analysis by the error bound of Section 4.  To analyze this algorithm, we will make, in addition to Assumptions A and B, the standard assumption that $\nabla d$ is Lipschitz continuous {\it everywhere}.  Interpreted in terms of the original problem data, this amounts to the following assumption on $f$:
%
%\pn
%{\bf Assumption D}.
%$f$ is strongly convex with modulus $\sigma > 0$.
%
%\pn
%It can be seen by using an argument similar to the proof of Lemma 3.2(c) that, under Assumption D, $\nabla d$ is  Lipschitz continuous on $\Re^m$ with Lipschitz constant $L = \|E\|\|E^T\|/\sigma$.
%
%Below we describe the gradient projection algorithm,  applied to solve this special case of the dual problem  (\ref{2.3})--(\ref{2.2}):
%
%\pn
%{\bf Dual Gradient Projection Algorithm}
%\bn
%Fix a parameter $\epsilon_1 \in (0,2/\sigma)$ and set $\epsilon_2 = 1/\epsilon_1 - \sigma/2$.  Starting with any $y^0$ in $Y$, we generate a sequence $y^0, y^1, ...$ in $Y$ according to:
%\begin{equation}\label{5.2.1}
%y^{r+1}=[y^r+\alpha^r\nabla d(y^r)]^+_Y,
%\end{equation}
%where $\alpha^r$ is any scalar exceeding $\epsilon_1$ for which $y^{r+1}$ given by (\ref{5.2.1}) satisfies
%\begin{equation}\label{5.2.2}
%d(y^{r+1})-d(y^r)\ge \epsilon_2 \|y^{r+1}-y^r\|^2.
%\end{equation}
%(There are many ways of choosing the stepsizes $\alpha^r$.  For example, one can set $\alpha^r = \epsilon_1$ for all $r$, as described in \cite{[Gol64]} and \cite{[LeP65]}, or set $\alpha^r$ according to the Armijo--like rule given in \cite{[1]}.)
%
%The gradient projection algorithm has been analyzed
%extensively, but most of the existing analyses assume the objective function to be in some sense strongly concave (or strongly convex if we are minimizing), which is not the case with $d$.  Below, we show that this algorithm  converges at least linearly when applied to
%solve this special case of (\ref{2.3})--(\ref{2.2}).  Similar to the proof of Theorem 6.1, the key lies in using Theorem 4.1 to obtain an estimate of the optimality gap $f(x^*) - d(y^r)$ similar to (\ref{6.3}) (see (\ref{7.3})).  Combining this estimate with an estimate of $d(y^r) - d(y^{r+1})$ given by (\ref{5.2.2}) completes the proof.
%
%
%\pn
%{\bf Theorem 7.1.} Let $\{y^r\}$ be a sequence generated by the dual gradient projection algorithm (\ref{5.2.1})--(\ref{5.2.2}). Then, $\{d(y^r)\}$ converges at least linearly to $f(x^*)$, $\{x(y^r)\}$ converges at least linearly to $x^*$, and
%$\{ y^r \}$ converges at least linearly to an element of $Y^*$.
%\pn
%{\bf Proof.} First we show that there exist a positive scalar $\tau'$ and an index $\bar r$ such that
%\begin{equation}\label{7.3}
%f(x^*) -  d(y^{r+1}) \le \tau' \| y^{r+1}  -  y^r\|^2 \qquad \forall r\ge \bar r.
%\end{equation}
% Since $\{d(y^r)\}$ is bounded above (by, for example, $f(x^*)$) and $\epsilon_2 > 0$,  (\ref{5.2.2}) implies that $\{d(y^r)\}$ is nondecreasing and $\|y^{r+1}-y^r\|\rightarrow 0$. Since, by (\ref{5.2.1}) and a certain property of the projection operator (cf.\ [9, Lemma 1]),
%\begin{equation}
%\|y^r-[y^r+ \nabla d(y^r)]^+_Y\|
%\le \frac{1}{\min\{1,\alpha^r\}}\|y^r-[y^r+\alpha^r\nabla d(y^r)]^+_Y\|
%\le \frac{1}{\min\{1,\epsilon_1\}}\|y^{r+1}-y^r\|,\label{5.2.4}
%\end{equation}
%for all $r$, this implies $y^r-[y^r+ \nabla d(y^r)]^+_Y \rightarrow 0$ so, by Theorem 4.1, there exists a positive scalar $\tau$ and an index $\bar r$ such that, for each $r \ge \bar r$, there is an $\bar y^r \in Y^*$ satisfying
%\begin{equation}\label{5.2.5}
%\|x(y^r)-x^*\| + \|\bar y^r - y^r\| \le \tau \|y^r-[y^r+ \nabla d(y^r)]^+_Y\|.
%\end{equation}
%For each such $r$, since $y^{r+1}$ is obtained by projecting $y^r + \alpha^r \nabla d(y^r)$
%onto $Y$ (cf.\ (\ref{5.2.1})) and $\bar y^r \in Y$, we have
%\[
%\langle y^{r+1} - y^r - \alpha^r \nabla d(y^r) , \bar y^r - y^{r+1} \rangle \ge 0.
%\]
%Also, by the Mean Value Theorem, there exists some $\psi^r$ lying on the line segment joining $y^{r+1}$ with $\bar y^r$ such that
%\[
%d(\bar y^r) - d(y^{r+1}) = \langle \nabla d(\psi^r) , \bar y^r - y^{r+1} \rangle,
%\]
%which, combined with the above relation and the strong duality relation $f(x^*) = d(\bar y^r)$, yields
%\begin{eqnarray}
%f(x^*) -  d(y^{r+1})
%&=& \langle \nabla d(\psi^r) , \bar y^r - y^{r+1} \rangle  \nonumber\\
%&\le& \langle \nabla d(\psi^r)  - \nabla d(y^r)
%+ {1 \over \alpha^r} ( y^{r+1} - y^r ) , \bar y^r - y^{r+1} \rangle \nonumber\\
%&\le& \left( \| \nabla d(\psi^r)  -  \nabla d(y^r)\|
%+ {1 \over \alpha^r} \| y^{r+1} - y^r\| \right)\| \bar y^r - y^{r+1}\|  \nonumber\\
%&\le& \left( L \| \psi^r  -  y^r\|
%+ {1 \over \alpha^r} \|y^{r+1} - y^r\| \right) \| \bar y^r - y^{r+1}\|  \nonumber\\
%&\le&  \left( L \|y^{r+1}  -  y^r\| + L \|\bar y^r - y^r\|
%+ {1 \over \alpha^r} \|y^{r+1} - y^r\| \right) \|\bar y^r - y^{r+1}\|  \nonumber\\
%&\le& \left(\left(L +{1 \over \alpha^r}\right)\| y^{r+1}  -  y^r\| + L \|\bar y^r - y^r\|
%\right)  \left(\|\bar y^r - y^r\| + \|y^r - y^{r+1}\| \right)       \nonumber\\
%&\le& \tau'\|y^{r+1} - y^r\|^2,  \nonumber
%\end{eqnarray}
%where the third inequality follows from the fact $\nabla d$ is Lipschitz continuous with Lipschitz constant $L$; the fourth inequality follows from the fact that $\psi^r$ lies between $y^{r+1}$ and $\bar y^r$; the last inequality follows from (\ref{5.2.4})--(\ref{5.2.5}) and $\alpha^r \ge \epsilon_1$, with $\tau' = (L + 1/ \epsilon_1 + L \tau / \min\{1,\epsilon_1\})(\tau /\min\{1,\epsilon_1\} +1)$. Thus (\ref{7.3}) holds with the given $\bar r$ and $\tau'$.
%
%Combining (\ref{5.2.2}) with (\ref{7.3}) and rearranging terms yields
%\[
%f(x^*) - d(y^{r+1})\le \frac{\tau'}{\tau' + \epsilon_2}
%\left(f(x^*) - d(y^r)\right)\qquad \forall r\ge \bar r.
%\]
%This shows that $\{d(y^r)\}$ converges at least linearly to $f(x^*)$.  Then, by (\ref{5.2.2}),  $\{y^r\}$ converges at least linearly. Since $d(y^r) \to f(x^*)$ and $y^r \in Y$ for all $r$, the limit point of $\{y^r\}$ is an element of $Y^*$.  Also, since $\{y^r\}$ converges at least linearly, then $\|y^r-y^{r+1}\|\to 0$ at least linearly and it follows from (\ref{5.2.4})--(\ref{5.2.5}) that $x(y^r)\to x^*$ also at least linearly.   \QED
%
%
%\newsection{\bf Concluding Remarks}
%
%\indent
%
%In this paper, we proved a local error bound for the dual of a problem of minimizing a strictly convex function subject to linear constraints.  By using this result, we  showed that a number of dual ascent methods, including dual coordinate ascent methods, certain dual gradient
%methods and a dual gradient projection algorithm, converge at least linearly.
%
%We note that, by combining the analysis in
%this paper with that in [16], the above results
%can be extended to a more general problem in which the linear function $y \mapsto\langle y, q \rangle$ is replaced by any function of the form  $y \mapsto -g(Dy)$, with $D$  a matrix of dimension $l \times m$ and $g$ a closed proper convex functions in $\Re^l$ such that
%$\hbox{dom } g$ is open and $\nabla^2 g$ is defined  and positive definite on $\hbox{dom } g$.  This yields the saddle point problem
%\[
%\max_{y \in Y} \min_{x\in X} \  - g(Dy)   - \langle y, Ex \rangle + f(x),
%\]
%which is symmetric in $x$ and in $y$.  An extension of our error bound results to such a problem and its generalization to a parametric convex-concave minimax problem was recently given by Li [13].
%
%We note that, with a more careful argument, it can be shown that $x(y)$ the projected gradient $[y + \nabla d(y)]^+_Y$ have a certain active constraint identification property for, respectively, the primal and the dual problem.   More precisely, let $X$ and $Y$ be of the form (\ref{4.1}) and (\ref{4.2}) respectively.  We say that an index set $I \subseteq \{1,...,h\}$ is \underbar{primal active} at an $y\in Y$ if there exists some multiplier vector $\lambda\in\Re^h$ satisfying (\ref{4.14e}) and (\ref{4.14f}) such that
%\[
%A_i x(y) = a_i\quad \forall i\in I, \qquad
%\lambda_i = 0\quad \forall i\not\in I.
%\]
%Analogously, we say that an index set $J \subseteq \{1,...,k\}$ is \underbar{dual active} at an $y\in Y$ if there exists some multiplier vector $\mu\in\Re^k$ satisfying (\ref{4.14g}) and (\ref{4.14h}) such that
%\[
%B_j [y + \nabla d(y)]^+_Y = b_j \quad \forall j\in J, \qquad
%\mu_j = 0\quad \forall j\not\in J.
%\]
%Then, it can be shown by using Lemma 3.2(a) and a result of Hoffman [Hof52], that, for any $y\in Y$ with $d(y)$ bounded and $y - [y + \nabla d(y)]^+_Y $ sufficiently small, any pair of indices $I$ and $J$ that are, respectively, primal and dual active at $y$ are also primal and dual active at some element of $Y^*$.  Such an identification property is  very useful in the design of active--set algorithms.
%
%An interesting open question concerns the convergence of the dual sequence generated by the BCR methods of Sections 5 and 6.  As we observed, this sequence need not be convergent in general, but can the methods be modified so to ensure the convergence of this sequence?
%
%\bigskip
%\pn
%{\bf Acknowledgement:} We thank Professor W.\ Li and an anonymous referee for suggesting the use of Robinson's result (i.e., Lemma 4.1) as a means to simplify the proof of Theorem 4.1.  We thank the same referee for other helpful suggestions.

\vfill
\eject


\begin{thebibliography}{ TL 99}

\bibitem {bertsekas} Bertsekas, D.P.: {Nonlinear Programming}. Athena Scientific (2010).

\bibitem{[2]} Bertsekas, D.\ P.\  and Gafni, E.: Projection
methods for variational inequalities with application to the traffic
assignment problem. { Math. Prog. Study.} 17, 139--159  (1982)

\bibitem{[4]} Bertsekas, D.\ P.\ and  Gallager,  R.: { Data Networks}. Prentice--Hall, Englewood Cliffs, New Jersey.  (1987)


\bibitem{[3]} Bertsekas, D.\ P., Hosein, P.\ A., and Tseng, P.:
Relaxation methods for network flow problems with convex arc costs.
{SIAM J. Control Optim.} 25, 1219--1243 (1987)


\bibitem{[5]}  Bertsekas, D.\ P.\ and Tsitsiklis, J.\ N.: { Parallel and Distributed Computation: Numerical Methods}. Prentice--Hall, Englewood Cliffs, New Jersey (1989)

\bibitem{Boley} Boley, D.: Linear convergence of ADMM on a model problem. TR 12-009, Department of
Computer Science and Engineering, University of Minnesota (2012)


\bibitem{boyd}
Boyd, S., Parikh, N., Chu, E., Peleato, B.\ and Eckstein, J.:
Distributed Optimization and Statistical Learning via the
Alternating Direction Method of Multipliers. Foundations and Trends
in Machine Learning, Michael Jordan, Editor in Chief, 3, 1--122
(2011)

\bibitem{[6]} Bregman, L.\ M.:
The relaxation method of finding the common point of convex sets and
its application to the solution of problems in convex programming.
{USSR Comp. Math. and Math. Physics} 7,  200--217 (1967)


\bibitem {latent} Chandrasekaran, V., Parrilo, P., and Willsky, A.:  Latent variable graphical model via convex optimization. Preprint. (2010)

\bibitem {[7]} Cottle, R.\ W.\, Duvall, S.\ G.,
and Zikan, K.: A Lagrangian relaxation algorithm for the constrained
matrix problem.  {Naval Res. Logistics Quarterly.} 33, 55--76 (1986)

\bibitem {[8]} De Pierro, A.\ R.\ and Iusem, A.\ N.: On the convergence properties of Hildreth's quadratic programming algorithm. { Math. Prog.} 47,  37--51  (1990)

\bibitem{Yin}Deng, W.\ and Yin, W.: On the global linear convergence of alternating direction
methods. Preprint. (2012)

\bibitem {douglas-rachford} Douglas, J. and Rachford, H.H.: On the numerical solution of the heat conduction problem in 2 and 3 space variables. {Transactions of the American Mathematical Society.} 82, 421-439  (1956)

\bibitem {eckstein} Eckstein, J.: {Splitting methods for monotone operators with applications to parallel optimization.} Ph.D Thesis, Operations Research Center, MIT. (1989)


\bibitem{eckstein-bertsekas}Eckstein, J.\ and Bertsekas, D.P.:
On the Douglas-Rachford splitting method and the proximal point
algorithm for maximal monotone operators. Mathematical
Programming.55, 293-318 (1992)

\bibitem {eckstein10} Eckstein, J.\ and Svaiter, B.F.:
General projective splitting methods for sums of maximal monotone
operators. SIAM Journal on Control and Optimization. 48, 787--811
(2010)



\bibitem{Ga83}  {Gabay, D.}: { Application of the method of multipliers to
varuational inequalities}, In: Fortin, M., Glowinski, R., eds.,
Augmented Lagrangian methods: Application to the numerical solution
of Boundary-Value Problem, North-Holland,
 Amsterdam, The Netherlands. 299-331 (1983)


\bibitem{Gab76} {Gabay, D.\ and  Mercier, B.}: { A dual algorithm for the
                solution of nonlinear variational problems via
                finite-element approximations}. Computer and Mathematics with Applications. 2,
                17-40 (1976)

\bibitem{Glow84} {Glowinski, R.}: { Numerical methods for nonlinear variational problems}.
         Springer-Verlag, New York, Berlin, Heidelberg,
                Tokyo (1984)

\bibitem{Glt89} {  Glowinski, R.\ and Le Tallec, P.}: Augmented Lagrangian
                and operator splitting methods in nonlinear mechanics. SIAM Studies
               in Applied Mathematics, Philadelphia, PA. (1989)

\bibitem{goldfarb-ma}  Goldfarb, D.\ and Ma, S.: Fast multiple splitting algorithms for convex optimization. Arxiv
preprint arXiv:0912.4570 (2009)

\bibitem {goldfarb-ma-scheinberg}  Goldfarb, D., Ma, S.\ and Scheinberg, K.: Fast alternating linearization methods for minimizing the sum of two convex functions. Arxiv preprint arXiv:0912.4571 (2009)


\bibitem {[Gol64]} Goldstein, A.\ A.: Convex programming in
hilbert space. {Bull.\ Am.\ Math.\ Soc.} 70, 709--710 (1964)

\bibitem{UCLA} Goldstein, T., O'Donoghue, B.\ and Setzer, S.: Fast alternating direction optimization methods.
CAM report 12-35, UCLA, (2012).

\bibitem{HeTY12}{  He, B.\;S.,  Tao, M.\ and  Yuan, X.M.}: { Alternating direction method with gaussian back substitution for separable
convex programming}.  SIAM J. Optim. 22, 313-340 (2012)

\bibitem{HeYuan12} { He, B.\;S.\ and Yuan, X.\;M.}: { On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method}. SIAM J. Numer. Anal. 50, 700-709 (2012)



\bibitem {[10]} Herman, G.\ T.: {Image Reconstruction from Projection: The Fundamentals of Computerized Tomography}. Academic Press, New York. (1980)

\bibitem {Hoffman} Hoffman, A.\ J.: {On Approximate Solutions of Systems of Linear Inequalities}. J. Res. Nat. Bur. Standards. 49, 263-265 (1952)


\bibitem {[11]} Iusem, A.\ N.: On dual convergence and the rate of primal convergence of bregman's convex programming method. {SIAM J. Control Optim.} 1, 401--423 (1991)


\bibitem{KoMe} {Kontogiorgis, S.\ and  Meyer, R.~R.}: { A variable-penalty alternating
directions method for convex optimization}, Mathematical
Programming. 83, 29-53 (1998)


\bibitem {[12]} Lamond, B., and Stewart, N.\ F.:
Bregman's balancing method.
{Transportation Res.} 15B, 239--248  (1981)

\bibitem {[LeP65]} Levitin, E.\ S.\ and Poljak, B.\ T.: Constrained
minimization methods. { Z.\ Vycisl.\ Mat.\ i Mat.\ Fiz.} 6, 787-823 (1965).
English translation in { USSR Comput.\ Math.\ Phys.} 6,  1--50 (1965)

%\bibitem {[13]} Li, W.:  Error Bounds for Solutions of Parametric Convex-Concave Minimax Problems.
%To appear in {Proc. of the International Conf. on Parametric Optim. and Related Topics III}, G\"ustrow, Germany.


\bibitem{LionsMercier}
Lions, P.\ L., and Mercier., B.: Splitting algorithms for the sum of
two nonlinear operators. {SIAM Journal on Numerical Analysis}, 16,
964--979, (1979)



\bibitem {[14]}
 Lin, Y.\ Y., and Pang, J.-S.: Iterative methods for large convex quadratic programs: a survey.
 { SIAM J. Control Optim.}
18, 383-411 (1987)



\bibitem {[15]} Luo, Z.-Q., and Tseng, P.:
On the convergence of the coordinate descent method for convex differentiable minimization.
{ J. Optim. Theory and Appl.}  72, 7--35  (1992)

\bibitem
{[16]} Luo, Z.-Q., and Tseng, P.: On the
Linear convergence of descent methods for convex essentially smooth minimization. {
SIAM J. Control Optim.} 30, 408-425 (1992)

\bibitem {luo-tseng} Luo, Z.-Q.\ and Tseng, P.:   On the convergence rate of
dual ascent methods for strictly convex minimization. {Mathematics
of Operations Research} 18, 846--867 (1993)

\bibitem{mashiqian} Ma, S.: Alternating proximal gradient method for convex minimization. Preprint (2012)


\bibitem{[17]}
 Mangasarian, O.\ L., and Shiau, T.-H.: Lipschitz
Continuity of solutions of linear inequalities, programs and complementarity problems.  {
SIAM J. Control Optim}. 25 583--595 (1987)


\bibitem{[19]} Ohuchi, A., and Kaji, I.: Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs. { Networks}  14, 515--530 (1984)

\bibitem {[20]} Ortega, J.\ M., and Rheinboldt, W.\ C.: { Iterative
Solution of Nonlinear Equations in Several Variables}.
Academic Press, New York, New York.  (1970)

\bibitem {[21]} Pang, J.-S.: On the convergence of dual ascent methods for large scale linearly constrained optimization problems. The University of Texas, School of Management,
Dallas, Texas.  (1984)

\bibitem {[22]} Pang, J.-S.: A posteriori
error bounds for the linearly--constrained variational
inequality problem. { Math. Oper. Res.}
12, 474--484 (1987)


\bibitem {[25]} Rockafellar, R.\ T.: { Convex
Analysis}, Princeton
University Press, Princeton, New Jersey.  (1970)

\bibitem {[26]} Schneider, M.\ H., and Zenios, S.\ A.: A comparative study of algorithms for matrix balancing. { Oper. Res.} 38, 439--455  (1990)

\bibitem {[27]} Stephenson, D.: { Pipeflow Analysis}, Elsevier, Amsterdam.  (1984)

\bibitem{TaoYuan} {Tao, M.\  and  Yuan, X.M.}: { Recovering low-rank and sparse components
of matrices from incomplete and noisy observations}. SIAM J.\ Optim.
21, 57-81 (2011)


\bibitem{lasso}
Tibshirani, R.: Regression shrinkage and selection via the Lasso. { Jourbal of the Royal Statistical Society} Ser.\ B. 58, 267-288 (1996)

\bibitem{[30]}
 Tseng, P.:  Dual ascent methods for problems with
strictly convex costs and linear constraints: a unified approach.
{SIAM J. Control Optim.} 28, 214-242 (1990)


\bibitem{tseng09}
Tseng, P.: Approximation accuracy, gradient methods, and error bound for structured convex optimization. Technical report. (2009)



\bibitem{[28]}
 Tseng, P., and Bertsekas D.\ P.: Relaxation methods for problems with strictly convex separable costs and linear constraints. { Math. Prog.} 38, 303--321  (1987)

\bibitem{[29]}
 Tseng, P., and Bertsekas D.\ P.: Relaxation methods for problems with strictly convex costs and linear constraints. { Math. Oper. Res.} 16, 462--481 (1991)


\bibitem{[31]} Ventura, J.\ A., and Hearn, D.\ W.:  Computational development of a Lagrangian dual approach for quadratic networks. University of Florida, Industrial and Systems Engineering Department Report 88--14  (1988)

\bibitem{WangYuan2012}
Wang, X.\ F., and Yuan, X.\ M.: The linearized alternating direction
method of multipliers for dantzig selector. SIAM Journal on
Scientific Computing, 34, 2792--2811, (2012).

\bibitem{YangZhang2011}
Yang, J. \ F.,  and Zhang, Y.: Alternating direction algorithms for
$l_1$-problems in compressive
  sensing. {SIAM Journal on Scientific Computing}, 33, 250--278 (2011).


\bibitem{group-lasso}
Yuan, M.\, and Lin, Y.:  Model selection and estimation in
regression with grouped variables. { Journal of the Royal
Statistical Society: Series B (Statistical Methodology)}. 68, 49-67
(2006)


%\bibitem{DR56} {  J. Douglas and H. H. Rachford}, { On the numerical solution of the
%               heat conduction problem in 2 and 3 space
%               variables}, Transactions of the American Mathematical Society, 82 (1956), pp. 421-439.




\bibitem {luo-zhang}  Zhang, H., Jiang, J.J.\ and Luo, Z.-Q.: On the linear convergence of a
proximal gradient  method for a class of nonsmooth convex
minimization problems. Preprint. (2012)

\bibitem{[32]} Zenios, S.\ A., and Mulvey, J.\ M.:  Relaxation techniques for strictly convex network problems. { Ann. Oper. Res.} 5,  517--538  (1986)



\bibitem {rpca} Zhou, Z., Li, X., Wright, J., Candes, E.J., and Ma, Y.:  Stable principal component pursuit. {Proceedings of 2010 IEEE International Symposium on Information Theory} (2010)

\end{thebibliography}


\end{document}

1208.3922.extracted_bib
\begin{thebibliography}{ TL 99}

\bibitem {bertsekas} Bertsekas, D.P.: {Nonlinear Programming}. Athena Scientific (2010).

\bibitem{[2]} Bertsekas, D.\ P.\  and Gafni, E.: Projection
methods for variational inequalities with application to the traffic
assignment problem. { Math. Prog. Study.} 17, 139--159  (1982)

\bibitem{[4]} Bertsekas, D.\ P.\ and  Gallager,  R.: { Data Networks}. Prentice--Hall, Englewood Cliffs, New Jersey.  (1987)


\bibitem{[3]} Bertsekas, D.\ P., Hosein, P.\ A., and Tseng, P.:
Relaxation methods for network flow problems with convex arc costs.
{SIAM J. Control Optim.} 25, 1219--1243 (1987)


\bibitem{[5]}  Bertsekas, D.\ P.\ and Tsitsiklis, J.\ N.: { Parallel and Distributed Computation: Numerical Methods}. Prentice--Hall, Englewood Cliffs, New Jersey (1989)

\bibitem{Boley} Boley, D.: Linear convergence of ADMM on a model problem. TR 12-009, Department of
Computer Science and Engineering, University of Minnesota (2012)


\bibitem{boyd}
Boyd, S., Parikh, N., Chu, E., Peleato, B.\ and Eckstein, J.:
Distributed Optimization and Statistical Learning via the
Alternating Direction Method of Multipliers. Foundations and Trends
in Machine Learning, Michael Jordan, Editor in Chief, 3, 1--122
(2011)

\bibitem{[6]} Bregman, L.\ M.:
The relaxation method of finding the common point of convex sets and
its application to the solution of problems in convex programming.
{USSR Comp. Math. and Math. Physics} 7,  200--217 (1967)


\bibitem {latent} Chandrasekaran, V., Parrilo, P., and Willsky, A.:  Latent variable graphical model via convex optimization. Preprint. (2010)

\bibitem {[7]} Cottle, R.\ W.\, Duvall, S.\ G.,
and Zikan, K.: A Lagrangian relaxation algorithm for the constrained
matrix problem.  {Naval Res. Logistics Quarterly.} 33, 55--76 (1986)

\bibitem {[8]} De Pierro, A.\ R.\ and Iusem, A.\ N.: On the convergence properties of Hildreth's quadratic programming algorithm. { Math. Prog.} 47,  37--51  (1990)

\bibitem{Yin}Deng, W.\ and Yin, W.: On the global linear convergence of alternating direction
methods. Preprint. (2012)

\bibitem {douglas-rachford} Douglas, J. and Rachford, H.H.: On the numerical solution of the heat conduction problem in 2 and 3 space variables. {Transactions of the American Mathematical Society.} 82, 421-439  (1956)

\bibitem {eckstein} Eckstein, J.: {Splitting methods for monotone operators with applications to parallel optimization.} Ph.D Thesis, Operations Research Center, MIT. (1989)


\bibitem{eckstein-bertsekas}Eckstein, J.\ and Bertsekas, D.P.:
On the Douglas-Rachford splitting method and the proximal point
algorithm for maximal monotone operators. Mathematical
Programming.55, 293-318 (1992)

\bibitem {eckstein10} Eckstein, J.\ and Svaiter, B.F.:
General projective splitting methods for sums of maximal monotone
operators. SIAM Journal on Control and Optimization. 48, 787--811
(2010)



\bibitem{Ga83}  {Gabay, D.}: { Application of the method of multipliers to
varuational inequalities}, In: Fortin, M., Glowinski, R., eds.,
Augmented Lagrangian methods: Application to the numerical solution
of Boundary-Value Problem, North-Holland,
 Amsterdam, The Netherlands. 299-331 (1983)


\bibitem{Gab76} {Gabay, D.\ and  Mercier, B.}: { A dual algorithm for the
                solution of nonlinear variational problems via
                finite-element approximations}. Computer and Mathematics with Applications. 2,
                17-40 (1976)

\bibitem{Glow84} {Glowinski, R.}: { Numerical methods for nonlinear variational problems}.
         Springer-Verlag, New York, Berlin, Heidelberg,
                Tokyo (1984)

\bibitem{Glt89} {  Glowinski, R.\ and Le Tallec, P.}: Augmented Lagrangian
                and operator splitting methods in nonlinear mechanics. SIAM Studies
               in Applied Mathematics, Philadelphia, PA. (1989)

\bibitem{goldfarb-ma}  Goldfarb, D.\ and Ma, S.: Fast multiple splitting algorithms for convex optimization. Arxiv
preprint arXiv:0912.4570 (2009)

\bibitem {goldfarb-ma-scheinberg}  Goldfarb, D., Ma, S.\ and Scheinberg, K.: Fast alternating linearization methods for minimizing the sum of two convex functions. Arxiv preprint arXiv:0912.4571 (2009)


\bibitem {[Gol64]} Goldstein, A.\ A.: Convex programming in
hilbert space. {Bull.\ Am.\ Math.\ Soc.} 70, 709--710 (1964)

\bibitem{UCLA} Goldstein, T., O'Donoghue, B.\ and Setzer, S.: Fast alternating direction optimization methods.
CAM report 12-35, UCLA, (2012).

\bibitem{HeTY12}{  He, B.\;S.,  Tao, M.\ and  Yuan, X.M.}: { Alternating direction method with gaussian back substitution for separable
convex programming}.  SIAM J. Optim. 22, 313-340 (2012)

\bibitem{HeYuan12} { He, B.\;S.\ and Yuan, X.\;M.}: { On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method}. SIAM J. Numer. Anal. 50, 700-709 (2012)



\bibitem {[10]} Herman, G.\ T.: {Image Reconstruction from Projection: The Fundamentals of Computerized Tomography}. Academic Press, New York. (1980)

\bibitem {Hoffman} Hoffman, A.\ J.: {On Approximate Solutions of Systems of Linear Inequalities}. J. Res. Nat. Bur. Standards. 49, 263-265 (1952)


\bibitem {[11]} Iusem, A.\ N.: On dual convergence and the rate of primal convergence of bregman's convex programming method. {SIAM J. Control Optim.} 1, 401--423 (1991)


\bibitem{KoMe} {Kontogiorgis, S.\ and  Meyer, R.~R.}: { A variable-penalty alternating
directions method for convex optimization}, Mathematical
Programming. 83, 29-53 (1998)


\bibitem {[12]} Lamond, B., and Stewart, N.\ F.:
Bregman's balancing method.
{Transportation Res.} 15B, 239--248  (1981)

\bibitem {[LeP65]} Levitin, E.\ S.\ and Poljak, B.\ T.: Constrained
minimization methods. { Z.\ Vycisl.\ Mat.\ i Mat.\ Fiz.} 6, 787-823 (1965).
English translation in { USSR Comput.\ Math.\ Phys.} 6,  1--50 (1965)

%\bibitem {[13]} Li, W.:  Error Bounds for Solutions of Parametric Convex-Concave Minimax Problems.
%To appear in {Proc. of the International Conf. on Parametric Optim. and Related Topics III}, G\"ustrow, Germany.


\bibitem{LionsMercier}
Lions, P.\ L., and Mercier., B.: Splitting algorithms for the sum of
two nonlinear operators. {SIAM Journal on Numerical Analysis}, 16,
964--979, (1979)



\bibitem {[14]}
 Lin, Y.\ Y., and Pang, J.-S.: Iterative methods for large convex quadratic programs: a survey.
 { SIAM J. Control Optim.}
18, 383-411 (1987)



\bibitem {[15]} Luo, Z.-Q., and Tseng, P.:
On the convergence of the coordinate descent method for convex differentiable minimization.
{ J. Optim. Theory and Appl.}  72, 7--35  (1992)

\bibitem
{[16]} Luo, Z.-Q., and Tseng, P.: On the
Linear convergence of descent methods for convex essentially smooth minimization. {
SIAM J. Control Optim.} 30, 408-425 (1992)

\bibitem {luo-tseng} Luo, Z.-Q.\ and Tseng, P.:   On the convergence rate of
dual ascent methods for strictly convex minimization. {Mathematics
of Operations Research} 18, 846--867 (1993)

\bibitem{mashiqian} Ma, S.: Alternating proximal gradient method for convex minimization. Preprint (2012)


\bibitem{[17]}
 Mangasarian, O.\ L., and Shiau, T.-H.: Lipschitz
Continuity of solutions of linear inequalities, programs and complementarity problems.  {
SIAM J. Control Optim}. 25 583--595 (1987)


\bibitem{[19]} Ohuchi, A., and Kaji, I.: Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs. { Networks}  14, 515--530 (1984)

\bibitem {[20]} Ortega, J.\ M., and Rheinboldt, W.\ C.: { Iterative
Solution of Nonlinear Equations in Several Variables}.
Academic Press, New York, New York.  (1970)

\bibitem {[21]} Pang, J.-S.: On the convergence of dual ascent methods for large scale linearly constrained optimization problems. The University of Texas, School of Management,
Dallas, Texas.  (1984)

\bibitem {[22]} Pang, J.-S.: A posteriori
error bounds for the linearly--constrained variational
inequality problem. { Math. Oper. Res.}
12, 474--484 (1987)


\bibitem {[25]} Rockafellar, R.\ T.: { Convex
Analysis}, Princeton
University Press, Princeton, New Jersey.  (1970)

\bibitem {[26]} Schneider, M.\ H., and Zenios, S.\ A.: A comparative study of algorithms for matrix balancing. { Oper. Res.} 38, 439--455  (1990)

\bibitem {[27]} Stephenson, D.: { Pipeflow Analysis}, Elsevier, Amsterdam.  (1984)

\bibitem{TaoYuan} {Tao, M.\  and  Yuan, X.M.}: { Recovering low-rank and sparse components
of matrices from incomplete and noisy observations}. SIAM J.\ Optim.
21, 57-81 (2011)


\bibitem{lasso}
Tibshirani, R.: Regression shrinkage and selection via the Lasso. { Jourbal of the Royal Statistical Society} Ser.\ B. 58, 267-288 (1996)

\bibitem{[30]}
 Tseng, P.:  Dual ascent methods for problems with
strictly convex costs and linear constraints: a unified approach.
{SIAM J. Control Optim.} 28, 214-242 (1990)


\bibitem{tseng09}
Tseng, P.: Approximation accuracy, gradient methods, and error bound for structured convex optimization. Technical report. (2009)



\bibitem{[28]}
 Tseng, P., and Bertsekas D.\ P.: Relaxation methods for problems with strictly convex separable costs and linear constraints. { Math. Prog.} 38, 303--321  (1987)

\bibitem{[29]}
 Tseng, P., and Bertsekas D.\ P.: Relaxation methods for problems with strictly convex costs and linear constraints. { Math. Oper. Res.} 16, 462--481 (1991)


\bibitem{[31]} Ventura, J.\ A., and Hearn, D.\ W.:  Computational development of a Lagrangian dual approach for quadratic networks. University of Florida, Industrial and Systems Engineering Department Report 88--14  (1988)

\bibitem{WangYuan2012}
Wang, X.\ F., and Yuan, X.\ M.: The linearized alternating direction
method of multipliers for dantzig selector. SIAM Journal on
Scientific Computing, 34, 2792--2811, (2012).

\bibitem{YangZhang2011}
Yang, J. \ F.,  and Zhang, Y.: Alternating direction algorithms for
$l_1$-problems in compressive
  sensing. {SIAM Journal on Scientific Computing}, 33, 250--278 (2011).


\bibitem{group-lasso}
Yuan, M.\, and Lin, Y.:  Model selection and estimation in
regression with grouped variables. { Journal of the Royal
Statistical Society: Series B (Statistical Methodology)}. 68, 49-67
(2006)


%\bibitem{DR56} {  J. Douglas and H. H. Rachford}, { On the numerical solution of the
%               heat conduction problem in 2 and 3 space
%               variables}, Transactions of the American Mathematical Society, 82 (1956), pp. 421-439.




\bibitem {luo-zhang}  Zhang, H., Jiang, J.J.\ and Luo, Z.-Q.: On the linear convergence of a
proximal gradient  method for a class of nonsmooth convex
minimization problems. Preprint. (2012)

\bibitem{[32]} Zenios, S.\ A., and Mulvey, J.\ M.:  Relaxation techniques for strictly convex network problems. { Ann. Oper. Res.} 5,  517--538  (1986)



\bibitem {rpca} Zhou, Z., Li, X., Wright, J., Candes, E.J., and Ma, Y.:  Stable principal component pursuit. {Proceedings of 2010 IEEE International Symposium on Information Theory} (2010)

\end{thebibliography}