# On convergence rates of proximal alternating direction method of multipliers

Qinian Jin  Mathematical Sciences Institute, Australian National University,
Canberra, ACT 2601, Australia<EMAIL_ADDRESS>
(Date: March 3, 2023)

###### Abstract.

In this paper we consider from two different aspects the proximal alternating
direction method of multipliers (ADMM) in Hilbert spaces. We first consider
the application of the proximal ADMM to solve well-posed linearly constrained
two-block separable convex minimization problems in Hilbert spaces and obtain
new and improved non-ergodic convergence rate results, including linear and
sublinear rates under certain regularity conditions. We next consider proximal
ADMM as a regularization method for solving linear ill-posed inverse problems
in Hilbert spaces. When the data is corrupted by additive noise, we establish,
under a benchmark source condition, a convergence rate result in terms of the
noise level when the number of iteration is properly chosen.

###### Key words and phrases:

proximal alternating direction method of multipliers, linearly constrained
convex programming, linear inverse problems, convergence rates

##  1\. Introduction

The alternating direction method of multipliers (ADMM) was introduced and
developed in the 1970s by Glowinski, Marrocco [16] and Gabay, Mercier [15] for
the numerical solutions of partial differential equations. Due to its
decomposability and superior flexibility, ADMM and its variants have gained
renewed interest in recent years and have been widely used for solving large-
scale optimization problems that arise in signal/image processing, statistics,
machine learning, inverse problems and other fields, see [5, 17, 21]. Because
of their popularity, many works have been devoted to the analysis of ADMM and
its variants, see [5, 8, 10, 14, 19, 26, 33] for instance. In this paper we
will devote to deriving convergence rates of ADMM in two aspects: its
applications to solve well-posed convex optimization problems and its use to
solve linear ill-posed inverse problems as a regularization method.

In the first part of this paper we consider ADMM for solving linearly
constrained two-block separable convex minimization problems. Let
$\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ be real Hilbert spaces with
possibly infinite dimensions. We consider the convex minimization problem of
the form

$\displaystyle\begin{split}\mbox{minimize }&\quad H(x,y):=f(x)+g(y)\\\
\mbox{subject to }&\quad Ax+By=c,\end{split}$ (1.1)

where $c\in\mathcal{Z}$, $A:\mathcal{X}\to\mathcal{Z}$ and
$B:\mathcal{Y}\to\mathcal{Z}$ are bounded linear operators, and
$f:\mathcal{X}\to(-\infty,\infty]$ and $g:\mathcal{Y}\to(-\infty,\infty]$ are
proper, lower semi-continuous, convex functions. The classical ADMM solves
(1.1) approximately by constructing an iterative sequence via alternatively
minimizing the augmented Lagrangian function

${\mathscr{L}}_{\rho}(x,y,z):=f(x)+g(y)+\langle\lambda,Ax+By-c\rangle+\frac{\rho}{2}\|Ax+By-c\|^{2}$

with respect to the primal variables $x$ and $y$ and then updating the dual
variable $\lambda$; more precisely, starting from an initial guess
$y^{0}\in\mathcal{Y}$ and $\lambda^{0}\in\mathcal{Z}$, an iterative sequence
$\\{(x^{k},y^{k},\lambda^{k})\\}$ is defined by

$\displaystyle\begin{split}x^{k+1}&=\arg\min_{x\in\mathcal{X}}\left\\{f(x)+\langle\lambda^{k},Ax\rangle+\frac{\rho}{2}\|Ax+By^{k}-c\|^{2}\right\\},\\\
y^{k+1}&=\arg\min_{y\in\mathcal{Y}}\left\\{g(y)+\langle\lambda^{k},By\rangle+\frac{\rho}{2}\|Ax^{k+1}+By-c\|^{2}\right\\},\\\
\lambda^{k+1}&=\lambda^{k}+\rho(Ax^{k+1}+By^{k+1}-c),\end{split}$ (1.2)

where $\rho>0$ is a given penalty parameter. The implementation of (1.2)
requires to determine $x^{k+1}$ and $y^{k+1}$ by solving two convex
minimization problems during each iteration. Although $f$ and $g$ may have
special structures so that their proximal mappings are easy to be determined,
solving the minimization problems in (1.2) in general is highly nontrivial due
to the appearance of the terms $\|Ax\|^{2}$ and $\|By\|^{2}$. In order to
avoid this implementation issue, one may consider to add certain proximal
terms to the $x$-subproblem and $y$-subproblem in (1.2) to remove the terms
$\|Ax\|^{2}$ and $\|By\|^{2}$. For any bounded linear positive semi-definite
self-adjoint operator $D$ on a real Hilbert space $\mathcal{H}$, we will use
the notation

$\|u\|_{D}^{2}:=\langle z,Du\rangle,\quad\forall u\in\mathcal{H}.$

By taking two bounded linear positive semi-definite self-adjoint operators
$P:\mathcal{X}\to\mathcal{X}$ and $Q:\mathcal{Y}\to\mathcal{Y}$, we may add
the terms $\frac{1}{2}\|x-x^{k}\|_{P}^{2}$ and
$\frac{1}{2}\|y-y^{k}\|_{Q}^{2}$ to the $x$\- and $y$-subproblems in (1.2)
respectively to obtain the following proximal alternating direction method of
multipliers ([4, 9, 19, 20, 22, 33])

$\displaystyle\begin{split}x^{k+1}&=\arg\min_{x\in\mathcal{X}}\left\\{f(x)+\langle\lambda^{k},Ax\rangle+\frac{\rho}{2}\left\|Ax+By^{k}-c\right\|^{2}+\frac{1}{2}\|x-x^{k}\|_{P}^{2}\right\\},\\\
y^{k+1}&=\arg\min_{y\in\mathcal{Y}}\left\\{g(y)+\langle\lambda^{k},By\rangle+\frac{\rho}{2}\left\|Ax^{k+1}+By-c\right\|^{2}+\frac{1}{2}\|y-y^{k}\|_{Q}^{2}\right\\},\\\\[4.30554pt]
\lambda^{k+1}&=\lambda^{k}+\rho(Ax^{k+1}+By^{k+1}-c).\end{split}$ (1.3)

The advantage of (1.3) over (1.2) is that, with wise choices of $P$ and $Q$,
it is possible to remove the terms $\|Ax\|^{2}$ and $\|By\|^{2}$ and thus make
the determination of $x^{k+1}$ and $y^{k+1}$ much easier.

In recent years, various convergence rate results have been established for
ADMM and its variants in either ergodic or non-ergodic sense. In [19, 25] the
ergodic convergence rate

$\displaystyle|H(\bar{x}^{k},\bar{y}^{k})-H_{*}|=O\left(\frac{1}{k}\right)\quad\mbox{and}\quad\|A\bar{x}^{k}+B\bar{y}^{k}-c\|=O\left(\frac{1}{k}\right)$
(1.4)

has been derived in terms of the objective error and the constraint error,
where $H_{*}$ denotes the minimum value of (1.1), $k$ denotes the number of
iteration, and

$\bar{x}^{k}:=\frac{1}{k}\sum_{j=1}^{k}x^{j}\qquad\mbox{and}\qquad\bar{y}^{k}:=\frac{1}{k}\sum_{j=1}^{k}y^{j}$

denote the ergodic iterates of $\\{x^{k}\\}$ and $\\{y^{k}\\}$ respectively;
see also [4, Theorem 15.4]. A criticism on ergodic result is that it may fail
to capture the feature of the sought solution of the underlying problem
because ergodic iterate has the tendency to average out the expected property
and thus destroy the feature of the solution. This is in particular undesired
in sparsity optimization and low-rank learning. In contrast, the non-ergodic
iterate tends to share structural properties with the solution of the
underlying problem. Therefore, the use of non-ergodic iterates becomes more
favorable in practice. In [20] a non-ergodic convergence rate has been derived
for the proximal ADMM (1.3) with $Q=0$ and the result reads as

$\displaystyle\|x^{k+1}-x^{k}\|_{P}^{2}+\|B(y^{k+1}-y^{k})\|^{2}+\|\lambda^{k+1}-\lambda^{k}\|^{2}=o\left(\frac{1}{k}\right).$
(1.5)

By exploiting the connection with the Douglas-Rachford splitting algorithm,
the non-ergodic convergence rate

$\displaystyle|H(x^{k},y^{k})-H_{*}|=o\left(\frac{1}{\sqrt{k}}\right)\quad\mbox{and}\quad\|Ax^{k}+By^{k}-c\|=o\left(\frac{1}{\sqrt{k}}\right)$
(1.6)

in terms of the objective error and the constraint error has been established
in [8] for the ADMM (1.2) and an example has been provided to demonstrate that
the estimates in (1.6) are sharp. However, the derivation of (1.6) in [8]
relies on some unnatural technical conditions involving the convex conjugate
of $f$ and $g$, see Remark 2.1. Note that the estimate (1.5) implies the
second estimate in (1.6), however it does not imply directly the first
estimate in (1.6). In Section 2 we will show, by a simpler argument, that
similar estimate as in (1.5) can be established for the proximal ADMM (1.3)
with arbitrary positive semi-definite $Q$. Based on this result and some
additional properties of the method, we will further show that the non-ergodic
rate (1.6) holds for the proximal ADMM (1.3) with arbitrary positive semi-
definite $P$ and $Q$. Our result does not require any technical conditions as
assumed in [8].

In order to obtain faster convergence rates for the proximal ADMM (1.3),
certain regularity conditions should be imposed. In finite dimensional
situation, a number of linear convergence results have been established. In
[9] some linear convergence results of the proximal ADMM have been provided
under a number of scenarios involving the strong convexity of $f$ and/or $g$,
the Lipschitz continuity of $\nabla f$ and/or $\nabla g$, together with
further full row/column rank assumptions on $A$ and/or $B$. Under a bounded
metric subregularity condition, in particular under the assumption that both
$f$ and $g$ are convex piecewise linear-quadratic functions, a global linear
convergence rate has been established in [32] for the proximal ADMM (1.3) with

$\displaystyle P:=\tau_{1}I-\rho A^{*}A\succ 0\quad\mbox{and}\quad
Q:=\tau_{2}I-\rho B^{*}B\succ 0,$ (1.7)

where $A^{*}$ and $B^{*}$ denotes the adjoints of $A$ and $B$ respectively;
the condition (1.7) plays an essential role in the convergence analysis in
[32]. We will derive faster convergence rates for the proximal ADMM (1.3) in
the general Hilbert space setting. To this end, we need first to consider the
weak convergence of $\\{(x^{k},y^{k},\lambda^{k})\\}$ and demonstrate that
every weak cluster point of this sequence is a KKT point of (1.1). This may
not be an issue in finite dimensions. However, this is nontrivial in infinite
dimensional spaces because extra care is required to dealing with weak
convergence. In [6] the weak convergence of the proximal ADMM (1.3) has been
considered by transforming the method into a proximal point method and the
result there requires restrictive conditions, see [6, Lemma 3.4 and Theorem
3.1]. These restrictive conditions have been weakened later in [31] by using
machinery from the maximal monotone operator theory. We will explore the
structure of the proximal ADMM and show by an elementary argument that every
weak cluster point of $\\{(x^{k},y^{k},\lambda^{k})\\}$ is indeed a KKT point
of (1.1) without any additional conditions. We will then consider the linear
convergence of the proximal ADMM under a bounded metric subregularity
condition and obtain the linear convergence for any positive semi-definite $P$
and $Q$; in particular, we obtain the linear convergence of
$|H(x^{k},y^{k})-H_{*}|$ and $\|Ax^{k}+By^{k}-c\|$. We also consider deriving
convergence rates under a bounded Hölder metric subregularity condition which
is weaker than the bounded metric subregularity. This weaker condition holds
if both $f$ and $g$ are semi-algebraic functions and thus a wider range of
applications can be covered. We show that, under a bounded Hölder metric
subrigularity condition, among other things the convergence rates in (1.6) can
be improved to

$\|Ax^{k}+By^{k}-c\|=O(k^{-\beta})\quad\mbox{ and
}\quad|H(x^{k},y^{k})-H_{*}|=O(k^{-\beta})$

for some number $\beta>1/2$; the value of $\beta$ depends on the properties of
$f$ and $g$. To further weaken the bounded (Hölder) metric subregularity
assumption, we introduce an iteration based error bound condition which is an
extension of the one in [27] to the general proximal ADMM (1.3). It is
interesting to observe that this error bound condition holds under any one of
the scenarios proposed in [9]. Hence, we provide a unified analysis for
deriving convergence rates under the bounded (Hölder) metric subregularity or
the scenarios in [9]. Furthermore, we extend the scenarios in [9] to the
general Hilbert space setting and demonstrate that some conditions can be
weakened and the convergence result can be strengthened; see Theorem 2.11.

In the second part of this paper, we consider using ADMM as a regularization
method to solve linear ill-posed inverse problems in Hilbert spaces. Linear
inverse problems have a wide range of applications, including medical imaging,
geophysics, astronomy, signal processing, and more ([12, 18, 28]). We consider
linear inverse problems of the form

$\displaystyle Ax=b,\quad x\in\mathcal{C},$ (1.8)

where $A:\mathcal{X}\to\mathcal{H}$ is a compact linear operator between two
Hilbert spaces $\mathcal{X}$ and $\mathcal{H}$, $\mathcal{C}$ is a closed
convex set in $\mathcal{X}$, and $b\in\mbox{Ran}(A)$, the range of $A$. In
order to find a solution of (1.8) with desired properties, a priori available
information on the sought solution should be incorporated into the problem.
Assume that, under a suitable linear transform $L$ from $\mathcal{X}$ to
another Hilbert spaces $\mathcal{Y}$ with domain $\mbox{dom}(L)$, the feature
of the sought solution can be captured by a proper convex penalty function
$f:\mathcal{Y}\to(-\infty,\infty]$. One may consider instead of (1.8) the
constrained optimization problem

$\displaystyle\min\\{f(Lx):Ax=b,\ x\in\mathcal{C},\ x\in\mbox{dom}(L)\\}.$
(1.9)

A challenging issue related to the numerical resolution of (1.9) is its ill-
posedness in the sense that the solution of (1.9) does not depend continuously
on the data and thus a small perturbation on data can lead to a large
deviation on solutions. In practical applications, the exact data $b$ is
usually unavailable, instead only a noisy data $b^{\delta}$ is at hand with

$\|b^{\delta}-b\|\leq\delta$

for some small noise level $\delta>0$. To overcome ill-posedness,
regularization methods should be introduced to produce reasonable approximate
solutions; one may refer to [7, 12, 23, 29] for various regularization
methods.

The common use of ADMM to solve (1.9) with noisy data $b^{\delta}$ first
considers the variational regularization

$\displaystyle\min_{x\in\mathcal{C}}\left\\{\frac{1}{2}\|Ax-b^{\delta}\|^{2}+\alpha
f(Lx)\right\\},$ (1.10)

then uses the splitting technique to rewrite (1.10) into the form (1.1), and
finally applies the ADMM procedure to produce approximate solutions. The
parameter $\alpha>0$ is the so-called regularization parameter which should be
adjusted carefully to achieve reasonable good performance; consequently one
has to run ADMM to solve (1.10) for many different values of $\alpha$, which
can be time consuming.

In [21, 22] the ADMM has been considered to solve (1.9) directly to reduce the
computational load. Note that (1.9) can be written as

$\displaystyle\left\\{\begin{array}[]{lll}\min f(y)+\iota_{\mathcal{C}}(x)\\\
\mbox{subject to }Az=b,\ Lz-y=0,\ z-x=0,\
z\in\mbox{dom}(L),\end{array}\right.$

where $\iota_{\mathcal{C}}$ denotes the indicator function of $\mathcal{C}$.
With the noisy data $b^{\delta}$ we introduce the augmented Lagrangian
function

$\displaystyle{\mathscr{L}}_{\rho_{1},\rho_{2},\rho_{3}}(z,y,x,\lambda,\mu,\nu)$
$\displaystyle:=f(y)+\iota_{\mathcal{C}}(x)+\langle\lambda,Az-b^{\delta}\rangle+\langle\mu,Lz-y\rangle+\langle\nu,z-x\rangle$
$\displaystyle\quad\,+\frac{\rho_{1}}{2}\|Az-b^{\delta}\|^{2}+\frac{\rho_{2}}{2}\|Lz-y\|^{2}+\frac{\rho_{3}}{2}\|z-x\|^{2},$

where $\rho_{1}$, $\rho_{2}$ and $\rho_{3}$ are preassigned positive numbers.
The proximal ADMM proposed in [22] for solving (1.9) then takes the form

$\displaystyle\begin{split}&z^{k+1}=\arg\min_{z\in\mbox{dom}(L)}\left\\{{\mathscr{L}}_{\rho_{1},\rho_{2},\rho_{3}}(z,y^{k},x^{k},\lambda^{k},\mu^{k},\nu^{k})+\frac{1}{2}\|z-z^{k}\|_{Q}^{2}\right\\},\\\
&y^{k+1}=\arg\min_{y\in\mathcal{Y}}\left\\{{\mathscr{L}}_{\rho_{1},\rho_{2},\rho_{3}}(z^{k+1},y,x^{k},\lambda^{k},\mu^{k},\nu^{k})\right\\},\\\
&x^{k+1}=\arg\min_{x\in\mathcal{X}}\left\\{{\mathscr{L}}_{\rho_{1},\rho_{2},\rho_{3}}(z^{k+1},y^{k+1},x,\lambda^{k},\mu^{k},\nu^{k})\right\\},\\\
&\lambda^{k+1}=\lambda^{k}+\rho_{1}(Az^{k+1}-b^{\delta}),\\\
&\mu^{k+1}=\mu^{k}+\rho_{2}(Lz^{k+1}-y^{k+1}),\\\
&\nu^{k+1}=\nu^{k}+\rho_{3}(z^{k+1}-x^{k+1}),\end{split}$ (1.11)

where $Q$ is a bounded linear positive semi-definite self-adjoint operator.
The method (1.11) is not a 3-block ADMM. Note that the variables $y$ and $x$
are not coupled in
${\mathscr{L}}_{\rho_{1},\rho_{2},\rho_{3}}(z,y,x,\lambda,\mu,\nu)$. Thus,
$y^{k+1}$ and $x^{k+1}$ can be updated simultaneously, i.e.

$\displaystyle(y^{k+1},x^{k+1})=\arg\min_{y\in\mathcal{Y},x\in\mathcal{X}}\left\\{{\mathscr{L}}_{\rho_{1},\rho_{2},\rho_{3}}(z^{k+1},y,x,\lambda^{k},\mu^{k},\nu^{k})\right\\}.$

This demonstrates that (1.11) is a 2-block proximal ADMM.

It should be highlighted that all well-established convergence results on
proximal ADMM for well-posed optimization problems are not applicable to
(1.11) directly. Note that (1.11) uses the noisy data $b^{\delta}$. If the
convergence theory for well-posed optimization problems could be applicable,
one would obtain a solution of the perturbed problem

$\displaystyle\min\left\\{f(Lx):Ax=b^{\delta},\ x\in\mathcal{C},\
x\in\mbox{dom}(L)\right\\}$ (1.12)

of (1.9). Because $A$ is compact, it is very likely that
$b^{\delta}\not\in\mbox{Ran}(A^{*})$ and thus (1.12) makes no sense as the
feasible set is empty. Even if $b^{\delta}\in\mbox{Ran}(A^{*})$ and (1.12) has
a solution, this solution could be far away from the solution of (1.9) because
of the ill-posedness.

Therefore, if (1.11) is used to solve (1.9), better result can not be expected
even if larger number of iterations are performed. In contrast, like all other
iterative regularization methods, when (1.11) is used to solve (1.9), it shows
the semi-convergence property, i.e., the iterate becomes close to the sought
solution at the beginning; however, after a critical number of iterations, the
iterate leaves the sought solution far away as the iteration proceeds. Thus,
properly terminating the iteration is important to produce acceptable
approximate solutions. One may hope to determine a stopping index
$k_{\delta}$, depending on $\delta$ and/or $b^{\delta}$, such that
$\|x^{k_{\delta}}-x^{\dagger}\|$ is as small as possible and
$\|x^{k_{\delta}}-x^{\dagger}\|\to 0$ as $\delta\to 0$, where $x^{\dagger}$
denotes the solutio of (1.9). This has been done in our previous work [21, 22]
in which early stopping rules have been proposed for the method (1.11) to
render it into a regularization method and numerical results have been
reported to demonstrate the nice performance. However, the work in [21, 22]
does not provide convergence rates, i.e. the estimate on
$\|x^{k_{\delta}}-x^{\dagger}\|$ in terms of $\delta$. Deriving convergence
rates for iterative regularization methods involving general convex
regularization terms is a challenging question and only a limited number of
results are available. In order to derive a convergence rate of a
regularization method for ill-posed problems, certain source condition should
be imposed on the sought solution. In Section 3, under a benchmark source
condition on the sought solution, we will provide a partial answer to this
question by establishing a convergence rate result for (1.11) if the iteration
is terminated by an a priori stopping rule.

We conclude this section with some notation and terminology. Let $\mathcal{V}$
be a real Hilbert spaces. We use $\langle\cdot,\cdot\rangle$ and $\|\cdot\|$
to denote its inner product and the induced norm. We also use “$\to$” and
“$\rightharpoonup$” to denote the strong convergence and weak convergence
respectively. For a function $\varphi:\mathcal{V}\to(-\infty,\infty]$ its
domain is defined as
$\mbox{dom}(\varphi):=\\{x\in\mathcal{V}:\varphi(x)<\infty\\}$. If
$\mbox{dom}(\varphi)\neq\emptyset$, $\varphi$ is called proper. For a proper
convex function $\varphi:\mathcal{V}\to(-\infty,\infty]$, its modulus of
convexity, denoted by $\sigma_{\varphi}$, is defined to be the largest number
$c$ such that

$\varphi(tx+(1-t)y)+ct(1-t)\|x-y\|^{2}\leq t\varphi(x)+(1-t)\varphi(y)$

for all $x,y\in\mbox{dom}(\varphi)$ and $0\leq t\leq 1$. We always have
$\sigma_{\varphi}\geq 0$. If $\sigma_{\varphi}>0$, $\varphi$ is called
strongly convex. For a proper convex function
$\varphi:\mathcal{V}\to(-\infty,\infty]$, we use $\partial\varphi$ to denote
its subdifferential, i.e.

$\partial\varphi(x):=\\{\xi\in\mathcal{V}:\varphi(y)\geq\varphi(x)+\langle\xi,y-x\rangle\mbox{
for all }y\in\mathcal{V}\\},\quad x\in\mathcal{V}.$

Let
$\mbox{dom}(\partial\varphi):=\\{x\in\mathcal{V}:\partial\varphi(x)\neq\emptyset\\}$.
It is easy to see that

$\varphi(y)-\varphi(x)-\langle\xi,y-x\rangle\geq\sigma_{\varphi}\|y-x\|^{2}$

for all $y\in\mathcal{V}$, $x\in\mbox{dom}(\partial\varphi)$ and
$\xi\in\partial\varphi(x)$ which in particular implies the monotonicity of
$\partial\varphi$, i.e.

$\langle\xi-\eta,x-y\rangle\geq 2\sigma_{\varphi}\|x-y\|^{2}$

for all $x,y\in\mbox{dom}(\partial\varphi)$, $\xi\in\partial\varphi(x)$ and
$\eta\in\partial\varphi(y)$.

##  2\. Proximal ADMM for convex optimization problems

In this section we will consider the proximal ADMM (1.3) for solving the
linearly constrained convex minimization problem (1.1). For the convergence
analysis, we will make the following standard assumptions.

######  Assumption 2.1.

$\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ are real Hilbert spaces,
$A:\mathcal{X}\to\mathcal{Z}$ and $B:\mathcal{Y}\to\mathcal{Z}$ are bounded
linear operators, $P:\mathcal{X}\to\mathcal{X}$ and
$Q:\mathcal{Y}\to\mathcal{Y}$ are bounded linear positive semi-definite self-
adjoint operators, and $f:\mathcal{X}\to(-\infty,\infty]$ and
$g:\mathcal{Y}\to(-\infty,\infty]$ are proper, lower semi-continuous, convex
functions.

######  Assumption 2.2.

The problem (1.1) has a Karush-Kuhn-Tucker (KKT) point, i.e. there exists
$(\bar{x},\bar{y},\bar{\lambda})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$
such that

$-A^{*}\bar{\lambda}\in\partial f(\bar{x}),\quad-B^{*}\bar{\lambda}\in\partial
g(\bar{y}),\quad A\bar{x}+B\bar{y}=c.$

It should be mentioned that, to guarantee the proximal ADMM (1.3) to be well-
defined, certain additional conditions need to be imposed to ensure that the
$x$\- and $y$-subproblems do have minimizers. Since the well-definedness can
be easily seen in concrete applications, to make the presentation more
succinct we will not state these conditions explicitly.

By the convexity of $f$ and $g$, it is easy to see that, for any KKT point
$(\bar{x},\bar{y},\bar{\lambda})$ of (1.1), there hold

$\displaystyle 0$ $\displaystyle\leq
f(x)-f(\bar{x})+\langle\bar{\lambda},A(x-\bar{x})\rangle,\quad\forall
x\in\mathcal{X},$ $\displaystyle 0$ $\displaystyle\leq
g(y)-g(\bar{y})+\langle\bar{\lambda},B(y-\bar{y})\rangle,\quad\forall
y\in\mathcal{Y}.$

Adding these two equations and using $A\bar{x}+B\bar{y}-c=0$, it follows that

$\displaystyle 0\leq
H(x,y)-H(\bar{x},\bar{y})+\langle\bar{\lambda},Ax+By-c\rangle,\quad\forall(x,y)\in\mathcal{X}\times\mathcal{Y}.$
(2.1)

This in particular implies that $(\bar{x},\bar{y})$ is a solution of (1.1) and
thus $H_{*}:=H(\bar{x},\bar{y})$ is the minimum value of (1.1).

Based on Assumptions 2.1 and 2.2 we will analyze the proximal ADMM (1.3). For
ease of exposition, we set $\widehat{Q}:=\rho B^{*}B+Q$ and define

$\displaystyle Gu:=(Px,\widehat{Q}y,\lambda/\rho),\quad\forall
u:=(x,y,\lambda)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$

which is a bounded linear positive semi-definite self-adjoint operator on
$\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. Then, for any
$u:=(x,y,\lambda)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$ we have

$\|u\|_{G}^{2}:=\langle
u,Gu\rangle=\|x\|_{P}^{2}+\|y\|_{\widehat{Q}}^{2}+\frac{1}{\rho}\|\lambda\|^{2}.$

For the sequence $\\{u^{k}:=(x^{k},y^{k},\lambda^{k})\\}$ defined by the
proximal ADMM (1.3), we use the notation

$\displaystyle\Delta x^{k}:=x^{k}-x^{k-1},\ \ \Delta y^{k}:=y^{k}-y^{k-1},\ \
\Delta\lambda^{k}:=\lambda^{k}-\lambda^{k-1},\ \ \Delta u^{k}:=u^{k}-u^{k-1}.$

We start from the first order optimality conditions on $x^{k+1}$ and $y^{k+1}$
which by definition can be stated as

$\displaystyle\begin{split}-A^{*}\lambda^{k}-\rho
A^{*}(Ax^{k+1}+By^{k}-c)-P(x^{k+1}-x^{k})&\in\partial f(x^{k+1}),\\\
-B^{*}\lambda^{k}-\rho B^{*}(Ax^{k+1}+By^{k+1}-c)-Q(y^{k+1}-y^{k})&\in\partial
g(y^{k+1}).\end{split}$ (2.2)

By using $\lambda^{k+1}=\lambda^{k}+\rho(Ax^{k+1}+By^{k+1}-c)$ we may rewrite
(2.2) as

$\displaystyle\begin{split}-A^{*}(\lambda^{k+1}-\rho B\Delta y^{k+1})-P\Delta
x^{k+1}&\in\partial f(x^{k+1}),\\\ -B^{*}\lambda^{k+1}-Q\Delta
y^{k+1}&\in\partial g(y^{k+1})\end{split}$ (2.3)

which will be frequently used in the following analysis. We first prove the
following important result which is inspired by [19, Lemma 3.1] and [4,
Theorem 15.4].

######  Proposition 2.1.

Let Assumption 2.1 hold. Then for the proximal ADMM (1.3) there holds

$\displaystyle\sigma_{f}\|x^{k+1}-x\|^{2}+\sigma_{g}\|y^{k+1}-y\|^{2}$
$\displaystyle\leq H(x,y)-H(x^{k+1},y^{k+1})+\langle\lambda^{k+1}-\rho B\Delta
y^{k+1},Ax+By-c\rangle$
$\displaystyle\quad\,-\langle\lambda,Ax^{k+1}+By^{k+1}-c\rangle+\frac{1}{2}\left(\|u^{k}-u\|_{G}^{2}-\|u^{k+1}-u\|_{G}^{2}\right)$
$\displaystyle\quad\,-\frac{1}{2\rho}\|\Delta\lambda^{k+1}-\rho B\Delta
y^{k+1}\|^{2}-\frac{1}{2}\|\Delta x^{k+1}\|_{P}^{2}-\frac{1}{2}\|\Delta
y^{k+1}\|_{Q}^{2}$

for all $u:=(x,y,\lambda)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$,
where $\sigma_{f}$ and $\sigma_{g}$ denote the modulus of convexity of $f$ and
$g$ respectively.

###### Proof.

Let $\tilde{\lambda}^{k+1}:=\lambda^{k+1}-\rho B\Delta y^{k+1}$. By using
(2.3) and the convexity of $f$ and $g$ we have for any
$(x,y,\lambda)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$ that

$\displaystyle\sigma_{f}\|x^{k+1}-x\|^{2}+\sigma_{g}\|y^{k+1}-y\|^{2}$
$\displaystyle\leq f(x)-f(x^{k+1})+\langle\lambda^{k+1}-\rho B\Delta
y^{k+1},A(x-x^{k+1})\rangle+\langle P\Delta x^{k+1},x-x^{k+1}\rangle$
$\displaystyle\quad\,+g(y)-g(y^{k+1})+\langle\lambda^{k+1},B(y-y^{k+1})\rangle+\langle
Q\Delta y^{k+1},y-y^{k+1}\rangle$
$\displaystyle=H(x,y)-H(x^{k+1},y^{k+1})+\langle\tilde{\lambda}^{k+1},A(x-x^{k+1})+B(y-y^{k+1})\rangle$
$\displaystyle\quad\,+\langle P\Delta
x^{k+1},x-x^{k+1}\rangle+\langle\widehat{Q}\Delta y^{k+1},y-y^{k+1}\rangle$
$\displaystyle=H(x,y)-H(x^{k+1},y^{k+1})+\langle\tilde{\lambda}^{k+1},Ax+By-c\rangle$
$\displaystyle\quad\,-\langle\lambda,Ax^{k+1}+By^{k+1}-c\rangle+\langle\lambda-\tilde{\lambda}^{k+1},Ax^{k+1}+By^{k+1}-c\rangle$
$\displaystyle\quad\,+\langle P\Delta
x^{k+1},x-x^{k+1}\rangle+\langle\widehat{Q}\Delta y^{k+1},y-y^{k+1}\rangle.$

Since $\rho(Ax^{k+1}+By^{k+1}-c)=\Delta\lambda^{k+1}$ we then obtain

$\displaystyle\sigma_{f}\|x^{k+1}-x\|^{2}+\sigma_{g}\|y^{k+1}-y\|^{2}$
$\displaystyle\leq
H(x,y)-H(x^{k+1},y^{k+1})+\langle\tilde{\lambda}^{k+1},Ax+By-c\rangle-\langle\lambda,Ax^{k+1}+By^{k+1}-c\rangle$
$\displaystyle\quad\,+\frac{1}{\rho}\langle\lambda-\lambda^{k+1},\Delta\lambda^{k+1}\rangle+\frac{1}{\rho}\langle\lambda^{k+1}-\tilde{\lambda}^{k+1},\Delta\lambda^{k+1}\rangle$
$\displaystyle\quad\,+\langle P\Delta
x^{k+1},x-x^{k+1}\rangle+\langle\widehat{Q}\Delta y^{k+1},y-y^{k+1}\rangle.$

By using the polarization identity and the definition of $G$, it follows that

$\displaystyle\sigma_{f}\|x^{k+1}-x\|^{2}+\sigma_{g}\|y^{k+1}-y\|^{2}$
$\displaystyle\leq
H(x,y)-H(x^{k+1},y^{k+1})+\langle\tilde{\lambda}^{k+1},Ax+By-c\rangle-\langle\lambda,Ax^{k+1}+By^{k+1}-c\rangle$
$\displaystyle\quad\,+\frac{1}{2\rho}\left(\|\lambda^{k}-\lambda\|^{2}-\|\lambda^{k+1}-\lambda\|^{2}-\|\Delta\lambda^{k+1}\|^{2}\right)$
$\displaystyle\quad\,-\frac{1}{2\rho}\left(\|\lambda^{k}-\tilde{\lambda}^{k+1}\|^{2}-\|\lambda^{k+1}-\tilde{\lambda}^{k+1}\|^{2}-\|\Delta\lambda^{k+1}\|^{2}\right)$
$\displaystyle\quad\,+\frac{1}{2}\left(\|x^{k}-x\|_{P}^{2}-\|x^{k+1}-x\|_{P}^{2}-\|\Delta
x^{k+1}\|_{P}^{2}\right)$
$\displaystyle\quad\,+\frac{1}{2}\left(\|y^{k}-y\|_{\widehat{Q}}^{2}-\|y^{k+1}-y\|_{\widehat{Q}}^{2}-\|\Delta
y^{k+1}\|_{\widehat{Q}}^{2}\right)$
$\displaystyle=H(x,y)-H(x^{k+1},y^{k+1})+\langle\tilde{\lambda}^{k+1},Ax+By-c\rangle-\langle\lambda,Ax^{k+1}+By^{k+1}-c\rangle$
$\displaystyle\quad\,+\frac{1}{2}\left(\|u^{k}-u\|_{G}^{2}-\|u^{k+1}-u\|_{G}^{2}\right)-\frac{1}{2\rho}\left(\|\lambda^{k}-\tilde{\lambda}^{k+1}\|^{2}-\|\lambda^{k+1}-\tilde{\lambda}^{k+1}\|^{2}\right)$
$\displaystyle\quad\,-\frac{1}{2}\|\Delta
x^{k+1}\|_{P}^{2}-\frac{1}{2}\|\Delta y^{k+1}\|_{\widehat{Q}}^{2}.$

Using the definition of $\tilde{\lambda}^{k+1}$ gives

$\displaystyle\lambda^{k}-\tilde{\lambda}^{k+1}=-\Delta\lambda^{k+1}+\rho
B\Delta y^{k+1},\quad\lambda^{k+1}-\tilde{\lambda}^{k+1}=\rho B\Delta
y^{k+1}.$

Therefore

$\displaystyle\sigma_{f}\|x^{k+1}-x\|^{2}+\sigma_{g}\|y^{k+1}-y\|^{2}$
$\displaystyle\leq
H(x,y)-H(x^{k+1},y^{k+1})+\langle\tilde{\lambda}^{k+1},Ax+By-c\rangle-\langle\lambda,Ax^{k+1}+By^{k+1}-c\rangle$
$\displaystyle\quad\,+\frac{1}{2}\left(\|u^{k}-u\|_{G}^{2}-\|u^{k+1}-u\|_{G}^{2}\right)-\frac{1}{2\rho}\|\Delta\lambda^{k+1}-\rho
B\Delta y^{k+1}\|^{2}$ $\displaystyle\quad\,-\frac{1}{2}\|\Delta
x^{k+1}\|_{P}^{2}-\frac{1}{2}\|\Delta
y^{k+1}\|_{\widehat{Q}}^{2}+\frac{\rho}{2}\|B\Delta y^{k+1}\|^{2}.$

Since $\rho\|B\Delta y^{k+1}\|^{2}-\|\Delta
y^{k+1}\|_{\widehat{Q}}^{2}=-\|\Delta y^{k+1}\|_{Q}^{2}$, we thus complete the
proof. ∎

######  Corollary 2.2.

Let Assumption 2.1 and Assumption 2.2 hold and let
$\bar{u}:=(\bar{x},\bar{y},\bar{\lambda})$ be any KKT point of (1.1). Then for
the proximal ADMM (1.3) there holds

$\displaystyle\sigma_{f}\|x^{k+1}-\bar{x}\|^{2}+\sigma_{g}\|y^{k+1}-\bar{y}\|^{2}$
$\displaystyle\leq
H_{*}-H(x^{k+1},y^{k+1})-\langle\bar{\lambda},Ax^{k+1}+By^{k+1}-c\rangle$
$\displaystyle\quad\,+\frac{1}{2}\left(\|u^{k}-\bar{u}\|_{G}^{2}-\|u^{k+1}-\bar{u}\|_{G}^{2}\right)$
(2.4)

for all $k\geq 0$. Moreover, the sequence $\\{\|u^{k}-\bar{u}\|_{G}^{2}\\}$ is
monotonically decreasing.

###### Proof.

By taking $u=\bar{u}$ in Proposition 2.1 and using $A\bar{x}+B\bar{y}-c=0$ we
immediately obtain (2.2). According to (2.1) we have

$H(x^{k+1},y^{k+1})-H_{*}+\langle\bar{\lambda},Ax^{k+1}+By^{k+1}-c\rangle\geq
0.$

Thus, from (2.2) we can obtain

$\displaystyle\sigma_{f}\|x^{k+1}-\bar{x}\|^{2}+\sigma_{g}\|y^{k+1}-\bar{y}\|^{2}\leq\frac{1}{2}\left(\|u^{k}-\bar{u}\|_{G}^{2}-\|u^{k+1}-\bar{u}\|_{G}^{2}\right)$
(2.5)

which implies the monotonicity of the sequence
$\\{\|u^{k}-\bar{u}\|_{G}^{2}\\}$. ∎

We next show that $\|\Delta u^{k}\|_{G}^{2}=o(1/k)$ as $k\to\infty$. This
result for the proximal ADMM (1.3) with $Q=0$ has been established in [20]
based on a variational inequality approach. We will establish this result for
the proximal ADMM (1.3) with general bounded linear positive semi-definite
self-adjoint operators $P$ and $Q$ by a simpler argument.

######  Lemma 2.3.

Let Assumption 2.1 hold. For the proximal ADMM (1.3), the sequence
$\\{\|\Delta u^{k}\|_{G}^{2}\\}$ is monotonically decreasing.

###### Proof.

By using (2.3) and the monotonicity of $\partial f$ and $\partial g$, we can
obtain

$\displaystyle 0\leq$
$\displaystyle\left\langle-A^{*}(\Delta\lambda^{k+1}-\rho B\Delta y^{k+1}+\rho
B\Delta y^{k})-P\Delta x^{k+1}+P\Delta x^{k},\Delta x^{k+1}\right\rangle$
$\displaystyle+\left\langle-B^{*}\Delta\lambda^{k+1}-Q\Delta y^{k+1}+Q\Delta
y^{k},\Delta y^{k+1}\right\rangle$ $\displaystyle=$
$\displaystyle-\langle\Delta\lambda^{k+1},A\Delta x^{k+1}+B\Delta
y^{k+1}\rangle+\rho\langle B(\Delta y^{k+1}-\Delta y^{k}),A\Delta
x^{k+1}\rangle$ $\displaystyle-\langle P(\Delta x^{k+1}-\Delta x^{k}),\Delta
x^{k+1}\rangle-\langle Q(\Delta y^{k+1}-\Delta y^{k}),\Delta y^{k+1}\rangle.$

Note that

$\displaystyle A\Delta x^{k+1}+B\Delta
y^{k+1}=\frac{1}{\rho}(\Delta\lambda^{k+1}-\Delta\lambda^{k}).$

We therefore have

$\displaystyle 0$
$\displaystyle\leq-\frac{1}{\rho}\langle\Delta\lambda^{k+1},\Delta\lambda^{k+1}-\Delta\lambda^{k}\rangle-\rho\langle
B(\Delta y^{k+1}-\Delta y^{k}),B\Delta y^{k+1}\rangle$
$\displaystyle\quad\,+\langle B(\Delta y^{k+1}-\Delta
y^{k}),\Delta\lambda^{k+1}-\Delta\lambda^{k}\rangle$
$\displaystyle\quad\,-\langle P(\Delta x^{k+1}-\Delta x^{k}),\Delta
x^{k+1}\rangle-\langle Q(\Delta y^{k+1}-\Delta y^{k}),\Delta y^{k+1}\rangle.$

By the polarization identity we then have

$\displaystyle 0$
$\displaystyle\leq\frac{1}{2\rho}\left(\|\Delta\lambda^{k}\|^{2}-\|\Delta\lambda^{k+1}\|^{2}-\|\Delta\lambda^{k}-\Delta\lambda^{k+1}\|^{2}\right)$
$\displaystyle\quad\,+\frac{\rho}{2}\left(\|B\Delta y^{k}\|^{2}-\|B\Delta
y^{k+1}\|^{2}-\|B(\Delta y^{k}-\Delta y^{k+1})\|^{2}\right)$
$\displaystyle\quad\,+\frac{1}{2}\left(\|\Delta x^{k}\|_{P}^{2}-\|\Delta
x^{k+1}\|_{P}^{2}-\|\Delta x^{k}-\Delta x^{k+1}\|_{P}^{2}\right)$
$\displaystyle\quad\,+\frac{1}{2}\left(\|\Delta y^{k}\|_{Q}^{2}-\|\Delta
y^{k+1}\|_{Q}^{2}-\|\Delta y^{k}-\Delta y^{k+1}\|_{Q}^{2}\right)$
$\displaystyle\quad\,+\langle B(\Delta y^{k+1}-\Delta
y^{k}),\Delta\lambda^{k+1}-\Delta\lambda^{k}\rangle.$

With the help of the definition of $G$, we obtain

$\displaystyle 0$ $\displaystyle\leq\|\Delta u^{k}\|_{G}^{2}-\|\Delta
u^{k+1}\|_{G}^{2}-\|\Delta x^{k}-\Delta x^{k+1}\|_{P}^{2}-\|\Delta
y^{k}-\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\quad\,-\frac{\rho}{2}\left\|B(\Delta y^{k+1}-\Delta
y^{k})-\frac{1}{\rho}(\Delta\lambda^{k+1}-\Delta\lambda^{k})\right\|^{2}$

which completes the proof. ∎

######  Lemma 2.4.

Let Assumptions 2.1 and 2.2 hold and let
$\bar{u}:=(\bar{x},\bar{y},\bar{\lambda})$ be any KKT point of (1.1). For the
proximal ADMM (1.3) there holds

$\displaystyle\|\Delta
u^{k+1}\|_{G}^{2}\leq\left(\|u^{k}-\bar{u}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}\right)-\left(\|u^{k+1}-\bar{u}\|_{G}^{2}+\|\Delta
y^{k+1}\|_{Q}^{2}\right)$

for all $k\geq 1$.

###### Proof.

We will use (2.3) together with $-A^{*}\bar{\lambda}\in\partial f(\bar{x})$
and $-B^{*}\bar{\lambda}\in\partial g(\bar{y})$. By using the monotonicity of
$\partial f$ and $\partial g$ we have

$\displaystyle 0$
$\displaystyle\leq\left\langle-A^{*}(\lambda^{k+1}-\bar{\lambda}-\rho B\Delta
y^{k+1})-P\Delta x^{k+1},x^{k+1}-\bar{x}\right\rangle$
$\displaystyle\quad\,+\left\langle-B^{*}(\lambda^{k+1}-\bar{\lambda})-Q\Delta
y^{k+1},y^{k+1}-\bar{y}\right\rangle$
$\displaystyle=\langle\bar{\lambda}-\lambda^{k+1},Ax^{k+1}+By^{k+1}-c\rangle+\rho\langle
B\Delta y^{k+1},A(x^{k+1}-\bar{x})\rangle$ $\displaystyle\quad\,-\langle
P\Delta x^{k+1},x^{k+1}-\bar{x}\rangle-\langle Q\Delta
y^{k+1},y^{k+1}-\bar{y}\rangle.$

By virtue of $\rho(Ax^{k+1}+By^{k+1}-c\rangle=\Delta\lambda^{k+1}$ we further
have

$\displaystyle 0$
$\displaystyle\leq\frac{1}{\rho}\langle\bar{\lambda}-\lambda^{k+1},\Delta\lambda^{k+1}\rangle-\rho\langle
B\Delta y^{k+1},B(y^{k+1}-\bar{y})\rangle+\langle B\Delta
y^{k+1},\Delta\lambda^{k+1}\rangle$ $\displaystyle\quad\,-\langle P\Delta
x^{k+1},x^{k+1}-\bar{x}\rangle-\langle Q\Delta
y^{k+1},y^{k+1}-\bar{y}\rangle.$

By using the second equation in (2.3) and the monotonicity of $\partial g$ we
have

$\displaystyle 0$
$\displaystyle\leq\left\langle-B^{*}\Delta\lambda^{k+1}-Q\Delta
y^{k+1}+Q\Delta y^{k},\Delta y^{k+1}\right\rangle$
$\displaystyle=-\langle\Delta\lambda^{k+1},B\Delta y^{k+1}\rangle-\langle
Q(\Delta y^{k+1}-\Delta y^{k}),\Delta y^{k+1}\rangle$

which shows that

$\langle\Delta\lambda^{k+1},B\Delta y^{k+1}\rangle\leq-\langle Q(\Delta
y^{k+1}-\Delta y^{k}),\Delta y^{k+1}\rangle.$

Therefore

$\displaystyle 0\leq$
$\displaystyle\frac{1}{\rho}\langle\bar{\lambda}-\lambda^{k+1},\Delta\lambda^{k+1}\rangle-\langle\widehat{Q}\Delta
y^{k+1},y^{k+1}-\bar{y}\rangle-\langle P\Delta x^{k+1},x^{k+1}-\bar{x}\rangle$
$\displaystyle-\langle Q(\Delta y^{k+1}-\Delta y^{k}),\Delta y^{k+1}\rangle.$

By using the polarization identity we then obtain

$\displaystyle 0\leq$
$\displaystyle\frac{1}{2\rho}\left(\langle\lambda^{k}-\bar{\lambda}\|^{2}-\|\lambda^{k+1}-\bar{\lambda}\|^{2}-\|\Delta\lambda^{k+1}\|^{2}\right)$
$\displaystyle+\frac{1}{2}\left(\|y^{k}-\bar{y}\|_{\widehat{Q}}^{2}-\|y^{k+1}-\bar{y}\|_{\widehat{Q}}^{2}-\|\Delta
y^{k+1}\|_{\widehat{Q}}^{2}\right)$
$\displaystyle+\frac{1}{2}\left(\|x^{k}-\bar{x}\|_{P}^{2}-\|x^{k+1}-\bar{x}\|_{P}^{2}-\|\Delta
x^{k+1}\|_{P}^{2}\right)$ $\displaystyle+\frac{1}{2}\left(\|\Delta
y^{k}\|_{Q}^{2}-\|\Delta y^{k+1}\|_{Q}^{2}-\|\Delta y^{k+1}-\Delta
y^{k}\|_{Q}^{2}\right).$

Recalling the definition of $G$ we then complete the proof. ∎

######  Proposition 2.5.

Let Assumption 2.1 and Assumption 2.2 hold. Then for the proximal ADMM (1.3)
there holds $\|\Delta u^{k}\|_{G}^{2}=o(1/k)$ as $k\to\infty$.

###### Proof.

Let $\bar{u}$ be a KKT point of (1.1). From Lemma 2.4 it follows that

$\displaystyle\sum_{j=1}^{k}\|\Delta u^{j+1}\|_{G}^{2}$
$\displaystyle\leq\sum_{j=1}^{k}\left(\left(\|u^{j}-\bar{u}\|_{G}^{2}+\|\Delta
y^{j}\|_{Q}^{2}\right)-\left(\|u^{j+1}-\bar{u}\|_{G}^{2}+\|\Delta
y^{j+1}\|_{Q}^{2}\right)\right)$
$\displaystyle\leq\|u^{1}-\bar{u}\|_{G}^{2}+\|\Delta y^{1}\|_{Q}^{2}$ (2.6)

for all $k\geq 1$. By Lemma 2.3, $\\{\|\Delta u^{j+1}\|_{G}^{2}\\}$ is
monotonically decreasing. Thus

$\displaystyle\left(\frac{k}{2}+1\right)\|\Delta
u^{k+1}\|_{G}^{2}\leq\sum_{j=[k/2]}^{k}\|\Delta u^{j+1}\|_{G}^{2},$ (2.7)

where $[k/2]$ denotes the largest integer $\leq k/2$. Since (2) shows that

$\sum_{j=1}^{\infty}\|\Delta u^{j+1}\|_{G}^{2}<\infty,$

the right hand side of (2.7) must converge to $0$ as $k\to\infty$. Thus
$(k+1)\|\Delta u^{k+1}\|_{G}^{2}=o(1)$ and hence $\|\Delta
u^{k}\|_{G}^{2}=o(1/k)$ as $k\to\infty$. ∎

As a byproduct of Proposition 2.5 and Corollary 2.2, we can prove the
following non-ergodic convergence rate result for the proximal ADMM (1.3) in
terms of the objective error and the constraint error.

######  Theorem 2.6.

Let Assumption 2.1 and Assumption 2.2 hold. Consider the proximal ADMM (1.3)
for solving (1.1). Then

$\displaystyle|H(x^{k},y^{k})-H_{*}|=o\left(\frac{1}{\sqrt{k}}\right)\quad\mbox{and}\quad\|Ax^{k}+By^{k}-c\|=o\left(\frac{1}{\sqrt{k}}\right)$
(2.8)

as $k\to\infty$.

###### Proof.

Since

$\displaystyle\rho(Ax^{k}+By^{k}-c)=\Delta\lambda^{k}\quad\mbox{and}\quad\|\Delta\lambda^{k}\|^{2}\leq\rho\|\Delta
u^{k}\|_{G}^{2}$ (2.9)

we may use Proposition 2.5 to obtain the estimate
$\|Ax^{k}+By^{k}-c\|=o(1/\sqrt{k})$ as $k\rightarrow\infty$.

In the following we will focus on deriving the estimate of
$|H(x^{k},y^{k})-H_{*}|$. Let $\bar{u}:=(\bar{x},\bar{y},\bar{\lambda})$ be a
KKT point of (1.1). By using (2.2) we have

$\displaystyle H(x^{k},y^{k})-H_{*}$
$\displaystyle\leq-\langle\bar{\lambda},Ax^{k}+By^{k}-c\rangle+\frac{1}{2}\left(\|u^{k-1}-\bar{u}\|_{G}^{2}-\|u^{k}-\bar{u}\|_{G}^{2}\right)$
$\displaystyle=-\frac{1}{\rho}\langle\bar{\lambda},\Delta\lambda^{k}\rangle-\langle
u^{k-1}-\bar{u},G\Delta u^{k}\rangle-\frac{1}{2}\|\Delta u^{k}\|_{G}^{2}$
$\displaystyle\leq\frac{\|\bar{\lambda}\|}{\rho}\|\Delta\lambda^{k}\|+\|u^{k-1}-\bar{u}\|_{G}\|\Delta
u^{k}\|_{G}.$ (2.10)

By virtue of the monotonicity of $\\{\|u^{k}-\bar{u}\|_{G}^{2}\\}$ given in
Corollary 2.2 we then obtain

$\displaystyle H(x^{k},y^{k})-H_{*}$
$\displaystyle\leq\frac{\|\bar{\lambda}\|}{\rho}\|\Delta\lambda^{k}\|+\|u^{0}-\bar{u}\|_{G}\|\Delta
u^{k}\|_{G}$
$\displaystyle\leq\left(\|u^{0}-\bar{u}\|_{G}+\frac{\|\bar{\lambda}\|}{\sqrt{\rho}}\right)\|\Delta
u^{k}\|_{G}.$

On the other hand, by using (2.1) we have

$\displaystyle H(x^{k},y^{k})-H_{*}$
$\displaystyle\geq-\langle\bar{\lambda},Ax^{k}+By^{k}-c\rangle=-\frac{1}{\rho}\langle\bar{\lambda},\Delta\lambda^{k}\rangle$
$\displaystyle\geq-\frac{\|\bar{\lambda}\|}{\rho}\|\Delta\lambda^{k}\|\geq-\frac{\|\bar{\lambda}\|}{\sqrt{\rho}}\|\Delta
u^{k}\|_{G}.$

Therefore

$\displaystyle\left|H(x^{k},y^{k})-H_{*}\right|\leq\left(\|u^{0}-\bar{u}\|_{G}+\frac{\|\bar{\lambda}\|}{\sqrt{\rho}}\right)\|\Delta
u^{k}\|_{G}.$ (2.11)

Now we can use Proposition 2.5 to conclude the proof. ∎

######  Remark 2.1.

By exploiting the connection between the Douglas-Rachford splitting algorithm
and the classical ADMM (1.2), the non-ergodic convergence rate (2.8) has been
established in [8] for the classical ADMM (1.2) under the conditions that

$\displaystyle\mbox{zero}(\partial d_{f}+\partial d_{g})\neq\emptyset$ (2.12)

and

$\displaystyle\partial d_{f}=A^{*}\circ\partial f^{*}\circ A,\qquad\partial
d_{g}=B^{*}\circ\partial g^{*}\circ B-c,$ (2.13)

where $d_{f}(\lambda):=f^{*}(A^{*}\lambda)$ and
$d_{g}(\lambda):=g^{*}(B^{*}\lambda)-\langle\lambda,c\rangle$ with $f^{*}$ and
$g^{*}$ denoting the convex conjugates of $f$ and $g$ respectively. The
conditions (2.12) and (2.13) seems strong and unnatural because they are posed
on the convex conjugates $f^{*}$ and $g^{*}$ instead of $f$ and $g$
themselves. In Theorem 2.6 we establish the non-ergodic convergence rate (2.8)
for the proximal ADMM (1.3) with any positive semi-definite $P$ and $Q$
without requiring the conditions (2.12) and (2.13) and therefore our result
extends and improves the one in [8].

Next we will consider establishing faster convergence rates under suitable
regularity conditions. As a basis, we first prove the following result which
tells that any weak cluster point of $\\{u^{k}\\}$ is a KKT point of (1.1).
This result can be easily established for ADMM in finite-dimensional spaces,
however it is nontrivial for the proximal ADMM (1.3) in infinite-dimensional
Hilbert spaces due to the required treatment of weak convergence; Proposition
2.1 plays a crucial role in our proof.

######  Theorem 2.7.

Let Assumption 2.1 and Assumption 2.2 hold. Consider the sequence
$\\{u^{k}:=(x^{k},y^{k},\lambda^{k})\\}$ generated by the proximal ADMM (1.3).
Assume $\\{u^{k}\\}$ is bounded and let
$u^{\dagger}:=(x^{\dagger},y^{\dagger},\lambda^{\dagger})$ be a weak cluster
point of $\\{u^{k}\\}$. Then $u^{\dagger}$ is a KKT point of (1.1). Moreover,
for any weak cluster point $u^{*}$ of $\\{u^{k}\\}$ there holds
$\|u^{*}-u^{\dagger}\|_{G}=0.$

###### Proof.

We first show that $u^{\dagger}$ is a KKT point of (1.1). According to
Propositon 2.5 we have $\|\Delta u^{k}\|_{G}^{2}\to 0$ which means

$\displaystyle\Delta\lambda^{k}\to 0,\quad P\Delta x^{k}\to 0,\quad B\Delta
y^{k}\to 0,\quad Q\Delta y^{k}\to 0$ (2.14)

as $k\to\infty$. According to Theorem 2.6 we also have

$\displaystyle Ax^{k}+By^{k}-c\to 0\quad\mbox{and}\quad H(x^{k},y^{k})\to
H_{*}\quad\mbox{as }k\to\infty.$ (2.15)

Since $u^{\dagger}$ is a weak cluster point of the sequence $\\{u^{k}\\}$,
there exists a subsequence
$\\{u^{k_{j}}:=(x^{k_{j}},y^{k_{j}},\lambda^{k_{j}})\\}$ of $\\{u^{k}\\}$ such
that $u^{k_{j}}\rightharpoonup u^{\dagger}$ as $j\to\infty$. By using the
first equation in (2.15) we immediately obtain

$\displaystyle Ax^{\dagger}+By^{\dagger}-c=0.$ (2.16)

By using Proposition 2.1 with $k=k_{j}-1$ we have for any
$u:=(x,y,\lambda)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$ that

$\displaystyle 0$ $\displaystyle\leq
H(x,y)-H(x^{k_{j}},y^{k_{j}})+\langle\lambda^{k_{j}}-\rho B\Delta
y^{k_{j}},Ax+By-c\rangle$
$\displaystyle\quad-\langle\lambda,Ax^{k_{j}}+By^{k_{j}}-c\rangle+\frac{1}{2}\left(\|u^{k_{j}-1}-u\|_{G}^{2}-\|u^{k_{j}}-u\|_{G}^{2}\right).$
(2.17)

According to Corollary 2.2, $\\{\|u^{k}\|_{G}\\}$ is bounded. Thus we may use
Proposition 2.5 to conclude

$\left|\|u^{k_{j}-1}-u\|_{G}^{2}-\|u^{k_{j}}-u\|_{G}^{2}\right|\leq\left(\|u^{k_{j}-1}-u\|_{G}+\|u^{k_{j}}-u\|_{G}\right)\|\Delta
u^{k_{j}}\|_{G}\to 0$

as $j\to\infty$. Therefore, by taking $j\to\infty$ in (2) and using (2.14),
(2.15) and $\lambda^{k_{j}}\rightharpoonup\lambda^{\dagger}$ we can obtain

$\displaystyle 0\leq H(x,y)-H_{*}+\langle\lambda^{\dagger},Ax+By-c\rangle$
(2.18)

for all $(x,y)\in\mathcal{X}\times\mathcal{Y}$. Since $f$ and $g$ are convex
and lower semi-continuous, they are also weakly lower semi-continuous (see
[11, Chapter 1, Corollary 2.2]). Thus, by using $x^{k_{j}}\rightharpoonup
x^{\dagger}$ and $y^{k_{j}}\rightharpoonup y^{\dagger}$ we obtain

$\displaystyle H(x^{\dagger},y^{\dagger})$
$\displaystyle=f(x^{\dagger})+g(y^{\dagger})\leq\liminf_{j\to\infty}f(x^{k_{j}})+\liminf_{j\to\infty}g(y^{k_{j}})$
$\displaystyle\leq\liminf_{j\to\infty}\left(f(x^{k_{j}})+g(y^{k_{j}})\right)$
$\displaystyle=\liminf_{j\to\infty}H(x^{k_{j}},y^{k_{j}})=H_{*}.$

Since $(x^{\dagger},y^{\dagger})$ satisfies (2.16), we also have
$H(x^{\dagger},y^{\dagger})\geq H_{*}$. Therefore
$H(x^{\dagger},y^{\dagger})=H_{*}$ and then it follows from (2.18) and (2.16)
that

$0\leq
H(x,y)-H(x^{\dagger},y^{\dagger})+\langle\lambda^{\dagger},A(x-x^{\dagger})+B(y-y^{\dagger})\rangle$

for all $(x,y)\in\mathcal{X}\times\mathcal{Y}$. Using the definition of $H$ we
can immediately see that $-A^{*}\lambda^{\dagger}\in\partial f(x^{\dagger})$
and $-B^{*}\lambda^{\dagger}\in\partial g(y^{\dagger})$. Therefore
$u^{\dagger}$ is a KKT point of (1.1).

Let $u^{*}$ be another weak cluster point of $\\{u^{k}\\}$. Then there exists
a subsequence $\\{u^{l_{j}}\\}$ of $\\{u^{k}\\}$ such that
$u^{l_{j}}\rightharpoonup u^{*}$ as $j\to\infty$. Noting the identity

$\displaystyle 2\langle
u^{k},G(u^{*}-u^{\dagger})\rangle=\|u^{k}-u^{\dagger}\|_{G}^{2}-\|u^{k}-u^{*}\|_{G}^{2}-\|u^{\dagger}\|_{G}^{2}+\|u^{*}\|_{G}^{2}.$
(2.19)

Since both $u^{*}$ and $u^{\dagger}$ are KKT points of (1.1) as shown above,
it follows from Corollary 2.2 that both $\\{\|u^{k}-u^{\dagger}\|_{G}^{2}\\}$
and $\\{\|u^{k}-u^{*}\|_{G}^{2}\\}$ are monotonically decreasing and thus
converge as $k\to\infty$. By taking $k=k_{j}$ and $k=l_{j}$ in (2.19)
respectively and letting $j\to\infty$ we can see that, for the both cases, the
right hand side tends to the same limit. Therefore

$\displaystyle\langle u^{*},G(u^{*}-u^{\dagger})\rangle$
$\displaystyle=\lim_{j\to\infty}\langle u^{l_{j}},G(u^{*}-u^{\dagger})\rangle$
$\displaystyle=\lim_{j\to\infty}\langle u^{k_{j}},G(u^{*}-u^{\dagger})\rangle$
$\displaystyle=\langle u^{\dagger},G(u^{*}-u^{\dagger})\rangle$

which implies $\|u^{*}-u^{\dagger}\|_{G}^{2}=0$. ∎

######  Remark 2.2.

Theorem 2.7 requires $\\{u^{k}\\}$ to be bounded. According to Corollary 2.2,
$\\{\|u^{k}\|_{G}^{2}\\}$ is bounded which implies the boundedness of
$\\{\lambda^{k}\\}$. In the following we will provide sufficient conditions to
guarantee the boundedness of $\\{(x^{k},y^{k})\\}$.

  1. (i)

From (2.5) it follows that
$\\{\sigma_{f}\|x^{k}\|^{2}+\sigma_{g}\|y^{k}\|^{2}+\|u^{k}\|_{G}^{2}\\}$ is
bounded. By the definition of $G$, this in particular implies the boundedness
of $\\{\lambda^{k}\\}$ and $\\{By^{k}\\}$. Consequently, it follows from
$\Delta\lambda^{k}=\rho(Ax^{k}+By^{k}-c)$ that $\\{Ax^{k}\\}$ is bounded.
Putting the above together we can conclude that both
$\\{(\sigma_{f}I+P+A^{*}A)x^{k}\\}$ and $\\{(\sigma_{g}I+Q+B^{*}B)y^{k}\\}$
are bounded. Therefore, if both the bounded linear self-adjoint operators

$\sigma_{f}I+P+A^{*}A\quad\mbox{and}\quad\sigma_{g}I+Q+B^{*}B$

are coercive, we can conclude the boundedness of $\\{x^{k}\\}$ and
$\\{y^{k}\\}$. Here a linear operator $L:\mathcal{V}\to\mathcal{H}$ between
two Hilbert spaces $\mathcal{V}$ and $\mathcal{H}$ is called coercive if
$\|Lv\|\to\infty$ whenever $\|v\|\to\infty$. It is easy to see that $L$ is
coercive if and only if there is a constant $c>0$ such that $c\|v\|\leq\|Lv\|$
for all $v\in\mathcal{V}$.

  2. (ii)

If there exist $\beta>H_{*}$ and $\sigma>0$ such that the set

$\\{(x,y)\in\mathcal{X}\times\mathcal{Y}:H(x,y)\leq\beta\mbox{ and
}\|Ax+By-c\|\leq\sigma\\}$

is bounded, then $\\{(x^{k},y^{k})\\}$ is bounded. In fact, since
$H(x^{k},y^{k})\to H_{*}$ and $Ax^{k}+By^{k}-c\to 0$ as shown in Theorem 2.6,
the sequence $\\{(x^{k},y^{k})\\}$ is contained in the above set except for
finite many terms. Thus $\\{(x^{k},y^{k})\\}$ is bounded.

######  Remark 2.3.

It is interesting to investigate under what conditions $\\{u^{k}\\}$ has a
unique weak cluster point. According to Theorem 2.7, for any two weak cluster
points $u^{*}:=(x^{*},y^{*},\lambda^{*})$ and
$u^{\dagger}:=(x^{\dagger},y^{\dagger},\lambda^{\dagger})$ of $\\{u^{k}\\}$
there hold

$\displaystyle\|u^{*}-u^{\dagger}\|_{G}^{2}=0,\quad
Ax^{*}+By^{*}=c,\quad-A^{*}\lambda^{*}\in\partial
f(x^{*}),\quad-B^{*}\lambda^{*}\in\partial g(y^{*}),$ $\displaystyle
Ax^{\dagger}+By^{\dagger}=c,\quad-A^{*}\lambda^{\dagger}\in\partial
f(x^{\dagger}),\quad-B^{*}\lambda^{\dagger}\in\partial g(y^{\dagger}).$

By using the definition of $G$ and the monotonicity of $\partial f$ and
$\partial g$ we can deduce that

$\displaystyle\lambda^{*}=\lambda^{\dagger},\quad P(x^{*}-x^{\dagger})=0,\quad
Q(y^{*}-y^{\dagger})=0,\quad B(y^{*}-y^{\dagger})=0,$ $\displaystyle
A(x^{*}-x^{\dagger})=0,\quad\sigma_{f}\|x^{*}-x^{\dagger}\|^{2}=0,\quad\sigma_{g}\|y^{*}-y^{\dagger}\|^{2}=0.$

Consequently

$(\sigma_{f}I+P+A^{*}A)(x^{*}-x^{\dagger})=0\quad\mbox{ and
}\quad(\sigma_{g}I+Q+B^{*}B)(y^{*}-y^{\dagger})=0.$

Therefore, if both $\sigma_{f}I+P+A^{*}A$ and $\sigma_{g}I+Q+B^{*}B$ are
injective, then $x^{*}=x^{\dagger}$ and $y^{*}=y^{\dagger}$ and hence
$\\{u^{k}\\}$ has a unique weak cluster point, say $u^{\dagger}$; consequently
$u^{k}\rightharpoonup u^{\dagger}$ as $k\to\infty$.

######  Remark 2.4.

In [31] the proximal ADMM (with relaxation) has been considered under the
condition that

$\displaystyle P+\rho A^{*}A+\partial f\mbox{ and }Q+\rho B^{*}B+\partial
g\mbox{ are strongly maximal monotone}.$ (2.20)

which requires both $(P+\rho A^{*}A+\partial f)^{-1}$ and $(Q+\rho
B^{*}B+\partial g)^{-1}$ exist as single valued mappings and are Lipschitz
continuous. It has been shown that the iterative sequence converges weakly to
a KKT point which is its unique weak cluster point. The argument in [31] used
the facts that the KKT mapping $F(u)$, defined in (2.24) below, is maximal
monotone and maximal monotone operators are closed under the weak-strong
topology ([2, 3]). Our argument is essentially based on Proposition 2.1, it is
elementary and does not rely on any machinery from the maximal monotone
operator theory.

Based on Theorem 2.7, we now devote to deriving convergence rates of the
proximal ADMM (1.3) under certain regularity conditions. To this end, we
introduce the multifuncton
$F:\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}\rightrightarrows\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$
defined by

$\displaystyle F(u):=\left(\begin{array}[]{ccc}\partial f(x)+A^{*}\lambda\\\
\partial g(y)+B^{*}\lambda\\\ Ax+By-c\end{array}\right),\quad\forall
u=(x,y,\lambda)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}.$ (2.24)

Then $\bar{u}$ is a KKT point of (1.1) means $0\in F(\bar{u})$ or,
equivalently, $\bar{u}\in F^{-1}(0)$, where $F^{-1}$ denotes the inverse
multifunction of $F$. We will achieve our goal under certain bounded (Hölder)
metric subregularity conditions of $F$. We need the following calculus lemma.

######  Lemma 2.8.

Let $\\{\Delta_{k}\\}$ be a sequence of nonnegative numbers satisfying

$\displaystyle\Delta_{k}^{\theta}\leq C(\Delta_{k-1}-\Delta_{k})$ (2.25)

for all $k\geq 1$, where $C>0$ and $\theta>1$ are constants. Then there is a
constant $\tilde{C}>0$ such that

$\Delta_{k}\leq\tilde{C}(1+k)^{-\frac{1}{\theta-1}}$

for all $k\geq 0$.

###### Proof.

Please refer to the proof of [1, Theorem 2]. ∎

######  Theorem 2.9.

Let Assumption 2.1 and Assumption 2.2 hold. Consider the sequence
$\\{u^{k}:=(x^{k},y^{k},\lambda^{k})\\}$ generated by the proximal ADMM (1.3).
Assume $\\{u^{k}\\}$ is bounded and let
$u^{\dagger}:=(x^{\dagger},y^{\dagger},\lambda^{\dagger})$ be a weak cluster
point of $\\{u^{k}\\}$. Let $R$ be a number such that
$\|u^{k}-u^{\dagger}\|\leq R$ for all $k$ and assume that there exist
$\kappa>0$ and $\alpha\in(0,1]$ such that

$\displaystyle d(u,F^{-1}(0))\leq\kappa[d(0,F(u))]^{\alpha},\quad\forall u\in
B_{R}(u^{\dagger}).$ (2.26)

  1. _(i)_

If $\alpha=1$, then there exists a constant $0<q<1$ such that

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}\leq
q^{2}\left(\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k}\|_{Q}^{2}\right)$
(2.27)

for all $k\geq 0$ and consequently there exist $C>0$ and $0<q<1$ such that

$\displaystyle\begin{split}\|u^{k}-u^{\dagger}\|_{G},\,\|\Delta
u^{k}\|_{G}&\leq Cq^{k},\\\ \|Ax^{k}+By^{k}-c\|&\leq Cq^{k},\\\
|H(x^{k},y^{k})-H_{*}|&\leq Cq^{k}\end{split}$ (2.28)

for all $k\geq 0$.

  2. _(ii)_

If $\alpha\in(0,1)$ then there is a constant $C$ such that

$\displaystyle\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k}\|_{Q}^{2}\leq
C(k+1)^{-\frac{\alpha}{1-\alpha}}$ (2.29)

and consequently

$\displaystyle\begin{split}\|u^{k}-u^{\dagger}\|_{G},\,\|\Delta
u^{k}\|_{G}&\leq C(k+1)^{-\frac{1}{2(1-\alpha)}},\\\ \|Ax^{k}+By^{k}-c\|&\leq
C(k+1)^{-\frac{1}{2(1-\alpha)}},\\\ |H(x^{k},y^{k})-H_{*}|&\leq
C(k+1)^{-\frac{1}{2(1-\alpha)}}\end{split}$ (2.30)

for all $k\geq 0$.

###### Proof.

According to Theorem 2.7, $u^{\dagger}$ is a KKT point of (1.1). Therefore we
may use Lemma 2.4 with $\bar{u}=u^{\dagger}$ to obtain

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-\|\Delta u^{k+1}\|_{G}^{2}$
$\displaystyle=\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-\eta\|\Delta u^{k+1}\|_{G}^{2}$
$\displaystyle\quad\,-(1-\eta)\|\Delta u^{k+1}\|_{G}^{2},$ (2.31)

where $\eta\in(0,1)$ is any number. According to (2.3),

$\begin{pmatrix}\rho A^{*}B\Delta y^{k+1}-P\Delta x^{k+1}\\\ -Q\Delta
y^{k+1}\\\ Ax^{k+1}+By^{k+1}-c\end{pmatrix}\in F(u^{k+1}).$

Thus, by using $\Delta\lambda^{k+1}=\rho(Ax^{k+1}+By^{k+1}-c)$ we can obtain

$\displaystyle d^{2}(0,F(u^{k+1}))$ $\displaystyle\leq\|\rho A^{*}B\Delta
y^{k+1}-P\Delta x^{k+1}\|^{2}+\|-Q\Delta y^{k+1}\|^{2}$
$\displaystyle\quad\,+\|Ax^{k+1}+By^{k+1}-c\|^{2}$ $\displaystyle\leq
2\|P\Delta x^{k+1}\|^{2}+2\rho^{2}\|A\|^{2}\|B\Delta y^{k+1}\|^{2}$
$\displaystyle\quad\,+\|Q\Delta
y^{k+1}\|^{2}+\frac{1}{\rho^{2}}\|\Delta\lambda^{k+1}\|^{2}$
$\displaystyle\leq\gamma\|\Delta u^{k+1}\|_{G}^{2},$ (2.32)

where

$\gamma:=\max\left\\{2\|P\|,2\rho\|A\|^{2},\|Q\|,\frac{1}{\rho}\right\\}.$

Combining this with (2) gives

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-\eta\|\Delta u^{k+1}\|_{G}^{2}$
$\displaystyle\quad\,-\frac{1-\eta}{\gamma}d^{2}(0,F(u^{k+1})).$

Since $\|u^{k}-u^{\dagger}\|\leq R$ for all $k$ and $F$ satisfies (2.26), one
can see that

$d(u^{k+1},F^{-1}(0))\leq\kappa[d(0,F(u^{k+1}))]^{\alpha},\quad\forall k\geq
0.$

Consequently

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-\eta\|\Delta u^{k+1}\|_{G}^{2}$
$\displaystyle\quad\,-\frac{1-\eta}{\gamma\kappa^{2/\alpha}}[d(u^{k+1},F^{-1}(0))]^{2/\alpha}.$

For any $u=(x,y,\lambda)\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$ let

$d_{G}(u,F^{-1}(0)):=\inf_{\bar{u}\in F^{-1}(0)}\|u-\bar{u}\|_{G}$

which measures the “distance” from $u$ to $F^{-1}(0)$ under the semi-norm
$\|\cdot\|_{G}$. It is easy to see that

$d_{G}^{2}(u,F^{-1}(0))\leq\|G\|d^{2}(u,F^{-1}(0)),$

where $\|G\|$ denotes the norm of the operator $G$. Then we have

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-\eta\|\Delta u^{k+1}\|_{G}^{2}$
$\displaystyle\quad\,-\frac{1-\eta}{\gamma(\kappa^{2}\|G\|)^{1/\alpha}}[d_{G}(u^{k+1},F^{-1}(0))]^{2/\alpha}.$

Now let $\bar{u}\in F^{-1}(0)$ be any point. Then

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}\leq\|u^{k+1}-\bar{u}\|_{G}+\|u^{\dagger}-\bar{u}\|_{G}.$

Since $u^{\dagger}$ is a weak cluster point of $\\{u^{k}\\}$, there is a
subsequence $\\{u^{k_{j}}\\}$ of $\\{u^{k}\\}$ such that
$u^{k_{j}}\rightharpoonup u^{\dagger}$. Thus

$\displaystyle\|u^{\dagger}-\bar{u}\|_{G}^{2}=\lim_{j\to\infty}\langle
u^{k_{j}}-\bar{u},G(u^{\dagger}-\bar{u})\rangle\leq\liminf_{j\to\infty}\|u^{k_{j}}-\bar{u}\|_{G}\|u^{\dagger}-\bar{u}\|_{G}$

which implies
$\|u^{\dagger}-\bar{u}\|_{G}\leq\liminf_{j\to\infty}\|u^{k_{j}}-\bar{u}\|_{G}$.
From Corollary 2.2 we know that $\\{\|u^{k}-\bar{u}\|_{G}^{2}\\}$ is
monotonically decreasing. Thus

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}\leq\|u^{k+1}-\bar{u}\|_{G}+\liminf_{j\to\infty}\|u^{k_{j}}-\bar{u}\|_{G}\leq
2\|u^{k+1}-\bar{u}\|_{G}.$

Since $\bar{u}\in F^{-1}(0)$ is arbitrary, we thus have

$\|u^{k+1}-u^{\dagger}\|_{G}\leq 2d_{G}(u^{k+1},F^{-1}(0)).$

Therefore

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-\eta\|\Delta u^{k+1}\|_{G}^{2}$
$\displaystyle\quad\,-\frac{1-\eta}{\gamma(4\kappa^{2}\|G\|)^{1/\alpha}}\|u^{k+1}-u^{\dagger}\|_{G}^{2/\alpha}.$

By using the fact $\|\Delta u^{k}\|_{G}\to 0$ established in Proposition 2.5,
we can find a constant $C>0$ such that

$\|\Delta u^{k+1}\|_{G}^{2}\geq C\|\Delta u^{k+1}\|_{G}^{2/\alpha}.$

Note that $\|\Delta u^{k+1}\|_{G}^{2}\geq\|\Delta y^{k+1}\|_{Q}^{2}$. Thus

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-C\eta\|\Delta y^{k+1}\|_{Q}^{2/\alpha}$
$\displaystyle\quad\,-\frac{1-\eta}{\gamma(4\kappa^{2}\|G\|)^{1/\alpha}}\|u^{k+1}-u^{\dagger}\|_{G}^{2/\alpha}.$

Choose $\eta$ such that

$\eta=\frac{1}{1+C\gamma(4\kappa^{2}\|G\|)^{1/\alpha}}.$

Then

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-C\eta\left(\|\Delta
y^{k+1}\|_{Q}^{2/\alpha}+\|u^{k+1}-u^{\dagger}\|_{G}^{2/\alpha}\right).$

Using the inequality $(a+b)^{p}\leq 2^{p-1}(a^{p}+b^{p})$ for $a,b\geq 0$ and
$p\geq 1$, we then obtain

$\displaystyle\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{k+1}\|_{Q}^{2}$
$\displaystyle\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}-2^{1-1/\alpha}C\eta\left(\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k+1}\|_{Q}^{2}\right)^{1/\alpha}.$ (2.33)

(i) If $\alpha=1$, then we obtain the linear convergence

$(1+C\eta)\left(\|u^{k+1}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k+1}\|_{Q}^{2}\right)\leq\|u^{k}-u^{\dagger}\|_{G}^{2}+\|\Delta
y^{k}\|_{Q}^{2}$

which is (2.27) with $q=1/(1+C\eta)$. By using Lemma 2.4 and (2.27) we
immediately obtain the first estimate in (2.28). By using (2.9) and (2.11) we
then obtain the last two estimates in (2.28).

(ii) If $\alpha\in(0,1)$, we may use (2) and Lemma 2.8 to obtain (2.29). To
derive the first estimate in (2.30), we may use Lemma 2.4 to obtain

$\sum_{j=l}^{k}\|\Delta
u^{j}\|_{G}^{2}\leq\|u^{l}-u^{\dagger}\|_{G}^{2}+\|\Delta y^{l}\|_{Q}^{2}$

for all integers $1\leq l<k$. By using the monotonicity of $\\{\|\Delta
u^{j}\|_{G}^{2}\\}$ shown in Lemma 2.3 and the estimate (2.29) we have

$(k-l+1)\|\Delta u^{k}\|_{G}^{2}\leq C(l+1)^{-\frac{\alpha}{1-\alpha}}.$

Taking $l=[k/2]$, the largest integers $\leq k/2$, gives

$\|\Delta u^{k}\|_{G}^{2}\leq
C(k+1)^{-\frac{\alpha}{1-\alpha}-1}=C(k+1)^{-\frac{1}{1-\alpha}}$

with a possibly different generic constant $C$. This shows the first estimate
in (2.30). Based on this, we can use (2.9) and (2.11) to obtain the last two
estimates in (2.30). The proof is therefore complete. ∎

######  Remark 2.5.

Let us give some comments on the condition (2.26). In finite dimensional
Euclidean spaces, it has been proved in [30] that for every polyhedral
multifunction $\Psi:{\mathbb{R}}^{m}\rightrightarrows{\mathbb{R}}^{n}$ there
is a constant $\kappa>0$ such that for any $y\in{\mathbb{R}}^{n}$ there is a
number $\varepsilon>0$ such that

$d(x,\Psi^{-1}(y))\leq\kappa d(y,\Psi(x)),\quad\forall x\mbox{ satisfying
}d(y,\Psi(x))<\varepsilon.$

This result in particular implies the bounded metric subregularity of $\Psi$,
i.e. for any $r>0$ and any $y\in{\mathbb{R}}^{n}$ there is a number $C>0$ such
that

$d(x,\Psi^{-1}(y))\leq Cd(y,\Psi(x)),\quad\forall x\in B_{r}(0).$

Therefore, if $\partial f$ and $\partial g$ are polyhedral multifunctions,
then the multifunction $F$ defined by (2.24) is also polyhedral and thus
(2.26) with $\alpha=1$ holds. The bounded metric subregularity of polyhedral
multifunctions in arbitrary Banach spaces has been established in [34].

On the other hand, if $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ are
finite dimensional Euclidean spaces, and if $f$ and $g$ are semi-algebraic
convex functions, then the multifunction $F$ satisfies (2.26) for some
$\alpha\in(0,1]$. Indeed, the semi-algebraicity of $f$ and $g$ implies that
their subdifferentials $\partial f$ and $\partial g$ are semi-algebraic
multifunctions with closed graph; consequently $F$ is semi-algebraic with
closed graph. According to [24, Proposition 3.1], $F$ is bounded Hölder
metrically subregular at any point $(\bar{u},\bar{\xi})$ on its graph, i.e.
for any $r>0$ there exist $\kappa>0$ and $\alpha\in(0,1]$ such that

$d(u,F^{-1}(\bar{\xi}))\leq\kappa[d(\bar{\xi},F(u))]^{\alpha},\quad\forall
u\in B_{r}(\bar{u})$

which in particular implies (2.26).

By inspecting the proof of Theorem 2.9, it is easy to see that the same
convergence rate results can be derived with the condition (2.26) replaced by
the weaker condition: there exist $\kappa>0$ and $\alpha\in(0,1]$ such that

$\displaystyle d_{G}(u^{k},F^{-1}(0))\leq\kappa\left\|\Delta
u^{k}\right\|_{G}^{\alpha},\quad\forall k\geq 1.$ (2.34)

Therefore we have the following result.

######  Theorem 2.10.

Let Assumption 2.1 and Assumption 2.2 hold. Consider the sequence
$\\{u^{k}:=(x^{k},y^{k},\lambda^{k})\\}$ generated by the proximal ADMM (1.3).
Assume $\\{u^{k}\\}$ is bounded. If there exist $\kappa>0$ and
$\alpha\in(0,1]$ such that (2.34) holds, then, for any weak cluster point
$u^{\dagger}$ of $\\{u^{k}\\}$, the same convergence rate results in Theorem
2.9 hold.

######  Remark 2.6.

Note that the condition (2.34) is based on the iterative sequence itself.
Therefore, it makes possible to check the condition by exploring not only the
property of the multifunction $F$ but also the structure of the algorithm. The
condition (2.34) with $\alpha=1$ has been introduced in [27] as an iteration
based error bound condition to study the linear convergence of the proximal
ADMM (1.3) with $Q=0$ in finite dimensions.

######  Remark 2.7.

The condition (2.34) is strongly motivated by the proof of Theorem 2.9. We
would like to provide here an alternative motivation. Consider the proximal
ADMM (1.3). We can show that if $\|\Delta u^{k}\|_{G}=0$ then $u^{k}$ must be
a KKT point of (1.1). Indeed, $\|\Delta u^{k}\|_{G}^{2}=0$ implies $P\Delta
x^{k}=0$, ${\widehat{Q}}\Delta y^{k}=0$ and $\Delta\lambda^{k}=0$. Since
${\widehat{Q}}=Q+\rho B^{T}B$ with $Q$ positive semi-definite and
$\Delta\lambda^{k}=\rho(Ax^{k}+By^{k}-c)$, we also have $B\Delta y^{k}=0$,
$Q\Delta y^{k}=0$ and $Ax^{k}+By^{k}-c=0$. Thus, it follows from (2.3) that

$-A^{*}\lambda^{k}\in\partial f(x^{k}),\quad-B^{*}\lambda^{k}\in\partial
g(y^{k}),\quad Ax^{k}+By^{k}=c$

which shows that $u^{k}=(x^{k},y^{k},\lambda^{k})$ is a KKT point, i.e.,
$u^{k}\in F^{-1}(0)$. Therefore, it is natural to ask, if $\|\Delta
u^{k}\|_{G}$ is small, can we guarantee $d_{G}(u^{k},F^{-1}(0))$ to be small
as well? This motivates us to propose a condition like

$d_{G}(u^{k},F^{-1}(0))\leq\varphi(\|\Delta u^{k}\|_{G}),\quad\forall k\geq 1$

for some function $\varphi:[0,\infty)\to[0,\infty)$ with $\varphi(0)=0$. The
condition (2.34) corresponds to $\varphi(s)=\kappa s^{\alpha}$ for some
$\kappa>0$ and $\alpha\in(0,1]$.

In finite dimensional Euclidean spaces some linear convergence results on the
proximal ADMM (1.3) have been established in [9] under various scenarios
involving strong convexity of $f$ and/or $g$, Lipschitz continuity of $\nabla
f$ and/or $\nabla g$, together with further conditions on $A$ and/or $B$, see
[9, Theorem 3.1 and Table 1]. In the following theorem we will show that
(2.34) with $\alpha=1$ holds under any one of these scenarios and thus the
linear convergence in [9, Theorem 3.1 and Theorem 3.4] can be established by
using Theorem 2.10. Therefore, the linear convergence results based on the
bounded metric subregularity of $F$ or the scenarios in [9] can be treated in
a unified manner.

Actually our next theorem improves the results in [9] by establishing the
linear convergence of $\\{u^{k}\\}$ and $\\{H(x^{k},y^{k})\\}$ and relaxing
the Lipschitz continuity of gradient(s) to the local Lipschitz continuity.
Furthermore, Our result is established in general Hilbert spaces. To formulate
the scenarios from [9] in this general setting, we need to replace the full
row/column rank of matrices by the coercivity of linear operators. We also
need the linear operator $M:\mathcal{X}\times\mathcal{Y}\to\mathcal{Z}$
defined by

$M(x,y):=Ax+By,\quad\forall(x,y)\in\mathcal{X}\times\mathcal{Y}$

which is constructed from $A$ and $B$. It is easy to see that the adjoint of
$M$ is $M^{*}z=(A^{*}z,B^{*}z)$ for any $z\in\mathcal{Z}$.

######  Theorem 2.11.

Let Assumption 2.1 and Assumption 2.2 hold. Let $\\{u^{k}\\}$ be the sequence
generated by the proximal ADMM (1.3). Then $\\{u^{k}\\}$ is bounded and there
exists a constant $C>0$ such that

$\displaystyle d_{G}(u^{k},F^{-1}(0))\leq C\|\Delta u^{k}\|_{G}$ (2.35)

for all $k\geq 1$, provided any one of the following conditions holds:

  1. _(i)_

$\sigma_{g}>0$, $A$ and $B^{*}$ are coercive, $g$ is differentiable and its
gradient is Lipschitz continuous over bounded sets;

  2. _(ii)_

$\sigma_{f}>0$, $\sigma_{g}>0$, $B^{*}$ is coercive, $g$ is differentiable and
its gradient is Lipschitz continuous over bounded sets;

  3. _(iii)_

$\lambda^{0}=0$, $\sigma_{f}>0$, $\sigma_{g}>0$, $M^{*}$ restricted on
$\mathcal{N}(M^{*})^{\perp}$ is coercive, both $f$ and $g$ are differentiable
and their gradients are Lipschitz continuous over bounded sets;

  4. _(iv)_

$\lambda^{0}=0$, $\sigma_{g}>0$, $A$ is coercive, $M^{*}$ restricted on
$\mathcal{N}(M^{*})^{\perp}$ is coercive, both $f$ and $g$ are differentiable
and their gradients are Lipschitz continuous over bounded sets;

where $\mathcal{N}(M^{*})$ denotes the null space of $M^{*}$. Consequently,
there exist $C>0$ and $0<q<1$ such that

$\|u^{k}-u^{\dagger}\|\leq Cq^{k}\quad\mbox{ and
}\quad|H(x^{k},y^{k})-H_{*}|\leq Cq^{k}$

for all $k\geq 0$, where
$u^{\dagger}:=(x^{\dagger},y^{\dagger},\lambda^{\dagger})$ is a KKT point of
(1.1).

###### Proof.

We will only consider the scenario (i) since the proofs for other scenarios
are similar. In the following we will use $C$ to denote a generic constant
which may change from line to line but is independent of $k$.

We first show the boundedness of $\\{u^{k}\\}$. According to Corollary 2.2,
$\\{\|u^{k}\|_{G}^{2}\\}$ is bounded which implies the boundedness of
$\\{\lambda^{k}\\}$. Since $\sigma_{g}>0$, it follows from (2.5) that
$\\{y^{k}\\}$ is bounded. Consequently, it follows from
$\Delta\lambda^{k}=\rho(Ax^{k}+By^{k}-c)$ that $\\{Ax^{k}\\}$ is bounded.
Since $A$ is coercive, $\\{x^{k}\\}$ must be bounded.

Next we show (2.35). Let
$u^{\dagger}:=(x^{\dagger},y^{\dagger},\lambda^{\dagger})$ be a weak cluster
point of $\\{u^{k}\\}$ whose existence is guaranteed by the boundedness of
$\\{u^{k}\\}$. According to Theorem 2.7, $u^{\dagger}$ is a KKT point of
(1.1). Let $(\xi,\eta,\tau)\in F(u^{k})$ be any element. Then

$\xi-A^{*}\lambda^{k}\in\partial
f(x^{k}),\quad\eta-B^{*}\lambda^{k}\in\partial
g(y^{k}),\quad\tau=Ax^{k}+By^{k}-c.$

By using the monotonicity of $\partial f$ and $\partial g$ we have

$\displaystyle\sigma_{f}\|x^{k}-x^{\dagger}\|^{2}+\sigma_{g}\|y^{k}-y^{\dagger}\|^{2}$
$\displaystyle\leq\langle\xi-A^{*}\lambda^{k}+A^{*}\lambda^{\dagger},x^{k}-x^{\dagger}\rangle+\langle\eta-B^{*}\lambda^{k}+B^{*}\lambda^{\dagger},y^{k}-y^{\dagger}\rangle$
$\displaystyle=\langle\xi,x^{k}-x^{\dagger}\rangle+\langle\eta,y^{k}-y^{\dagger}\rangle+\langle\lambda^{\dagger}-\lambda^{k},A(x^{k}-x^{\dagger})+B(y^{k}-y^{\dagger})\rangle$
$\displaystyle=\langle\xi,x^{k}-x^{\dagger}\rangle+\langle\eta,y^{k}-y^{\dagger}\rangle+\langle\lambda^{\dagger}-\lambda^{k},\tau\rangle.$
(2.36)

Since $\sigma_{g}>0$, it follows from (2) and the Cauchy-Schwarz inequality
that

$\displaystyle\|y^{k}-y^{\dagger}\|^{2}\leq
C\left(\|\eta\|^{2}+\|\xi\|\|x^{k}-x^{\dagger}\|+\|\tau\|\|\lambda^{k}-\lambda^{\dagger}\|\right).$
(2.37)

Note that
$A(x^{k}-x^{\dagger})=-B(y^{k}-y^{\dagger})+\frac{1}{\rho}\Delta\lambda^{k}$.
Since $A$ is coercive, we have

$\displaystyle\|x^{k}-x^{\dagger}\|^{2}\leq C\|A(x^{k}-x^{\dagger})\|^{2}\leq
C\left(\|y^{k}-y^{\dagger}\|^{2}+\|\Delta\lambda^{k}\|^{2}\right).$ (2.38)

By the differentiability of $g$ we have $-B^{*}\lambda^{\dagger}=\nabla
g(y^{\dagger})$ and $-B^{*}\lambda^{k}-Q\Delta y^{k}=\nabla g(y^{k})$. Since
$B^{*}$ is coercive and $\nabla g$ is Lipschitz continuous over bounded sets,
we thus obtain

$\displaystyle\|\lambda^{k}-\lambda^{\dagger}\|^{2}$ $\displaystyle\leq
C\|B^{*}(\lambda^{k}-\lambda^{\dagger})\|^{2}=\|Q\Delta y^{k}+\nabla
g(y^{k})-\nabla g(y^{\dagger})\|^{2}$ $\displaystyle\leq C\left(\|\Delta
y^{k}\|_{Q}^{2}+\|y^{k}-y^{\dagger}\|^{2}\right).$ (2.39)

Adding (2.38) and (2) and then using (2.37), it follows

$\displaystyle\|x^{k}-x^{\dagger}\|^{2}+\|\lambda^{k}-\lambda^{\dagger}\|^{2}$
$\displaystyle\leq C\left(\|\eta\|^{2}+\|\Delta
u^{k}\|_{G}^{2}+\|\xi\|\|x^{k}-x^{\dagger}\|+\|\tau\|\|\lambda^{k}-\lambda^{\dagger}\|\right)$

which together with the Cauchy-Schwarz inequality then implies

$\displaystyle\|x^{k}-x^{\dagger}\|^{2}+\|\lambda^{k}-\lambda^{\dagger}\|^{2}\leq
C\left(\|\xi\|^{2}+\|\eta\|^{2}+\|\tau\|^{2}+\|\Delta u^{k}\|_{G}^{2}\right).$
(2.40)

Combining (2.37) and (2.40) we can obtain

$\displaystyle\|x^{k}-x^{\dagger}\|^{2}+\|y^{k}-y^{\dagger}\|^{2}+\|\lambda^{k}-\lambda^{\dagger}\|^{2}\leq
C\left(\|\xi\|^{2}+\|\eta\|^{2}+\|\tau\|^{2}+\|\Delta u^{k}\|_{G}^{2}\right).$

Since $(\xi,\eta,\tau)\in F(u^{k})$ is arbitrary, we therefore have

$\displaystyle\|u^{k}-u^{\dagger}\|^{2}\leq
C\left([d(0,F(u^{k}))]^{2}+\|\Delta u^{k}\|_{G}^{2}\right).$

With the help of (2), we then obtain

$\displaystyle\|u^{k}-u^{\dagger}\|^{2}\leq C\|\Delta u^{k}\|_{G}^{2}.$ (2.41)

Thus

$\displaystyle[d_{G}(u^{k},F^{-1}(0))]^{2}\leq C[d(u^{k},F^{-1}(0))]^{2}\leq
C\|u^{k}-u^{\dagger}\|^{2}\leq C\|\Delta u^{k}\|_{G}^{2}$

which shows (2.35).

Because $\\{u^{k}\\}$ is bounded and (2.35) holds, we may use Theorem 2.10 to
conclude the existence of a constant $q\in(0,1)$ such that

$\|\Delta u^{k}\|_{G}\leq Cq^{k}\quad\mbox{and}\quad|H(x^{k},y^{k})-H_{*}|\leq
Cq^{k}.$

Finally we may use (2.41) to obtain $\|u^{k}-u^{\dagger}\|\leq Cq^{k}$. ∎

######  Remark 2.8.

If $\mathcal{Z}$ is finite-dimensional, the coercivity of $M^{*}$ restricted
on $\mathcal{N}(M^{*})^{\perp}$ required in the scenarios (iii) and (iv) holds
automatically. If it is not, then there exists a sequence
$\\{z^{k}\\}\subset\mathcal{N}(M^{*})^{\perp}\setminus\\{0\\}$ such that

$\|z^{k}\|\geq k\|M^{*}z^{k}\|,\quad k=1,2,\cdots.$

By rescaling we may assume $\|z^{k}\|=1$ for all $k$. Since $\mathcal{Z}$ is
finite-dimensional, by taking a subsequence if necessary, we may assume
$z^{k}\to z$ for some $z\in\mathcal{Z}$. Clearly
$z\in\mathcal{N}(M^{*})^{\perp}$ and $\|z\|=1$. Note that $\|M^{*}z^{k}\|\leq
1/k$ for all $k$, we have $\|M^{*}z\|=\lim_{k\to\infty}\|M^{*}z^{k}\|=0$ which
means $z\in\mathcal{N}(M^{*})$. Thus
$z\in\mathcal{N}(M^{*})\cap\mathcal{N}(M^{*})^{\perp}=\\{0\\}$ which is a
contradiction.

##  3\. Proximal ADMM for linear inverse problems

In this section we consider the method (1.11) as a regularization method for
solving (1.9) and establish a convergence rate result under a benchmark source
condition on the sought solution. Throughout this section we make the
following assumptions on the operators $Q$, $L$, $A$, the constraint set
$\mathcal{C}$ and the function $f$:

######  Assumption 3.1.

  1. _(i)_

$A:\mathcal{X}\to\mathcal{H}$ is a bounded linear operator,
$Q:\mathcal{X}\to\mathcal{X}$ is a bounded linear positive semi-definite self-
adjoint operator, and $\mathcal{C}\subset\mathcal{X}$ is a closed convex
subset.

  2. _(ii)_

$L$ is a densely defined, closed, linear operator from $\mathcal{X}$ to
$\mathcal{Y}$ with domain $\emph{dom}(L)$.

  3. _(iii)_

There is a constant $c_{0}>0$ such that

$\|Ax\|^{2}+\|Lx\|^{2}\geq c_{0}\|x\|^{2},\qquad\forall x\in\emph{dom}(L).$

  4. _(iv)_

$f:\mathcal{Y}\to(-\infty,\infty]$ is proper, lower semi-continuous, and
strongly convex.

This assumptions is standard in the literature on regularization methods and
has been used in [21, 22]. Based on (iii), we can define the adjoint $L^{*}$
of $L$ which is also closed and densely defined; moreover,
$z\in\mbox{dom}(L^{*})$ if and only if $\langle L^{*}z,x\rangle=\langle
z,Lx\rangle$ for all $x\in\mbox{dom}(L)$. Under Assumption 3.1, it has been
shown in [21, 22] that the proximal ADMM (1.11) is well-defined and if the
exact data $b$ is consistent in the sense that there exists
$\hat{x}\in\mathcal{X}$ such that

$\hat{x}\in\mbox{dom}(L)\cap\mathcal{C},\quad
L\hat{x}\in\mbox{dom}(f)\quad\mbox{ and }\quad A\hat{x}=b,$

then the problem (1.9) has a unique solution, denoted by $x^{\dagger}$.
Furthermore, there holds the following monotonicity result, see [22, Lemma
2.3]; alternatively, it can also be derived from Lemma 2.3..

######  Lemma 3.1.

Let $\\{z^{k},y^{k},x^{k},\lambda^{k},\mu^{k},\nu^{k}\\}$ be defined by the
proximal ADMM (1.11) with noisy data and let

$\displaystyle E_{k}$
$\displaystyle:=\frac{1}{2\rho_{1}}\|\Delta\lambda^{k}\|^{2}+\frac{1}{2\rho_{2}}\|\Delta\mu^{k}\|^{2}+\frac{1}{2\rho_{3}}\|\Delta\nu^{k}\|^{2}$
$\displaystyle\quad\ +\frac{\rho_{2}}{2}\|\Delta
y^{k}\|^{2}+\frac{\rho_{3}}{2}\|\Delta x^{k}\|^{2}+\frac{1}{2}\|\Delta
z^{k}\|_{Q}^{2}.$ (3.1)

Then $\\{E_{k}\\}$ is monotonically decreasing with respect to $k$.

In the following we will always assume the exact data $b$ is consistent. We
will derive a convergence rate of $x^{k}$ to the unique solution $x^{\dagger}$
of (1.9) under the source condition

$\displaystyle\exists\mu^{\dagger}\in\partial
f(Lx^{\dagger})\cap\mbox{dom}(L^{*})\mbox{ and
}\nu^{\dagger}\in\partial\iota_{\mathcal{C}}(x^{\dagger})\mbox{ such that
}L^{*}\mu^{\dagger}+\nu^{\dagger}\in\mbox{Ran}(A^{*}).$ (3.2)

Note that when $L=I$ and $\mathcal{C}=\mathcal{X}$, (3.2) becomes the
benchmark source condition

$\partial f(x^{\dagger})\cap\mbox{Ran}(A^{*})\neq\emptyset$

which has been widely used to derive convergence rate for regularization
methods, see [7, 13, 23, 29] for instance. We have the following convergence
rate result.

######  Theorem 3.2.

Let Assumption 3.1 hold, let the exact data $b$ be consistent, and let the
sequence $\\{z^{k},y^{k},x^{k},\lambda^{k},\mu^{k},\nu^{k}\\}$ be defined by
the proximal ADMM (1.11) with noisy data $b^{\delta}$ satisfying
$\|b^{\delta}-b\|\leq\delta$. Assume the unique solution $x^{\dagger}$ of
(1.9) satisfies the source condition (3.2). Then for the integer $k_{\delta}$
chosen by $k_{\delta}\sim\delta^{-1}$ there hold

$\|x^{k_{\delta}}-x^{\dagger}\|=O(\delta^{1/4}),\quad\|y^{k_{\delta}}-Lx^{\dagger}\|=O(\delta^{1/4})\quad\mbox{and}\quad\|z^{k_{\delta}}-x^{\dagger}\|=O(\delta^{1/4})$

as $\delta\to 0$.

In order to prove this result, let us start from the formulation of the
algorithm (1.11) to derive some useful estimates. For simplicity of
exposition, we set

$\displaystyle\Delta x^{k+1}:=x^{k+1}-x^{k},\quad\Delta
y^{k+1}:=y^{k+1}-y^{k},\quad\Delta z^{k+1}:=z^{k+1}-z^{k},$
$\displaystyle\Delta\lambda^{k+1}:=\lambda^{k+1}-\lambda^{k},\quad\Delta\mu^{k+1}:=\mu^{k+1}-\mu^{k},\quad\Delta\nu^{k+1}:=\nu^{k+1}-\nu^{k}.$

According to the definition of $z^{k+1}$, $y^{k+1}$ and $x^{k+1}$ in (1.11),
we have the optimality conditions

$\displaystyle
0=A^{*}\lambda^{k}+\nu^{k}+\rho_{1}A^{*}(Az^{k+1}-b^{\delta})+L^{*}(\mu^{k}+\rho_{2}(Lz^{k+1}-y^{k}))$
$\displaystyle\quad\quad+\rho_{3}(z^{k+1}-x^{k})+Q(z^{k+1}-z^{k}),$ (3.3)
$\displaystyle 0\in\partial f(y^{k+1})-\mu^{k}-\rho_{2}(Lz^{k+1}-y^{k+1}),$
(3.4) $\displaystyle
0\in\partial\iota_{C}(x^{k+1})-\nu^{k}-\rho_{3}(z^{k+1}-x^{k+1}).$ (3.5)

By using the last two equations in (1.11), we have from (3.4) and (3.5) that

$\displaystyle\mu^{k+1}\in\partial
f(y^{k+1})\quad\mbox{and}\quad\nu^{k+1}\in\partial\iota_{\mathcal{C}}(x^{k+1}).$
(3.6)

Letting $y^{\dagger}=Lx^{\dagger}$. From the strong convexity of $f$, the
convexity of $\iota_{C}$, and (3.6) it follows that

$\displaystyle\sigma_{f}\|y^{k+1}-y^{\dagger}\|^{2}$ $\displaystyle\leq
f(y^{\dagger})-f(y^{k+1})-\langle\mu^{k+1},y^{\dagger}-y^{k+1}\rangle$
$\displaystyle\quad\,+\langle\nu^{k+1},x^{k+1}-x^{\dagger}\rangle.$ (3.7)

where $\sigma_{f}$ denotes the modulus of convexity of $f$; we have
$\sigma_{f}>0$ as $f$ is strongly convex. By taking the inner product of (3.3)
with $z^{k+1}-x^{\dagger}$ we have

$\displaystyle 0$
$\displaystyle=\langle\lambda^{k}+\rho_{1}(Az^{k+1}-b^{\delta}),A(z^{k+1}-x^{\dagger})\rangle$
$\displaystyle\quad\,+\langle\mu^{k}+\rho_{2}(Lz^{k+1}-y^{k}),L(z^{k+1}-x^{\dagger})\rangle$
$\displaystyle\quad\,+\langle\nu^{k}+\rho_{3}(z^{k+1}-x^{k}),z^{k+1}-x^{\dagger}\rangle$
$\displaystyle\quad\,+\langle Q(z^{k+1}-z^{k}),z^{k+1}-x^{\dagger}\rangle.$

Therefore we may use the definition of $\lambda^{k+1},\mu^{k+1},\nu^{k+1}$ in
(1.11) and the fact $Ax^{\dagger}=b$ to further obtain

$\displaystyle 0$
$\displaystyle=\langle\lambda^{k+1},Az^{k+1}-b\rangle+\langle\mu^{k+1}+\rho_{2}\Delta
y^{k+1},Lz^{k+1}-y^{\dagger}\rangle$
$\displaystyle\quad\,+\langle\nu^{k+1}+\rho_{3}\Delta
x^{k+1},z^{k+1}-x^{\dagger}\rangle$ $\displaystyle\quad\,+\langle Q\Delta
z^{k+1},z^{k+1}-x^{\dagger}\rangle.$ (3.8)

Subtracting (3) by (3) gives

$\displaystyle\sigma_{f}\|y^{k+1}-y^{\dagger}\|^{2}$ $\displaystyle\leq
f(y^{\dagger})-f(y^{k+1})-\langle\lambda^{k+1},Az^{k+1}-b\rangle+\langle\mu^{k+1},y^{k+1}-Lz^{k+1}\rangle$
$\displaystyle\quad\,-\rho_{2}\langle\Delta
y^{k+1},Lz^{k+1}-y^{\dagger}\rangle+\langle\nu^{k+1},x^{k+1}-z^{k+1}\rangle$
$\displaystyle\quad\,-\rho_{3}\langle\Delta
x^{k+1},z^{k+1}-x^{\dagger}\rangle-\langle Q\Delta
z^{k+1},z^{k+1}-x^{\dagger}\rangle.$

Note that under the source condition (3.2), there exist $\mu^{\dagger}$,
$\nu^{\dagger}$ and $\lambda^{\dagger}$ such that

$\displaystyle\mu^{\dagger}\in\partial
f(y^{\dagger}),\quad\nu^{\dagger}\in\partial\iota_{\mathcal{C}}(x^{\dagger})\quad\mbox{
and }\quad L^{*}\mu^{\dagger}+\nu^{\dagger}+A^{*}\lambda^{\dagger}=0.$ (3.9)

Thus, it follows from the above equation and the last two equations in (1.11)
that

$\displaystyle\sigma_{f}\|y^{k+1}-y^{\dagger}\|^{2}$ $\displaystyle\leq
f(y^{\dagger})-f(y^{k+1})-\langle\lambda^{\dagger},Az^{k+1}-b\rangle-\langle\mu^{\dagger},Lz^{k+1}-y^{k+1}\rangle-\langle\nu^{\dagger},z^{k+1}-x^{k+1}\rangle$
$\displaystyle\quad\
-\langle\lambda^{k+1}-\lambda^{\dagger},Az^{k+1}-b^{\delta}+b^{\delta}-b\rangle$
$\displaystyle\quad\
-\frac{1}{\rho_{2}}\langle\mu^{k+1}-\mu^{\dagger},\Delta\mu^{k+1}\rangle-\rho_{2}\langle\Delta
y^{k+1},Lz^{k+1}-y^{\dagger}\rangle$ $\displaystyle\quad\
-\frac{1}{\rho_{3}}\langle\nu^{k+1}-\nu^{\dagger},\Delta\nu^{k+1}\rangle-\rho_{3}\langle\Delta
x^{k+1},z^{k+1}-x^{\dagger}\rangle$ $\displaystyle\quad\,-\langle Q\Delta
z^{k+1},z^{k+1}-x^{\dagger}\rangle.$

By using (3.9), $b=Ax^{\dagger}$ and the convexity of $f$, we can see that

$\displaystyle
f(y^{\dagger})-f(y^{k+1})-\langle\lambda^{\dagger},Az^{k+1}-b\rangle-\langle\mu^{\dagger},Lz^{k+1}-y^{k+1}\rangle-\langle\nu^{\dagger},z^{k+1}-x^{k+1}\rangle$
$\displaystyle=f(y^{\dagger})-f(y^{k+1})+\langle\lambda^{\dagger},b\rangle+\langle\mu^{\dagger},y^{k+1}\rangle+\langle\nu^{\dagger},x^{k+1}\rangle$
$\displaystyle=f(y^{\dagger})-f(y^{k+1})+\langle
A^{*}\lambda^{\dagger},x^{\dagger}\rangle+\langle\mu^{\dagger},y^{k+1}\rangle+\langle\nu^{\dagger},x^{k+1}\rangle$
$\displaystyle=f(y^{\dagger})-f(y^{k+1})-\langle
L^{*}\mu^{\dagger},x^{\dagger}\rangle+\langle\mu^{\dagger},y^{k+1}\rangle+\langle\nu^{\dagger},x^{k+1}-x^{\dagger}\rangle$
$\displaystyle=f(y^{\dagger})-f(y^{k+1})+\langle\mu^{\dagger},y^{k+1}-y^{\dagger}\rangle+\langle\nu^{\dagger},x^{k+1}-x^{\dagger}\rangle\leq
0.$

Consequently, by using the fourth equation in (1.11), we have

$\displaystyle\sigma_{f}\|y^{k+1}-y^{\dagger}\|^{2}$
$\displaystyle\leq-\langle\lambda^{k+1}-\lambda^{\dagger},b^{\delta}-b\rangle-\frac{1}{\rho_{1}}\langle\lambda^{k+1}-\lambda^{\dagger},\Delta\lambda^{k+1}\rangle$
$\displaystyle\quad\
-\frac{1}{\rho_{2}}\langle\mu^{k+1}-\mu^{\dagger},\Delta\mu^{k+1}\rangle-\frac{1}{\rho_{3}}\langle\nu^{k+1}-\nu^{\dagger},\Delta\nu^{k+1}\rangle$
$\displaystyle\quad\ -\rho_{2}\langle\Delta
y^{k+1},y^{k+1}-y^{\dagger}+Lz^{k+1}-y^{k+1}\rangle$ $\displaystyle\quad\
-\rho_{3}\langle\Delta x^{k+1},x^{k+1}-x^{\dagger}+z^{k+1}-x^{k+1}\rangle$
$\displaystyle\quad\ -\langle Q\Delta z^{k+1},z^{k+1}-x^{\dagger}\rangle.$

By using the polarization identity and the last two equations in (1.11) we
further have

$\displaystyle\sigma_{f}\|y^{k+1}-y^{\dagger}\|^{2}$
$\displaystyle\leq-\langle\lambda^{k+1}-\lambda^{\dagger},b^{\delta}-b\rangle$
$\displaystyle\quad\
+\frac{1}{2\rho_{1}}\left(\|\lambda^{k}-\lambda^{\dagger}\|^{2}-\|\lambda^{k+1}-\lambda^{\dagger}\|^{2}-\|\Delta\lambda^{k+1}\|^{2}\right)$
$\displaystyle\quad\
+\frac{1}{2\rho_{2}}\left(\|\mu^{k}-\mu^{\dagger}\|^{2}-\|\mu^{k+1}-\mu^{\dagger}\|^{2}-\|\Delta\mu^{k+1}\|^{2}\right)$
$\displaystyle\quad\
+\frac{1}{2\rho_{3}}\left(\|\nu^{k}-\nu^{\dagger}\|^{2}-\|\nu^{k+1}-\nu^{\dagger}\|^{2}-\|\Delta\nu^{k+1}\|^{2}\right)$
$\displaystyle\quad\
+\frac{1}{2}\left(\|z^{k}-z^{\dagger}\|_{Q}^{2}-\|z^{k+1}-z^{\dagger}\|_{Q}^{2}-\|\Delta
z^{k+1}\|_{Q}^{2}\right)$ $\displaystyle\quad\
+\frac{\rho_{2}}{2}\left(\|y^{k}-y^{\dagger}\|^{2}-\|y^{k+1}-y^{\dagger}\|^{2}-\|\Delta
y^{k+1}\|^{2}\right)$ $\displaystyle\quad\
+\frac{\rho_{3}}{2}\left(\|x^{k}-x^{\dagger}\|^{2}-\|x^{k+1}-x^{\dagger}\|^{2}-\|\Delta
x^{k+1}\|^{2}\right)$ $\displaystyle\quad\ -\langle\Delta
y^{k+1},\Delta\mu^{k+1}\rangle-\langle\Delta x^{k+1},\Delta\nu^{k+1}\rangle.$

Let

$\displaystyle\Phi_{k}$
$\displaystyle:=\frac{1}{2\rho_{1}}\|\lambda^{k}-\lambda^{\dagger}\|^{2}+\frac{1}{2\rho_{2}}\|\mu^{k}-\mu^{\dagger}\|^{2}+\frac{1}{2\rho_{3}}\|\nu^{k}-\nu^{\dagger}\|^{2}$
$\displaystyle\quad\
+\frac{1}{2}\|z^{k}-x^{\dagger}\|_{Q}^{2}+\frac{\rho_{2}}{2}\|y^{k}-y^{\dagger}\|^{2}+\frac{\rho_{3}}{2}\|x^{k}-x^{\dagger}\|^{2}.$

Then

$\displaystyle\sigma_{f}\|y^{k+1}-y^{\dagger}\|^{2}$
$\displaystyle\leq\Phi_{k}-\Phi_{k+1}-\langle\lambda^{k+1}-\lambda^{\dagger},b^{\delta}-b\rangle-
E_{k+1}$ $\displaystyle\quad\ -\langle\Delta
y^{k+1},\Delta\mu^{k+1}\rangle-\langle\Delta x^{k+1},\Delta\nu^{k+1}\rangle,$
(3.10)

where $E_{k}$ is defined by (3.1).

######  Lemma 3.3.

For all $k=0,1,\cdots$ there hold

$\displaystyle\sigma_{f}\|y^{k+1}-y^{\dagger}\|^{2}\leq\Phi_{k}-\Phi_{k+1}-\langle\lambda^{k+1}-\lambda^{\dagger},b^{\delta}-b\rangle-
E_{k+1},$ (3.11) $\displaystyle
E_{k+1}\leq\Phi_{k}-\Phi_{k+1}+\sqrt{2\rho_{1}\Phi_{k+1}}\delta$ (3.12)

and

$\displaystyle\Phi_{k+1}\leq\Phi_{0}+\left(\sum_{j=1}^{k+1}\sqrt{2\rho_{1}\Phi_{j}}\right)\delta.$
(3.13)

###### Proof.

By using (3.6) and the monotonicity of the subdifferentials $\partial f$ and
$\partial\iota_{\mathcal{C}}$ we have

$0\leq\sigma_{f}\|\Delta y^{k+1}\|^{2}\leq\langle\Delta\mu^{k+1},\Delta
y^{k+1}\rangle+\langle\Delta\nu^{k+1},\Delta x^{k+1}\rangle.$

This together with (3) implies (3.11). From (3.11) it follows immediately that

$\displaystyle E_{k+1}$
$\displaystyle\leq\Phi_{k}-\Phi_{k+1}-\langle\lambda^{k+1}-\lambda^{\dagger},b^{\delta}-b\rangle$
$\displaystyle\leq\Phi_{k}-\Phi_{k+1}+\|\lambda^{k+1}-\lambda^{\dagger}\|\delta$
$\displaystyle\leq\Phi_{k}-\Phi_{k+1}+\sqrt{2\rho_{1}\Phi_{k+1}}\delta$

which shows (3.12). By the non-negativity of $E_{k+1}$ we then obtain from
(3.12) that

$\Phi_{k+1}\leq\Phi_{k}+\sqrt{2\rho_{1}\Phi_{k+1}}\delta,\quad\forall k\geq 0$

which clearly implies (3.13). ∎

In order to derive the estimate on $\Phi_{k}$ from (3.13), we need the
following elementary result.

######  Lemma 3.4.

Let $\\{a_{k}\\}$ and $\\{b_{k}\\}$ be two sequences of nonnegative numbers
such that

$a_{k}^{2}\leq b_{k}^{2}+c\sum_{j=1}^{k}a_{j},\quad k=0,1,\cdots,$

where $c\geq 0$ is a constant. If $\\{b_{k}\\}$ is non-decreasing, then

$a_{k}\leq b_{k}+ck,\quad k=0,1,\cdots.$

###### Proof.

We show the result by induction on $k$. The result is trivial for $k=0$ since
the given condition with $k=0$ gives $a_{0}\leq b_{0}$. Assume that the result
is valid for all $0\leq k\leq l$ for some $l\geq 0$. We show it is also true
for $k=l+1$. If $a_{l+1}\leq\max\\{a_{0},\cdots,a_{l}\\}$, then $a_{l+1}\leq
a_{j}$ for some $0\leq j\leq l$. Thus, by the induction hypothesis and the
monotonicity of $\\{b_{k}\\}$ we have

$a_{l+1}\leq a_{j}\leq b_{j}+cj\leq b_{l+1}+c(l+1).$

If $a_{l+1}>\max\\{a_{0},\cdots,a_{l}\\}$, then

$\displaystyle a_{l+1}^{2}\leq b_{l+1}^{2}+c\sum_{j=1}^{l+1}a_{j}\leq
b_{l+1}^{2}+c(l+1)a_{l+1}$

which implies that

$\displaystyle\left(a_{l+1}-\frac{1}{2}c(l+1)\right)^{2}$
$\displaystyle=a_{l+1}^{2}-c(l+1)a_{l+1}+\frac{1}{4}c^{2}(l+1)^{2}$
$\displaystyle\leq b_{l+1}^{2}+\frac{1}{4}c^{2}(l+1)^{2}$
$\displaystyle\leq\left(b_{l+1}+\frac{1}{2}c(l+1)\right)^{2}.$

Taking square roots shows $a_{l+1}\leq b_{l+1}+c(l+1)$ again. ∎

######  Lemma 3.5.

There hold

$\displaystyle\Phi_{k}^{1/2}\leq\Phi_{0}^{1/2}+\sqrt{2\rho_{1}}k\delta,\quad\forall
k\geq 0$ (3.14)

and

$\displaystyle
E_{k}\leq\frac{2\Phi_{0}}{k}+\frac{5}{2}\rho_{1}k\delta^{2},\quad\forall k\geq
1.$ (3.15)

###### Proof.

Based on (3.13), we may use Lemma 3.4 with $a_{k}=\Phi_{k}^{1/2}$,
$b_{k}=\Phi_{0}^{1/2}$ and $c=(2\rho_{2})^{1/2}\delta$ to obtain (3.14)
directly. Next, by using the monotonicity of $\\{E_{k}\\}$, (3.12) and (3.14)
we have

$\displaystyle kE_{k}$
$\displaystyle\leq\sum_{j=1}^{k}E_{j}\leq\sum_{j=1}^{k}\left(\Phi_{j-1}-\Phi_{j}+\sqrt{2\rho_{1}\Phi_{j}}\delta\right)$
$\displaystyle\leq\Phi_{0}-\Phi_{k}+\sum_{j=1}^{k}\sqrt{2\rho_{1}\Phi_{j}}\delta$
$\displaystyle\leq\Phi_{0}+\sum_{j=1}^{k}\sqrt{2\rho_{1}}\left(\sqrt{\Phi_{0}}+\sqrt{2\rho_{1}}j\delta\right)\delta$
$\displaystyle=\Phi_{0}+\sqrt{2\rho_{1}\Phi_{0}}k\delta+\rho_{1}k(k+1)\delta^{2}$
$\displaystyle\leq 2\Phi_{0}+\frac{5}{2}\rho_{1}k^{2}\delta^{2}$

which shows (3.15). ∎

Now we are ready to complete the proof of Theorem 3.2.

###### Proof of Theorem 3.2.

Let $k_{\delta}$ be an integer such that $k_{\delta}\sim\delta^{-1}$. From
(3.14) and (3.15) in Lemma 3.5 it follows that

$\displaystyle E_{k_{\delta}}\leq C_{0}\delta\quad\mbox{and}\quad\Phi_{k}\leq
C_{1}\mbox{ for all }k\leq k_{\delta},$ (3.16)

where $C_{0}$ and $C_{1}$ are constants independent of $k$ and $\delta$. In
order to use (3.11) in Lemma 3.3 to estimate $\|y^{k_{\delta}}-y^{\dagger}\|$,
we first consider $\Phi_{k}-\Phi_{k+1}$ for all $k\geq 0$. By using the
definition of $\Phi_{k}$ and the inequality
$\|u\|^{2}-\|v\|^{2}\leq(\|u\|+\|v\|)\|u-v\|$, we have for $k\geq 0$ that

$\displaystyle\Phi_{k}-\Phi_{k+1}$
$\displaystyle\leq\frac{1}{2\rho_{1}}\left(\|\lambda^{k}-\lambda^{\dagger}\|+\|\lambda^{k+1}-\lambda^{\dagger}\|\right)\|\Delta\lambda^{k+1}\|$
$\displaystyle\quad\
+\frac{1}{2\rho_{2}}\left(\|\mu^{k}-\mu^{\dagger}\|+\|\mu^{k+1}-\mu^{\dagger}\|\right)\|\Delta\mu^{k+1}\|$
$\displaystyle\quad\
+\frac{1}{2\rho_{3}}\left(\|\nu^{k}-\nu^{\dagger}\|+\|\nu^{k+1}-\nu^{\dagger}\|\right)\|\Delta\nu^{k+1}\|$
$\displaystyle\quad\
+\frac{1}{2}\left(\|z^{k}-x^{\dagger}\|_{Q}+\|z^{k+1}-x^{\dagger}\|_{Q}\right)\|\Delta
z^{k+1}\|_{Q}$ $\displaystyle\quad\
+\frac{\rho_{2}}{2}\left(\|y^{k}-y^{\dagger}\|+\|y^{k+1}-y^{\dagger}\|\right)\|\Delta
y^{k+1}\|$ $\displaystyle\quad\
+\frac{\rho_{3}}{2}\left(\|x^{k}-x^{\dagger}\|+\|x^{k+1}-x^{\dagger}\|\right)\|\Delta
x^{k+1}\|.$

By virtue of the Cauchy-Schwarz inequality and the inequality $(a+b)^{2}\leq
2(a^{2}+b^{2})$ for any numbers $a,b\in{\mathbb{R}}$ we can further obtain

$\displaystyle\Phi_{k}-\Phi_{k+1}\leq\sqrt{2(\Phi_{k}+\Phi_{k+1})E_{k+1}},\quad\forall
k\geq 0.$

This together with (3.16) in particular implies

$\Phi_{k_{\delta}-1}-\Phi_{k_{\delta}}\leq\sqrt{4C_{0}C_{1}\delta}.$

Therefore, it follows from (3.11) that

$\displaystyle\sigma_{f}\|y^{k_{\delta}}-y^{\dagger}\|^{2}$
$\displaystyle\leq\Phi_{k_{\delta}-1}-\Phi_{k_{\delta}}+\|\lambda^{k_{\delta}}-\lambda^{\dagger}\|\delta$
$\displaystyle\leq\sqrt{4C_{0}C_{1}\delta}+\sqrt{2\rho_{1}\Phi_{k_{\delta}}}\delta$
$\displaystyle\leq\sqrt{4C_{0}C_{1}\delta}+\sqrt{2\rho_{1}C_{1}}\delta.$

Thus

$\displaystyle\|y^{k_{\delta}}-y^{\dagger}\|^{2}\leq C_{2}\delta^{1/2},$

where $C_{2}$ is a constant independent of $\delta$ and $k$. By using the
estimate $E_{k_{\delta}}\leq C_{0}\delta$ in (3.16), the definition of
$E_{k_{\delta}}$, and the last three equations in (1.11), we can see that

$\displaystyle\|Az^{k_{\delta}}-b^{\delta}\|^{2}=\frac{1}{\rho_{1}^{2}}\|\Delta\lambda^{k_{\delta}}\|^{2}\leq\frac{2}{\rho_{1}}E_{k_{\delta}}\leq\frac{2C_{0}}{\rho_{1}}\delta,$
$\displaystyle\|Lz^{k_{\delta}}-y^{k_{\delta}}\|^{2}=\frac{1}{\rho_{2}^{2}}\|\Delta\mu^{k_{\delta}}\|^{2}\leq\frac{2}{\rho_{2}}E_{k_{\delta}}\leq\frac{2C_{0}}{\rho_{2}}\delta,$
$\displaystyle\|z^{k_{\delta}}-x^{k_{\delta}}\|^{2}=\frac{1}{\rho_{3}^{2}}\|\Delta\nu^{k_{\delta}}\|^{2}\leq\frac{2}{\rho_{3}}E_{k_{\delta}}\leq\frac{2C_{0}}{\rho_{3}}\delta.$

Therefore

$\displaystyle\|L(z^{k_{\delta}}-x^{\dagger})\|^{2}\leq
2\left(\|Lz^{k_{\delta}}-y^{k_{\delta}}\|^{2}+\|y^{k_{\delta}}-y^{\dagger}\|^{2}\right)\leq\frac{4C_{0}}{\rho_{2}}\delta+2C_{2}\delta^{1/2},$
$\displaystyle\|A(z^{k_{\delta}}-x^{\dagger})\|^{2}\leq
2\left(\|Az^{k_{\delta}}-b^{\delta}\|^{2}+\|b^{\delta}-b\|^{2}\right)\leq
2\left(\frac{2C_{0}}{\rho_{1}}+1\right)\delta.$

By virtue of (iii) in Assumption 3.1 on $A$ and $L$ we thus obtain

$\displaystyle c_{0}\|z^{k_{\delta}}-x^{\dagger}\|^{2}$
$\displaystyle\leq\|A(z^{k_{\delta}}-x^{\dagger})\|^{2}+\|L(z^{k_{\delta}}-x^{\dagger})\|^{2}$
$\displaystyle\leq
2\left(\frac{2C_{0}}{\rho_{1}}+\frac{2C_{0}}{\rho_{1}}+1\right)\delta+2C_{2}\delta^{1/2}.$

This means there is a constant $C_{3}$ independent of $\delta$ and $k$ such
that

$\displaystyle\|z^{k_{\delta}}-x^{\dagger}\|^{2}\leq C_{3}\delta^{1/2}.$

Finally we obtain

$\|x^{k_{\delta}}-x^{\dagger}\|^{2}\leq
2\left(\|x^{k_{\delta}}-z^{k_{\delta}}\|^{2}+\|z^{k_{\delta}}-x^{\dagger}\|^{2}\right)\leq\frac{4C_{0}}{\rho_{3}}\delta+2C_{3}\delta^{1/2}.$

The proof is thus complete. ∎

######  Remark 3.1.

Under the benchmark source condition (3.2), we have obtained in Theorem 3.2
the convergence rate $O(\delta^{1/4})$ for the proximal ADMM (1.11). This rate
is not order optimal. It is not yet clear if the order optimal rate
$O(\delta^{1/2})$ can be achieved.

######  Remark 3.2.

When using the proximal ADMM to solve (1.9) with $L=I$, i.e.

$\displaystyle\min\left\\{f(x):Ax=b\mbox{ and }x\in\mathcal{C}\right\\},$
(3.17)

it is not necessary to introduce the $y$-variable as is done in (1.11) and
thus (1.11) can be simplified to the scheme

$\displaystyle\begin{split}&z^{k+1}=\arg\min_{z\in\mathcal{X}}\left\\{{\mathscr{L}}_{\rho_{1},\rho_{2}}(z,x^{k},\lambda^{k},\nu^{k})+\frac{1}{2}\|z-z^{k}\|_{Q}^{2}\right\\},\\\
&x^{k+1}=\arg\min_{x\in\mathcal{X}}\left\\{{\mathscr{L}}_{\rho_{1},\rho_{2}}(z^{k+1},x,\lambda^{k},\nu^{k})\right\\},\\\
&\lambda^{k+1}=\lambda^{k}+\rho_{1}(Az^{k+1}-b^{\delta}),\\\
&\nu^{k+1}=\nu^{k}+\rho_{2}(z^{k+1}-x^{k+1}),\end{split}$ (3.18)

where

${\mathscr{L}}_{\rho_{1},\rho_{2}}(z,x,\lambda,\nu):=f(z)+\iota_{\mathcal{C}}(x)+\langle\lambda,Az-b^{\delta}\rangle+\langle\nu,z-x\rangle+\frac{\rho_{1}}{2}\|Az-b^{\delta}\|^{2}+\frac{\rho_{2}}{2}\|z-x\|^{2}.$

The source condition (1.9) reduces to the form

$\displaystyle\exists\mu^{\dagger}\in\partial f(x^{\dagger})\mbox{ and
}\nu^{\dagger}\in\partial\iota_{\mathcal{C}}(x^{\dagger})\mbox{ such that
}\mu^{\dagger}+\nu^{\dagger}\in\mbox{Ran}(A^{*}).$ (3.19)

If the unique solution $x^{\dagger}$ of (3.17) satisfies the source condition
(3.19), one may follow the proof of Theorem 3.2 with minor modification to
deduce for the method (3.18) that

$\|x^{k_{\delta}}-x^{\dagger}\|=O(\delta^{1/4})\quad\mbox{ and
}\quad\|z^{k_{\delta}}-x^{\dagger}\|=O(\delta^{1/4})$

whenever the integer $k_{\delta}$ is chosen such that
$k_{\delta}\sim\delta^{-1}$.

We conclude this section by presenting a numerical result to illustrate the
semi-convergence property of the proximal ADMM and the convergence rate. We
consider finding a solution of (1.8) with minimal norm. This is equivalent to
solving (3.17) with $f(y)=\frac{1}{2}\|y\|^{2}$. With a noisy data
$b^{\delta}$ satisfying $\|b^{\delta}-b\|\leq\delta$, the corresponding
proximal ADMM (3.18) takes the form

$\displaystyle\begin{split}z^{k+1}&=\left((1+\rho_{2})I+Q+\rho_{1}A^{*}A\right)^{-1}\left(\rho_{1}A^{*}b^{\delta}+\rho_{2}x^{k}+Qz^{k}-A^{*}\lambda^{k}-\nu^{k}\right),\\\
x^{k+1}&=P_{\mathcal{C}}\left(z^{k+1}+\nu^{k}/\rho_{2}\right),\\\
\lambda^{k+1}&=\lambda^{k}+\rho_{1}(Az^{k+1}-b^{\delta}),\\\
\nu^{k+1}&=\nu^{k}+\rho_{2}(z^{k+1}-x^{k+1}),\end{split}$ (3.20)

where $P_{\mathcal{C}}$ denotes the orthogonal projection of $\mathcal{X}$
onto $\mathcal{C}$. The source condition (3.19) now takes the form

$\displaystyle\exists\nu^{\dagger}\in\partial\iota_{\mathcal{C}}(x^{\dagger})\mbox{
such that }x^{\dagger}+\nu^{\dagger}\in\mbox{Ran}(A^{*})$ (3.21)

which is equivalent to the projected source condition $x^{\dagger}\in
P_{\mathcal{C}}(\mbox{Ran}(A^{*}))$.

######  Example 3.1.

In our numerical simulation we consider the first kind integral equation

$\displaystyle(Ax)(t):=\int_{0}^{1}\kappa(s,t)x(s)ds=b(t),\quad t\in[0,1]$
(3.22)

on $L^{2}[0,1]$, where the kernel $\kappa$ is continuous on
$[0,1]\times[0,1]$. Such equations arise naturally in many linear ill-posed
inverse problems, see [12, 18]. Clearly $A$ is a compact linear operator from
$L^{2}[0,1]$ to itself. We will use

$\kappa(s,t)=d\left(d^{2}+(s-t)^{2}\right)^{-3/2}$

with $d=0.1$. The corresponding equation is a 1-D model problem in gravity
surveying. Assume the equation (3.22) has a nonnegative solution. We will
employ the method (3.20) to determine the unique nonnegative solution of
(3.22) with minimal norm in case the data is corrupted by noise. Here
$\mathcal{C}:=\\{x\in L^{2}[0,1]:x\geq 0\mbox{ a.e.}\\}$ and thus
$P_{\mathcal{C}}(x)=\max\\{x,0\\}$.

Figure 1. (a) plots the true solution $x^{\dagger}$, (b) and (c) plot the
relative errors versus the number of iterations for the method (3.20) using
noisy data with noise level $\delta=10^{-2}$ and $10^{-4}$ respectively

In order to investigate the convergence rate of the method, we generate our
data as follows. First take $\omega^{\dagger}\in L^{2}[0,1]$, set
$x^{\dagger}:=\max\\{A^{*}\omega^{\dagger},0\\}$ and define $b:=Ax^{\dagger}$.
Thus $x^{\dagger}$ is a nonnegative solution of $Ax=b$ satisfying
$x^{\dagger}=P_{\mathcal{C}}(A^{*}\omega^{\dagger})$, i.e. the source
condition (3.21) holds. We use $\omega^{\dagger}=t^{3}(0.9-t)(t-0.35)$, the
corresponding $x^{\dagger}$ is plotted in Figure 1 (a). We then pick a random
data $\xi$ with $\|\xi\|_{L^{2}[0,1]}=1$ and generate the noisy data
$b^{\delta}$ by $b^{\delta}:=b+\delta\xi$. Clearly
$\|b^{\delta}-b\|_{L^{2}[0,1]}=\delta$.

Table 1. Numerical results for the method (3.20) using noisy data with diverse noise levels, where $\texttt{err}_{\min}$ and $\texttt{iter}_{\min}$ denote respectively the the smallest relative error and the required number of iterations.  $\delta$ | $\texttt{err}_{\min}$ | $\texttt{iter}_{\min}$ | $\texttt{err}_{\min}/\delta^{1/2}$ | $\texttt{err}_{\min}/\delta^{1/4}$
---|---|---|---|---
1e-1 | 4.9307e-2 | 1 | 0.155922 | 0.087681
1e-2 | 1.3255e-2 | 2 | 0.132553 | 0.041917
1e-3 | 5.2985e-3 | 19 | 0.167552 | 0.029796
1e-4 | 2.1196e-3 | 501 | 0.211957 | 0.021196
1e-5 | 7.2638e-4 | 2512 | 0.229702 | 0.012917
1e-6 | 2.7450e-4 | 31447 | 0.274496 | 0.008680
1e-7 | 7.4693e-5 | 329542 | 0.236199 | 0.004200

For numerical implementation, we discretize the equation by the trapzoidal
rule based on partitioning $[0,1]$ into $N-1$ subintervals of equal length
with $N=600$. We then execute the method (3.20) with $Q=0$, $\rho_{1}=10$,
$\rho_{2}=1$ and the initial guess $x^{0}=\lambda^{0}=\nu^{0}=0$ using the
noisy data $b^{\delta}$ for several distinct values of $\delta$. In Figure 1
(b) and (c) we plot the relative error
$\|x^{k}-x^{\dagger}\|_{L^{2}}/\|x^{\dagger}\|_{L^{2}}$ versus $k$, the number
of iterations, for $\delta=10^{-2}$ and $\delta=10^{-4}$ respectively. These
plots demonstrate that the proximal ADMM always exhibits the semi-convergence
phenomenon when used to solve ill-posed problems, no matter how small the
noise level is. Therefore, properly terminating the iteration is important to
produce useful approximate solutions. This has been done in [21, 22].

In Table 1 we report further numerical results. For the noisy data
$b^{\delta}$ with each noise level $\delta=10^{-i}$, $i=1,\cdots,7$, we
execute the method and determine the smallest relative error, denoted by
$\texttt{err}_{\min}$, and the required number of iterations, denoted by
$\texttt{iter}_{\min}$. The ratios $\texttt{err}_{\min}/\delta^{1/2}$ and
$\texttt{err}_{\min}/\delta^{1/4}$ are then calculated. Since $x^{\dagger}$
satisfies the source condition (3.21), our theoretical result predicts the
convergence rate $O(\delta^{1/4})$. However, Table 1 illustrates that the
value of $\texttt{err}_{\min}/\delta^{1/2}$ does not change much while the
value of $\texttt{err}_{\min}/\delta^{1/4}$ tends to decrease to 0 as
$\delta\to 0$. This strongly suggests that the proximal ADMM admits the order
optimal convergence rate $O(\delta^{1/2})$ if the source condition (3.21)
holds. However, how to derive this order optimal rate remains open.

## References

  * [1] H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., Ser. B, 116 (2009), 5–16.
  * [2] H. Attouch and M. Soueycatt, Augmented Lagrangian and proximal alternating direction methods of multipliers in Hilbert spaces. Applications to games, PDE’s and control, Pac. J. Optim., 5 (2009), no. 1, 17–37.
  * [3] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York, 2011.
  * [4] A. Beck, First-Order Methods in Optimization, MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, 2017.
  * [5] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3(1): 1–122, 2011.
  * [6] K. Bredies and H. Sun, A proximal point analysis of the preconditioned alternating direction method of multipliers, J. Optim. Theory Appl., 173 (2017), no. 3, 878–907.
  * [7] M. Burger and S. Osher, Convergence rates of convex variational regularization, Inverse Problems 20 (2004), no. 5, 1411–1421.
  * [8] D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, Splitting methods in communication, imaging, science, and engineering, 115–163, Sci. Comput., Springer, Cham, 2016.
  * [9] W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), 889–916.
  * [10] J. Eckstein and D. P. Bertsekas, On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55(1-3): 293–318, 1992.
  * [11] I. Ekeland and R. Temam, Convex Analysis and Variational Problems, Amsterdam: North Holland, 1976.
  * [12] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Dordrecht, Kluwer, 1996.
  * [13] K. Frick and O. Scherzer, Regularization of ill-posed linear equations by the non-stationary augmented Lagrangian method, J. Integral Equ. Appl., 22 (2010), no. 2, 217–257.
  * [14] D. Gabay, Applications of the method of multipliers to variational inequalities, Studies in Mathematics and its Applications, 15, 299–331, 1983.
  * [15] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), 17–40.
  * [16] R. Glowinski and A. Marrocco, Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problémes de Dirichlet non linéaires, ESAIM: Math. Model. Numer. Anal., 9(R2):41–76, 1975.
  * [17] T. Goldstein, X. Bresson and S. Osher, Geometric applications of the split Bregman method: segmentation and surface reconstruction, J. Sci. Comput., 45 (2010), no. 1, 272–293.
  * [18] C. W. Groetsch, The theory of Tikhonov regularization for Fredholm equations of the first kind, Research Notes in Mathematics, 105. Pitman (Advanced Publishing Program), Boston, MA, 1984.
  * [19] B. He and X. Yuan, On the $O(1/n)$ convergence rate of Douglas–Rachford alternating direction method, SIAM J. Numer. Anal., 50 (2012), 700–709.
  * [20] B. He and X. Yuan, On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers, Numer. Math., 130 (2015), 567–577.
  * [21] Y. Jiao, Q. Jin, X. Lu and W. Wang, Alternating direction method of multipliers for linear inverse problems, SIAM J. Numer. Anal., 54 (2016), no. 4, 2114–2137.
  * [22] Y. Jiao, Q. Jin, X. Lu and W. Wang, Preconditioned alternating direction method of multipliers for solving inverse problems with constraints, Inverse Problems, 33 (2017), 025004 (34pp).
  * [23] Q. Jin, Convergence rates of a dual gradient method for constrained linear ill-posed problems, Numer. Math. 151 (2022), no. 4, 841–871.
  * [24] J. H. Lee and T. S. Pham, Openness, Hölder metric regularity, and Hölder continuity properties of semialgebraic set-valued maps, SIAM J. Optim., 32 (2022), no. 1, pp. 56–74.
  * [25] T. Lin, S. Ma and S. Zhang, On the Sublinear Convergence Rate of Multi-Block ADMM, J. Oper. Res. Soc. China, 3 (2015), no. 3, 251–274.
  * [26] P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16(6), 964–979, 1979.
  * [27] Y. Liu, X. Yuan, S. Zeng and J. Zhang, Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers, SIAM J. Numer. Anal., 56 (2018), no. 4, 2095–2123.
  * [28] F. Natterer,The Mathematics of Computerized Tomography, SIAM, Philadelphia, 2001.
  * [29] E. Resmerita and O. Scherzer, Error estimates for non-quadratic regularization and the relation to enhancement, Inverse Problems, 22 (2006), no. 3, 801–814.
  * [30] S. M. Robinson, Some continuity properties of polyhedral multifunctions, Math. Program. Study, 14 (1981), pp. 206–214.
  * [31] H. Sun, Analysis of Fully Preconditioned Alternating Direction Method of Multipliers with Relaxation in Hilbert Spaces, J. Optim. Theory Appl., 183 (2019), no. 1, 199–229.
  * [32] W. H. Yang and D. R. Han, Linear convergence of alternating direction method of multipliers for a class of convex optimization problems, SIAM J. Numer. Anal., 54 (2016), no. 2, 625–640.
  * [33] X. Zhang, M. Burger and S. Osher, A unified primal–dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2011), 20–46.
  * [34] X. Y. Zheng and K. F. Ng, Metric subregularity of piecewise linear multifunctions and applications to piecewise linear multiobjective optimization, SIAM J. Optim., 24 (2014), no. 1, 154–174.