# Distributed and Asynchronous Algorithms for N-block Convex Optimization with
Coupling Constraints

Run Chen
School of Industrial Engineering
Purdue University
West Lafayette, IN 47906
<EMAIL_ADDRESS>
&Andrew L. Liu
School of Industrial Engineering
Purdue University
West Lafayette, IN 47906
<EMAIL_ADDRESS>

##  1 Introduction

In this work, we focus on designing a distributed algorithm for solving block-
separable convex optimization problems with both linear and nonlinear coupling
constraints. More specifically, we consider the following problem:

$\displaystyle\underset{\mathbf{x}_{1},\dots,\mathbf{x}_{N}}{\text{minimize}}$
$\displaystyle
f(\mathbf{x}_{1},\ldots,\mathbf{x}_{N})=\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i})$
(1) subject to $\displaystyle\mathbf{x}_{i}\in\mathcal{X}_{i},\quad
i=1,\dots,N,$ $\displaystyle\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}=\mathbf{b},$
$\displaystyle
g_{j}(\mathbf{x}_{1},\dots,\mathbf{x}_{N})=\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i})\leq
0,\quad j=1,\dots,M,$

where each block of decision variable $\mathbf{x}_{i}\in\mathbb{R}^{n_{i}}$ is
constrained by a closed and convex set
$\mathcal{X}_{i}\subset\mathbb{R}^{n_{i}}$ for all $i=1,\dots,N$, and
$\sum_{i=1}^{N}n_{i}=n$. The objective function
$f:\mathbb{R}^{n}\to\mathbb{R}$ is block-separable, and each function
$f_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}$ is assumed to be continuous and convex
for all $i=1,\dots,N$. All blocks $\mathbf{x}_{i}$’s are coupled in a linear
equality constraint, where each $A_{i}\in\mathbb{R}^{m\times n_{i}}$ is a
given matrix for all $i=1,\dots,N$, and $\mathbf{b}\in\mathbb{R}^{m}$ is a
given vector. All blocks $\mathbf{x}_{i}$’s are also coupled in a system of
nonlinear inequality constraints, where each constraint function
$g_{j}:\mathbb{R}^{n}\to\mathbb{R}$ is also block-separable and each function
$g_{ji}:\mathbb{R}^{n_{i}}\to\mathbb{R}$ is assumed to be continuous and
convex for all $i=1,\dots,N$ and $j=1,\dots,M$. A wide range of application
problems can be mathematically formulated as optimization problems of the form
(1), arising from the areas including optimal control [14], network
optimization [7], statistical learning [2] and etc.

The alternating direction method of multipliers (ADMM) [2], as well as its
variants [6, 12, 13], is an efficient distributed algorithm for solving convex
block-separable optimization problems with linear coupling constraints, but
problems of (1) with nonlinear coupling constraints can not be directly
handled by ADMM-typed algorithms.

To overcome the above-mentioned limitations of the ADMM-typed algorithms, we
first extend the $2$-block Predictor Corrector Proximal Multiplier Method
(PCPM) algorithm to solve an $N$-block convex optimization problem with both
linear and nonlinear coupling constraints. We further extend the $N$-block
PCPM algorithm to an asynchronous iterative scheme, where a maximum tolerable
delay is allowed for each distributed unit, and apply it to solve an $N$-block
convex optimization problem with general linear coupling constraints.

The remainder of the chapter is organized as follows. In Section 2, we present
an extended $N$-block PCPM algorithm for solving general constrained $N$-block
convex optimization problems. We first establish global convergence under mild
assumptions, and then prove the linear convergence rate with slightly stronger
assumptions. In Section 3, we further extend the N-block PCPM algorithm to an
asynchronous scheme with the bounded delay assumption. We establish both
convergence and global sub-linear convergence rate under the conditions of
strong convexity. Section 4 presents the numerical results of applying the
proposed algorithms to solve a graph optimization problem arising from an
application of housing price prediction. Finally, Section 5 concludes this
chapter with discussions of the limitations of the algorithms and possible
future research directions.

##  2 Extending the PCPM Algorithm to Solving General Constrained N-block
Convex Optimization Problems

###  2.1 PCPM Algorithm

To present our distributed algorithm, we first briefly describe the original
PCPM algorithm [5] to make this paper self-contained. For this purpose, it
suffices to consider a 2-block linearly constrained convex optimization
problem:

$\displaystyle\underset{\mathbf{x}_{1}\in\mathbb{R}^{n_{1}},\
\mathbf{x}_{2}\in\mathbb{R}^{n_{2}}}{\text{minimize}}$ $\displaystyle
f_{1}(\mathbf{x}_{1})+f_{2}(\mathbf{x}_{2})$ (2) subject to $\displaystyle
A_{1}\mathbf{x}_{1}+A_{2}\mathbf{x}_{2}=\mathbf{b},\quad(\bm{\lambda})$

where $f_{1}:\mathbb{R}^{n_{1}}\to(-\infty,+\infty]$ and
$f_{2}:\mathbb{R}^{n_{2}}\to(-\infty,+\infty]$ are closed proper convex
functions, $A_{1}\in\mathbb{R}^{m\times n_{1}}$ and
$A_{2}\in\mathbb{R}^{m\times n_{2}}$ are full row-rank matrices,
$\mathbf{b}\in\mathbb{R}^{m}$ is a given vector, and
$\bm{\lambda}\in\mathbb{R}^{m}$ is the corresponding Lagrangian multiplier
associated with the linear equality constraint. The classic Lagrangian
function
$\mathcal{L}:\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}\times\mathbb{R}^{m}\to\mathbb{R}$
is defined as:

$\mathcal{L}(\mathbf{x}_{1},\mathbf{x}_{2},\bm{\lambda})=f_{1}(\mathbf{x}_{1})+f_{2}(\mathbf{x}_{2})+\bm{\lambda}^{T}(A_{1}\mathbf{x}_{1}+A_{2}\mathbf{x}_{2}-\mathbf{b}).$
(3)

It is well-known that for a convex problem of the specific form in (2) (where
the linear constraint qualification automatically holds), finding an optimal
solution is equivalent to finding a saddle point
$(\mathbf{x}_{1}^{*},\mathbf{x}_{2}^{*},\bm{\lambda}^{*})$ such that
$\mathcal{L}(\mathbf{x}_{1}^{*},\mathbf{x}_{2}^{*},\bm{\lambda})\leq\mathcal{L}(\mathbf{x}_{1}^{*},\mathbf{x}_{2}^{*},\bm{\lambda}^{*})\leq\mathcal{L}(\mathbf{x}_{1},\mathbf{x}_{2},\bm{\lambda}^{*})$.
To find such a saddle point, a simple dual decomposition algorithm can be
applied to $\mathcal{L}(\mathbf{x}_{1},\mathbf{x}_{2},\bm{\lambda})$. More
specifically, at each iteration $k$, given a fixed Lagrangian multiplier
$\bm{\lambda}^{k}$, the primal decision variables
$(\mathbf{x}_{1}^{k+1},\mathbf{x}_{2}^{k+1})$ can be obtained, in parallel, by
minimizing $\mathcal{L}(\mathbf{x}_{1},\mathbf{x}_{2},\bm{\lambda}^{k})$. Then
a dual update
$\bm{\lambda}^{k+1}=\bm{\lambda}^{k}+\rho(A_{1}\mathbf{x}_{1}^{k+1}+A_{2}\mathbf{x}_{2}^{k+1}-\mathbf{}b)$
is performed.

While the above algorithmic idea is simple, it is well-known that convergence
cannot be established without more restrictive assumptions, such as strict
convexity of $f_{1}$ and $f_{2}$ (e.g., Theorem 26.3 in [10]). One approach to
overcome such difficulties is the proximal point algorithm, which obtains
$(\mathbf{x}_{1}^{k+1},\mathbf{x}_{2}^{k+1})$ by minimizing the proximal
augmented Lagrangian function defined as
$\mathcal{L}_{\rho}(\mathbf{x}_{1},\mathbf{x}_{2},\bm{\lambda}^{k}):=\mathcal{L}(\mathbf{x}_{1},\mathbf{x}_{2},\bm{\lambda}^{k})+\frac{\rho}{2}\lVert
A_{1}\mathbf{x}_{1}+A_{2}\mathbf{x}_{2}-\mathbf{b}\rVert_{2}^{2}+\frac{1}{2\rho}\lVert\mathbf{x}_{1}-\mathbf{x}_{1}^{k}\rVert_{2}^{2}+\frac{1}{2\rho}\lVert\mathbf{x}_{2}-\mathbf{x}_{2}^{k}\rVert_{2}^{2}$.
The parameter $\rho$ is given, which determines the step-size for updating
both primal and dual variables in each iteration, and plays a key role in the
convergence of the overall algorithm. The primal minimization step now
becomes:

$\displaystyle(\mathbf{x}_{1}^{k+1},\mathbf{x}_{2}^{k+1})=\underset{\mathbf{x}_{1}\in\mathbb{R}^{n_{1}},\mathbf{x}_{2}\in\mathbb{R}^{n_{2}}}{\operatorname*{\arg\\!\min}}$
$\displaystyle
f_{1}(\mathbf{x}_{1})+f_{2}(\mathbf{x}_{2})+(\bm{\lambda}^{k})^{T}(A_{1}\mathbf{x}_{1}+A_{2}\mathbf{x}_{2}-\mathbf{b})$
$\displaystyle+$ $\displaystyle\frac{\rho}{2}\lVert
A_{1}\mathbf{x}_{1}+A_{2}\mathbf{x}_{2}-\mathbf{b}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle\frac{1}{2\rho}\lVert\mathbf{x}_{1}-\mathbf{x}_{1}^{k}\rVert_{2}^{2}+\frac{1}{2\rho}\lVert\mathbf{x}_{2}-\mathbf{x}_{2}^{k}\rVert_{2}^{2}.$
(4)

With (4), however, $\mathbf{x}_{1}^{k+1}$ and $\mathbf{x}_{2}^{k+1}$ can no
longer be obtained in parallel due to the augmented term $\lVert
A_{1}\mathbf{x}_{1}+A_{2}\mathbf{x}_{2}-\mathbf{b}\rVert_{2}^{2}$. To overcome
this difficulty, the PCPM algorithm introduces a predictor variable
$\bm{\mu}^{k+1}$:

$\bm{\mu}^{k+1}\coloneqq\bm{\lambda}^{k}+\rho(A_{1}\mathbf{x}_{1}^{k}+A_{2}\mathbf{x}_{2}^{k}-\mathbf{b}).$
(5)

Using the predictor variable, the optimization in (4) can be approximated as:

$\displaystyle(\mathbf{x}_{1}^{k+1},\mathbf{x}_{2}^{k+1})=\underset{\mathbf{x}_{1}\in\mathbb{R}^{n_{1}},\mathbf{x}_{2}\in\mathbb{R}^{n_{2}}}{\operatorname*{\arg\\!\min}}$
$\displaystyle
f_{1}(\mathbf{x}_{1})+f_{2}(\mathbf{x}_{2})+(\bm{\mu}^{k+1})^{T}(A_{1}\mathbf{x}_{1}+A_{2}\mathbf{x}_{2}-\mathbf{b})$
$\displaystyle+$
$\displaystyle\frac{1}{2\rho}\lVert\mathbf{x}_{1}-\mathbf{x}_{1}^{k}\rVert_{2}^{2}+\frac{1}{2\rho}\lVert\mathbf{x}_{2}-\mathbf{x}_{2}^{k}\rVert_{2}^{2},$
(6)

which allows $\mathbf{x}_{1}^{k+1}$ and $\mathbf{x}_{2}^{k+1}$ to be obtained
in parallel again. After solving (6), the PCPM algorithm updates the dual
variable as follows:

$\bm{\lambda}^{k+1}=\bm{\lambda}^{k}+\rho(A_{1}\mathbf{x}_{1}^{k+1}+A_{2}\mathbf{x}_{2}^{k+1}-\mathbf{b}),$
(7)

which is referred to as a corrector update.

###  2.2 N-block PCPM Algorithm for General Constrained Convex Optimization
Problems

In the $2$-block PCPM algorithm presented in Section 2.1, we observe that the
introduction of the predictor variable eliminates the quadratic term in the
proximal augmented Lagrangian function and make the primal minimization step
parallelizable again, which is a major difference from the ADMM algorithm. For
an $N$-block convex optimization problem with additional nonlinear coupling
constraints:

$\displaystyle\underset{\mathbf{x}_{1},\dots,\mathbf{x}_{N}}{\text{minimize}}$
$\displaystyle\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i})$ (8) subject to
$\displaystyle\mathbf{x}_{i}\in\mathcal{X}_{i},\quad i=1,\dots,N,$
$\displaystyle\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}=\mathbf{b},\quad(\bm{\lambda})$
$\displaystyle\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i})\leq 0,\quad
j=1,\dots,M,\quad(\mu_{j})$

the potential coupling caused by the quadratic term
$\lVert\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i})\rVert_{2}^{2}$ could be even
worse. Using the same technique of introducing the predictor variable, we
extend the $2$-block PCPM algorithm for solving (8).

First, we make a blanket assumption on problem (8) throughout this chapter
that the Slater’s constraint qualification (CQ) holds.

######  Assumption 2.1 (Slater’s CQ).

There exists a point $(\bar{\mathbf{x}}_{1},\dots,\bar{\mathbf{x}}_{N})$ such
that

$\Bigg{\\{}\bar{\mathbf{x}}_{i}\in relint(\mathcal{X}_{i}),\quad
i=1,\dots,N\Bigg{|}\begin{array}[]{ll}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}=\mathbf{b}\\\
\sum_{i=1}^{N}g_{ji}(\bar{\mathbf{x}}_{i})<0,\quad
j=1,\dots,M\end{array}\Bigg{\\}},$

where $relint(\mathcal{X}_{i})$ denotes the relative interior of the convex
set $\mathcal{X}_{i}$ for all $i=1,\dots,N$.

To apply the PCPM algorithm to (8), at each iteration $k$, with a given primal
dual pair,
$\big{(}\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\mu}^{k}\coloneqq(\mu_{1}^{k},\dots,\mu_{M}^{k})^{T}\big{)}$,
we start with a predictor update:

$\displaystyle\textbf{(predictor update)}:$ (9)
$\displaystyle\bm{\gamma}^{k+1}=\bm{\lambda}^{k}+\rho\Big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k}-\mathbf{b}\Big{)},$
$\displaystyle\nu_{j}^{k+1}=\Pi_{\mathbb{R}_{+}}\Big{[}\mu_{j}^{k}+\rho\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i}^{k})\Big{]},\quad
j=1,\dots,M,$

where $\Pi_{\mathbb{Z}}(\mathbf{z})$ denotes the projection of a vector
$\mathbf{z}\in\mathbb{R}^{n}$ onto a set $\mathbb{Z}\subset\mathbb{R}^{n}$,
and $\mathbb{R}_{+}$ refers to the set of all non-negative real numbers.

After the predictor update, we update the primal variables
$(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1})$ by minimizing the
Lagrangian function
$\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})$
evaluated at the predictor variable
$\big{(}\bm{\gamma}^{k+1},\bm{\nu}^{k+1}\coloneqq(\nu_{1}^{k+1},\dots,\nu_{M}^{k+1})^{T}\big{)}$,
plus the proximal terms. The primal minimization step can be decomposed as

$\displaystyle\textbf{(primal minimization)}:$ (10)
$\displaystyle\mathbf{x}_{i}^{k+1}=\underset{\mathbf{x}_{i}\in\mathcal{X}_{i}}{\operatorname*{\arg\\!\min}}\enspace
f_{i}(\mathbf{x}_{i})+(\bm{\gamma}^{k+1})^{T}A_{i}\mathbf{x}_{i}+\sum_{j=1}^{M}\nu_{j}^{k+1}g_{ji}(\mathbf{x}_{i})+\frac{1}{2\rho}\lVert\mathbf{x}_{i}-\mathbf{x}_{i}^{k}\rVert_{2}^{2},$
$\displaystyle i=1,\dots,N.$

A corrector update is then performed for each Lagrangian multiplier
$(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$:

$\displaystyle\textbf{(dual corrector)}:$ (11)
$\displaystyle\bm{\lambda}^{k+1}=\bm{\lambda}^{k}+\rho\Big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\mathbf{b}\Big{)},$
$\displaystyle\mu_{j}^{k+1}=\Pi_{\mathbb{R}_{+}}\Big{[}\mu_{j}^{k}+\rho\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i}^{k+1})\Big{]},\quad
j=1,\dots,M.$

The overall structure of $N$-block PCPM algorithm is presented in Algorithm 1
below.

Algorithm 1 $N$-PCPM

1:Initialization choose an arbitrary starting point
$(\mathbf{x}_{1}^{0},\dots,\mathbf{x}_{N}^{0},\bm{\lambda}^{0},\bm{\nu}^{0})$.

2:$k\leftarrow 0$.

3:while termination conditions are not met do

4: (Predictor update) update $(\bm{\gamma}^{k+1},\bm{\nu}^{k+1})$ according to
(9);

5: (Primal minimization) update
$(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1})$ according to (10);

6: (Corrector update) update $(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$ according
to (11);

7: $k\leftarrow k+1$

8:return
$(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\nu}^{k})$.

###  2.3 Convergence Analysis

We make the following additional assumptions on the optimization problem (8).

######  Assumption 2.2 (Lipschitz Continuity).

For all $j=1\dots M$ and $i=1\dots N$, each single-valued function
$g_{ij}:\mathcal{X}_{i}\to\mathbb{R}$ is Lipschitz continuous with modulus of
$L_{ji}$, i.e., $\lVert
g_{ji}(\mathbf{x}_{1})-g_{ji}(\mathbf{x}_{2})\rVert_{2}\leq
L_{ji}\lVert\mathbf{x}_{1}-\mathbf{x}_{2}\rVert_{2}$ for any
$\mathbf{x}_{1},\mathbf{x}_{2}\in\mathcal{X}_{i}$.

######  Assumption 2.3 (Existence of a Saddle Point).

For the Lagrangian function of (8):

$\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda},\bm{\mu})\coloneqq\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i})+\bm{\lambda}^{T}\Big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}-\mathbf{b}\Big{)}+\sum_{j=1}^{M}\mu_{j}\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i}),$
(12)

we assume that a saddle point
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$
exists; that is, for any $\mathbf{x}_{i}\in\mathcal{X}_{i}$, $i=1,\dots,N$,
$\bm{\lambda}\in\mathbb{R}^{m}$ and $\bm{\mu}\in\mathbb{R}_{+}^{M}$,

$\mathcal{L}(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda},\bm{\mu})\leq\mathcal{L}(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})\leq\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda}^{*},\bm{\mu}^{*}).$
(13)

Note that coupled with the blanket Assumption 2.1 that Slater’s CQ holds for
the optimization problem (8), the above assumption is equivalent to say that
an optimal solution of (8) is assumed to exist (see Corollary 28.3.1 in [10]).

Next, we derive some essential lemmas for constructing the main convergence
proof. The following lemma is due to Proposition $6$ in [9], and for
completeness, we provide the detailed statements below.

######  Lemma 2.1 (Inequality of Proximal Minimization Point).

Given a closed, convex set $\mathbb{Z}\subset\mathbb{R}^{n}$, and a
continuous, convex function $F:\mathbb{Z}\to\mathbb{R}$. With a given point
$\bar{\mathbf{z}}\in\mathbb{Z}$ and a positive number $\rho>0$, if
$\widehat{\mathbf{z}}$ is a proximal minimization point; i.e.
$\widehat{\mathbf{z}}\coloneqq\arg\underset{\mathbf{z}\in\mathbb{Z}}{\min}\
F(\mathbf{z})+\frac{1}{2\rho}\lVert\mathbf{z}-\bar{\mathbf{z}}\rVert_{2}^{2}$,
then we have that

$2\rho[F(\widehat{\mathbf{z}})-F(\mathbf{z})]\leq\lVert\bar{\mathbf{z}}-\mathbf{z}\rVert_{2}^{2}-\lVert\widehat{\mathbf{z}}-\mathbf{z}\rVert_{2}^{2}-\lVert\widehat{\mathbf{z}}-\bar{\mathbf{z}}\rVert_{2}^{2},\quad\forall\mathbf{z}\in\mathbb{Z}.$
(14)

###### Proof.

Denote
$\Phi(\mathbf{z})=F(\mathbf{z})+\frac{1}{2\rho}\lVert\mathbf{z}-\bar{\mathbf{z}}\rVert_{2}^{2}$.
By the definition of $\widehat{\mathbf{z}}$, we have
$\mathbf{0}\in\partial_{\mathbf{z}}\Phi(\widehat{\mathbf{z}})$. Since
$\Phi(\mathbf{z})$ is strongly convex with modulus $\frac{1}{\rho}$, it
follows that
$2\rho\big{[}\Phi(\mathbf{z})-\Phi(\widehat{\mathbf{z}})\big{]}\geq\lVert\widehat{\mathbf{z}}-\mathbf{z}\rVert_{2}^{2}$
for any $\mathbf{z}\in\mathbb{Z}$. ∎

######  Lemma 2.2.

The update steps (9) and (11) are equivalent to obtaining proximal
minimization points as follows:

$\displaystyle(\bm{\gamma}^{k+1},\bm{\nu}^{k+1})=\underset{\bm{\lambda}\in\mathbb{R}^{m},\bm{\mu}\in\mathbb{R}_{+}^{M}}{\operatorname*{\arg\\!\min}}\enspace-$
$\displaystyle\mathcal{L}(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda},\bm{\mu})$
(15) $\displaystyle+$
$\displaystyle\frac{1}{2\rho}\lVert\bm{\lambda}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{1}{2\rho}\lVert\bm{\mu}-\bm{\mu}^{k}\rVert_{2}^{2},$
$\displaystyle(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})=\underset{\bm{\lambda}\in\mathbb{R}^{m},\bm{\mu}\in\mathbb{R}_{+}^{M}}{\operatorname*{\arg\\!\min}}\enspace-$
$\displaystyle\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda},\bm{\mu})$
$\displaystyle+$
$\displaystyle\frac{1}{2\rho}\lVert\bm{\lambda}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{1}{2\rho}\lVert\bm{\mu}-\bm{\mu}^{k}\rVert_{2}^{2}.$

Similar to the convergence analysis of the PCPM algorithm in [5], we now
establish some fundamental estimates of the distance at each iteration $k$
between the solution point
$(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$
and the saddle point
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$.

######  Proposition 2.3.

Let
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$
be a saddle point of the optimization problem (8). For all $k\geq 0$, we have
that

$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}-\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}$
(16) $\displaystyle+$ $\displaystyle
2\rho\Big{[}(\bm{\lambda}^{*}-\bm{\gamma}^{k+1})^{T}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}+\sum_{j=1}^{M}(\mu_{j}^{*}-\nu_{j}^{k+1})\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i}^{k+1})\Big{]}$

and

$\displaystyle\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}\leq\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}$
(17) $\displaystyle-$
$\displaystyle\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}-\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}-\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}-\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}$
$\displaystyle+$ $\displaystyle
2\rho\Big{[}(\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1})^{T}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k}+\sum_{j=1}^{M}(\nu_{j}^{k+1}-\mu_{j}^{k+1})\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i}^{k})$
$\displaystyle\hskip
12.0pt+(\bm{\lambda}^{k+1}-\bm{\lambda}^{*})^{T}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}+\sum_{j=1}^{M}(\mu_{j}^{k+1}-\mu_{j}^{*})\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i}^{k+1})\Big{]}$

###### Proof.

The details of the proof are provided in Section A.1. ∎

######  Theorem 2.4 (Global Convergence).

Assume that Assumption 2.1 to Assumption 2.3 hold. Given a scalar
$0<\epsilon<1$, choose a step size $\rho$ satisfying

$0<\rho\leq\min\Bigg{\\{}\frac{1-\epsilon}{A_{max}+ML_{max}},\frac{1-\epsilon}{NA_{max}},\frac{1-\epsilon}{NL_{max}}\Bigg{\\}},$
(18)

where $A_{max}\coloneqq\max_{i=1}^{N}\\{\lVert A_{i}\rVert_{2}\\}$, and
$L_{max}\coloneqq\max_{j=1}^{M}\big{\\{}\max_{i=1}^{N}\\{L_{ji}\\}\big{\\}}$.
Let
$\\{\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\mu}^{k}\\}$
be the sequence generated by Algorithm 1, with an arbitrary point
$(\mathbf{x}_{1}^{0},\dots,\mathbf{x}_{N}^{0},\bm{\lambda}^{0},\bm{\mu}^{0})$;
then the sequence converges globally to a saddle point
$(\mathbf{x}_{1}^{*}\dots\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$ of
the optimization problem (8).

###### Proof.

Please see Section A.2 for details. ∎

To establish convergence rate, we need to make an additional assumption on
Problem (8), as follows.

######  Assumption 2.4 (Lipschitz Inverse Mapping).

Assume that there exists a unique saddle point
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$
such that, given an inverse mapping
$\mathcal{S}^{-1}:\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}^{M}\to\mathbb{R}$:

$\displaystyle\mathcal{S}^{-1}(\mathbf{u}_{1},\dots,\mathbf{u}_{N},\mathbf{v})$
(19) $\displaystyle=$
$\displaystyle\arg\underset{(\mathbf{x}_{1},\dots,\mathbf{x}_{N})\in\prod_{i=1}^{N}\mathcal{X}_{i}}{\min}\quad\underset{\bm{\lambda}\in\mathbb{R}^{m},\bm{\mu}\in\mathbb{R}_{+}^{M}}{\max}\Bigg{\\{}\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda},\bm{\mu})-\sum_{i=1}^{N}\mathbf{x}_{i}^{T}\mathbf{u}_{i}+\bm{\lambda}^{T}\mathbf{v}+\bm{\mu}^{T}\mathbf{w}\Bigg{\\}},$

and a fixed positive real number $\tau>0$, we have

$\sum_{i=1}^{N}\lVert\mathbf{x}_{i}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}-\bm{\mu}^{*}\rVert_{2}^{2}\leq
a^{2}\Big{(}\sum_{i=1}^{N}\lVert\mathbf{u}_{i}\rVert_{2}^{2}+\lVert\mathbf{v}\rVert_{2}^{2}+\lVert\mathbf{w}\rVert_{2}^{2}\Big{)}$

for some $a\geq 0$, whenever the point
$(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda},\bm{\mu})\in\mathcal{S}^{-1}(\mathbf{u}_{1},\dots,\mathbf{u}_{N},\mathbf{v},\mathbf{w})$
and

$\sum_{i=1}^{N}\lVert\mathbf{u}_{i}\rVert_{2}^{2}+\lVert\mathbf{v}\rVert_{2}^{2}+\lVert\mathbf{w}\rVert_{2}^{2}\leq\tau^{2}.$

The above assumption states that the inverse mapping $\mathcal{S}^{-1}$ is
Lipschitz continuous at the origin with modulus $a$. By Proposition 2 in [8],
to obtain a plausible condition for the Lipschitz continuity of
$\mathcal{S}^{-1}$ at the origin, we appeal to the strong second-order
conditions for optimality which are comprised of the following properties:

  1. (i)

There is a saddle point
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$
of the optimization problem (8) such that $\mathbf{x}_{i}^{*}\in
int(\mathcal{X}_{i})$ for all $i=1\dots N$, where $int(\mathcal{X}_{i})$
denotes the interior of the convex set $\mathcal{X}_{i}$. Moreover, for all
$i=1\dots N$ and $j=1,\dots,M$, function $g_{ji}(\mathbf{x}_{i})$ is twice
continuously differentiable on a neighborhood of $\mathbf{x}_{i}^{*}$.

  2. (ii)

Let $\mathcal{J}$ denote the set of active constraint indices at the point of
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*})$:
$\mathcal{J}=\Big{\\{}j=1,\dots,M\Big{|}\sum_{i=1}^{N}g_{ji}(\mathbf{x}_{i}^{*})=0\Big{\\}}$.
Then $\mu_{j}^{*}>0$ for all $j\in\mathcal{J}$, and
$\Big{\\{}\sum_{i=1}^{N}\nabla_{\mathbf{x}_{i}}g_{ji}(\mathbf{x}_{i}^{*})\Big{\\}}_{j\in\mathcal{J}}\cup\Big{\\{}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{*}\Big{\\}}$
forms a linearly independent set.

  3. (iii)

The Hessian matrix
$H\coloneqq\nabla_{(\mathbf{x}_{1},\dots,\mathbf{x}_{N})}^{2}\mathcal{L}(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$
satisfies $\mathbf{y}^{T}H\mathbf{y}>0$ for any

$\mathbf{y}\coloneqq\left(\begin{array}[]{c}\mathbf{y}_{1}\\\\[-6.0pt]
\vdots\\\\[-8.0pt]
\mathbf{y}_{N}\end{array}\right)\in\Bigg{\\{}\mathbf{y}\not=\mathbf{0}\Bigg{|}\begin{array}[]{l}\sum_{i=1}^{N}A_{i}\mathbf{y}_{i}=\mathbf{0}\\\
\sum_{i=1}^{N}\mathbf{y}_{i}^{T}\big{[}\nabla_{\mathbf{x}_{i}}g_{ji}(\mathbf{x}_{i}^{*})\big{]}=0,\quad\forall
j\in\mathcal{J}\end{array}\Bigg{\\}}.$

We now establish the linear convergence rate of Algorithm 1.

######  Theorem 2.5 (Linear Convergence Rate).

Assume that Assumption 2.1 to Assumption 2.4 hold. Let $\rho$ satisfy (18) and
let
$\\{\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\mu}^{k}\\}$
be a sequence generated by Algorithm 1, with an arbitrary starting point
$(\mathbf{x}_{1}^{0},\dots,\mathbf{x}_{N}^{0},\bm{\lambda}^{0},\bm{\mu}^{0})$;
then the sequence converges linearly to the unique saddle point
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$.
More specifically, there exists an integer $\bar{k}$ such that, for all
$k\geq\bar{k}$, we have:

$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}$
(20) $\displaystyle\leq$
$\displaystyle\theta^{2}\Big{(}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}\Big{)},$

where $0<\theta<1$.

###### Proof.

Please see Section A.3 for details. ∎

###  2.4 Numerical Experiments

Consider the following $20$-dimensioned, block-separable convex optimization
problem with $17$ nonlinear coupling constraints, modeling a decentralized
planning of an economic system and suggested by [1]:

$\displaystyle\underset{x_{1},\dots,x_{20}}{\text{minimize}}\quad$
$\displaystyle
x_{1}^{2}+x_{2}^{2}+x_{1}x_{2}-14x_{1}-16x_{2}+(x_{3}-10)^{2}+4(x_{4}-5)^{2}+(x_{5}-3)^{2}$
$\displaystyle+$ $\displaystyle
2(x_{6}-1)^{2}+5x_{7}^{2}+7(x_{8}-11)^{2}+2(x_{9}-10)^{2}+(x_{10}-7)^{2}+(x_{11}-9)^{2}$
$\displaystyle+$ $\displaystyle
10(x_{12}-1)^{2}+5(x_{13}-7)^{2}+4(x_{14}-14)^{2}+27(x_{15}-1)^{2}+x_{16}^{4}$
$\displaystyle+$
$\displaystyle(x_{17}-2)^{2}+13(x_{18}-2)^{2}+(x_{19}-3)^{2}+x_{20}^{2}+95$
subject to $\displaystyle
3(x_{1}-2)^{2}+4(x_{2}-3)^{2}+2x_{3}^{2}-7x_{4}-120\leq 0$ $\displaystyle
5x_{1}^{2}+8x_{2}+(x_{3}-6)^{2}-2x_{4}-40\leq 0$
$\displaystyle\frac{1}{2}(x_{1}-8)^{2}+2(x_{2}-4)^{2}+3x_{5}^{2}-x_{6}-30\leq
0$ $\displaystyle x_{1}^{2}+2(x_{2}-2)^{2}-2x_{1}x_{2}+14x_{5}-6x_{6}\leq 0$
$\displaystyle 4x_{1}+5x_{2}-3x_{7}+9x_{8}-105\leq 0$ $\displaystyle
10x_{1}-8x_{2}-17x_{7}+2x_{8}\leq 0$ $\displaystyle
3x_{1}+6x_{2}+12(x_{9}-8)^{2}-7x_{10}\leq 0$
$\displaystyle-8x_{1}+2x_{2}+5x_{9}-2x_{10}-12\leq 0$ $\displaystyle
x_{1}+x_{2}+4x_{11}-21x_{12}\leq 0$ $\displaystyle
x_{1}^{2}+15x_{11}-8x_{12}-28\leq 0$ $\displaystyle
4x_{1}+9x_{2}+5x_{13}^{2}-9x_{14}-87\leq 0$ $\displaystyle
3x_{1}+4x_{2}+3(x_{13}-6)^{2}-14x_{14}-10\leq 0$ $\displaystyle
14x_{1}^{2}+35x_{15}-79x_{16}-92\leq 0$ $\displaystyle
15x_{2}^{2}+11x_{15}-61x_{16}-54\leq 0$ $\displaystyle
5x_{1}^{2}+2x_{2}+9x_{17}^{4}-x_{18}-68\leq 0$ $\displaystyle
x_{1}^{2}-x_{2}+19x_{19}-20x_{20}+19\leq 0$ $\displaystyle
7x_{1}^{2}+5x_{2}^{2}+x_{19}^{2}-30x_{20}\leq 0$ (21)

A minimum function value of $133.723$ can be obtained at the point of ($2.18$,
$2.35$, $8.77$, $5.07$, $0.99$, $1.43$, $1.33$, $9.84$, $8.29$, $8.37$,
$2.28$, $1.36$, $6.08$, $14.17$, $1.00$, $0.66$, $1.47$, $2.00$, $1.05$,
$2.06$).111The solution is obtained using the nonlinear constrained
optimization solver filter of Neos Solver at https://neos-
server.org/neos/solvers/. Applying Algorithm 1 and decomposing the original
problem into $19$ small sub-problems, we achieve the following convergence
results, presented in Figure 1.

Figure 1: Convergence Results of Applying Algorithm 1 to Problem (21) with
$\rho=0.009$.

Next, by replacing the term of $x_{16}^{4}$ in the objective function of (21)
with $x_{16}^{2}$ and the term of $x_{17}^{4}$ in the $15$-th constraint with
$x_{17}^{2}$, we make the modified problem satisfy Assumption 2.4. A minimum
function value of $133.687$ can be obtained at the point of ($2.18$, $2.34$,
$8.76$, $5.07$, $0.99$, $1.43$, $1.34$, $9.84$, $8.30$, $8.36$, $2.27$,
$1.36$, $6.08$, $14.17$, $1.00$, $0.64$, $2.00$, $2.00$, $1.04$, $2.06$). An
additional linear convergence rate of applying Algorithm 1 is observed in the
following convergence results, presented in Figure 2.

Figure 2: Convergence Results of Applying Algorithm 1 to the Modified Problem
(21) with $\rho=0.009$.

##  3 Extending the N-block PCPM Algorithm to an Asynchronous Scheme

As a starting point, we first consider the following N-block convex
optimization problem with only linear coupling constraints:

$\displaystyle\underset{\mathbf{x}_{1},\dots,\mathbf{x}_{N}}{\text{minimize}}$
$\displaystyle\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i})$ (22) subject to
$\displaystyle\mathbf{x}_{i}\in\mathcal{X}_{i},\quad i=1\dots N,$
$\displaystyle\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}=\mathbf{b}.$

The decision variables, the objective function and the constraints are the
same as in the optimization problem (1). When applying Algorithm 1 to solving
the above problem, each iteration can be interpreted as main-worker paradigm
[11], shown in Figure 3.

Figure 3: Main-Worker Paradigm for Algorithm 1.

At each iteration $k$, a predictor update of $\bm{\gamma}^{k+1}$ is first
performed on a main processor and is broadcast to each worker processor, which
is called a pre-processing task. Upon receiving the updated predictor variable
from the main processor, each worker processor solves the decomposed sub-
problem in parallel and send its updated primal decision variable
$\mathbf{x}_{i}^{k+1}$ back to the main processor, which is called a worker
task. After gathering all updated decision variables, a corrector update is
then performed on the main processor, which is called a post-processing task.

The speed of the algorithm is significantly limited by the slowest worker
processor, since the post-processing task can not start until all worker tasks
are finished and the results are sent back to the main processor. For large-
scale problems, with the number of worker processors increasing, the issue of
node synchronization can be a major concern for the performance of synchronous
distributed algorithms. While in an asynchronous scheme, the main processor
can proceed with only part of worker tasks finished. Figure 4

Figure 4: Illustration of how asynchronous scheme iterates faster than
synchronous scheme.

shows an example of $1$ main processor and $4$ worker processors with
different lengths of computation and communication delays. In the asynchronous
scheme, the main processor starts a new iteration whenever receives the
results from at least $2$ worker processors, which leads to much faster
iterations than the synchronous scheme.

In this section, we extend the $N$-block PCPM algorithm to an asynchronous
scheme to solve the linearly constrained $N$-block convex optimization problem
(22).

###  3.1 Asynchronous N-block PCPM Algorithm for Convex Optimization Problems
with Linear Coupling Constraints

To achieve the convergence of the asynchronous $N$-block PCPM algorithm,
similar to [3, 4], we require that the asynchronous delay of each parallel
worker processor is bounded. Let $k\geq 0$ denote the iteration index on the
main processor. At each iteration $k$, let
$\mathcal{A}_{k}\subseteq\\{1,\dots,N\\}$ denote the subset of worker
processors from whom the main processor receives the updated decision variable
$\widehat{\mathbf{x}}_{i}$, and let
$\mathcal{A}_{k}^{\complement}\subseteq\\{1,\dots,N\\}$ denote the rest of the
worker processors, whose information does not arrive.

######  Definition 3.1 (Bounded Delay).

Let an integer $\tau\geq 1$ denote the maximum tolerable delay. At any
iteration $k\geq 0$, with a bounded delay, it must holds that
$i\in\mathcal{A}_{k}\cup\mathcal{A}_{k-1}\cup\cdots\cup\mathcal{A}_{k-\tau+1}$
for all $i=1,\dots,N$. When $\tau=1$, it’s a synchronous scheme.

At each each iteration $k$ on the main processor, all worker processors are
divided into two sets $\mathcal{A}_{k}$ and $\mathcal{A}_{k}^{\complement}$,
distinguished by whether their information arrives or not at the current
moment. Let $d_{i}$ denote the number of iterations that each worker processor
$i$ is delayed. If $d_{i}<\tau-1$ for each worker processor
$i\in\mathcal{A}_{k}^{\complement}$, the main processor uses the partially
updated decision variables $(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1})$
to perform both corrector and predictor updates for the Lagrangian multiplier;
otherwise, the main processor must wait until the worker processors with
$d_{i}=\tau-1$ finish their tasks with information received by the master
processor. Consequently, new divide of worker processors into
$\mathcal{A}_{k}$ and $\mathcal{A}_{k}^{\complement}$ is generated, and the
bounded delay condition is then satisfied. The overall structure of the
Asynchronous $N$-Block PCPM algorithm for solving the linearly constrained
convex optimization problem (22) is presented in Algorithm 2 and Algorithm 3.

Algorithm 2 AN-PCPM (Main Processor)

1:Initialization choose an arbitrary starting point $\bm{\lambda}^{0}$.

2:$k\leftarrow 0$, $d_{1},d_{2},\dots,d_{N}\leftarrow 0$

3:wait until receiving $\\{\hat{\mathbf{x}}_{i}\\}_{i=1\dots N}$

4:update:  $\mathbf{x}_{i}^{0}=\hat{\mathbf{x}}_{i},\quad i=1\dots N$ (23)

5:broadcast
$\hat{\bm{\gamma}}=\bm{\lambda}^{0}+\rho(\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{0}-\mathbf{b})$
to all worker processors

6:while termination conditions are not met do

7: wait until receiving $\\{\hat{\mathbf{x}}_{i}\\}_{i\in\mathcal{A}_{k}}$
such that $d_{i}<\tau,\quad\forall i\in\mathcal{A}_{k}^{\complement}$

8: update:  $\displaystyle\mathbf{x}_{i}^{k+1}=\left\\{\begin{aligned}
&\hat{\mathbf{x}}_{i},&\forall i\in\mathcal{A}_{k}\\\
&\mathbf{x}_{i}^{k},&\forall
i\in\mathcal{A}_{k}^{\complement}\end{aligned}\right.$ (24) $\displaystyle
d_{i}=\left\\{\begin{aligned} &0,&\forall i\in\mathcal{A}_{k}\\\
&d_{i}+1,&\forall i\in\mathcal{A}_{k}^{\complement}\end{aligned}\right.$

9: update:
$\bm{\lambda}^{k+1}=\bm{\lambda}^{k}+\rho\big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\mathbf{b}\big{)}$
(25)

10: broadcast
$\hat{\bm{\gamma}}=\bm{\lambda}^{k+1}+\rho\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}$
to the worker processors in $\mathcal{A}_{k}$

11: $k++$

12:return $(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k})$

Algorithm 3 AN-PCPM (Woker Processor)

1:send $\hat{\mathbf{x}}_{i}=\mathbf{x}_{i}^{0}$ to the main processor

2:while not receiving termination signal do

3: wait until receiving $\hat{\bm{\gamma}}$

4: calculate:
$\mathbf{y}_{i}=\underset{\mathbf{x}_{i}\in\mathcal{X}_{i}}{\operatorname*{\arg\\!\min}}f_{i}(\mathbf{x}_{i})+\hat{\bm{\gamma}}^{T}A_{i}\mathbf{x}_{i}+\frac{1}{2\rho}\lVert\mathbf{x}_{i}-\hat{\mathbf{x}}_{i}\rVert^{2}$
(26)

5: update: $\hat{\mathbf{x}}_{i}=\mathbf{y}_{i}$

6: send $\hat{\mathbf{x}}_{i}$ to the main processor

###  3.2 Convergence Analysis

Different from the synchronous $N$-block PCPM algorithm, the convexity of
$f_{i}$ is not enough to achieve the global convergence due to the
asynchronous delay in the system. We make the following additional assumption
on problem (22).

######  Assumption 3.1 (Strong Convexity).

For all $i=1\dots N$, each $f_{i}:\mathcal{X}_{i}\to\mathbb{R}$ is a
continuous, strongly convex function with modulus $\sigma_{i}>0$.

Accordingly, we extend Lemma 2.1 to functions with strong convexity.

######  Lemma 3.1 (Inequality of Proximal Minimization Point with Strong
Convexity).

Given a closed, convex set $\mathbb{Z}\subset\mathbb{R}^{n}$, and a
continuous, strongly convex function $F:\mathbb{Z}\to\mathbb{R}$ with modulus
$\sigma$. With a given point $\bar{\mathbf{z}}\in\mathbb{Z}$ and a positive
number $\rho>0$, if $\widehat{\mathbf{z}}$ is a proximal minimization point;
i.e.
$\widehat{\mathbf{z}}\coloneqq\arg\underset{\mathbf{z}\in\mathbb{Z}}{\min}\
F(\mathbf{z})+\frac{1}{2\rho}\lVert\mathbf{z}-\bar{\mathbf{z}}\rVert_{2}^{2}$,
then we have that

$F(\widehat{\mathbf{z}})-F(\mathbf{z})\leq\frac{1}{2\rho}\lVert\bar{\mathbf{z}}-\mathbf{z}\rVert_{2}^{2}-(\frac{\sigma}{2}+\frac{1}{2\rho})\lVert\widehat{\mathbf{z}}-\mathbf{z}\rVert_{2}^{2}-\frac{1}{2\rho}\lVert\widehat{\mathbf{z}}-\bar{\mathbf{z}}\rVert_{2}^{2},\quad\forall\mathbf{z}\in\mathbb{Z}.$
(27)

###### Proof.

Denote
$\Phi(\mathbf{z})=F(\mathbf{z})+\frac{1}{2\rho}\lVert\mathbf{z}-\bar{\mathbf{z}}\rVert_{2}^{2}$.
By the definition of $\widehat{\mathbf{z}}$, we have
$\partial_{\mathbf{z}}\Phi(\widehat{\mathbf{z}})=\mathbf{0}$. Since
$\Phi(\mathbf{z})$ is strongly convex with modulus $\sigma+\frac{1}{\rho}$, it
follows that
$\Phi(\mathbf{z})-\Phi(\widehat{\mathbf{z}})\geq(\frac{\sigma}{2}+\frac{1}{2\rho})\lVert\widehat{\mathbf{z}}-\mathbf{z}\rVert_{2}^{2}$
for any $\mathbf{z}\in\mathbb{Z}$. ∎

Now, we present the main convergence result.

######  Theorem 3.2 (Sub-linear Convergence Rate).

Let Assumption 2.1, Assumption 2.3 and Assumption 3.1 hold. Choose a step size
$\rho$ satisfying:

$\rho\leq\frac{\sigma_{min}}{25N(\tau-1)^{2}A_{max}},$ (28)

where $\sigma_{min}\coloneqq\min_{i=1}^{N}\\{\sigma_{i}\\}$. Denote
$\bar{\mathbf{x}}_{i}^{k}=\frac{1}{k}\sum_{k^{\prime}=1}^{k}\mathbf{x}_{i}^{k^{\prime}}$
for all $i=1,\dots,N$, where
$\\{(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k})\\}$ is the sequence
generated by Algorithm 2 and Algorithm 3, then for all $k>0$, it holds that:

$\Big{\lvert}\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{k})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})\Big{\rvert}\leq\frac{\delta_{\bm{\lambda}}C_{1}+C_{2}}{k},\quad\Big{\lVert}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{k}-\mathbf{b}\Big{\rVert}_{2}\leq\frac{C_{1}}{k},$
(29)

where $\delta_{\bm{\lambda}}=\lVert\bm{\lambda}^{*}\rVert_{2}$ and $C_{1}$,
$C_{2}$ are some finite constants.

###### Proof.

Please see Section B.1 for details. ∎

##  4 Numerical Experiments

###  4.1 An Optimization Problem on a Graph

In this subsection, we consider an optimization problem on a graph, arising
from the training process of regressors with spatial clustering, proposed by
[7]. Traditional regressors obtains a parameter vector $\mathbf{x}$ via
solving the following optimization problem on a training data set:

$\underset{\mathbf{x}\in\mathcal{X}}{\text{minimize}}\quad\sum_{i=1}^{N}f_{i}(\mathbf{x})+r(\mathbf{x}),$
(30)

where $N$ is the number of data points, $\mathcal{X}\subset\mathbb{R}^{n}$
describes the constraints on the parameter vector, each function
$f_{i}:\mathbb{R}^{n}\to\mathbb{R}$ denotes the loss function on each training
data point for all $i=1,\dots,N$, and $r:\mathbb{R}^{n}\to\mathbb{R}$ denotes
some type of regularization function.

When the spatial information is accessible, such as the latitude and longitude
data, a map of data points then becomes available. Instead of using a global
regressor with a common parameter vector $\mathbf{x}$ for the whole data set,
a local regressor can be built at each data point $i=1,\dots,N$ with a local
parameter vector $\mathbf{x}_{i}\in\mathbb{R}^{n}$. Let $d_{ij}$ denote the
distance between the data point $i$ and $j$ ($i\not=j$). Different from
distributed learning, where a consensus constraint should be satisfied for all
local variables, we require that the difference between two local parameter
vectors $\lVert\mathbf{x}_{i}-\mathbf{x}_{j}\rVert_{2}^{2}$ decreases as the
distance $d_{ij}$ decreases. Let $\mathcal{N}_{\epsilon}(i)$ denote a set of
data points within a neighborhood of point $i$, i.e.,
$\mathcal{N}_{\epsilon}(i)\coloneqq\\{j=1,\dots,N|j\not=i,d_{ij}\leq\epsilon\\}$.
If any data point is regarded as a vertex and any two data points within a
neighborhood are connected through an edge, a graph is then constructed as
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ denotes the set
of vertices with $N=\lvert\mathcal{V}\rvert$ and $\mathcal{E}$ denotes the set
of edges with $p=\lvert\mathcal{E}\rvert$. Consider the following optimization
problem on the graph:

$\displaystyle\underset{\mathbf{x}_{1},\dots,\mathbf{x}_{N}}{\text{minimize}}$
$\displaystyle\sum_{i\in\mathcal{V}}\big{[}f_{i}(\mathbf{x}_{i})+r(\mathbf{x}_{i})\big{]}+\omega\sum_{(j,k)\in\mathcal{E}}w_{jk}\lVert\mathbf{x}_{j}-\mathbf{x}_{k}\rVert_{2}^{2}$
(31) subject to $\displaystyle\mathbf{x}_{i}\in\mathcal{X}_{i},\quad
i=1,\dots,N.$

Different from [7], we use $\lVert\cdot\rVert_{2}^{2}$ instead of
$\lVert\cdot\rVert_{2}$. The parameter $w_{jk}$ along each edge
$(j,k)\in\mathcal{E}$, describing the weight of the penalty term of the
difference between the two connected vertices, increases as $d_{jk}$
decreases. The global parameter $\omega$ describes the trade-off between
minimizing the individual loss function on each data point and agreeing with
neighbors. When $\omega=0$, $\mathbf{x}_{i}^{*}$ is simply the solution to the
optimization problem:
$\underset{\mathbf{x}_{i}\in\mathbb{X}_{i}}{\text{minimize}}\quad
f_{i}(\mathbf{x}_{i})+r(\mathbf{x}_{i})$, obtained locally at each vertex $i$.
When $\omega\to+\infty$, the model reduces to a traditional regressor without
spatial clustering.

Once the optimal solution $(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*})$ is
obtained, for any new node $i^{\prime}$, the local regressor can be evaluated
with the local parameter vector $\mathbf{x}_{i^{\prime}}$, estimated through
the interpolation of the solution:

$\underset{\mathbf{x_{i^{\prime}}}\in\mathcal{X}_{i^{\prime}}}{\text{minimize}}\quad\sum_{j\in\mathcal{N}_{\epsilon}(i^{\prime})}w_{i^{\prime}j}\lVert\mathbf{x}_{i^{\prime}}-\mathbf{x}_{j}^{*}\rVert_{2}^{2}.$
(32)

###  4.2 Two Problem Reformulations

To apply $N$-block PCPM algorithm to solve the graph optimization problem
(31), we first need to reformulate it into the block-separable form as in
(22).

Similar to [7], for each pair of connected vertices
$(\mathbf{x}_{j},\mathbf{x}_{k})$ along the edge $(j,k)\in\mathcal{E}$,
introducing a copy $(\mathbf{z}_{jk},\mathbf{z}_{kj})$, we can rewrite the
graph optimization problem (31) as

  * •

Problem Reformulation 1

$\displaystyle\underset{\mathbf{x}_{1},\dots,\mathbf{x}_{N}}{\text{minimize}}$
$\displaystyle\sum_{i\in\mathcal{V}}\big{[}f_{i}(\mathbf{x}_{i})+r(\mathbf{x}_{i})\big{]}+\omega\sum_{(j,k)\in\mathcal{E}}w_{jk}\lVert\mathbf{z}_{jk}-\mathbf{z}_{kj}\rVert_{2}^{2}$
(33) subject to $\displaystyle\mathbf{x}_{i}\in\mathcal{X}_{i},\quad\forall
i\in\mathcal{V},$
$\displaystyle\mathbf{x}_{i}-\mathbf{z}_{ij}=\mathbf{0},\quad\forall
j\in\mathcal{N}_{\epsilon}(i),\quad\forall i\in\mathcal{V}.$

The reformulated problem can be decomposed into $N$ sub-problems on vertices
and $p$ sub-problems along edges, using $N$-block PCPM algorithm. One small
issue is that the objective function of the edge sub-problem,
$\lVert\mathbf{z}_{jk}-\mathbf{z}_{kj}\rVert_{2}^{2}$, is not strongly convex.

To overcome this limitation, we propose an alternative way of rewriting (31).
For each edge $(j,k)\in\mathcal{E}$, introducing a slack variable
$\mathbf{z}_{jk}=\mathbf{x}_{j}-\mathbf{x}_{k}$, we can rewrite the graph
optimization problem (31) as

  * •

Problem Reformulation 2

$\displaystyle\underset{\mathbf{x}_{1},\dots,\mathbf{x}_{N}}{\text{minimize}}$
$\displaystyle\sum_{i\in\mathcal{V}}\big{[}f_{i}(\mathbf{x}_{i})+r(\mathbf{x}_{i})\big{]}+\omega\sum_{(j,k)\in\mathcal{E}}w_{jk}\lVert\mathbf{z}_{jk}\rVert_{2}^{2}$
(34) subject to $\displaystyle\mathbf{x}_{i}\in\mathcal{X}_{i},\quad\forall
i\in\mathcal{V},$
$\displaystyle\mathbf{x}_{j}-\mathbf{x}_{k}-\mathbf{z}_{jk}=\mathbf{0},\quad\forall(j,k)\in\mathcal{E}.$

The reformulated problem can also be decomposed into $N$ sub-problems on
vertices and $p$ sub-problems along edges. However, in this way of rewriting
(31), the objective function of each decomposed sub-problem enjoys the nice
property of strong convexity. When applying $N$-block PCPM algorithm, a linear
convergence rate is expected for synchronous iteration scheme, and a sub-
linear convergence rate is expected for an asynchronous scheme.

###  4.3 Housing Price Prediction

In this subsection, we present an application example of the graph
optimization problem, where the housing price is predicted based on a set of
features, including the number of bedrooms, the number of bathrooms, the
number of square feet, and the latitude and longitude of each house. We use
the same data set as [7], a list of 985 real estate transactions over a period
of one week during May of 2008 in the Greater Sacramento area. All data is
standardized with zero mean and unit variance, and all missing data is then
set to zero. We randomly select a subset of 193 transactions as our test data
set, and use the rest as our training data set.

The graph is constructed based on the latitude and longitude of each house.
The rule of selecting neighbors is slightly different from [7]. For each
house, we connect it with all the other houses within a distance of $1.0$
mile. If the number of connected houses is less then $5$, we connect more
nearest houses until the number of neighbors reaches $5$. The resulting graph
has $792$ vertices and $4303$ edges. Thus, the graph optimization problem can
be decomposed into $792+4303=5095$ sub-problems, using $N$-block PCPM
algorithm.

At each data point $i=1\dots 792$, the decision variable is
$\mathbf{x}_{i}=(x_{i0},x_{i1},x_{i2},x_{i3})$. The predicted price for each
house is:

$x_{i0}+x_{i1}\times\text{(num\\_bed)}_{i}+x_{i2}\times\text{(num\\_bath)}_{i}+x_{i3}\times\text{(num\\_sq\\_ft)}_{i},$

where $\text{(num\\_bed)}_{i}$, $\text{(num\\_bath)}_{i}$ and
$\text{(num\\_sq\\_ft)}_{i}$ are the number of bedrooms, the number of
bathrooms and the number of square feets for each house respectively. At each
vertex $i$, the objective function

$f_{i}(\mathbf{x}_{i})=\lVert
x_{i0}+x_{i1}\times\text{(num\\_bed)}_{i}+x_{i2}\times\text{(num\\_bath)}_{i}+x_{i3}\times\text{(num\\_sq\\_ft)}_{i}-\text{(price)}_{i}\rVert_{2}^{2}$

is strongly convex, as well as the regularization function

$r(\mathbf{x}_{i})=\mu\big{(}\lVert x_{i1}\rVert_{2}^{2}+\lVert
x_{i2}\rVert_{2}^{2}+\lVert x_{i3}\rVert_{2}^{2}\big{)},$

where $\text{(price)}_{i}$ is the actual sales price for each house, and $\mu$
is a constant regularization parameter, fixed as $\mu=0.1$.

###  4.4 Numerical Results of Synchronous N-block PCPM Algorithm

We first apply Algorithm 1 to solve the two reformulated problem (33) and
(34), and compare the performance. The convergence results are shown in Figure
5.

Figure 5: Convergence Results of Applying Algorithm 1 to solve Reformulated
Problems (33) and (34) with $\omega=1.0$ and $\rho=0.06$.

Due to the strong convexity of the reformulated problem (34), the algorithm
converges much faster than solving the reformulated problem (33).

We also plot the mean square error (MSE) on the testing data set using various
values of $\omega$, shown in Figure 6.

Figure 6: MSE for Testing Data Set with $\omega$ Varying from $10^{-2}$ to
$10^{3}$ and $\mu=0.1$.

When $\omega=1.0$, a minimum MSE of $0.27$ can be obtained on the testing data
set. We fixed $\omega=1.0$ for all the numerical experiments.

###  4.5 Numerical Results of Asynchronous N-block PCPM Algorithm

We apply Algorithm 2 and Algorithm 3 to solve the reformulated problem (34)
with a maximum delay $\tau=4$. The convergence results of are shown in Figure
7.

Figure 7: Convergence Results of Applying Algorithm 2 and Algorithm 3 to Solve
the Reformulated Problem (34) with $\tau=4$ and $\rho=0.0005$.

A sub-linear convergence rate is observed.

While implementing the algorithm as a sequential code, we simulate the elapsed
wall-clock time on the main processor. As illustrated in Figure 4, the
computation delay of the main processor is set as $1.0$ second, the
computation delay of each worker processor for solving vertex sub-problem is
set as $1.2$ second, the computation delay of each worker processor for
solving edge sub-problem is set as $0.6$ second, and the communication delay
of each worker processor is uniformly drawn from a range of $0.0$ to $1.0$
second. Under these settings, we simulate the elapsed wall-clock time on the
main processor for the different values of maximum delay $\tau=1,2,4,7$, shown
in Figure 8.

Figure 8: Simulated Elapsed Wall-clock Time on the Main Processor with Various
Maximum Delay $\tau$ and a Same $\rho=0.0005$.

We observe that, with a larger number of maximum delay, the number of
iterations, used for the asynchronous algorithm to converge, increases but the
simulated elapsed wall-clock time decreases, which implies a faster
convergence with more short-time iterations.

##  5 Conclusion and Future Works

In this paper, we first proposed an $N$-block PCPM algorithm to solve
$N$-block convex optimization problems with both linear and nonlinear
constraints, with global convergence established. A linear convergence rate
under the strong second-order conditions for optimality is observed in the
numerical experiments. Next, for a starting point, we proposed an asynchronous
$N$-block PCPM algorithm to solve linearly constrained $N$-block convex
optimization problems. The numerical results demonstrate the sub-linear
convergence rate under the bounded delay assumption, as well as the faster
convergence with more short-time iterations than a synchronous iterative
scheme.

However, the performance of real asynchronous implementation of $N$-block PCPM
algorithm is unknown, and thus in the future, more experiments (probably with
much larger problem sizes) will be conducted on a multi-node computer cluster
using MPI functions without blocking communication, such as MPI_Isend and
MPI_Irecv. Also, the extension of the asynchronous $N$-block PCPM algorithm to
solve $N$-block convex optimization problems with both linear and nonlinear
constraints is worth to be explored.

## References

  * [1] J. Asaadi.  A computational comparison of some non-linear programs.  Mathematical Programming, 4(1):144–154, 1973.
  * [2] Stephen Boyd, Neal Parikh, and Eric Chu.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Foundations and Trends® in Machine learning, 3(1):1–122, 2011.
  * [3] Tsung-Hui Chang, Mingyi Hong, Wei-Cheng Liao, and Xiangfeng Wang.  Asynchronous distributed ADMM for large-scale optimization—part i: Algorithm and convergence analysis.  IEEE Transactions on Signal Processing, 64(12):3118–3130, 2016\.
  * [4] Tsung-Hui Chang, Wei-Cheng Liao, Mingyi Hong, and Xiangfeng Wang.  Asynchronous distributed admm for large-scale optimization—part ii: Linear convergence analysis and numerical performance.  IEEE Transactions on Signal Processing, 64(12):3131–3144, 2016\.
  * [5] Gong Chen and Marc Teboulle.  A proximal-based decomposition method for convex minimization problems.  Mathematical Programming, 64(1-3):81–101, 1994.
  * [6] Wei Deng, Ming-Jun Lai, Zhimin Peng, and Wotao Yin.  Parallel multi-block ADMM with o (1/k) convergence.  Journal of Scientific Computing, 71(2):712–736, 2017.
  * [7] David Hallac, Jure Leskovec, and Stephen Boyd.  Network lasso: clustering and optimization in large graphs.  In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 387–396. ACM, 2015.
  * [8] R Tyrrell Rockafellar.  Augmented Lagrangians and applications of the proximal point algorithm in convex programming.  Mathematics of Operations Research, 1(2):97–116, 1976.
  * [9] R Tyrrell Rockafellar.  Monotone operators and the proximal point algorithm.  SIAM Journal on Control and Optimization, 14(5):877–898, 1976.
  * [10] R. Tyrrell Rockafellar.  Convex Analysis.  Princeton University Press, 2015.
  * [11] Sartaj Sahni and George Vairaktarakis.  The master-slave paradigm in parallel computer and industrial settings.  Journal of Global Optimization, 9(3-4):357–377, 1996.
  * [12] Huahua Wang, Arindam Banerjee, and Zhi-Quan Luo.  Parallel direction method of multipliers.  In Advances in Neural Information Processing Systems, pages 181–189, 2014.
  * [13] Xiangfeng Wang, Mingyi Hong, Shiqian Ma, and Zhi-Quan Luo.  Solving multiple-block separable convex minimization problems using two-block alternating direction method of multipliers.  arXiv preprint arXiv:1308.5294, 2013.
  * [14] Hao Yu and Michael J Neely.  A simple parallel algorithm with an o(1/t) convergence rate for general convex programs.  SIAM Journal on Optimization, 27(2):759–783, 2017.

##  Appendix A Proofs in Section 2.3

###  A.1 Proof of Proposition 2.3

We first prove the inequality (16). From the primal minimization step (10), we
know that $(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1})$ is the unique
proximal minimization point of the Lagrangian function evaluated at the
predictor variable:
$\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})$.
Applying Lemma 2.1 with
$\widehat{\mathbf{z}}=(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1})$,
$\bar{\mathbf{z}}=(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k})$ and
$\mathbf{z}=(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*})$, we have:

$\displaystyle
2\rho\Big{[}\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})-\mathcal{L}(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})\Big{]}$
(35) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}-\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}-\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}.$

Since
$(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*},\bm{\mu}^{*})$
is a saddle point of the Lagrangian function
$\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda},\bm{\mu})$,
i.e.,
$\mathcal{L}(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\mathbf{p}^{k+1})\leq\mathcal{L}(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\lambda}^{*})\leq\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{*})$,
we have:

$2\rho\Big{[}\mathcal{L}(\mathbf{x}_{1}^{*},\dots,\mathbf{x}_{N}^{*},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})-\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{*},\bm{\mu}^{*})\Big{]}\leq
0.$ (36)

Adding the above two inequalities yields the inequality (16) in Proposition
2.3.

To prove the second inequality, (17), in Proposition 2.3, we use a similar
approach as above. By Lemma 2.2, we know that
$(\bm{\gamma}^{k+1},\bm{\nu}^{k+1})$ is the unique proximal minimization point
of the function
$-\mathcal{L}(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda},\bm{\mu})$.
Applying Lemma 2.1 with
$\widehat{\mathbf{z}}=(\bm{\gamma}^{k+1},\bm{\nu}^{k+1})$,
$\bar{\mathbf{z}}=(\bm{\lambda}^{k},\bm{\mu}^{k})$ and
$\mathbf{z}=(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$, we have:

$\displaystyle
2\rho\Bigg{\\{}\Big{[}-\mathcal{L}(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})\Big{]}-\Big{[}-\mathcal{L}(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})\Big{]}\Bigg{\\}}$
$\displaystyle\leq$
$\displaystyle\lVert\bm{\lambda}^{k}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{k+1}\rVert_{2}^{2}$
$\displaystyle-$
$\displaystyle\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}-\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}-\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}-\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}.$
(37)

By Lemma 2.2, we also know that $(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$ is the
unique proximal minimization point of the function
$-\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda},\bm{\mu})$.
Applying Lemma 2.1 with
$\widehat{\mathbf{z}}=(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$,
$\bar{\mathbf{z}}=(\bm{\lambda}^{k},\bm{\mu}^{k})$ and
$\mathbf{z}=(\bm{\lambda}^{*},\bm{\mu}^{*})$, we have:

$\displaystyle
2\rho\Bigg{\\{}\Big{[}-\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})\Big{]}-\Big{[}-\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{*},\bm{\mu}^{*})\Big{]}\Bigg{\\}}$
$\displaystyle\leq$
$\displaystyle\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle-$
$\displaystyle\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}-\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}-\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}-\lVert\bm{\mu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}.$
(38)

Adding the above two inequalities yields the inequality (17) in Proposition
2.3.

###  A.2 Proof of Theorem 2.4

By adding the two inequalities (16) and (17) in Proposition 2.3, we have:

$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle-$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}-\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}-\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}-\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}-\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{N}\underbrace{2\rho(\bm{\lambda}^{k+1}-\bm{\gamma}^{k+1})^{T}A_{i}(\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k})}_{(a)_{i}}+\sum_{j=1}^{M}\sum_{i=1}^{N}\underbrace{2\rho(\mu_{j}^{k+1}-\nu_{j}^{k+1})\Big{[}g_{ji}(\mathbf{x}_{i}^{k+1})-g_{ji}(\mathbf{x}_{i}^{k})\Big{]}}_{(b)_{ji}}.$
(39)

Before we continue with the proof, we first show an extension of the Young’s
inequality222Young’s inequality states that if $a$ and $b$ are two non-
negative real numbers, and $p$ and $q$ are real numbers greater than 1 such
that $\frac{1}{p}+\frac{1}{q}=1$, then $ab<\frac{a^{p}}{p}+\frac{b^{q}}{q}$.
on vector products that will play a key role in the following proof. Given any
two vectors $\mathbf{z}_{1},\mathbf{z}_{2}\in\mathbb{R}^{n}$, we have that

$\mathbf{z}_{1}^{T}\mathbf{z}_{2}=\sum_{j=1}^{n}z_{1j}z_{2j}=\sum_{j=1}^{n}\Big{(}\frac{1}{\delta}z_{1j}\Big{)}\Big{(}\delta
z_{2j}\Big{)}\leq\sum_{j=1}^{n}\Big{\lvert}\frac{1}{\delta}z_{1j}\Big{\rvert}\Big{\lvert}\delta
z_{2j}\Big{\rvert},$

where $\delta$ is a non-zero real number. Applying Young’s inequality on each
summation term with $p=q=2$, we obtain that

$\mathbf{z}_{1}^{T}\mathbf{z}_{2}\leq\sum_{j=1}^{n}\left[\frac{1}{2}\Big{(}\frac{1}{\delta}z_{1j}\Big{)}^{2}+\frac{1}{2}\Big{(}\delta
z_{2j}\Big{)}^{2}\right]=\frac{1}{2\delta^{2}}\lVert\mathbf{z}_{1}\rVert_{2}^{2}+\frac{\delta^{2}}{2}\lVert\mathbf{z}_{2}\rVert_{2}^{2}.$
(40)

Applying (40) on each term $(a)_{i}$ yields

$\displaystyle(a)_{i}\leq$ $\displaystyle
2\rho\Big{[}\frac{1}{2\delta^{2}}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\frac{\delta^{2}}{2}\lVert
A_{i}(\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k})\rVert_{2}^{2}\Big{]}$ (41)
$\displaystyle\leq$ $\displaystyle
2\rho\Big{[}\frac{1}{2\delta^{2}}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\frac{\delta^{2}}{2}\lVert
A_{i}\rVert_{2}^{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}\Big{]},$

and letting $\delta^{2}=\frac{1}{\lVert A_{i}\rVert_{2}}$ yields

$\displaystyle(a)_{i}\leq$ $\displaystyle\rho\lVert
A_{i}\rVert_{2}\Big{(}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}\Big{)}$
(42) $\displaystyle\leq$ $\displaystyle\rho
A_{max}\Big{(}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}\Big{)}.$

Applying (40) on each term $(b)_{ji}$ yields

$\displaystyle(b)_{ji}\leq$ $\displaystyle
2\rho\Big{[}\frac{1}{2\delta^{2}}\lVert\nu_{j}^{k+1}-\mu_{j}^{k+1}\rVert_{2}^{2}+\frac{\delta^{2}}{2}\lVert
g_{ji}(\mathbf{x}_{i}^{k+1})-g_{ji}(\mathbf{x}_{i}^{k})\rVert_{2}^{2}\Big{]}$
(43) $\displaystyle\leq$ $\displaystyle
2\rho\Big{[}\frac{1}{2\delta^{2}}\lVert\nu_{j}^{k+1}-\mu_{j}^{k+1}\rVert_{2}^{2}+\frac{\delta^{2}}{2}L_{ji}^{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}\Big{]},$

and letting $\delta^{2}=\frac{1}{L_{ji}}$ yields

$\displaystyle(b)_{ji}\leq$ $\displaystyle\rho
L_{ji}\Big{(}\lVert\nu_{j}^{k+1}-\mu_{j}^{k+1}\rVert_{2}^{2}+\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}\Big{)}$
(44) $\displaystyle\leq$ $\displaystyle\rho
L_{max}\Big{(}\lVert\nu_{j}^{k+1}-\mu_{j}^{k+1}\rVert_{2}^{2}+\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}\Big{)}.$

Substituting (42) and (44) into (39) yields

$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle-$ $\displaystyle(1-\rho A_{max}-\rho
ML_{max})\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}-(1-\rho
NA_{max})\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}$
$\displaystyle-$ $\displaystyle(1-\rho
NL_{max})\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}-\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}-\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}$
(45)

Since
$0<\rho\leq\min\Big{\\{}\frac{1-\epsilon}{A_{max}+ML_{max}},\frac{1-\epsilon}{NA_{max}},\frac{1-\epsilon}{NL_{max}}\Big{\\}}$,
we have:

$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle-$
$\displaystyle\epsilon\Big{(}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}+\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}$
$\displaystyle\hskip
15.0pt+\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}\Big{)}.$
(46)

It implies that for all $k\geq 0$:

$\displaystyle 0\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k-1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k-1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k-1}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\cdots\leq\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{0}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{0}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{0}-\bm{\mu}^{*}\rVert_{2}^{2}.$
(47)

It further implies that the sequence
$\Big{\\{}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}\Big{\\}}$
is monotonically decreasing and bounded below by $0$; hence the sequence must
be convergent to a limit, denoted by $\xi$:

$\lim_{k\to+\infty}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}=\xi.$
(48)

Taking the limit on both sides of (46) yields:

$\displaystyle\lim_{k\to+\infty}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}=0,$
(49)
$\displaystyle\lim_{k\to+\infty}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}=0,\quad$
$\displaystyle\lim_{k\to+\infty}\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}=0,$
$\displaystyle\lim_{k\to+\infty}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}=0,\quad$
$\displaystyle\lim_{k\to+\infty}\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}=0.$

Additionally, (48) also implies that
$\\{(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\mu}^{k})\\}$
is a bounded sequence, and thus there exists a sub-sequence
$\\{(\mathbf{x}_{1}^{k_{j}},\dots,\mathbf{x}_{N}^{k_{j}},\bm{\lambda}^{k_{j}},\bm{\mu}^{k_{j}})\\}$
that converges to a limit point
$(\mathbf{x}_{1}^{\infty},\dots,\mathbf{x}_{N}^{\infty},\bm{\lambda}^{\infty},\bm{\mu}^{\infty})$.
We next show that the limit point is indeed a saddle point and is also the
unique limit point of
$\\{(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\mu}^{k})\\}$.
Applying Lemma 2.1 with
$\widehat{\mathbf{z}}=(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1})$,
$\bar{\mathbf{z}}=(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k})$ and any
$\mathbf{z}=(\mathbf{x}_{1},\dots,\mathbf{x}_{N})\in\prod_{i=1}^{N}\mathcal{X}_{i}$,
we have:

$\displaystyle
2\rho\Big{[}\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})-\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\gamma}^{k+1},\bm{\nu}^{k+1})\Big{]}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}\rVert_{2}^{2}-\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}\rVert_{2}^{2}-\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\big{(}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{k+1}\rVert^{2}+\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}\rVert^{2}\big{)}-\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}\rVert^{2}-\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert^{2}=0$
$\displaystyle\forall(\mathbf{x}_{1},\dots,\mathbf{x}_{N})\in\prod_{i=1}^{N}\mathcal{X}_{i}.$
(50)

Taking the limits over an appropriate sub-sequence $\\{k_{j}\\}$ on both sides
and using (49), we have:

$\mathcal{L}(\mathbf{x}_{1}^{\infty},\dots,\mathbf{x}_{N}^{\infty},\bm{\lambda}^{\infty},\bm{\mu}^{\infty})\leq\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda}^{\infty},\bm{\mu}^{\infty}),\quad\forall(\mathbf{x}_{1},\dots,\mathbf{x}_{N})\in\prod_{i=1}^{N}\mathcal{X}_{i}.$
(51)

Similarly, applying Lemma 2.1 with
$\widehat{\mathbf{z}}=(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$,
$\bar{\mathbf{z}}=(\bm{\lambda}^{k},\bm{\mu}^{k})$ and any
$\mathbf{z}=(\bm{\lambda},\bm{\mu}\in\mathbb{R}_{+}^{m_{2}})$, we have:

$\displaystyle
2\rho\left[\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda},\bm{\mu})-\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})\right]$
$\displaystyle\leq$
$\displaystyle\lVert\bm{\lambda}^{k}-\bm{\lambda}\rVert^{2}-\lVert\bm{\lambda}^{k+1}-\bm{\lambda}\rVert^{2}-\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert^{2}$
$\displaystyle+$
$\displaystyle\lVert\bm{\mu}^{k}-\bm{\mu}\rVert^{2}-\lVert\bm{\mu}^{k+1}-\bm{\mu}\rVert^{2}-\lVert\bm{\mu}^{k+1}-\bm{\mu}^{k}\rVert^{2}$
$\displaystyle\leq$
$\displaystyle\big{(}\lVert\bm{\lambda}^{k}-\bm{\lambda}^{k+1}\rVert^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}\rVert^{2}\big{)}-\lVert\bm{\lambda}^{k+1}-\bm{\lambda}\rVert^{2}-\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert^{2}$
$\displaystyle+$
$\displaystyle\big{(}\lVert\bm{\mu}^{k}-\bm{\mu}^{k+1}\rVert^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}\rVert^{2}\big{)}-\lVert\bm{\mu}^{k+1}-\bm{\mu}\rVert^{2}-\lVert\bm{\mu}^{k+1}-\bm{\mu}^{k}\rVert^{2}=0,\quad\forall\bm{\mu}\in\mathbb{R}_{+}^{m_{2}}.$
(52)

Taking the limits over an appropriate sub-sequence $\\{k_{j}\\}$ on both sides
and using (49), we have:

$\mathcal{L}(\mathbf{x}_{1}^{\infty},\dots,\mathbf{x}_{N}^{\infty},\bm{\lambda},\bm{\mu})\leq\mathcal{L}(\mathbf{x}_{1}^{\infty},\dots,\mathbf{x}_{N}^{\infty},\bm{\lambda}^{\infty},\bm{\mu}^{\infty}),\quad\forall\bm{\mu}\in\mathbb{R}_{+}^{m_{2}}.$
(53)

Therefore, we show that
$(\mathbf{x}_{1}^{\infty},\dots,\mathbf{x}_{N}^{\infty},\bm{\lambda}^{\infty},\bm{\mu}^{\infty})$
is indeed a saddle point of the Lagrangian function
$\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda},\bm{\mu})$. Then
(48) implies that

$\lim_{k\to+\infty}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{\infty}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{\infty}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{\infty}\rVert_{2}^{2}=\xi.$
(54)

Since we have already argued (after Eq. (49)) that there exists a bounded
sequence of
$\\{(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\mu}^{k})\\}$
that converges to 0; that is, there exists $\\{k_{j}\\}$ such that

$\lim_{k_{j}\to+\infty}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k_{j}}-\mathbf{x}_{i}^{\infty}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k_{j}}-\bm{\lambda}^{\infty}\rVert_{2}^{2}+\lVert\bm{\mu}^{k_{j}}-\bm{\mu}^{\infty}\rVert_{2}^{2}=0,$

which then implies that $\xi=0$. Therefore, we show that
$\\{(\mathbf{x}_{1}^{k},\dots,\mathbf{x}_{N}^{k},\bm{\lambda}^{k},\bm{\mu}^{k})\\}$
converges globally to a saddle point
$(\mathbf{x}_{1}^{\infty},\dots,\mathbf{x}_{N}^{\infty},\bm{\lambda}^{\infty},\bm{\mu}^{\infty})$.

###  A.3 Proof of Theorem 2.5

Letting

$\displaystyle\mathbf{u}_{i}^{k}=A_{i}^{T}(\bm{\lambda}^{k+1}-\bm{\gamma}^{k+1})+\sum_{j=1}^{m_{2}}(\mu_{j}^{k+1}-\nu_{j}^{k+1})\nabla_{\mathbf{x}_{i}}g_{ji}(\mathbf{x}_{i}^{k+1})-\frac{1}{\rho}(\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}),\quad\forall
i=1\dots N,$ (55)
$\displaystyle\mathbf{v}^{k}=-\frac{1}{\rho}(\bm{\lambda}^{k+1}-\bm{\lambda}^{k}),$
$\displaystyle\mathbf{w}^{k}=-\frac{1}{\rho}(\bm{\mu}^{k+1}-\bm{\mu}^{k}),$

we first show that
$(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})\in
S^{-1}(\mathbf{u}_{1}^{k},\dots,\mathbf{u}_{N}^{k},\mathbf{v}^{k},\mathbf{w}^{k})$.
By the primal minimization step (10), we have, for all $i=1\dots N$:

$-\nabla_{\mathbf{x}_{i}}f_{i}(\mathbf{x}_{i}^{k+1})-\underbrace{\Big{[}A_{i}^{T}\bm{\gamma}^{k+1}+\sum_{j=1}^{M}\nu_{j}^{k+1}\nabla_{\mathbf{x}_{i}}g_{ji}(\mathbf{x}_{i}^{k+1})+\frac{1}{\rho}(\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k})\Big{]}}_{\Delta_{u_{i}}}\in\mathcal{N}_{\mathcal{X}_{i}}(\mathbf{x}_{i}^{k+1}),$
(56)

where
$\mathcal{N}_{\mathcal{X}_{i}}(\mathbf{x}^{k+1})\coloneqq\\{\mathbf{y}\in\mathbb{R}^{n_{1}}|\mathbf{y}^{T}(\mathbf{x}-\mathbf{x}^{k+1})\leq\mathbf{0},\forall\mathbf{x}\in\mathcal{X}_{i}\\}$
denotes the normal cone to the set $\mathcal{X}_{i}$ at the point
$\mathbf{x}_{i}^{k+1}$ for all $i=1,\dots,N$. Plugging

$\Delta_{u_{i}}=A_{i}^{T}\bm{\lambda}^{k+1}+\sum_{j=1}^{M}\mu_{j}^{k+1}\nabla_{\mathbf{x}_{i}}g_{ji}(\mathbf{x}_{i}^{k+1})-\mathbf{u}_{i}^{k}$

into the above expression, we have that, for all $i=1,\dots,N$:

$-\nabla_{\mathbf{x}_{i}}f_{i}(\mathbf{x}_{i}^{k+1})-A_{i}^{T}\bm{\lambda}^{k+1}-\sum_{j=1}^{M}\mu_{j}^{k+1}\nabla_{\mathbf{x}_{i}}g_{ji}(\mathbf{x}_{i}^{k+1})+\mathbf{u}_{i}^{k}\in\mathcal{N}_{\mathcal{X}_{i}}(\mathbf{x}_{i}^{k+1}),$
(57)

which implies

$\displaystyle(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1})$ (58)
$\displaystyle\in$
$\displaystyle\underset{(\mathbf{x}_{1},\dots,\mathbf{x}_{N})\in\prod_{i=1}^{N}\mathcal{X}_{i}}{\operatorname*{\arg\\!\min}}\mathcal{L}(\mathbf{x}_{1},\dots,\mathbf{x}_{N},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})-\sum_{i=1}^{N}\mathbf{x}_{i}^{T}\mathbf{u}_{i}^{k}+(\bm{\lambda}^{k+1})^{T}\mathbf{v}^{k}+(\bm{\mu}^{k+1})^{T}\mathbf{w}^{k}.$

Similarly, by the interpretation of $(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})$ in
Lemma 2.2, we have:

$\displaystyle\nabla_{\bm{\lambda}}\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})+\underbrace{\Big{[}-\frac{1}{\rho}(\bm{\lambda}^{k+1}-\bm{\lambda}^{k})\Big{]}}_{\mathbf{v}^{k}}=\mathbf{0},$
(59)
$\displaystyle\nabla_{\bm{\mu}}\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})+\underbrace{\Big{[}-\frac{1}{\rho}(\bm{\mu}^{k+1}-\bm{\mu}^{k})\Big{]}}_{\mathbf{w}^{k}}\in\mathcal{N}_{\mathbb{R}_{+}^{m_{2}}}(\bm{\mu}^{k+1}),$

which imply

$\displaystyle(\bm{\lambda}^{k+1},\bm{\mu}^{k+1})\in\underset{\bm{\lambda}\in\mathbb{R}^{m},\bm{\mu}\in\mathbb{R}^{M}}{\operatorname*{\arg\\!\max}}\mathcal{L}(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda},\bm{\mu})-\sum_{i=1}^{N}(\mathbf{x}_{i}^{k+1})^{T}\mathbf{u}_{i}^{k}+\bm{\lambda}^{T}\mathbf{v}^{k}+\bm{\mu}^{T}\mathbf{w}^{k}.$
(60)

The first-order optimality conditions (58) and (60) together imply that

$(\mathbf{x}_{1}^{k+1},\dots,\mathbf{x}_{N}^{k+1},\bm{\lambda}^{k+1},\bm{\mu}^{k+1})\in
S^{-1}(\mathbf{u}_{1}^{k},\dots,\mathbf{u}_{N}^{k},\mathbf{v}^{k},\mathbf{w}^{k}).$

By (49), we have
$\lim_{k\to\infty}(\mathbf{u}_{1}^{k},\dots,\mathbf{u}_{N}^{k},\mathbf{v}^{k},\mathbf{w}^{k})\to\mathbf{0}$.
Choose in integer $\bar{k}$ such that, for all $k\geq\bar{k}$,
$\lVert(\mathbf{u}_{1}^{k},\dots,\mathbf{u}_{N}^{k},\mathbf{v}^{k},\mathbf{w}^{k})\rVert_{2}\leq\tau$,
then by Assumption 2.4, we have:

$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}$
$\displaystyle\leq$ $\displaystyle
a^{2}\Big{(}\sum_{i=1}^{N}\lVert\mathbf{u}_{i}^{k}\rVert_{2}^{2}+\lVert\mathbf{v}^{k}\rVert_{2}^{2}+\lVert\mathbf{w}^{k}\rVert_{2}^{2}\Big{)}$
$\displaystyle\leq$ $\displaystyle
a^{2}\Big{(}NA_{max}^{2}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+NL_{max}^{2}\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}+\frac{1}{\rho^{2}}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}$
$\displaystyle\hskip
15.0pt+\frac{1}{\rho^{2}}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{1}{\rho^{2}}\lVert\bm{\mu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}\Big{)}$
$\displaystyle\leq$ $\displaystyle
a^{2}\Bigg{[}\frac{1}{\rho^{2}}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}+NA_{max}^{2}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+NL_{max}^{2}\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}$
$\displaystyle\hskip
15.0pt+\frac{1}{\rho^{2}}\Big{(}\lVert\bm{\lambda}^{k+1}-\bm{\gamma}^{k+1}\rVert_{2}^{2}+\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}\Big{)}$
$\displaystyle\hskip
15.0pt+\frac{1}{\rho^{2}}\Big{(}\lVert\bm{\mu}^{k+1}-\bm{\nu}^{k+1}\rVert_{2}^{2}+\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}\Big{)}\Bigg{]}$
$\displaystyle\leq$ $\displaystyle
a^{2}\Bigg{[}\frac{1}{\rho^{2}}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}$
$\displaystyle\hskip
15.0pt+(NA_{max}^{2}+\frac{1}{\rho^{2}})\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+(NL_{max}^{2}+\frac{1}{\rho^{2}})\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}$
$\displaystyle\hskip
15.0pt+\frac{1}{\rho^{2}}\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{1}{\rho^{2}}\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}\Bigg{]}$
$\displaystyle\leq$ $\displaystyle
a^{2}(N\alpha^{2}+\frac{1}{\rho^{2}})\Big{(}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{k}\rVert_{2}^{2}+\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k+1}\rVert_{2}^{2}$
$\displaystyle\hskip
80.0pt+\lVert\bm{\gamma}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\lVert\bm{\nu}^{k+1}-\bm{\mu}^{k}\rVert_{2}^{2}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{a^{2}(N\alpha^{2}+\frac{1}{\rho^{2}})}{\epsilon}\Bigg{[}\Big{(}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle\hskip
65.0pt-\Big{(}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}\Big{)}\Bigg{]}.$
(61)

The last inequality is due to (46), and
$\alpha\coloneqq\max\\{A_{max},L_{max}\\}$. We further derive

$\displaystyle\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k+1}-\bm{\mu}^{*}\rVert_{2}^{2}$
(62) $\displaystyle\leq$
$\displaystyle\theta^{2}\Big{(}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k}-\bm{\lambda}^{*}\rVert_{2}^{2}+\lVert\bm{\mu}^{k}-\bm{\mu}^{*}\rVert_{2}^{2}\Big{)},$

where $\theta=\sqrt{\frac{1}{1+\beta}}<1$ and
$\beta=\frac{\epsilon}{a^{2}(N\alpha^{2}+\frac{1}{\rho^{2}})}>0$.

##  Appendix B Proofs in Section 3.2

###  B.1 Proof of Theorem 3.2

For all $k\geq 0$, we can equivalently write the update steps in Algorithm 2
and Algorithm 3 as

$\mathbf{x}_{i}^{k+1}=\left\\{\begin{aligned}
&\underset{\mathbf{x}_{i}\in\mathcal{X}_{i}}{\operatorname*{\arg\\!\min}}f_{i}(\mathbf{x}_{i})+(2\bm{\lambda}^{\hat{k}_{i}+1}-\bm{\lambda}^{\hat{k}_{i}})^{T}A_{i}\mathbf{x}_{i}+\frac{1}{2\rho}\lVert\mathbf{x}_{i}-\mathbf{x}_{i}^{\hat{k}_{i}+1}\rVert^{2},&\forall
i\in\mathcal{A}_{k}\\\ &\mathbf{x}_{i}^{k},&\forall
i\in\mathcal{A}_{k}^{\complement}\end{aligned}\right.,$ (63)
$\bm{\lambda}^{k+1}=\bm{\lambda}^{k}+\rho\big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\mathbf{b}\big{)},$
(64)
$\hat{\bm{\gamma}}=\bm{\lambda}^{k+1}+\rho\big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\mathbf{b}\big{)}=2\bm{\lambda}^{k+1}-\bm{\lambda}^{k},$
(65)

where $\hat{k}_{i}$ is the last iteration when the main processor receives
$\widehat{\mathbf{x}}_{i}$ from the worker processor $i\in\mathcal{A}_{k}$
before iteration $k$. For each worker processor
$i\in\mathcal{A}_{k}^{\complement}$, we denote $\bar{k}_{i}\in(k-\tau,k)$ as
the last iteration when the main processor receives $\hat{\mathbf{x}}_{i}$
from the worker processor $i$ before iteration $k$, and further denote
$\bar{\bar{k}}_{i}\in[\bar{k}_{i}-\tau,\bar{k}_{i})$ as the last iteration
when the main processor receives $\widehat{\mathbf{x}}_{i}$ from the worker
processor $i$ before iteration $\bar{k}_{i}$. We can rewrite the primal
minimization step as

$\mathbf{x}_{i}^{k+1}=\left\\{\begin{aligned}
&\arg\underset{\mathbf{x}_{i}}{\min}f_{i}(\mathbf{x}_{i})+(2\bm{\lambda}^{\hat{k}_{i}+1}-\bm{\lambda}^{\hat{k}_{i}})^{T}A_{i}\mathbf{x}_{i}+\frac{1}{2\rho}\lVert\mathbf{x}_{i}-\mathbf{x}_{i}^{\hat{k}_{i}+1}\rVert^{2},&\forall
i\in\mathcal{A}_{k}\\\
\mathbf{x}_{i}^{\bar{k}_{i}+1}=&\arg\underset{\mathbf{x}_{i}}{\min}f_{i}(\mathbf{x}_{i})+(2\bm{\lambda}^{\bar{\bar{k}}_{i}+1}-\bm{\lambda}^{\bar{\bar{k}}_{i}})^{T}A_{i}\mathbf{x}_{i}+\frac{1}{2\rho}\lVert\mathbf{x}_{i}-\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}\rVert^{2},&\forall
i\in\mathcal{A}_{k}^{\complement}\end{aligned}\right..$ (66)

At each iteration $k\geq 0$, for any $i\in\mathcal{A}_{k}$, applying Lemma 3.1
with $\widehat{\mathbf{z}}=\mathbf{x}_{i}^{k+1}$,
$\bar{\mathbf{z}}=\mathbf{x}_{i}^{\hat{k}_{i}+1}$, and
$\mathbf{z}=\mathbf{x}_{i}^{*}$, we have:

$\displaystyle
f_{i}(\mathbf{x}_{i}^{k+1})-f_{i}(\mathbf{x}_{i}^{*})+\bm{\lambda}^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}+(\frac{\sigma_{i}}{2}+\frac{1}{2\rho})\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle\frac{1}{2\rho}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{\hat{k}_{i}+1}\rVert_{2}^{2}-\frac{1}{2\rho}\lVert\mathbf{x}_{i}^{\hat{k}_{i}+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle(\bm{\lambda}^{k+1}-\bm{\lambda})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}+(2\bm{\lambda}^{\hat{k}_{i}+1}-\bm{\lambda}^{\hat{k}_{i}}-\bm{\lambda}^{k+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}\leq
0.$ (67)

At each iteration $k\geq 0$, for any $i\in\mathcal{A}_{k}^{\complement}$,
applying Lemma 3.1 with $\widehat{\mathbf{z}}=\mathbf{x}_{i}^{k+1}$,
$\bar{\mathbf{z}}=\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}$, and
$\mathbf{z}=\mathbf{x}_{i}^{*}$, we have:

$\displaystyle
f_{i}(\mathbf{x}_{i}^{k+1})-f_{i}(\mathbf{x}_{i}^{*})+\bm{\lambda}^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}+(\frac{\sigma_{i}}{2}+\frac{1}{2\rho})\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle\frac{1}{2\rho}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}\rVert_{2}^{2}-\frac{1}{2\rho}\lVert\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle(\bm{\lambda}^{k+1}-\bm{\lambda})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}+(2\bm{\lambda}^{\bar{\bar{k}}_{i}+1}-\bm{\lambda}^{\bar{\bar{k}}_{i}}-\bm{\lambda}^{k+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}\leq
0.$ (68)

Summing (67) over all $i\in\mathcal{A}_{k}$ and (68) over all
$i\in\mathcal{A}_{k}^{\complement}$ yields

$\displaystyle\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{k+1})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+\underbrace{\bm{\lambda}^{T}\sum_{i=1}^{N}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}}_{\text{(a)}}+\frac{\sigma_{min}}{2}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle\underbrace{\frac{1}{2\rho}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}}_{\text{(b)}}$
$\displaystyle+$
$\displaystyle\underbrace{\frac{1}{2\rho}\Big{[}\sum_{i\in\mathcal{A}_{k}}\big{(}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{\hat{k}_{i}+1}\rVert_{2}^{2}-\lVert\mathbf{x}_{i}^{\hat{k}_{i}+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\big{)}+\sum_{i\in\mathcal{A}_{k}^{\complement}}\big{(}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}\rVert_{2}^{2}-\lVert\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\big{)}\Big{]}}_{\text{(c)}}$
$\displaystyle+$
$\displaystyle\underbrace{(\bm{\lambda}^{k+1}-\bm{\lambda})^{T}\sum_{i=1}^{N}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}}_{\text{(d)}}$
$\displaystyle+$
$\displaystyle\sum_{i\in\mathcal{A}_{k}}(2\bm{\lambda}^{\hat{k}_{i}+1}-\bm{\lambda}^{\hat{k}_{i}}-\bm{\lambda}^{k+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle+$
$\displaystyle\sum_{i\in\mathcal{A}_{k}^{\complement}}(2\bm{\lambda}^{\bar{\bar{k}}_{i}+1}-\bm{\lambda}^{\bar{\bar{k}}_{i}}-\bm{\lambda}^{k+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle\leq 0.$ (69)

The term (a) can be rewritten as:

$(a)=\bm{\lambda}^{T}\big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{*}\big{)}=\bm{\lambda}^{T}\Big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\mathbf{b}\Big{)}.$
(70)

The term (b) + (c) can be rewritten as:

$\displaystyle(b)+(c)=$
$\displaystyle\frac{1}{2\rho}\sum_{i\in\mathcal{A}_{k}}\big{(}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{\hat{k}_{i}+1}\rVert_{2}^{2}-\lVert\mathbf{x}_{i}^{\hat{k}_{i}+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\big{)}$
$\displaystyle+$
$\displaystyle\frac{1}{2\rho}\sum_{i\in\mathcal{A}_{k}^{\complement}}\big{(}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}+\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}\rVert_{2}^{2}-\lVert\mathbf{x}_{i}^{\bar{\bar{k}}_{i}+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\big{)}$
$\displaystyle\geq 0.$ (71)

The term (d) can be rewritten as:

$(d)=(\bm{\lambda}^{k+1}-\bm{\lambda})^{T}\big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{*}\big{)}=\frac{1}{\rho}(\bm{\lambda}^{k+1}-\bm{\lambda})^{T}(\bm{\lambda}^{k+1}-\bm{\lambda}^{k}).$
(72)

We substitute (70), (71) and (72) into (69), and sum it over $k=0\dots K-1$.
Taking the average yields

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{k+1})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+\frac{1}{K}\bm{\lambda}^{T}\Big{(}\sum_{k=0}^{K-1}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\mathbf{b}\Big{)}$
$\displaystyle\leq-$
$\displaystyle\frac{\sigma_{min}}{2K}\sum_{k=0}^{K-1}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}$
$\displaystyle-$ $\displaystyle\frac{1}{\rho
K}\underbrace{\sum_{k=0}^{K-1}(\bm{\lambda}^{k+1}-\bm{\lambda})^{T}(\bm{\lambda}^{k+1}-\bm{\lambda}^{k})}_{\text{(e)}}$
$\displaystyle+$
$\displaystyle\frac{1}{K}\underbrace{\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}}(\bm{\lambda}^{\hat{k}_{i}}+\bm{\lambda}^{k+1}-2\bm{\lambda}^{\hat{k}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}}_{\text{(f)}}$
$\displaystyle+$
$\displaystyle\frac{1}{K}\underbrace{\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}(\bm{\lambda}^{\bar{\bar{k}}_{i}}+\bm{\lambda}^{k+1}-2\bm{\lambda}^{\bar{\bar{k}}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}}_{\text{(g)}}.$
(73)

The term (e) in (73) can be rewritten as:

$\displaystyle(e)=$
$\displaystyle\frac{1}{2}\sum_{k=0}^{k-1}\big{(}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}\rVert_{2}^{2}-\lVert\bm{\lambda}-\bm{\lambda}^{k}\rVert_{2}^{2}+\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}\big{)}$
(74) $\displaystyle=$
$\displaystyle\frac{1}{2}\lVert\bm{\lambda}^{K}-\bm{\lambda}\rVert_{2}^{2}-\frac{1}{2}\lVert\bm{\lambda}^{0}-\bm{\lambda}\rVert_{2}^{2}+\frac{1}{2}\sum_{k=0}^{K-1}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}.$

The term (f) in (73) can be bounded as:

$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}}(\bm{\lambda}^{\hat{k}_{i}}+\bm{\lambda}^{k+1}-2\bm{\lambda}^{\hat{k}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}}(\bm{\lambda}^{\hat{k}_{i}}-\bm{\lambda}^{\hat{k}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}+\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}}(\bm{\lambda}^{k+1}-\bm{\lambda}^{\hat{k}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}}\sum_{l=\hat{k}_{i}}^{\hat{k}_{i}}(\bm{\lambda}^{l}-\bm{\lambda}^{l+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle+$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}}\sum_{l=\hat{k}_{i}+1}^{k}(\bm{\lambda}^{l+1}-\bm{\lambda}^{l})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle\leq$
$\displaystyle\sum_{i\in\mathcal{A}_{k}}\sum_{k=0}^{K-1}\sum_{l=\hat{k}_{i}}^{\hat{k}_{i}}\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{l}-\bm{\lambda}^{l+1}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle+$
$\displaystyle\sum_{i\in\mathcal{A}_{k}}\sum_{k=0}^{K-1}\sum_{l=\hat{k}_{i}+1}^{k}\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{l+1}-\bm{\lambda}^{l}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\sum_{k=0}^{K-1}(\tau-1)\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{k}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{N}\sum_{k=0}^{K-1}(\tau-1)\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{(\tau-1)N}{\delta^{2}}\sum_{k=0}^{K-1}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+(\tau-1)\delta^{2}A_{\max}^{2}\sum_{k=0}^{K-1}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2},$
(75)

where the first inequality is obtained by (40), and the second inequality is
due to the fact that the term
$\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}$ does not appear more
than $\tau-1$ times for each iteration $k$.

Similarly, the term (g) in (73) can be bounded as:

$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}(\bm{\lambda}^{\bar{\bar{k}}_{i}}+\bm{\lambda}^{k+1}-2\bm{\lambda}^{\bar{\bar{k}}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}(\bm{\lambda}^{\bar{\bar{k}}_{i}}-\bm{\lambda}^{\bar{\bar{k}}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}+\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}(\bm{\lambda}^{\bar{k}_{i}+1}-\bm{\lambda}^{\bar{\bar{k}}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle+$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}(\bm{\lambda}^{k+1}-\bm{\lambda}^{\bar{k}_{i}+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}\sum_{l=\bar{\bar{k}}_{i}}^{\bar{\bar{k}}_{i}}(\bm{\lambda}^{l}-\bm{\lambda}^{l+1})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle+$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}\sum_{l=\bar{\bar{k}}_{i}+1}^{\bar{k}_{i}}(\bm{\lambda}^{l+1}-\bm{\lambda}^{l})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle+$
$\displaystyle\sum_{k=0}^{K-1}\sum_{i\in\mathcal{A}_{k}^{\complement}}\sum_{l=\bar{k}_{i}+1}^{k}(\bm{\lambda}^{l+1}-\bm{\lambda}^{l})^{T}\big{(}A_{i}\mathbf{x}_{i}^{k+1}-A_{i}\mathbf{x}_{i}^{*}\big{)}$
$\displaystyle\leq$
$\displaystyle\sum_{i\in\mathcal{A}_{k}^{\complement}}\sum_{k=0}^{K-1}\sum_{l=\bar{\bar{k}}_{i}}^{\bar{\bar{k}}_{i}}\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{l}-\bm{\lambda}^{l+1}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle+$
$\displaystyle\sum_{i\in\mathcal{A}_{k}^{\complement}}\sum_{k=0}^{K-1}\sum_{l=\bar{\bar{k}}_{i}+1}^{\bar{k}_{i}}\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{l+1}-\bm{\lambda}^{l}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle+$
$\displaystyle\sum_{i\in\mathcal{A}_{k}^{\complement}}\sum_{k=0}^{K-1}\sum_{l=\bar{k}_{i}+1}^{k}\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{l+1}-\bm{\lambda}^{l}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\sum_{k=0}^{K-1}(\tau-1)\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{k}-\bm{\lambda}^{k+1}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{N}\sum_{k=0}^{K-1}(\tau-1)\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{N}\sum_{k=0}^{K-1}(\tau-1)\Big{(}\frac{1}{2\delta^{2}}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{\delta^{2}\lVert
A_{i}\rVert_{2}^{2}}{2}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{3(\tau-1)N}{2\delta^{2}}\sum_{k=0}^{K-1}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}+\frac{3(\tau-1)\delta^{2}}{2}A_{\max}^{2}\sum_{k=0}^{K-1}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2}.$
(76)

By substituting (74), (75) and (76) into (73) and denoting

$\bar{\mathbf{x}}_{i}^{K}=\frac{1}{K}\sum_{k=0}^{K-1}\mathbf{x}_{i}^{k+1},$

for all $i=1\dots N$, we have:

$\displaystyle\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{K})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+\bm{\lambda}^{T}\Big{(}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}^{K}-\mathbf{b}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{k+1})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+\frac{1}{K}\bm{\lambda}^{T}\sum_{k=0}^{K-1}\Big{(}\sum_{i=1}^{N}A_{i}\mathbf{x}_{i}^{k+1}-\mathbf{b}\Big{)}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2\rho
K}\lVert\bm{\lambda}^{0}-\bm{\lambda}\rVert_{2}^{2}-\frac{1}{2\rho
K}\lVert\bm{\lambda}^{K}-\bm{\lambda}\rVert_{2}^{2}$ $\displaystyle+$
$\displaystyle(-\frac{1}{2\rho
K}+\frac{5(\tau-1)N}{2\delta^{2}K})\sum_{k=0}^{K-1}\lVert\bm{\lambda}^{k+1}-\bm{\lambda}^{k}\rVert_{2}^{2}$
$\displaystyle+$
$\displaystyle(-\frac{\sigma_{min}}{2K}+\frac{5(\tau-1)\delta^{2}A_{\max}^{2}}{2K})\sum_{k=0}^{K-1}\sum_{i=1}^{N}\lVert\mathbf{x}_{i}^{k+1}-\mathbf{x}_{i}^{*}\rVert_{2}^{2},$
(77)

where the first inequality is due to the convexity of $f_{i}$ for all
$i=1\dots N$. By choosing
$\delta^{2}\leq\frac{\sigma_{min}}{5(\tau-1)A_{\max}^{2}}$ and
$\rho\leq\frac{\delta^{2}}{5(\tau-1)N}$, which implies

$\rho\leq\frac{\sigma_{min}}{25N(\tau-1)^{2}A_{\max}^{2}},$

we derive:

$\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{K})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+\bm{\lambda}^{T}\Big{(}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}^{K}-\mathbf{b}\Big{)}\leq\frac{1}{2\rho
K}\lVert\bm{\lambda}^{0}-\bm{\lambda}\rVert_{2}^{2}.$ (78)

Let
$\bm{\lambda}=\bm{\lambda}^{*}+\frac{\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{K}-\mathbf{b}}{\lVert\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{K}-\mathbf{b}\rVert_{2}}$,
and note that by the duality theory, we have:

$\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{K})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+(\bm{\lambda}^{*})^{T}\Big{(}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}^{K}-\mathbf{b}\Big{)}\geq
0.$ (79)

Then, we further derive:

$\displaystyle\big{\lVert}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{K}-\mathbf{b}\big{\rVert}_{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{K})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+(\bm{\lambda}^{*})^{T}\Big{(}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}^{K}-\mathbf{b}\Big{)}+\big{\lVert}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{K}-\mathbf{b}\big{\rVert}_{2}$
$\displaystyle\leq$ $\displaystyle\frac{1}{2\rho
K}\Bigg{\lVert}\bm{\lambda}^{0}-\Big{(}\bm{\lambda}^{*}+\frac{\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{K}-\mathbf{b}}{\lVert\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{K}-\mathbf{b}\rVert_{2}}\Big{)}\Bigg{\rVert}_{2}^{2},$
(80)

which implies

$\big{\lVert}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}^{K}-\mathbf{b}\big{\rVert}_{2}\leq\frac{1}{K}\Big{[}\frac{1}{2\rho}\underset{\lVert\bm{\gamma}\rVert_{2}\leq
1}{\max}\lVert\bm{\lambda}^{0}-\bm{\lambda}^{*}-\bm{\gamma}\rVert_{2}^{2}\Big{]}\overset{\Delta}{=}\frac{C_{1}}{K}.$

On the other hand, let $\bm{\lambda}=\bm{\lambda}^{*}$, and note that:

$\displaystyle\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{K})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})+(\bm{\lambda}^{*})^{T}\Big{(}\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}^{K}-\mathbf{b}\Big{)}$
(81) $\displaystyle\geq$
$\displaystyle\Big{\lvert}\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{K})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})\Big{\rvert}-\lVert\bm{\lambda}^{*}\rVert_{2}\cdot\lVert\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}^{K}-\mathbf{b}\rVert_{2}.$

Then, we have:

$\Big{\lvert}\sum_{i=1}^{N}f_{i}(\bar{\mathbf{x}}_{i}^{K})-\sum_{i=1}^{N}f_{i}(\mathbf{x}_{i}^{*})\Big{\rvert}\leq\lVert\bm{\lambda}^{*}\rVert_{2}\cdot\lVert\sum_{i=1}^{N}A_{i}\bar{\mathbf{x}}_{i}^{K}-\mathbf{b}\rVert_{2}+\frac{1}{K}(\frac{1}{2\rho}\lVert\bm{\lambda}^{0}-\bm{\lambda}^{*}\rVert_{2}^{2})\overset{\Delta}{=}\frac{\delta_{\bm{\lambda}}C_{1}+C_{2}}{K},$
(82)

where $\delta_{\bm{\lambda}}=\lVert\bm{\lambda}^{*}\rVert_{2}$ and
$C_{2}=\frac{1}{2\rho}\lVert\bm{\lambda}^{0}-\bm{\lambda}^{*}\rVert_{2}^{2}$.