###### Abstract

We present a distributed algorithm to solve a multi-agent optimization
problem, where the global objective function is the sum
$\tilde{f}(x)=\sum_{i=1}^{n}\tilde{f}_{i}(x)$ of $n$ functions, with
$\tilde{f}_{i}$ being a convex objective known only to agent $i$. Our focus is
on constrained problems where the agents’ estimates are restricted to be in
different convex sets. The interconnection topology among the $n$ agents has
directed links and each agent $i$ can only communicate with agents in its
neighborhood determined by a directed graph. In this article, we propose an
algorithm called Directed Constrained-Distributed Alternating Direction Method
of Multipliers (DC-DistADMM) to solve the above multi-agent convex
optimization problem. During every iteration of the DC-DistADMM algorithm,
each agent solves a local convex optimization problem and utilizes a finite-
time “approximate” consensus protocol to update its local estimate of the
optimal solution. To the best of our knowledge the proposed algorithm is the
first ADMM based algorithm to solve distributed multi-agent optimization
problems in directed interconnection topologies with convergence guarantees.
We show that in case of individual functions being convex and not-necessarily
differentiable the proposed DC-DistADMM algorithm converges at a rate of
$O(1/k)$, where $k$ is the iteration counter. We further establish a linear
rate of convergence for the DC-DistADMM algorithm when the global objective
function is strongly convex and smooth. We numerically evaluate our proposed
algorithm by solving a constrained distributed $\ell_{1}$-regularized logistic
regression problem. Additionally, we provide a numerical comparison of the
proposed DC-DistADMM algorithm with the other state-of-the-art algorithms in
solving a distributed least squares problem to show the efficacy of the DC-
DistADMM algorithm over the existing methods in the literature.

keywords: Distributed optimization, alternating direction method of
multipliers (ADMM), directed graphs, multi-agent networks, finite-time
consensus.

DC-DistADMM: ADMM Algorithm for Contrained Distributed Optimization over
Directed Graphs Vivek Khatana1 and Murti V. Salapaka1
This work is supported by Advanced Research Projects Agency-Energy OPEN
through the project titled "Rapidly Viable Sustained Grid" via grant no. DE-
AR0001016. 1 Vivek Khatana<EMAIL_ADDRESS>and Murti V. Salapaka
<EMAIL_ADDRESS>are with Department of Electrical and Computer Engineering,
University of Minnesota, Minneapolis, USA,

##  I Introduction

We focus on the problem of solving the following distributed optimization
problem involving $n$ agents:

$\displaystyle\operatorname*{argmin}\limits_{x}\ \tilde{f}(x)$
$\displaystyle=\sum_{i=1}^{n}\tilde{f}_{i}(x)$ (1) $\displaystyle\mbox{subject
to}\ \ x$ $\displaystyle\in\bigcap\limits_{i=1}^{n}\mathcal{X}_{i},$

where, $x\in\mathbb{R}^{p}$ is a global optimization variable and function
$\tilde{f}_{i}$ : $\mathbb{R}^{p}\rightarrow\mathbb{R}$ and set
$\mathcal{X}_{i}$ are a convex objective function and convex constraint set
respectively, known only to agent $i$. The agents are connected through a
directed interconnection topology which is modeled as a directed graph,
$\mathcal{G}(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ and $\mathcal{E}$
are sets of vertices and directed edges respectively. Each agent can only
communicate to its neighboring nodes connected to it via a directed edge in
$\mathcal{G}(\mathcal{V},\mathcal{E})$. Many problems in various engineering
fields such as wireless systems [1], sensor networks [2], multi-agent
coordination and control [3], machine learning [4, 5, 6], and robotics [7] can
be posed in the form of problem (1).

Early works on the distributed optimization problem can be found in seminal
works [8, 9]. Since then, the problem of minimizing sum of convex functions
has received significant attention [10, 11, 12, 13]. The methods proposed in
the literature to solve (1) can be broadly classified as : (i) primal and (ii)
dual based optimization methods. The primal based algorithms, with beginnings
in the Distributed Gradient Descent (DGD) [10], utilize the gradient
information of the objective function to steer towards the optimal solution.
Most of the existing methods in this category are (sub)-gradient based first-
order methods including the stochastic and asynchronous versions of DGD [14],
[15], [11], EXTRA [16], DIGing [17], FROST [18], Push-Pull [19], Gradient-
Consensus [20] and many others [21, 22, 23, 24, 25, 26]. The works [27] and
[28] have proposed fast gradient methods utilizing Nesterov’s acceleration.

The present work falls in the second category of dual based optimization
methods. These methods are based on using Lagrange multipliers. One such
method is Alternating Direction Method of Multipliers (ADMM). ADMM is known
for a better numerical convergence in centralized settings [29]. Due to its
parallel nature ADMM is also utilized in various dual based approaches in the
literature to solve distributed optimization problems [30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40]. ADMM based methods can be further classified in two
categories based on the communication architecture used by the agents: (i)
master-worker communication architecture, (ii) agent-to-agent distributed
communication architecture. The algorithms in the master-worker category [30,
31] have agents called workers which minimize their local objective functions
and send the updated local variables to a node designated as the master agent,
which is responsible for updating the global optimization variable and then
distributing the updated value back to the workers. Here, we focus on the
algorithms based on ADMM utilizing agent-to-agent distributed communication
architecture. References [34], [38] proposed a distributed ADMM algorithms to
solve a distributed optimization problem with a sublinear rate of convergence
when the objective functions $\tilde{f}_{i}$’s are convex. The authors in [35]
have established linear convergence rate of distributed ADMM under strong
convexity of the individual objective functions. However, the results in [34],
[38] and [35] are valid for undirected graph topologies which imply every
communication channel is necessarily bidirectional. A communication efficient
ADMM scheme under restricted assumptions such as the underlying graph being
bipartite was introduced in [33]. The work in [40] is based on minimizing a
proximal first-order approximation of the smooth and strongly convex function
$\tilde{f}_{i}$’s over an undirected network. None of the above multi-agent
ADMM algorithms in the literature are applicable in case of general directed
communication topologies. To this end, in this article we propose a novel ADMM
based algorithm called Directed Constrained-Distributed Alternating Direction
Method of Multipliers (DC-DistADMM) method to solve (1) over general directed
graphs. The proposed DC-DistADMM scheme utilizes a finite-time "approximate"
consensus protocol along with an ADMM based optimization scheme to steer
towards the optimal solution. In particular, during any iteration $k$, each
agent $i$ maintains two local primal variables $x_{i}^{k}\in\mathbb{R}^{p}$
and $y_{i}^{k}\in\mathbb{R}^{p}$ and a dual variable
$\lambda_{i}^{k}\in\mathbb{R}^{p}$. At each iteration $k$ of the DC-DistADMM
algorithm (explained in detail later) every agent solves a local optimization
problem to obtain $x_{i}^{k+1}$ and shares its computed value with its
neighbors in $\mathcal{G}(\mathcal{V},\mathcal{E})$. Agents then utilize a
finite-time $\varepsilon$-consensus protocol to determine their estimates
$y_{i}^{k+1}$ based on the local optimization variable $x_{i}^{k+1}$ and the
dual variable $\lambda_{i}^{k}$. And finally updates the dual variable to
$\lambda_{i}^{k+1}$ based on $x_{i}^{k+1}$ and $y_{i}^{k+1}$. Here,
$\varepsilon>0$ is a pre-specified tolerance that is independent of the
network topology and problem (1). Under the assumption of individual functions
being convex but not-necessarily differentiable the proposed DC-DistADMM
algorithm has an $O(1/k)$ rate of convergence, where $k$ is the iteration
counter. Further, in case of the global objective function being strongly
convex and smooth the proposed DC-DistADMM algorithm converges to the optimal
solution linearly. We demonstrate the efficacy of the DC-DistADMM algorithm by
numerically solving a constrained $\ell_{1}$ regularized distributed logistic
regression problem. We additionally compare the performance of DC-DistADMM
algorithm to other state-of-the-art algorithms to solve the distributed
problem proposed in the literature by solving a distributed least squares
problem. The results demonstrate advantage of using DC-DistADMM over the other
algorithms.

###  I-A Summary of contributions and Paper Organization

The main contribution of this article, is fourfold. First, we develop a novel
DC-DistADMM algorithm for solving constrained distributed optimization
problems, on directed graph interconnections. At each iteration of DC-DistADMM
the agents perform a local convex minimization and utilize a finite-time
$\varepsilon$-consensus protocol to update the estimate of the optimal
solution. The scheme proposed here is applicable to solve (1) in a distributed
manner over directed networks, unlike [41, 32, 33, 35, 34, 38, 39, 40]. To the
best of our knowledge this is the first ADMM based algorithm with strong
convergence guarantees that enjoys such property.

Second, the DC-DistADMM algorithm is applicable for solving constrained
distributed optimization problems unlike most of the algorithms present in the
literature [14, 15, 11, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28],
[30, 31, 32, 34, 35, 36, 38, 39, 40] which are focused on unconstrained
optimization problems.

Third, we establish an $O(1/k)$ rate of convergence, where $k$ is the
iteration counter, for the proposed DC-DistADMM algorithm under the assumption
of individual functions being convex and not-necessarily differentiable
objective function. This is same as the best known rate estimate under these
assumptions in the literature. Further, in case when the global function is
strongly convex and smooth we prove that the proposed DC-DistADMM algorithm
converges to the optimal solution at a linear rate. Note, that we do not
require any strong assumptions of the individual functions $\tilde{f}_{i}$
being strongly convex as assumed in the analysis of most existing methods in
the literature [27, 19, 28, 16, 35, 38, 17]. We also do not make strong
assumptions on the solution set as done in [28], for example.

Fourth, we combine the techniques used in the ADMM based optimization methods
with the average consensus literature to develop DC-DistADMM algorithm which
has a superior performance over the existing methods as shown in the results.
This unification is useful as it builds underlying guidelines for further
developments on distributed optimization algorithms. Also, our proposed DC-
DistADMM algorithm eliminates the requirement of an optimization step to
update the global variable in the standard ADMM [30] setup and replaces it
with a less computation intensive $\varepsilon$-consensus protocol. Further,
the DC-DistADMM does not require a centralized co-ordination among the agents
and thus, is amenable to distributed synthesis unlike the existing methods in
the literature [32, 33, 34, 35, 36, 37, 38, 39, 40].

The authors have introduced a preliminary version [42] of the method developed
here termed as D-DistADMM; the current work presents a significant
generalization, DC-DistADMM where a constrained distributed optimization
problem is considered compared to the unconstrained case focused in the
preliminary version. The constrained optimization problem poses significant
technical challenges over the unconstrained case; however, we establish
stronger and more comprehensive results under less restrictive assumptions.
Here, we provide a comprehensive and detailed analysis where we establish a
linear rate of convergence for the DC-DistADMM algorithm when the global
objective function is strongly convex and smooth and an $O(1/k)$ rate of
convergence in terms of the objective function residuals (difference between
the objective function value at any iteration $k$ and the optimal objective
function value) in the case when the individual functions are convex but not-
necessarily convex (in comparison to preliminary results on convergence of the
Lagrangian function residuals presented in [42]). In the current work, we also
provide numerical validation of the DC-DistADMM algorithm and its
applicability using detailed numerical tests and comparison with other state-
of-the-art algorithms which is missing in the preliminary version [42].

The rest of the article is organized as follows. We present the framework for
the DC-DistADMM algorithm along with basic definitions and notations in
Section II. In Section III we discuss the DC-DistADMM algorithm along with the
finite-time $\varepsilon$-consensus protocol in detail and provide supporting
analysis. The convergence analysis of the proposed algorithm is provided in
Section IV. In particular, we establish two different convergence rate
characterization under two different set of assumptions. In Section V we
conduct numerical simulations on a $\ell_{1}$ regularized distributed logistic
regression problem and present the results. Further, we carry out a
performance comparison between the existing state-of-the-art methods and DC-
DistADMM in solving a distributed least squares problem. The comparison
results verify our theoretical claims and provide a discussion on the
effectiveness and suitability of the proposed algorithm. Section VI provides
the concluding remarks and discusses some future work of this article.

##  II Definitions, Problem Formulation and Assumptions

###  II-A Definition, Notations and Assumptions

In this section, we present definitions and notations that is used later in
the analysis. Detailed description of these notions can be found in [43],
[44], [45] and [46].

######  Definition 1.

(Directed Graph) A directed graph $\mathcal{G}$ is a pair
$(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$ is a set of vertices (or
nodes) and $\mathcal{E}$ is a set of edges, which are ordered subsets of two
distinct elements of $\mathcal{V}$. If an edge from $j\in\mathcal{V}$ to
$i\in\mathcal{V}$ exists then it is denoted as $(i,j)\in\mathcal{E}$.

######  Definition 2.

(Path) In a directed graph, a directed path from node $i$ to $j$ exists if
there is a sequence of distinct directed edges of $\mathcal{G}$ of the form
$(p_{1},i),(p_{2},p_{1}),...,(j,p_{m}).$

######  Definition 3.

(Strongly Connected Graph) A directed graph is strongly connected if for any
pair $(i,j),\ i\not=j$, there is a directed path from node $i$ to node $j$.

######  Definition 4.

(Column-Stochastic Matrix) A matrix $M=[m_{ij}]\in\mathbb{R}^{n\times n}$ is
called a column-stochastic matrix if $0\leq m_{ij}\leq 1$ and
$\sum_{i=1}^{n}m_{ij}=1$ for all $1\leq i,j\leq n$.

######  Definition 5.

(Irreducible Matrix) A matrix $M=[m_{ij}]\in\mathbb{R}^{n\times n}$ is said to
be irreducible if for all $1\leq i,j\leq n$, there exist $t\in\mathbb{N}$ such
that $[M^{t}]_{ij}>0$.

######  Definition 6.

(Primitive Matrix) A non-negative matrix $M$ is primitive if it is irreducible
and has only one eigenvalue of maximum modulus.

######  Definition 7.

(Diameter of a Graph) The diameter of a directed graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$ is the longest shortest directed path
between any two nodes in the the graph.

######  Definition 8.

(In-Neighborhood) The set of in-neighbors of node $i\in\mathcal{V}$ is called
the in-neighborhood of node $i$ and is denoted by $\mathcal{N}^{-}_{i}=\\{j\
|\ (i,j)\in\mathcal{E}\\}$ not including the node $i$.

######  Definition 9.

(Out-Neighborhood) The set of out-neighbors of node $i\in\mathcal{V}$ is
called the out-neighborhood of node $i$ and is denoted by
$\mathcal{N}^{+}_{i}=\\{j\ |\ (j,i)\in\mathcal{E}\\}$ not including the node
$i$.

######  Definition 10.

(Convex function) A function $f$ is said to be convex if the domain of $f$ is
convex and for all $x,y\in\operatorname*{dom}f$ and $0\leq t\leq 1$,

$\displaystyle f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).$

######  Definition 11.

(Sub-gradient of a convex function) Let
$f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be a convex function. We say that a
vector $d\in\mathbb{R}^{p}$ is a subgradient of $f$ at a point
$x\in\mathbb{R}^{p}$ if

$\displaystyle f(z)\geq f(x)+d^{\top}(z-x),\ \mbox{for all}\
z\in\mathbb{R}^{p}.$

The set of all subgradients of a convex function $f$ at $x\in\mathbb{R}^{p}$
is called the subdifferential of $f$ at $x$, and is denoted by $\partial
f(x)$.

######  Definition 12.

(Lipschitz Differentiability) A differentiable function $f$ is called
Lipschitz differentiable with constant $L>0$, if the following inequality
holds:

$\displaystyle\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|,\ \forall\
x,y\in\operatorname*{dom}f.$

######  Definition 13.

(Strongly Convex Function) A differentiable function $f$ is called strongly
convex with parameter $\sigma>0$, if the following inequality holds:

$\displaystyle\langle\nabla f(x)-\nabla f(y),x-y\rangle\geq\sigma\|x-y\|^{2},\
\forall\ x,y\in\operatorname*{dom}f.$

######  Definition 14.

(Diameter of a set) For a norm $\|\cdot\|$ and a set $K\subset\mathbb{R}^{p}$
define the diameter of $K$ with respect to the norm $\|\cdot\|$,
$\operatorname*{diam}_{\|\cdot\|}(K):=\sup\limits_{x,y\in K}\|x-y\|$.

######  Definition 15.

(Affine hull of a set) The affine hull $\operatorname*{Aff}(X)$ of a set $X$
is the set of all affine combinations of elements of $X$, that is,

$\displaystyle\operatorname*{Aff}(X)=\left\\{\sum_{i=1}^{k}\theta_{i}x_{i}\ |\
k>0,x_{i}\in X,\theta_{i}\in\mathbb{R},\sum_{i=1}^{k}\theta_{i}=1\right\\}.$

######  Definition 16.

(Relative interior of a set) Let $X\subset\mathbb{R}^{n}$. We say that a point
$x\in X$ is in the relative interior of $X$, if $X$ contains the intersection
of a small enough ball centered at $x$ with the $\operatorname*{Aff}(X)$, that
is, there exists $r>0$ such that

$\displaystyle B_{r}(x)\cap\operatorname*{Aff}(X):=\\{y\ |\
y\in\operatorname*{Aff}(X),\|y-x\|\leq r\\}\subset X.$

The set of all relative interior points of $X$ is called its relative interior
denoted by $\operatorname*{relint}(X)$.

Throughout the paper, we assume vectors to be column vectors unless stated
otherwise. Each agent $i\in\mathcal{V}$ maintains two local primal variables
$x_{i}^{k}\in\mathbb{R}^{p}$, $y_{i}^{k}\in\mathbb{R}^{p}$ and a dual variable
$\lambda_{i}^{k}\in\mathbb{R}^{p}$ at all iterations $k\geq 0$ of the DC-
DistADMM algorithm. Let $\mathbf{X}^{k}=\\{x_{i}^{k}\\}_{i\in\mathcal{V}}$,
$\mathbf{Y}^{k}=\\{y_{i}^{k}\\}_{i\in\mathcal{V}}$,
$\mathbf{\Lambda}^{k}=\\{\lambda_{i}^{k}\\}_{i\in\mathcal{V}}$ denote the
collection of all the primal and dual variables at iteration $k$. We define
vectorization operations for the given collections
$\mathbf{X}^{k},\mathbf{Y}^{k}$ and, $\mathbf{\Lambda}^{k}$ as
$x_{[1:n]}^{k}=[(x_{1}^{k})^{\top}\ (x_{2}^{k})^{\top}\dots\
(x_{n}^{k})^{\top}]^{\top}\in\mathbb{R}^{np},y_{[1:n]}^{k}=[(y_{1}^{k})^{\top}\
(y_{2}^{k})^{\top}\dots\ (y_{n}^{k})^{\top}]^{\top}\in\mathbb{R}^{np}$ and,
$\mathbf{\lambda}_{[1:n]}^{k}=[(\lambda_{1}^{k})^{\top}\
(\lambda_{2}^{k})^{\top}\dots(\lambda_{n}^{k})^{\top}]^{\top}\in\mathbb{R}^{np}$
respectively. The directed graph $\mathcal{G}(\mathcal{V},\mathcal{E})$
represents the interconnection topology among the agents and $\mathcal{D}$
denotes an upper bound on the diameter of the graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$.

######  Assumption 1.

The directed graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ is strongly-
connected.

###  II-B Problem Formulation

Consider the distributed optimization problem given in (1),

$\displaystyle\operatorname*{minimize}\ \tilde{f}(x)$
$\displaystyle=\sum_{i=1}^{n}\tilde{f}_{i}(x)$ (2) $\displaystyle\text{subject
to}\ \ x$ $\displaystyle\in\bigcap\limits_{i=1}^{n}\mathcal{X}_{i},$

where, $\tilde{f}_{i}$ : $\mathbb{R}^{p}\rightarrow\mathbb{R}$ and
$\mathcal{X}_{i}$ are the convex objective function and the convex constraint
set of agent $i$ respectively, and $x\in\mathbb{R}^{p}$ is a (common) decision
vector for every agent in the network. We rewrite problem (2) by creating
local copies $x_{i}$ for all $i\in\mathcal{V}$, of the global variable $x$ and
impose the agreement in the solution of all the agents as a consensus
constraint. This leads to an equivalent formulation of (2) as described below:

$\displaystyle\operatorname*{minimize}\ \ $
$\displaystyle\sum_{i=1}^{n}\tilde{f}_{i}(x_{i})$ (3) subject to
$\displaystyle x_{i}\in\mathcal{X}_{i}\ \text{for all}\ i\in\mathcal{V}$
$\displaystyle x_{i}=x_{j}\ \text{for all}\ i,j\in\mathcal{V}.$

The constraints $x_{i}\in\mathcal{X}_{i}$ can be integrated into the objective
function using the indicator functions of the sets $\mathcal{X}_{i}$s, as:

$\displaystyle\operatorname*{minimize}\ $ $\displaystyle\
\sum_{i=1}^{n}f_{i}(x_{i})$ (4) subject to $\displaystyle\ x_{i}=x_{j}\
\text{for all}\ i,j\in\mathcal{V},$

where, $f_{i}(x_{i}):=\tilde{f}_{i}(x_{i})+\tilde{g}_{i}(x_{i})$ and
$\tilde{g}_{i}(x_{i})$ is the indicator function of set $\mathcal{X}_{i}$
given by:

$\displaystyle\tilde{g}_{i}(x_{i})=\begin{cases}0&\text{if}\
x_{i}\in\mathcal{X}_{i}\\\ +\infty&\text{otherwise}.\end{cases}$

We reformulate (4) to relax the exact consensus constraint to a requirement of
an $\varepsilon$-consensus among the variables of all the agents as follows:

$\displaystyle\operatorname*{minimize}\ \ $
$\displaystyle\sum_{i=1}^{n}f_{i}(x_{i})$ (5) subject to
$\displaystyle\|x_{i}-x_{j}\|\leq\varepsilon\ \text{for all}\
i,j\in\mathcal{V}.$

Here, the local variables of all the agents are required to remain
$\varepsilon$-close to each other. The parameter $\varepsilon>0$ can be
interpreted as a specified tolerance on the quality of consensus among the
agent variables. Note that for most applications finding an exact consensus
solution is not necessitated and utilizing an approximate consensus solution
helps in reducing the communication and computation resources required. Thus
such a relaxation is realistic. Further, under mild conditions on
$\mathcal{X}_{i}$ and objective functions $\tilde{f}_{i}(x)$ (see Assumptions
3-5), $\varepsilon$ can be chosen arbitrarily small according to the
application; and a corresponding solution within a pre-specified tolerance to
the optimal solution of (4) can be determined. Let
$\mathbf{X}=\\{x_{i}\\}_{i\in\mathcal{V}}$ represent the collection of all the
local variables. Denote $x_{[1:n]}=[x_{1}^{\top}\ x_{2}^{\top}\dots
x_{n}^{\top}]^{\top}\in\mathbb{R}^{np}$ as the vector formed from the entries
of $\mathbf{X}$. We define

$\displaystyle\mathcal{C}:=\big{\\{}y_{[1:n]}=[y_{1}^{\top}\ $ $\displaystyle
y_{2}^{\top}\dots y_{n}^{\top}]^{\top}\in\mathbb{R}^{np}\ $
$\displaystyle\Big{|}\ \|y_{i}-y_{j}\|\leq\varepsilon,\text{for all}\
i,j\in\mathcal{V}\big{\\}},$ (6)

to be a set of vectors $y_{[1:n]}\in\mathbb{R}^{np}$ such that the norm of the
difference between any two sub-vectors of $y_{[1:n]}$ with dimension $p$ is
less than $\varepsilon$. Using this description of set $\mathcal{C}$ and the
vector $x_{[1:n]}$, we write (5) as:

$\displaystyle\operatorname*{minimize}\ \ $
$\displaystyle\sum_{i=1}^{n}f_{i}(x_{i})$ (7) subject to $\displaystyle
x_{[1:n]}=y_{[1:n]},\ y_{[1:n]}\in\mathcal{C}.$

Let, $F(x_{[1:n]})=\sum_{i=1}^{n}f_{i}(x_{i})$, $x_{[1:n]}=[x_{1}^{\top}\dots
x_{n}^{\top}]^{\top}\in\mathbb{R}^{np}$. Using the definition of indicator
function of the set $\mathcal{C}$ we rewrite the objective function as:

$\displaystyle\operatorname*{minimize}\ \ $ $\displaystyle
F(x_{[1:n]})+G(y_{[1:n]})$ (8) subject to $\displaystyle x_{[1:n]}=y_{[1:n]},$

where, $G(y_{[1:n]})$ is the indicator function of set $\mathcal{C}$ given by:

$\displaystyle G(y_{[1:n]})=\begin{cases}0&\text{if}\
y_{[1:n]}\in\mathcal{C}\\\ \infty&\text{otherwise}.\end{cases}$

The augmented Lagrangian function is defined as:

$\displaystyle\mathcal{L}_{\gamma}(x_{[1:n]},y_{[1:n]},\lambda_{[1:n]})=F(x_{[1:n]})+G(y_{[1:n]})$
(9) $\displaystyle\hskip
57.81621pt+\lambda_{[1:n]}^{\top}(x_{[1:n]}-y_{[1:n]})+\frac{\gamma}{2}\|x_{[1:n]}-y_{[1:n]}\|^{2},$

where, $\lambda_{[1:n]}\in\mathbb{R}^{np}$ is the Lagrange multiplier
associated with the constraint $x_{[1:n]}-y_{[1:n]}=0$ and $\gamma>0$ is a
positive scalar.

###  II-C Standard ADMM Method

Here we provide a brief description of the ADMM method. The standard ADMM
method [30] is utilized to solve optimization problems of the following form:

$\displaystyle\operatorname*{minimize}_{x\in\mathbb{R}^{p},y\in\mathbb{R}^{q}}$
$\displaystyle\ \ f(x)+g(y)$ (10) subject to $\displaystyle\ \ Ax+By=c,$

where, $A\in\mathbb{R}^{n\times p},B\in\mathbb{R}^{n\times q}$, and
$c\in\mathbb{R}^{n}$. Consider, the augmented Lagrangian with the Lagrange
multiplier $\lambda$ and positive scalar $\gamma$,

$\displaystyle\mathcal{L}_{\gamma}(x,y,\lambda)=f(x)+g(y)+\lambda^{\top}(Ax+By-c)$
$\displaystyle\hskip 130.08621pt+\frac{\gamma}{2}\|Ax+By-c\|^{2}.$ (11)

The primal and dual variable updates in ADMM are given as: starting with the
initial guess $(x^{0},y^{0},\lambda^{0})$, at each iteration,

$\displaystyle x^{k+1}$
$\displaystyle=\operatorname*{argmin}\limits_{x}\mathcal{L}_{\gamma}(x,y^{k},\lambda^{k})$
(12) $\displaystyle y^{k+1}$
$\displaystyle=\operatorname*{argmin}\limits_{y}\mathcal{L}_{\gamma}(x^{k+1},y,\lambda^{k})$
(13) $\displaystyle\lambda^{k+1}$
$\displaystyle=\lambda^{k}+\gamma(Ax^{k+1}-By^{k+1}-c).$ (14)

Note that step-size in the dual variable update (14) is the same as the
parameter $\gamma$ in the augmented Lagrangian function.

##  III The Proposed DC-DistADMM Method

Using the definition (9), the augmented Lagrangian associated with (8) at any
iteration $k\geq 0$ is given as:

$\displaystyle\mathcal{L}_{\gamma}(x^{k}_{[1:n]},y^{k}_{[1:n]},\lambda^{k}_{[1:n]})=F(x^{k}_{[1:n]})+G(y^{k}_{[1:n]})$
(15) $\displaystyle\hskip
36.135pt+(\lambda_{[1:n]}^{k})^{\top}(x^{k}_{[1:n]}-y^{k}_{[1:n]})+\frac{\gamma}{2}\|x^{k}_{[1:n]}-y^{k}_{[1:n]}\|^{2}$
$\displaystyle=\sum_{i=1}^{n}\big{[}f_{i}(x_{i}^{k})+\frac{\gamma}{2}\|x_{i}^{k}-y_{i}^{k}\|^{2}+(\lambda_{i}^{k})^{\top}(x_{i}^{k}-y_{i}^{k})\big{]}+G(y^{k}_{[1:n]}),$

where, $y_{i}^{k}\in\mathbb{R}^{p}$ is the $i^{th}$ sub-vector of
$y^{k}_{[1:n]}\in\mathbb{R}^{np}$. Based on ADMM iterations (12)-(14) the
primal and dual updates corresponding to augmented Lagrangian (15) (where, the
quantities that do not affect the solution are omitted) are given as:

For all $i=1,2\dots,n$, $\displaystyle x_{i}^{k+1}$
$\displaystyle=\operatorname*{argmin}\limits_{x_{i}}f_{i}(x_{i})+\frac{\gamma}{2}\|x_{i}-y_{i}^{k}\|^{2}+(\lambda_{i}^{k})^{\top}(x_{i}-y_{i}^{k}).$
(16) $\displaystyle y^{k+1}_{[1:n]}$
$\displaystyle=\operatorname*{argmin}\limits_{y}G(y)+\frac{\gamma}{2}\|x_{[1:n]}^{k+1}-y\|^{2}+[x_{[1:n]}^{k+1}-y]^{\top}\lambda_{[1:n]}^{k},$
$\displaystyle=\operatorname*{argmin}\limits_{y}G(y)+\frac{\gamma}{2}\|x_{[1:n]}^{k+1}-y+\frac{1}{\gamma}\lambda_{[1:n]}^{k}\|^{2}.$
(17) For all $i=1,2\dots,n$, $\displaystyle\lambda_{i}^{k+1}$
$\displaystyle=\lambda_{i}^{k}+\gamma(x_{i}^{k+1}-y_{i}^{k+1}).$ (18)

The update in (16) can be solved via classical methods including gradient
descent [45] and proximal gradient [47]. The $y^{k+1}_{[1:n]}$ update in (17)
is the projection of $x_{[1:n]}^{k+1}+\frac{1}{\gamma}\lambda_{[1:n]}^{k}$
onto the set $\mathcal{C}$, whereas (18) gives the dual variable update at
each agent $i\in\mathcal{V}$. To find a solution of (17) we employ a
distributed finite-time $\varepsilon$-consensus protocol in higher-dimensions
[48]. The protocol was first introduced in [49], [50] in relation to consensus
among the agents on a scalar value.

###  III-A Finite-time $\varepsilon$-consensus protocol

Here, we will present a finite-time "approximate" consensus protocol which we
call the $\varepsilon$-consensus protocol. The protocol was first proposed in
an earlier work [48] by the authors. Here, we describe the
$\varepsilon$-consensus protocol for convenience. Consider, a set of $n$
agents connected through a directed graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$. Every agent $i$ has a vector
$u_{i}^{0}\in\mathbb{R}^{p}$. Let
$\widetilde{u}=\frac{1}{n}\sum_{i=1}^{n}u_{i}^{0}$ denote the average of the
vectors. The objective is to design a distributed protocol such that the
agents are able to compute an approximate estimate of $\widetilde{u}$ in
finite-time. This approximate estimate is parameterized by a tolerance
$\varepsilon$ that can be chosen arbitrarily small to make the estimate as
precise as needed. To this end, the agents maintain state variables
$u_{i}^{k}\in\mathbb{R}^{p},v_{i}^{k}\in\mathbb{R}$ and undergo an iterative
protocol with the following update rule: for $k=0,1,2,\dots$

$\displaystyle u_{i}^{k+1}$
$\displaystyle=p_{ii}u_{i}^{k}+\sum_{j\in\mathit{\mathcal{N}^{-}_{i}}}p_{ij}u_{j}^{k}$
(19) $\displaystyle v_{i}^{k+1}$
$\displaystyle=p_{ii}v_{i}^{k}+\sum_{j\in\mathit{\mathcal{N}^{-}_{i}}}p_{ij}v_{j}^{k}$
(20) $\displaystyle w_{i}^{k+1}$
$\displaystyle=\frac{1}{v_{i}^{k+1}}u_{i}^{k+1},$ (21)

where, $w_{i}^{0}=u_{i}^{0}$, $v_{i}^{0}=1$ for all $i\in\mathcal{V}$ and
$\mathcal{N}^{-}_{i}$ denotes the set of in-neighbors of agent $i$. The
updates (19)-(21) are closely related to the push-sum (or ratio consensus)
updates (see [51] or [52]). We make the following assumption on the weight
matrix $\mathcal{P}$:

######  Assumption 2.

Let $\mathcal{P}=[p_{ij}]$ the weighted adjacency matrix, associated with the
digraph $\mathcal{G}(\mathcal{V},\mathcal{E})$, be a primitive, column-
stochastic matrix.

######  Remark 0.1.

Note that $\mathcal{P}$ being a column stochastic matrix allows for a
distributed synthesis of the consensus protocol. The out-degree based equal
neighbor weights rule [53] is a common choice of weights that results in a
distributed synthesis based column stochastic $\mathcal{P}$ matrix. The
distributed synthesis provide a framework for the plug and play operation [54,
55]. This feature of the proposed protocol has an advantage over existing
schemes in the literature [10, 16, 27, 28] that utilize a doubly-stochastic
weight matrix and cannot achieve efficient distributed synthesis in directed
networks.

The variable $w_{i}^{k}\in\mathbb{R}^{p}$ is an estimate of $\widetilde{u}$
with each agent $i$ at any iteration $k$. It is established in prior work that
the vector estimates $w_{i}^{k}$ converge to the average $\widetilde{u}$
asymptotically.

######  Theorem 1.

Let Assumptions 1, 2 hold. Let $\\{u_{i}^{k}\\}_{k\geq
0},\\{v_{i}^{k}\\}_{k\geq 0}$ and $\\{w_{i}^{k}\\}_{k\geq 0}$ be the sequences
generated by (19), (20), and (21) at each agent $i\in\mathcal{V}$. Then
$w_{i}^{k}$ asymptotically converges to
$\widetilde{u}=\frac{1}{n}\sum_{i=1}^{n}u_{i}^{0}$ for all $i\in\mathcal{V}$,
that is

$\displaystyle\lim_{k\rightarrow\infty}w_{i}^{k}=\frac{1}{n}\sum_{i=1}^{n}u_{i}^{0},\
\text{for all}\ i\in\mathcal{V}.$

###### Proof.

Refer [48], [51] and [52] for the proof. ∎

It follows from Theorem 1 that as $w_{i}^{k}$ converges asymptotically to
$\widetilde{u}$, after possibly a large number of iterations $\overline{k}$
the agent states $w_{i}^{k},k\geq\overline{k}$ will be close to
$\widetilde{u}$. The $\varepsilon$-consensus protocol provides a distributed
algorithm to determine the iteration $\overline{k}$ such that the agent states
$w_{i}^{k},k\geq\overline{k}$, for all $i\in\mathcal{V}$ are simultaneously
$\varepsilon$-close to each other and hence from Theorem 1,
$\varepsilon$-close to $\widetilde{u}$. To this end, each agent maintains a
scalar value $R_{i}\in\mathbb{R}$ which is termed as the radius of agent $i$.
The motivation behind maintaining such a radius variable is as follows:
Consider an open ball at iteration $k$ that encloses all the agent states,
$w_{i}^{k}$, for all $i\in\mathcal{V}$, with a minimal radius (the existence
of such a ball can be shown due to bounded nature of the updates (19)-(21),
see Lemma 4.2 in [56]). Theorem 1 guarantees that all the agent states
$w_{i}^{k}$ converge to a single vector, which implies that the minimal ball
enclosing all the states will also shrink with iteration $k$ and eventually
the radius will become zero. The radius variable $R_{i}$ is designed to track
the radius of this minimal ball. Starting at an iteration $s$, at subsequent
iterations $k=0,1,2,\dots$ the radius $R_{i}^{k}(s)$ is updated to
$R_{i}^{k+1}(s)$ by agent $i$ as follows: for all $k=0,1,2\dots$

$\displaystyle
R_{i}^{k+1}(s)=\max\limits_{j\in\mathcal{N}_{i}^{-}}\big{\\{}\|w_{i}^{s+k+1}-w_{j}^{s+k}\|+R_{j}^{k}(s)\big{\\}},R_{i}^{0}(s):=0,$
(22)

for all $i\in\mathcal{V}$. Denote, $\mathcal{B}(w_{i}^{s+k},R_{i}^{k}(s))$ as
the ball of radius $R_{i}^{k}(s)$ centered at $w_{i}^{s+k}$. It is established
in [48] that, after $\mathcal{D}$ number of iterations of the update (22) the
ball $\mathcal{B}(w_{i}^{s+\mathcal{D}},R_{i}^{\mathcal{D}}(s))$ encloses the
states $w_{i}^{s}$ of all the agents $i\in\mathcal{V}$. We provide a proof of
Lemma 1 in the Appendix for completeness.

######  Lemma 1.

Let $\\{u_{i}^{k}\\}_{k\geq 0},\\{v_{i}^{k}\\}_{k\geq 0}$ and
$\\{w_{i}^{k}\\}_{k\geq 0}$ be the sequences generated by (19), (20), and (21)
at each agent $i\in\mathcal{V}$. Given, $s\geq 0$, let $R_{i}^{k}(s)$ be
updated as in (22) for all $k\geq 0$ and $i\in\mathcal{V}$. Under Assumptions
1 and 2,

$\displaystyle
w_{j}^{s}\in\mathcal{B}(w_{i}^{\mathcal{D}+s},R_{i}^{\mathcal{D}}(s)),\
\text{for all}\ j,i\in\mathcal{V}.$

###### Proof.

See Appendix VII-A for proof. ∎

Define,

$\displaystyle\widehat{R}_{i}^{m}:=R_{i}^{\mathcal{D}}(m\mathcal{D}),\
m=0,1,2,\dots,$ (23)

where, $R_{i}^{k}(s)$ follows the update rule (22) for any $s\geq 0$. We next
provide a result from [48] establishing the fact that the sequence of radii
$\\{\widehat{R}_{i}^{\mathcal{D}}(m\mathcal{D})\\}_{m\geq 0}$, for
$i\in\mathcal{V}$ converges to zero as $m\rightarrow\infty$. A short proof of
the result is provided in the Appendix for completeness.

######  Theorem 2.

Let $\\{u_{i}^{k}\\}_{k\geq 0},\\{v_{i}^{k}\\}_{k\geq
0},\\{w_{i}^{k}\\}_{k\geq 0},\\{\widehat{R}_{i}^{m}\\}_{m\geq 0}$ be the
sequences generated by (19), (20), (21) and (23) respectively by all agents
$i\in\mathcal{V}$. Under the Assumptions 1 and 2,

$\displaystyle\lim_{m\rightarrow\infty}\widehat{R}_{i}^{m}=0,\ \mbox{for all}\
i\in\mathcal{V}.$

Further, $\lim\limits_{m\rightarrow\infty}R_{i}^{m}=0$ if and only if
$\lim\limits_{m\rightarrow\infty}\max_{i,j\in\mathcal{V}}\|w^{m\mathcal{D}}_{i}-w_{j}^{m\mathcal{D}}\|=0$.

###### Proof.

See Appendix VII-B. ∎

Theorem 2 gives a criterion for termination of the consensus iterations
(19)-(21) by utilizing the radius updates at each agent $i\in\mathcal{V}$
given by (22). In particular, by tracking the radii
$\widehat{R}_{i}^{m},m=0,1,2\dots$ each agent can determine an estimate of the
radius of the minimal ball enclosing all the agent states (Lemma 1)
distributively. Further, monitoring the value of the
$\widehat{R}_{i}^{m},m=0,1,2\dots$ each agent can have the knowledge of the
state of consensus among all the agents. A protocol to determine
$\varepsilon$-consensus among the agents is presented in Algorithm 1.

Input:

Pre-specified tolerance $\varepsilon>0$;

Diameter upper bound $\mathcal{D}$;

Initialize:

$w_{i}^{0}=u_{i}^{0}$; $v_{i}^{0}=1$; $R_{i}^{0}=0$;

$m:=1$

Repeat for $k=0,1,2,\dots$

/* consensus updates (19)-(21) */

$u_{i}^{k+1}=p_{ii}u_{i}^{k}+\sum_{j\in\mathit{\mathcal{N}^{-}_{i}}}p_{ji}u_{j}^{k}$

$v_{i}^{k+1}=p_{ii}v_{i}^{k}+\sum_{j\in\mathit{\mathcal{N}^{-}_{i}}}p_{ji}v_{j}^{k}$

$w_{i}^{k+1}=\frac{1}{v_{i}^{k+1}}u_{i}^{k+1}$

/* radius update (22) */

$R_{i}^{k+1}=\max\limits_{j\in\mathcal{N}_{i}^{-}}\Big{\\{}\|w_{i}^{k+1}-w_{i}^{k}\|+R_{j}^{k}\Big{\\}}$

if  _$k=m\mathcal{D}-1$_ then

$\widehat{R}_{i}^{m-1}=R_{i}^{k+1}$;

if  _$\widehat{R}_{i}^{m-1} <\varepsilon$_ then

break ;

// $\varepsilon$-consensus achieved

else

$R_{i}^{k+1}=0$;

$m=m+1$;

end if

Algorithm 1 Finite-time $\varepsilon$-consensus protocol at each node
$i\in\mathcal{V}$ [48]

Algorithm 1 is initialized with $w_{i}^{0}=u_{i}^{0},v_{i}^{0}=1$ and
$R_{i}^{0}=0$ respectively for all $i\in\mathcal{V}$. Each agent follows rules
(19)-(21) to update its state variables. Note, that for ease of implementation
the update (22) is modified to remove the dependence on the iteration $s$ and
starting from $k=0$, $R_{i}^{k}$ is reset at each iteration of the form
$k=m\mathcal{D},m=1,2,\dots$ to have a value equal to $0$. The sequence of
radii $\\{\widehat{R}_{i}^{m}\\}_{m\geq 0}$ is determined by setting the value
$\widehat{R}_{i}^{m-1}$ equal to $R_{i}^{k}$ for all iterations of the form
$k=m\mathcal{D},m=1,2,\dots$. That is,
$\widehat{R}_{i}^{m-1}=R_{i}^{m\mathcal{D}}$ for all $m\geq 1$. From Lemma 1,
the ball $\mathcal{B}(w_{i}^{m\mathcal{D}},\widehat{R}_{i}^{m-1})$ will
contain all estimates $w_{i}^{(m-1)\mathcal{D}}$. This ball is the estimate of
the minimal ball enclosing all agent states $w_{i}^{(m-1)\mathcal{D}}$.
Therefore, as a method to detect $\varepsilon$-consensus, at every iteration
of the form $m\mathcal{D}$, for $m=1,2,\dots$, $\widehat{R}_{i}^{m-1}$ is
compared to the parameter $\varepsilon$, if
$\widehat{R}_{i}^{m-1}<\varepsilon$ then all the agent states
$w_{i}^{(m-1)\mathcal{D}}$ were $\varepsilon$-close to $\widetilde{u}$ (from
Theorem 1) and the iterations (19)-(21) are terminated. Proposition 1
establishes that the $\varepsilon$-consensus converges in finite number of
iterations.

######  Proposition 1.

Under the Assumptions 1 and 2, Algorithm 1 converges in finite number of
iterations at each agent $i\in\mathcal{V}$.

###### Proof.

Since, $\widehat{R}_{i}^{m}\rightarrow 0$ as $m\rightarrow\infty$. Therefore,
for all $\varepsilon>0$ and given $i\in\mathcal{V}$ there exists finite
$\overline{k}_{i}^{\varepsilon}$ such that for
$m\geq\overline{k}_{i}^{\varepsilon},\widehat{R}_{i}^{m}<\varepsilon$. This
completes the proof. ∎

Note, that the radius estimates $\widehat{R}_{i}^{m}$ can be different for
some of the agents. Thus, the detection of $\varepsilon$-consensus can happen
at different iterations for some nodes. In order to, have a global detection,
each agent can generate "converged flag" indicating its own detection. Such a
flag signal can then be combined by means of a distributed one-bit consensus
updates (see [48]), thus allowing the agents to agree on the global
$\varepsilon$-consensus status.

######  Remark 2.1.

Note that the only global parameter needed for Algorithm 1 is an upper bound
$\mathcal{D}$ on the diameter of the directed graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$, which is readily available in most
applications by design.

###  III-B $y$ variable updates in DC-DistADMM

The $\varepsilon$-consensus protocol discussed in the previous subsection can
be seen as a distributed projection operator which projects an input vector
$\mathbf{u}=[(u_{1}^{0})^{\top}\
(u_{2}^{0})^{\top}\dots(u_{n}^{0})^{\top}]^{\top}\in\mathbb{R}^{np}$ onto the
set $\mathcal{C}$ (II-B). It can be verified that

$\displaystyle\overline{y}_{[1:n]}:=[\overline{y}^{\top}\dots\overline{y}^{\top}]^{\top}\in\mathbb{R}^{np},\mbox{with},\
\overline{y}=\frac{1}{n}\sum_{i=1}^{n}[x_{i}^{k+1}+\frac{1}{\gamma}\lambda_{i}^{k}],$

is an optimal solution of the update (17). We utilize the
$\varepsilon$-consensus protocol to determine an approximate solution of the
update (17) distributively in the following manner:

At any iteration $k\geq 0$ of the DC-DistADMM algorithm, each agent
$i\in\mathcal{V}$ runs an $\varepsilon_{k+1}$-consensus protocol with the
following initialization:

$\displaystyle u_{i}^{0}=x_{i}^{k+1}+\frac{1}{\gamma}\lambda_{i}^{k},\
v_{i}^{0}=1,\ \mbox{and}\ w_{i}^{0}=u_{i}^{0}.$ (24)

From Proposition 1, the $\varepsilon_{k+1}$-consensus converges to approximate
consensus variables in a finite iteration $t$ such that for all
$i,j\in\mathcal{V}$,

$\displaystyle\|w_{i}^{t}-w_{j}^{t}\|\leq\varepsilon_{k+1},\ \ \mbox{and}\ \
\|w_{i}^{t}-\overline{y}\|\leq\varepsilon_{k+1},$

Each agent variable $y_{i}^{k+1}$ is then updated to the consensus variable
$w_{i}^{t}$. Further, the obtained vector
$y^{k+1}_{[1:n]}=[(y_{1}^{k+1})^{\top},\dots,(y_{n}^{k+1})^{\top}]^{\top}\in\mathbb{R}^{np}$
is $\sqrt{n}\varepsilon_{k+1}$-close to the actual (optimal) solution
$\overline{y}_{[1:n]}$, that is,

$\displaystyle\overline{y}_{[1:n]}=y^{k+1}_{[1:n]}+e^{k+1},\ \mbox{with}\
\|e^{k+1}\|\leq\sqrt{n}\varepsilon_{k+1}.$ (25)

The proposed DC-DistADMM algorithm is presented in Algorithm 2.

Input:

$\text{choose}\ \gamma>0,\\{\varepsilon_{k}\\}_{k\geq 0}$

Initialize:

For all $i\in\mathcal{V}$, pick
$x_{i}^{0}\in\mathbb{R}^{p},y_{i}^{0}\in\mathbb{R}^{p},\lambda_{i}^{0},\in\mathbb{R}^{p}$

Repeat for $k=0,1,2,\dots$

for  _$i=1,2,\dots n$ , (In parallel)_ do

$x_{i}^{k+1}=\operatorname*{argmin}\limits_{x_{i}}\big{[}f_{i}(x_{i})+\frac{\gamma}{2}\|x_{i}-y_{i}^{k}\|^{2}+(\lambda_{i}^{k})^{\top}(x_{i}-y_{i}^{k})\big{]}$

$y_{i}^{k+1}\xleftarrow[]{\text{$\varepsilon_{k+1}$ - consensus
protocol}}(x_{i}^{k+1}+\frac{1}{\gamma}\lambda_{i}^{k},\varepsilon_{k+1})$

$\lambda_{i}^{k+1}=\lambda_{i}^{k}+\gamma(x_{i}^{k+1}-y_{i}^{k+1})$

end for

until a stopping criterion is met

Algorithm 2 DC-DistADMM Algorithm

##  IV Convergence Results for DC-DistADMM

In this section, we present the convergence result for the proposed DC-
DistADMM algorithm. Define $x^{*}$ to be an optimal solution of (2). Also,
denote ($x_{[1:n]}^{*},y_{[1:n]}^{*}$) as an optimal solution of (8), where
$x_{[1:n]}^{*}=[x^{*\top}\ x^{*\top}\dots x^{*\top}]^{\top}\in\mathbb{R}^{np}$
and $y_{[1:n]}^{*}\in\mathbb{R}^{np}$. Let,
$\mathcal{X}=\mathcal{X}_{1}\times\dots\times\mathcal{X}_{n},\mathcal{S}=\mathcal{X}\times\mathcal{C}$,
and $\mathcal{X}^{*}\subset\mathcal{S}$ denote the set of optimal solutions of
(8). We make the following assumptions on the solution and constraint sets of
(8):

######  Assumption 3.

The optimal solution set $\mathcal{X}^{*}$ is non-empty.

######  Assumption 4.

Each $\mathcal{X}_{i}$ is a closed bounded convex set with diameter
$\operatorname*{diam}_{\|\cdot\|}(\mathcal{X}_{i})=\mathcal{M}_{i}$.

For further analysis of the DC-DistADMM algorithm we will make use of the
following:
1\. Sub-gradient inequality: Let $f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be a
convex function. Let $h(x)$ be a sub-gradient of $f$ at
$x\in\operatorname*{dom}f$, then for all $z\in\operatorname*{dom}f$,

$\displaystyle f(z)\geq f(x)+h^{\top}(x)(z-x).$ (26)

2\. For $x_{1},x_{2},x_{3},x_{4}\in\mathbb{R}^{p}$

$\displaystyle(x_{1}-x_{2})^{\top}(x_{3}-x_{4})$
$\displaystyle=\frac{1}{2}\big{(}\|x_{1}-x_{4}\|^{2}-\|x_{1}-x_{3}\|^{2}\big{)}$
$\displaystyle+\frac{1}{2}\big{(}\|x_{2}-x_{3}\|^{2}-\|x_{2}-x_{4}\|^{2}\big{)}.$
(27)

###  IV-A Sub-linear Rate of Convergence

Here, we analyze the convergence of the proposed DC-DistADMM algorithm for the
case when individual functions $\tilde{f}_{i}$ are convex but not necessarily
differentiable:

######  Assumption 5.

For all $i\in\\{1,2,\dots,n\\}$, $\tilde{f}_{i}$ is a not necessarily
differentiable, proper closed convex function having a lower bound.

Under Assumption 5, the first-order optimality conditions for (8) are:

$\displaystyle-\lambda_{i}^{*}$ $\displaystyle\in\partial f_{i}(x_{i}^{*}),\
i\in\\{1,\dots,n\\},$ (28) $\displaystyle x_{i}^{*}$
$\displaystyle=y_{i}^{*},\ i\in\\{1,\dots,n\\},$ (29) $\displaystyle
d(y_{[1:n]}^{*})-\lambda_{[1:n]}^{*}$ $\displaystyle=0,$ (30)

where, $\partial f_{i}(x_{i}^{*})$ is the set of all sub-gradients of $f_{i}$
at $x_{i}^{*}$, $d(y_{[1:n]}^{*})\in\partial G(y^{*}_{[1:n]})$ is a sub-
gradient of $G(.)$ at $y_{[1:n]}^{*}$, and
$\lambda_{[1:n]}^{*}=[\lambda_{1}^{*\top}\dots\lambda_{n}^{*\top}]^{\top}\in\mathbb{R}^{np}$.
Similarly, for the DC-DistADMM updates (16) and (17) by the first-order
optimality condition we have for all $i\in\\{1,\dots,n\\}$:

$\displaystyle-[\lambda_{i}^{k}+\gamma(x_{i}^{k+1}-y_{i}^{k})]$
$\displaystyle\in\partial f_{i}(x_{i}^{k+1}),$ (31)
$\displaystyle-[\lambda_{i}^{k+1}+\gamma(y_{i}^{k+1}-y_{i}^{k})]$
$\displaystyle\in\partial f_{i}(x_{i}^{k+1}),$ (32) $\displaystyle
d(\overline{y}_{[1:n]})+\gamma e^{k+1}-\lambda_{[1:n]}^{k+1}$
$\displaystyle=0,$ (33)

where, $\partial f_{i}(x_{i}^{k+1})$ is the set of all sub-gradients of
$f_{i}$ at $x_{i}^{k+1}$, $d(\overline{y}_{[1:n]})\in\partial
G(\overline{y}_{[1:n]})$ is a sub-gradient of $G(.)$ at
$\overline{y}_{[1:n]}$. The relation (32) comes from combining (31) with the
update formula (18) and (34) follows from combining (18) and (25). Since, $G$
is convex,

$\displaystyle G(y)$ $\displaystyle\geq
G(\overline{y}_{[1:n]})+d^{\top}(\overline{y}_{[1:n]})(y-\overline{y}_{[1:n]})$
$\displaystyle\implies 0\geq
d^{\top}(\overline{y}_{[1:n]})(y-\overline{y}_{[1:n]}).$

Since, $\overline{y}_{[1:n]}$ lies in the interior of $\mathcal{C}$, there
exists $\epsilon>0$, such that $\overline{y}_{[1:n]}+\epsilon
d(\overline{y}_{[1:n]})\in\mathcal{C}$, therefore,

$\displaystyle 0$ $\displaystyle\geq
d^{\top}(\overline{y}_{[1:n]})(\overline{y}_{[1:n]}+\epsilon
d(\overline{y}_{[1:n]})-\overline{y}_{[1:n]})$ $\displaystyle\implies\epsilon
d^{\top}(\overline{y}_{[1:n]})d(\overline{y}_{[1:n]})\leq 0$
$\displaystyle\implies d(\overline{y}_{[1:n]}))=0.$

Therefore, (33) becomes,

$\displaystyle\lambda_{[1:n]}^{k+1}=\gamma e^{k+1}.$ (34)

######  Lemma 2.

Let $\\{x_{i}^{k}\\}_{k\geq 1}$, $\\{\lambda_{i}^{k}\\}_{k\geq 1}$,
$\\{y_{i}^{k}\\}_{k\geq 1}$ for all $i\in\mathcal{V}$, be the sequences
generated by Algorithm 2. Let $\\{\varepsilon_{k}\\}_{k\geq 1}$ be the
sequence of tolerances in Algorithm 2. Under Assumptions 1-5 for all $k\geq
1$, the following holds,

$\displaystyle\|\lambda_{[1:n]}^{k}\|$
$\displaystyle\leq\gamma\sqrt{n}\varepsilon_{k},$
$\displaystyle\|y_{[1:n]}^{k}\|$
$\displaystyle\leq\sqrt{n}\mathcal{M}+\sqrt{n}\varepsilon_{k}+\sqrt{n}\varepsilon_{k-1},$

where, $\varepsilon_{k}$ is the consensus tolerance at iteration $k$,
$\mathcal{M}:=\max\limits_{1\leq i\leq n}\mathcal{M}_{i}$ with,
$\mathcal{M}_{i}$ being the diameter of the set $\mathcal{X}_{i}$.

###### Proof.

The first inequality follows directly from (34) and (25),

$\displaystyle\|\lambda_{[1:n]}^{k}\|\leq\gamma\|e^{k}\|\leq\gamma\sqrt{n}\varepsilon_{k}.$

From (18),

$\displaystyle\|y^{k}_{[1:n]}\|$
$\displaystyle\leq\|x_{[1:n]}^{k}-\frac{1}{\gamma}(\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k-1})\|$
$\displaystyle\leq\|x_{[1:n]}^{k}\|+\frac{1}{\gamma}\|\lambda_{[1:n]}^{k}\|+\frac{1}{\gamma}\|\lambda_{[1:n]}^{k-1}\|$
$\displaystyle\leq\sqrt{n}\mathcal{M}+\sqrt{n}\varepsilon_{k}+\sqrt{n}\varepsilon_{k-1},$

where, $\mathcal{M}:=\max\limits_{1\leq i\leq n}\mathcal{M}_{i}$ where,
$\mathcal{M}_{i}$ is the diameter of the set $\mathcal{X}_{i}$. This completes
the proof. ∎

######  Lemma 3.

Let $\\{x_{i}^{k}\\}_{k\geq 1}$, $\\{\lambda_{i}^{k}\\}_{k\geq 1}$,
$\\{y_{i}^{k}\\}_{k\geq 1}$ for all $i\in\mathcal{V}$, be the sequences
generated by Algorithm 2. Let $\\{\varepsilon_{k}\\}_{k\geq 1}$ be the
sequence of tolerances in Algorithm 2. Under Assumptions 1-5 for any
$\lambda\in\mathbb{R}^{np}$, the following holds,

$\displaystyle
F(x_{[1:n]}^{k+1})-F(x_{[1:n]}^{*})+G(y^{k+1}_{[1:n]})-G(y_{[1:n]}^{*})$
$\displaystyle+\lambda^{\top}[x_{[1:n]}^{k+1}-y^{k+1}_{[1:n]}]$
$\displaystyle\leq\frac{1}{\gamma}[\lambda-\lambda_{[1:n]}^{k+1}]^{\top}[\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k}]+(2\gamma+1)n(\varepsilon_{k+1})^{2}$
$\displaystyle+\gamma[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[y^{k+1}_{[1:n]}-y^{k}_{[1:n]}]+\gamma
n\mathcal{M}\varepsilon_{k+1}$
$\displaystyle+\gamma\sqrt{n}\|y_{[1:n]}^{*}\|\varepsilon_{k+1}+n(\varepsilon_{k})^{2},$

where, $(x_{[1:n]}^{*},y_{[1:n]}^{*})\in\mathcal{X}^{*}$ is any optimal
solution of (8), $\mathcal{M}$ is as defined in Lemma 2.

###### Proof.

Suppose $(x_{[1:n]}^{*},y_{[1:n]}^{*})$ is an optimal solution of (8). At any
iteration $k+1$ of the DC-DistADMM algorithm, by the optimality condition (32)
for all $i\in\\{1,2,\dots,n\\}$,

$\displaystyle
h_{i}(x_{i}^{k+1})+\lambda_{i}^{k+1}+\gamma(y_{i}^{k+1}-y_{i}^{k})=0,$

where, $h_{i}(x_{i}^{k+1})\in\partial f_{i}(x_{i}^{k+1})$ is a sub-gradient of
$f_{i}$ at $x_{i}^{k+1}$. Writing the above $n$ inequalities compactly,

$\displaystyle h$
$\displaystyle(x_{[1:n]}^{k+1})+\lambda_{[1:n]}^{k+1}+\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})=0,$

where, $h(x_{[1:n]}^{k+1})=[h^{\top}_{1}(x_{1}^{k+1})\dots
h^{\top}_{n}(x_{n}^{k+1})]^{\top}$ is a vector of subgradients
$h_{i}(x_{i}^{k+1})$ stacked together. Noticing that $F$ and $G$ are convex
and using sub-gradient inequality (26) for some
$d(\overline{y}_{[1:n]})\in\partial G(\overline{y}_{[1:n]})$ we have,

$\displaystyle F(x$ ${}_{[1:n]}^{k+1})-F(x)+G(\overline{y}_{[1:n]})-G(y)$
$\displaystyle\leq$
$\displaystyle-[x-x_{[1:n]}^{k+1}]^{\top}h(x_{[1:n]}^{k+1})-[y-\overline{y}_{[1:n]}]^{\top}d(\overline{y}_{[1:n]})$
$\displaystyle\leq$ $\displaystyle\
[x-x_{[1:n]}^{k+1}]^{\top}[\lambda_{[1:n]}^{k+1}+\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})]$
$\displaystyle+[y-\overline{y}_{[1:n]}]^{\top}(-\lambda_{[1:n]}^{k+1})+\gamma[y-\overline{y}_{[1:n]}]^{\top}e^{k+1}$
$\displaystyle=$ $\displaystyle\
[x-x_{[1:n]}^{k+1}]^{\top}[\lambda_{[1:n]}^{k+1}+\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})]$
$\displaystyle\hskip
7.22743pt+[y-y^{k+1}_{[1:n]}]^{\top}(-\lambda_{[1:n]}^{k+1})+\gamma\|e^{k+1}\|^{2}-(e^{k+1})^{\top}y$
$\displaystyle\hskip 7.22743pt+(e^{k+1})^{\top}[\lambda^{k+1}+\gamma
y^{k+1}_{[1:n]}]$ $\displaystyle\leq$ $\displaystyle\
[x-x_{[1:n]}^{k+1}]^{\top}[\lambda_{[1:n]}^{k+1}+\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})]$
$\displaystyle\ +[y-y^{k+1}_{[1:n]}]^{\top}(-\lambda_{[1:n]}^{k+1})+\gamma
n(\varepsilon_{k+1})^{2}+\gamma\sqrt{n}\varepsilon_{k+1}\|y\|$ $\displaystyle\
+(e^{k+1})^{\top}[\lambda^{k+1}+\gamma y^{k+1}_{[1:n]}]$

Using the result in Lemma 2,

$\displaystyle F(x$ ${}_{[1:n]}^{k+1})-F(x)+G(\overline{y}_{[1:n]})-G(y)$
$\displaystyle\leq$ $\displaystyle\
[x-x_{[1:n]}^{k+1}]^{\top}[\lambda_{[1:n]}^{k+1}+\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})]$
$\displaystyle\ +[y-y^{k+1}_{[1:n]}]^{\top}(-\lambda_{[1:n]}^{k+1})+\gamma
n(\varepsilon_{k+1})^{2}+\gamma\sqrt{n}\varepsilon_{k+1}\|y\|$ $\displaystyle\
+\gamma n(\varepsilon_{k+1})^{2}+\gamma
n\mathcal{M}\varepsilon_{k+1}+n(\varepsilon_{k+1})^{2}+n(\varepsilon_{k})^{2}.$

Here, $\mathcal{M}:=\max\limits_{1\leq i\leq n}\mathcal{M}_{i}$ where,
$\mathcal{M}_{i}$ is the diameter of the set $\mathcal{X}_{i}$. Setting
$(x,y)=(x_{[1:n]}^{*},y_{[1:n]}^{*})$ in the previous inequality and noting
that $G(\overline{y}_{[1:n]})=G(y^{k+1}_{[1:n]})$ gives,

$\displaystyle
F(x_{[1:n]}^{k+1})-F(x_{[1:n]}^{*})+G(y^{k+1}_{[1:n]})-G(y_{[1:n]}^{*})$
$\displaystyle\leq\
[x-x_{[1:n]}^{k+1}]^{\top}[\lambda_{[1:n]}^{k+1}+\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})]$
$\displaystyle\ +[y-y^{k+1}_{[1:n]}]^{\top}(-\lambda_{[1:n]}^{k+1})+\gamma
n(\varepsilon_{k+1})^{2}+\gamma\sqrt{n}\varepsilon_{k+1}\|y_{[1:n]}^{*}\|$
$\displaystyle\ +\gamma n(\varepsilon_{k+1})^{2}+\gamma
n\mathcal{M}\varepsilon_{k+1}+n(\varepsilon_{k+1})^{2}+n(\varepsilon_{k})^{2}.$

Therefore, for any fixed $\lambda$, we have

$\displaystyle
F(x_{[1:n]}^{k+1})-F(x_{[1:n]}^{*})+G(y^{k+1}_{[1:n]})-G(y_{[1:n]}^{*})$
$\displaystyle+\lambda^{\top}(x_{[1:n]}^{k+1}-y^{k+1}_{[1:n]})$
$\displaystyle\leq\
[\lambda_{[1:n]}^{k+1}-\lambda]^{\top}[y^{k+1}_{[1:n]}-x_{[1:n]}^{k+1}]+\gamma
n(\varepsilon_{k+1})^{2}$
$\displaystyle+\gamma[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[y^{k+1}_{[1:n]}-y^{k}_{[1:n]}]+\gamma\sqrt{n}\varepsilon_{k+1}\|y_{[1:n]}^{*}\|$
$\displaystyle+\gamma n\mathcal{M}\varepsilon_{k+1}+\gamma
n(\varepsilon_{k+1})^{2}+n(\varepsilon_{k+1})^{2}+n(\varepsilon_{k})^{2}$
$\displaystyle=\frac{1}{\gamma}[\lambda-\lambda_{[1:n]}^{k+1}]^{\top}[\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k}]+n(2\gamma+1)(\varepsilon_{k+1})^{2}$
$\displaystyle+\gamma[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[y^{k+1}_{[1:n]}-y^{k}_{[1:n]}]+\gamma
n\mathcal{M}\varepsilon_{k+1}$
$\displaystyle+\gamma\sqrt{n}\varepsilon_{k+1}\|y_{[1:n]}^{*}\|+n(\varepsilon_{k})^{2}.$
(35)

∎

Next, we establish an $O(1/k)$ rate of convergence for the proposed DC-
DistADMM algorithm under Assumption 5. Let the sequence of consensus
tolerances $\\{\varepsilon_{k}\\}_{k\geq 1}$ in Algorithm 2 satisfy the
following conditions:

$\displaystyle\varepsilon_{k+1}\leq\varepsilon_{k},\ \mbox{for all}\ k\geq 1,\
\mbox{and}\ \sum_{k=0}^{\infty}\varepsilon_{k}<\infty.$ (36)

######  Theorem 3.

Let $\\{x_{i}^{k}\\}_{k\geq 1}$, $\\{\lambda_{i}^{k}\\}_{k\geq 1}$,
$\\{y_{i}^{k}\\}_{k\geq 1}$ for all $i\in\mathcal{V}$, be the sequences
generated by Algorithm 2. Let $\\{\varepsilon_{k}\\}_{k\geq 1}$ be the
sequence of tolerances in Algorithm 2. Then, under Assumptions 1-5, the
following holds for all $k>0$,

$\displaystyle F(\widehat{x}^{k})-F(x_{[1:n]}^{*})$
$\displaystyle\leq\frac{\|\lambda_{[1:n]}^{0}\|^{2}}{\gamma
k}+\frac{\gamma(\|x_{[1:n]}^{*}\|^{2}+\|y^{0}_{[1:n]}\|^{2})}{k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}$
$\displaystyle+\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma(n\mathcal{M}+\sqrt{n}\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1},$

where, $(x_{[1:n]}^{*},y_{[1:n]}^{*})\in\mathcal{X}^{*}$ is any optimal
solution of (8),
$\widehat{x}^{k}:=\frac{1}{k}\sum_{s=0}^{k-1}x_{[1:n]}^{s+1}$,
$\widehat{y}^{k}:=\frac{1}{k}\sum_{s=0}^{k-1}y^{s+1}_{[1:n]}$, and
$\mathcal{M}$ is as defined in Lemma 2. Moreover, if the sequence of consensus
tolerances $\\{\varepsilon_{k}\\}_{k\geq 1}$ in Algorithm 2 satisfy condition
(36) then,

$\displaystyle\lim_{k\rightarrow\infty}F(\widehat{x}^{k})=F(x_{[1:n]}^{*}).$

###### Proof.

Using the identity (IV) for any $s\geq 0$ we get,

$\displaystyle\frac{1}{\gamma}[\lambda-\lambda_{[1:n]}^{s+1}]^{\top}[\lambda_{[1:n]}^{s+1}$
$\displaystyle-\lambda_{[1:n]}^{s}]=\frac{1}{2\gamma}(\|\lambda-\lambda_{[1:n]}^{s}\|^{2}$
$\displaystyle-\|\lambda$
$\displaystyle-\lambda_{[1:n]}^{s+1}\|^{2}-\|\lambda_{[1:n]}^{s+1}-\lambda_{[1:n]}^{s}\|^{2}).$
(37)

Similarly,

$\displaystyle\gamma(x_{[1:n]}^{*}-x_{[1:n]}^{s+1})^{\top}(y^{s+1}_{[1:n]}-y^{s}_{[1:n]})=\frac{\gamma}{2}(\|x_{[1:n]}^{s+1}-y^{s+1}_{[1:n]}\|^{2}$
$\displaystyle-\|x_{[1:n]}^{s+1}-y^{s}_{[1:n]}\|^{2}+\|x_{[1:n]}^{*}-y^{s}_{[1:n]}\|^{2}-\|x_{[1:n]}^{*}-y^{s+1}_{[1:n]}\|^{2}).$
(38)

From (35), (37) and (38) for any $\lambda$ and $s\geq 0$ we get,

$\displaystyle
F(x_{[1:n]}^{s+1})-F(x_{[1:n]}^{*})+G(y^{s+1}_{[1:n]})-G(y_{[1:n]}^{*})$
$\displaystyle+\lambda^{\top}(x_{[1:n]}^{s+1}-y^{s+1}_{[1:n]})$
$\displaystyle\leq\frac{1}{2\gamma}(\|\lambda-\lambda_{[1:n]}^{s}\|^{2}-\|\lambda-\lambda_{[1:n]}^{s+1}\|^{2}-\|\lambda_{[1:n]}^{s+1}-\lambda_{[1:n]}^{s}\|^{2})+$
$\displaystyle\frac{\gamma}{2}(\|x_{[1:n]}^{*}-y^{s}_{[1:n]}\|^{2}-\|x_{[1:n]}^{*}-y^{s+1}_{[1:n]}\|^{2}+\|x_{[1:n]}^{s+1}-y^{s+1}_{[1:n]}\|^{2}$
$\displaystyle\ \
-\|x_{[1:n]}^{s+1}-y^{s}_{[1:n]}\|^{2})+(2\gamma+1)n(\varepsilon_{s+1})^{2}+n(\varepsilon_{s})^{2}$
$\displaystyle\ \
+\gamma(n\mathcal{M}+\sqrt{n}\|y_{[1:n]}^{*}\|)\varepsilon_{s+1}$
$\displaystyle\leq\frac{1}{2\gamma}\big{(}\|\lambda-\lambda_{[1:n]}^{s}\|^{2}-\|\lambda-\lambda_{[1:n]}^{s+1}\|^{2}\big{)}+\frac{\gamma}{2}\big{(}\|x_{[1:n]}^{*}-y^{s}_{[1:n]}\|^{2}$
$\displaystyle\ \
-\|x_{[1:n]}^{*}-y^{s+1}_{[1:n]}\|^{2}\big{)}+(2\gamma+1)n(\varepsilon_{s+1})^{2}+n(\varepsilon_{s})^{2}$
$\displaystyle\ \
+\gamma(n\mathcal{M}+\sqrt{n}\|y_{[1:n]}^{*}\|)\varepsilon_{s+1},$

where, the last inequality follows from (18) and dropping the negative term.
Summing both sides from $s=0$ to $k-1$ and dividing by $\frac{1}{k}$ gives,

$\displaystyle\frac{1}{k}$
$\displaystyle\sum_{s=0}^{k-1}[F(x_{[1:n]}^{s+1})-F(x_{[1:n]}^{*})+G(y^{s+1}_{[1:n]})-G(y_{[1:n]}^{*})]$
$\displaystyle+\lambda^{\top}(\widehat{x}^{k}-\widehat{y}^{k})$
$\displaystyle\leq$ $\displaystyle\
\frac{\|\lambda-\lambda_{[1:n]}^{0}\|^{2}}{2\gamma
k}+\frac{\gamma\|x_{[1:n]}^{*}-y^{0}_{[1:n]}\|^{2}}{2k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}+$
$\displaystyle\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma(n\mathcal{M}+\sqrt{n}\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1},$

where, $\widehat{x}^{k}:=\frac{1}{k}\sum_{s=0}^{k-1}x_{[1:n]}^{s+1}$, and
$\widehat{y}^{k}:=\frac{1}{k}\sum_{s=0}^{k-1}y^{s+1}_{[1:n]}$. Note that,
$(\widehat{x}^{k},\widehat{y}^{k})\in\mathcal{X}$. Since, $F$ and $G$ are
convex we have, $\frac{1}{k}\sum_{s=0}^{k-1}F(x_{[1:n]}^{s+1})\geq
F(\widehat{x}^{k})$ and $\frac{1}{k}\sum_{s=0}^{k-1}G(y^{s+1}_{[1:n]})\geq
G(\widehat{y}^{k}).$ Therefore,

$\displaystyle F$
$\displaystyle(\widehat{x}^{k})-F(x_{[1:n]}^{*})+G(\widehat{y}^{k})-G(y_{[1:n]}^{*})+\lambda^{\top}(\widehat{x}^{k}-\widehat{y}^{k})$
$\displaystyle\leq$ $\displaystyle\
\frac{\|\lambda-\lambda_{[1:n]}^{0}\|^{2}}{2\gamma
k}+\frac{\gamma\|x_{[1:n]}^{*}-y^{0}_{[1:n]}\|^{2}}{2k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}+$
(39)
$\displaystyle\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma(n\mathcal{M}+\sqrt{n}\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1}.$

Taking
$\lambda=\delta\dfrac{\widehat{x}^{k}-\widehat{y}^{k}}{\|\widehat{x}^{k}-\widehat{y}^{k}\|}$,
$\delta\geq 0$, we get,

$\displaystyle F$ $\displaystyle(\widehat{x}^{k})-F(x_{[1:n]}^{*})$
$\displaystyle\leq$ $\displaystyle\
\frac{\delta^{2}+\|\lambda_{[1:n]}^{0}\|^{2}}{\gamma
k}+\frac{\gamma(\|x_{[1:n]}^{*}\|^{2}+\|y^{0}_{[1:n]}\|^{2})}{k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}+$
$\displaystyle\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma(n\mathcal{M}+\sqrt{n}\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1}.$

Since, $\delta$ is arbitrary we get,

$\displaystyle F(\widehat{x}^{k})-F(x_{[1:n]}^{*})$
$\displaystyle\leq\frac{\|\lambda_{[1:n]}^{0}\|^{2}}{\gamma
k}+\frac{\gamma(\|x_{[1:n]}^{*}\|^{2}+\|y^{0}_{[1:n]}\|^{2})}{k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}$
$\displaystyle+\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma(n\mathcal{M}+\sqrt{n}\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1}.$

If the sequence $\\{\varepsilon^{k}\\}_{k\geq 1}$ satisfy (36) as
$k\rightarrow\infty$ we get,

$\displaystyle\lim_{k\rightarrow\infty}F(\widehat{x}^{k})=F(x_{[1:n]}^{*}).$

∎

Theorem 3 establishes that the objective function evaluated at the ergodic
average of the optimization variables obtained by the proposed DC-DistADMM
algorithm converges to the optimal value. In particular, the objective
function value evaluated at the ergodic average converges to the optimal value
at a rate of $O(1/k)$. The next Theorem gives a bound on the norm of the
constraint residual, $\|\widehat{x}^{k}-\widehat{y}^{k}\|$ and establish that
the proposed DC-DistADMM converges to an optimal solution of (8) under
Assumption 5.

######  Theorem 4.

Let $\\{x_{i}^{k}\\}_{k\geq 1}$, $\\{\lambda_{i}^{k}\\}_{k\geq 1}$,
$\\{y_{i}^{k}\\}_{k\geq 1}$ for all $i\in\mathcal{V}$, be the sequences
generated by Algorithm 2. Let $\\{\varepsilon_{k}\\}_{k\geq 1}$ be the
sequence of tolerances in Algorithm 2. Under Assumptions 1-5, for any
$\delta>\|\lambda_{[1:n]}^{*}\|$, the following holds for all $k>0$:

$\displaystyle\|\widehat{x}^{k}-\widehat{y}^{k}\|\leq\frac{\delta^{2}+\|\lambda_{[1:n]}^{0}\|^{2}}{\gamma(\delta-\|\lambda_{[1:n]}^{*}\|)k}+\frac{\gamma(\|x_{[1:n]}^{*}\|^{2}+\|y^{0}_{[1:n]}\|^{2})}{(\delta-\|\lambda_{[1:n]}^{*}\|)k}$
$\displaystyle+\frac{n}{(\delta-\|\lambda_{[1:n]}^{*}\|)k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}+\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}$
$\displaystyle+\frac{\gamma\sqrt{n}(\mathcal{M}+\|y_{[1:n]}^{*}\|)}{(\delta-\|\lambda_{[1:n]}^{*}\|)k}\sum_{s=0}^{k-1}\varepsilon_{s+1},$

where, $(x_{[1:n]}^{*},y_{[1:n]}^{*})\in\mathcal{X}^{*}$ is any optimal
solution of (8), $\widehat{x}^{k}$ and $\widehat{y}^{k}$ are as defined in
Theorem 3. Further, if the sequence of consensus tolerances
$\\{\varepsilon_{k}\\}_{k\geq 1}$ in Algorithm 2 satisfy condition (36) then,

$\displaystyle\lim_{k\rightarrow\infty}\|\widehat{x}^{k}-\widehat{y}^{k}\|=0.$

###### Proof.

From (39) we have,

$\displaystyle F$
$\displaystyle(\widehat{x}^{k})-F(x_{[1:n]}^{*})+G(\widehat{y}^{k})-G(y_{[1:n]}^{*})+\lambda^{\top}(\widehat{x}^{k}-\widehat{y}^{k})$
$\displaystyle\leq$ $\displaystyle\
\frac{\|\lambda-\lambda_{[1:n]}^{0}\|^{2}}{2\gamma
k}+\frac{\gamma\|x_{[1:n]}^{*}-y^{0}_{[1:n]}\|^{2}}{2k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}$
$\displaystyle+\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma\sqrt{n}(\mathcal{M}+\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1}.$

Taking
$\lambda=\delta\dfrac{\widehat{x}^{k}-\widehat{y}^{k}}{\|\widehat{x}^{k}-\widehat{y}^{k}\|}$,
we get,

$\displaystyle F$
$\displaystyle(\widehat{x}^{k})-F(x_{[1:n]}^{*})+\delta\|\widehat{x}^{k}-\widehat{y}^{k}\|$
$\displaystyle\leq$ $\displaystyle\
\frac{\delta^{2}+\|\lambda_{[1:n]}^{0}\|^{2}}{\gamma
k}+\frac{\gamma(\|x_{[1:n]}^{*}\|^{2}+\|y^{0}_{[1:n]}\|^{2})}{k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}$
$\displaystyle+\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma\sqrt{n}(\mathcal{M}+\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1}.$

Define function $\omega(z):=\min\\{F(x)+G(y)\ |\
x\in\mathcal{X},y\in\mathcal{C},x-y=z\\}$. It can be verified that
$\omega(0)=F(x_{[1:n]}^{*})$, $\omega$ is convex, and
$-\lambda_{[1:n]}^{*}\in\partial\omega(0)$ (see [46], Chapter 8). From
convexity of $\omega$ it follows,

$\displaystyle\omega(z)\geq\omega(0)-\lambda_{[1:n]}^{*\top}z\geq
F(x_{[1:n]}^{*})-\|\lambda_{[1:n]}^{*}\|\|z\|.$ (40)

Let $z=\widehat{x}^{k}-\widehat{y}^{k}$. We have,

$\displaystyle F(\widehat{x}^{k})\geq
F(x_{[1:n]}^{*})-\|\lambda_{[1:n]}^{*}\|\|\widehat{x}^{k}-\widehat{y}^{k}\|$

Let $\delta>\|\lambda_{[1:n]}^{*}\|$. It follows that,

$\displaystyle(\delta-\|\lambda_{[1:n]}^{*}\|)\|\widehat{x}^{k}-\widehat{y}^{k}\|\leq
F(\widehat{x}^{k})-F(x_{[1:n]}^{*})+\delta\|\widehat{x}^{k}-\widehat{y}^{k}\|$
$\displaystyle\leq\frac{\delta^{2}+\|\lambda_{[1:n]}^{0}\|^{2}}{\gamma
k}+\frac{\gamma(\|x_{[1:n]}^{*}\|^{2}+\|y^{0}_{[1:n]}\|^{2})}{k}+\frac{n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}$
$\displaystyle+\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}+\frac{\gamma\sqrt{n}(\mathcal{M}+\|y_{[1:n]}^{*}\|)}{k}\sum_{s=0}^{k-1}\varepsilon_{s+1}.$

Therefore,

$\displaystyle\|\widehat{x}^{k}-\widehat{y}^{k}\|\leq\frac{\delta^{2}+\|\lambda_{[1:n]}^{0}\|^{2}}{\gamma(\delta-\|\lambda_{[1:n]}^{*}\|)k}+\frac{\gamma(\|x_{[1:n]}^{*}\|^{2}+\|y^{0}_{[1:n]}\|^{2})}{(\delta-\|\lambda_{[1:n]}^{*}\|)k}$
$\displaystyle+\frac{n}{(\delta-\|\lambda_{[1:n]}^{*}\|)k}\sum_{s=0}^{k-1}(\varepsilon_{s})^{2}+\frac{(2\gamma+1)n}{k}\sum_{s=0}^{k-1}(\varepsilon_{s+1})^{2}$
$\displaystyle+\frac{\gamma\sqrt{n}(\mathcal{M}+\|y_{[1:n]}^{*}\|)}{(\delta-\|\lambda_{[1:n]}^{*}\|)k}\sum_{s=0}^{k-1}\varepsilon_{s+1}.$
(41)

Let the sequence $\\{\varepsilon_{k}\\}_{k\geq 1}$ satisfy (36). Taking
$\lim_{k\rightarrow\infty}$ both sides gives,

$\displaystyle\lim_{k\rightarrow\infty}\|\widehat{x}^{k}-\widehat{y}^{k}\|=0.$

∎

######  Remark 4.1.

Let, $\hat{x}_{i}^{k}$ and $\hat{y}_{i}^{k}$ denote the ergodic averages of
the variables $x_{i}^{k}$ and $y_{i}^{k}$. Since,
$\|\widehat{x}^{k}-\widehat{y}^{k}\|=O(1/k)$ it implies that for all
$i\in\mathcal{V},\|\hat{x}_{i}^{k}-\hat{y}_{i}^{k}\|=O(1/k)$. Further, for all
$i,j\in\mathcal{V},\|\hat{y}_{i}^{k}-\hat{y}_{j}^{k}\|=O(1/k)$. Therefore, for
all $i,j\in\mathcal{V}$,

$\displaystyle\|\hat{x}_{i}^{k}-\hat{x}_{j}^{k}\|=O(1/k)\ \mbox{and}\
\lim_{k\rightarrow\infty}\|\hat{x}_{i}^{k}-\hat{x}_{j}^{k}\|=0.$

Thus, in practice, the DC-DistADMM algorithm can be implemented with an
additional variable $\hat{x}_{i}^{k}$ tracking the ergodic average of
$x_{i}^{k}$ at each agent $i\in\mathcal{V}$ to achieve a consensual solution
at the $O(1/k)$ rate of convergence given in Theorem 4 in a fully distributed
manner. Note, that the variable $\hat{x}_{i}^{k}$ is computed locally by each
agent without any additional cost of communication and a minor addition in
cost of computation.

###  IV-B Linear Rate of Convergence

In this subsection, we will prove a linear rate of convergence for the
proposed DC-DistADMM algorithm under the following assumptions:

######  Assumption 6.

Each function $\tilde{f}_{i}$ is Lipschitz differentiable with constant
$L_{f_{i}}>0$.

######  Assumption 7.

$\tilde{F}=\sum_{i=1}^{n}\tilde{f}_{i}$ is a strongly convex function with
parameter $\sigma>0$.

Note, that Assumption 7 does not require all the $\tilde{f}_{i}$’s to be
necessarily strongly convex. Assumptions 6 and 7 lead to a standard inequality
(see [45], section 2.1) for the function $F$ as detailed in the next lemma.

######  Lemma 4.

Under Assumptions 6 and 7, for any $x,y\in\operatorname*{relint}(\mathcal{X})$
we have,

$\displaystyle(\nabla F(x)-\nabla F(y))^{\top}(x-y)$
$\displaystyle\geq\mu_{1}\|x-y\|^{2}$ $\displaystyle\ \ \ +\mu_{2}\|\nabla
F(x)-\nabla F(y)\|^{2},$

where, $\nabla F(x)=[\nabla\tilde{f}^{\top}_{1}(x_{1})\
\nabla\tilde{f}^{\top}_{2}(x_{2})\dots\nabla\tilde{f}^{\top}_{n}(x_{n})]^{\top}$,
for $x=[x_{1}^{\top}\dots
x_{n}^{\top}]^{\top}\in\operatorname*{relint}(\mathcal{X}),x_{i}\in\mathbb{R}^{p}$
for all $i\in\mathcal{V}$ and $\mu_{1}=\frac{\sigma L}{\sigma+L}$,
$\mu_{2}=\frac{1}{\sigma+L}$ and $L:=\max\limits_{1\leq i\leq n}L_{f_{i}}$.

###### Proof.

See Appendix VII-C for proof. ∎

The next Theorem establishes a linear rate of convergence for the propose DC-
DistADMM algorithm to the optimal solution of (8). Here, we assume that the
sequence of consensus tolerances $\\{\varepsilon_{k}\\}_{k\geq 1}$ in
Algorithm 2 satisfy the following conditions:

$\displaystyle\varepsilon_{k+1}\leq\varepsilon_{k},\ \mbox{for all}\ k\geq 1\
\mbox{and}\lim_{k\rightarrow\infty}\varepsilon_{k}=0.$ (42)

######  Theorem 5.

Let $\\{x_{i}^{k}\\}_{k\geq 1}$, $\\{\lambda_{i}^{k}\\}_{k\geq 1}$,
$\\{y_{i}^{k}\\}_{k\geq 1}$ for all $i\in\mathcal{V}$, be the sequences
generated by Algorithm 2. Let the sequence of consensus tolerances
$\\{\varepsilon_{k}\\}_{k\geq 1}$ in Algorithm 2 satisfy condition (42). Let
$x_{i}^{k+1}\in\operatorname*{relint}(\mathcal{X}_{i})$ for all $k\geq 0$ and
$i\in\mathcal{V}$. Under Assumptions 1-4, 6 and 7 the following inequality
holds for all $k\geq 0$,

$\displaystyle u_{k}+Q\varepsilon_{k-1}\geq(1+\delta)u_{k+1},$

where,
$u_{k}:=\frac{\gamma}{2}\|x_{[1:n]}^{k}-x_{[1:n]}^{*}\|^{2}+\frac{1}{2\gamma}\|\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{*}\|^{2},Q:=4\gamma\sqrt{n}(\sqrt{n}\mathcal{M}+\|x^{*}_{[1:n]}\|)+\gamma\sqrt{n}(\sqrt{n}\mathcal{M}+2\sqrt{n}\varepsilon_{1}+\|y_{[1:n]}^{*}\|)+2\mu_{2}\gamma^{2}\sqrt{n}(2\sqrt{n}\mathcal{M}+4\sqrt{n}\varepsilon_{1})$
and
$\delta:=\frac{\min\left\\{\mu_{1},\mu_{2}\right\\}}{\max\left\\{\frac{1}{\gamma},\frac{\gamma}{2}\right\\}}$.
Additionally,

$\displaystyle\lim_{k\rightarrow\infty}u_{k}=0.$

###### Proof.

From (28), (32) and Lemma 4 we get,

$\displaystyle\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}+\mu_{2}\|\nabla
F(x_{[1:n]}^{k+1})-\nabla F(x_{[1:n]}^{*})\|^{2}$
$\displaystyle\leq[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[\nabla
F(x_{[1:n]}^{k+1})-\nabla F(x_{[1:n]}^{*})]$
$\displaystyle=[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[-\lambda_{[1:n]}^{k+1}-\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})+\lambda_{[1:n]}^{*}]$
$\displaystyle=[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}]$
$\displaystyle\hskip 86.72377pt-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[\gamma
y^{k+1}_{[1:n]}-\gamma y^{k}_{[1:n]}]$
$\displaystyle=[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}]$
$\displaystyle\hskip
7.22743pt+\gamma[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[x_{[1:n]}^{k+1}-x_{[1:n]}^{k}]$
$\displaystyle\hskip
7.22743pt-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}]$

From (30) and (34),

$\displaystyle\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}+\mu_{2}\|\nabla
F(x_{[1:n]}^{k+1})-\nabla F(x_{[1:n]}^{*})\|^{2}$
$\displaystyle=[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}]$
$\displaystyle\hskip
7.22743pt+\gamma[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[x_{[1:n]}^{k+1}-x_{[1:n]}^{k}]$
$\displaystyle\hskip
7.22743pt-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}]$
$\displaystyle\hskip
7.22743pt+[y_{[1:n]}^{k+1}-y^{*}_{[1:n]}]^{\top}[\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{*}-\gamma
e^{k+1}]$
$\displaystyle=[\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}]^{\top}[x_{[1:n]}^{k+1}-y_{[1:n]}^{k+1}]+\gamma[y_{[1:n]}^{k+1}-y^{*}_{[1:n]}]^{\top}e^{k+1}$
$\displaystyle\hskip
7.22743pt+\gamma[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[x_{[1:n]}^{k+1}-x_{[1:n]}^{k}]$
$\displaystyle\hskip
7.22743pt-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}]$
$\displaystyle=\frac{1}{\gamma}[\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{*}]^{\top}[\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}]+\gamma[y_{[1:n]}^{k+1}-y^{*}_{[1:n]}]^{\top}e^{k+1}$
$\displaystyle\hskip
7.22743pt+\gamma[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[x_{[1:n]}^{k+1}-x_{[1:n]}^{k}]$
$\displaystyle\hskip
7.22743pt-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}]$

Using (IV) for
$[\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{*}]^{\top}[\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}]$
and $[x_{[1:n]}^{*}-x_{[1:n]}^{k+1}]^{\top}[x_{[1:n]}^{k+1}-x_{[1:n]}^{k}]$
yields,

$\displaystyle\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}+\mu_{2}\|\nabla
F(x_{[1:n]}^{k+1})-\nabla F(x_{[1:n]}^{*})\|^{2}$
$\displaystyle\leq\left[\frac{\gamma}{2}\|x_{[1:n]}^{*}-x^{k}_{[1:n]}\|^{2}+\frac{1}{2\gamma}\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k}\|^{2}\right]$
$\displaystyle\hskip
7.22743pt-\left[\frac{\gamma}{2}\|x_{[1:n]}^{*}-x^{k+1}_{[1:n]}\|^{2}+\frac{1}{2\gamma}\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}\|^{2}\right]$
$\displaystyle\hskip
7.22743pt-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}]$
$\displaystyle\hskip
7.22743pt+\gamma[y_{[1:n]}^{k+1}-y^{*}_{[1:n]}]^{\top}e^{k+1}.$

Consider, the term on the left hand side of the above inequality,

$\displaystyle\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}+\mu_{2}\|\nabla
F(x_{[1:n]}^{k+1})-\nabla F(x_{[1:n]}^{*})\|^{2}$
$\displaystyle=\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}$
$\displaystyle\hskip
7.22743pt+\mu_{2}\|-\lambda_{[1:n]}^{k+1}-\gamma(y^{k+1}_{[1:n]}-y^{k}_{[1:n]})+\lambda_{[1:n]}^{*}\|^{2}$
$\displaystyle\geq\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}+\mu_{2}\|\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{*}\|^{2}$
$\displaystyle\hskip
7.22743pt+\mu_{2}\gamma^{2}\|y^{k+1}_{[1:n]}-y^{k}_{[1:n]}\|^{2}$
$\displaystyle\hskip
7.22743pt-2\mu_{2}\gamma\|\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}\|\|y^{k+1}_{[1:n]}-y^{k}_{[1:n]}\|$

Therefore,

$\displaystyle\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}+\mu_{2}\|\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{*}\|^{2}$
$\displaystyle\hskip
7.22743pt+\mu_{2}\gamma^{2}\|y^{k+1}_{[1:n]}-y^{k}_{[1:n]}\|^{2}$
$\displaystyle\leq\left[\frac{\gamma}{2}\|x_{[1:n]}^{*}-x^{k}_{[1:n]}\|^{2}+\frac{1}{2\gamma}\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k}\|^{2}\right]$
$\displaystyle\hskip
7.22743pt-\left[\frac{\gamma}{2}\|x_{[1:n]}^{*}-x^{k+1}_{[1:n]}\|^{2}+\frac{1}{2\gamma}\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}\|^{2}\right]$
$\displaystyle\hskip
7.22743pt-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}]$
$\displaystyle\hskip
7.22743pt+\gamma[y_{[1:n]}^{k+1}-y^{*}_{[1:n]}]^{\top}e^{k+1}$
$\displaystyle\hskip
7.22743pt+2\mu_{2}\gamma\|\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}\|\|y^{k+1}_{[1:n]}-y^{k}_{[1:n]}\|$
$\displaystyle\leq
u_{k}-u_{k+1}-[x_{[1:n]}^{k+1}-x_{[1:n]}^{*}]^{\top}[2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}]$
$\displaystyle\hskip
7.22743pt+\gamma[y_{[1:n]}^{k+1}-y^{*}_{[1:n]}]^{\top}e^{k+1}$
$\displaystyle\hskip
7.22743pt+2\mu_{2}\gamma\|\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}\|\|y^{k+1}_{[1:n]}-y^{k}_{[1:n]}\|$
$\displaystyle\leq
u_{k}-u_{k+1}+\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|\|2\lambda_{[1:n]}^{k}-\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{k-1}\|$
$\displaystyle\hskip
7.22743pt+\gamma\|y_{[1:n]}^{k+1}-y^{*}_{[1:n]}\|\|e^{k+1}\|$
$\displaystyle\hskip
7.22743pt+2\mu_{2}\gamma\|\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}\|\|y^{k+1}_{[1:n]}-y^{k}_{[1:n]}\|$
$\displaystyle\mbox{From Lemma~{}\ref{lem:ylambdabound}
and~{}(\ref{eq:ysolnoptcond})},$ $\displaystyle\leq
u_{k}-u_{k+1}+4\gamma\sqrt{n}(\sqrt{n}\mathcal{M}+\|x^{*}_{[1:n]}\|)\varepsilon_{k-1}$
$\displaystyle\hskip
7.22743pt+\gamma\sqrt{n}(\sqrt{n}\mathcal{M}+2\sqrt{n}\varepsilon_{1}+\|y_{[1:n]}^{*}\|)\varepsilon_{k-1}$
$\displaystyle\hskip
7.22743pt+2\mu_{2}\gamma^{2}\sqrt{n}(2\sqrt{n}\mathcal{M}+4\sqrt{n}\varepsilon_{1})\varepsilon_{k-1}$
$\displaystyle=u_{k}-u_{k-1}+Q\varepsilon_{k-1},$

where,
$Q:=4\gamma\sqrt{n}(\sqrt{n}\mathcal{M}+\|x^{*}_{[1:n]}\|)+\gamma\sqrt{n}(\sqrt{n}\mathcal{M}+2\sqrt{n}\varepsilon_{1}+\|y_{[1:n]}^{*}\|)+2\mu_{2}\gamma^{2}\sqrt{n}(2\sqrt{n}\mathcal{M}+4\sqrt{n}\varepsilon_{1})$.

Now consider $u_{k+1}$,

$\displaystyle u_{k+1}$
$\displaystyle=\frac{\gamma}{2}\|x^{k+1}_{[1:n]}-x_{[1:n]}^{*}\|^{2}+\frac{1}{2\gamma}\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}\|^{2}$
$\displaystyle\leq$ $\displaystyle\
\max\left\\{\frac{1}{\gamma},\frac{\gamma}{2}\right\\}\left[\|x^{k+1}_{[1:n]}-x_{[1:n]}^{*}\|^{2}+\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}\|^{2}\right].$
(43)

Also,

$\displaystyle\mu_{1}\|x_{[1:n]}^{k+1}-x^{*}_{[1:n]}\|^{2}+\mu_{2}\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}\|^{2}$
$\displaystyle\geq\min\left\\{\mu_{1},\mu_{2}\right\\}\left[\|x_{[1:n]}^{k+1}-x^{*}_{[1:n]}\|^{2}+\|\lambda_{[1:n]}^{*}-\lambda_{[1:n]}^{k+1}\|^{2}\right].$
(44)

Let
$\delta=\frac{\min\left\\{\mu_{1},\mu_{2}\right\\}}{\max\left\\{\frac{1}{\gamma},\frac{\gamma}{2}\right\\}}$.
Therefore, from (43) and (44),

$\displaystyle\delta u_{k+1}$
$\displaystyle\leq\mu_{1}\|x_{[1:n]}^{k+1}-x_{[1:n]}^{*}\|^{2}+\mu_{2}\|\lambda_{[1:n]}^{k+1}-\lambda_{[1:n]}^{*}\|^{2}.$

Thus,

$\displaystyle u_{k}+Q\varepsilon_{k-1}\geq(1+\delta)u_{k+1}.$

By repeated substitution for $k=0,1,\dots,k$ we get,

$\displaystyle
u_{k}\leq\left(\frac{1}{1+\delta}\right)^{k}u_{0}+Q\sum_{s=2}^{k+1}\left(\frac{1}{1+\delta}\right)^{s-1}\varepsilon_{k-s}.$

Re-writing the above inequality by doing a variable change, and following the
convention $\varepsilon_{-1}=\varepsilon_{0}=0$, we get

$\displaystyle
u_{k}\leq\left(\frac{1}{1+\delta}\right)^{k}u_{0}+Q\sum_{t=1}^{k-2}\left(\frac{1}{1+\delta}\right)^{k-t-1}\varepsilon_{t}.$

Define $\beta:=\frac{1}{1+\delta}$. Recall
$\lim_{k\rightarrow\infty}\varepsilon_{k}=0$. Given $\alpha>0$, let
$N=\dfrac{\log(\frac{\alpha(1-\beta)}{2\varepsilon_{1}})}{\log\beta}$ and $T$
be such that
$\varepsilon_{T}\left(\frac{\beta}{1-\beta}\right)<\frac{\alpha}{2}$. Let
$k_{0}\geq N+T$. Then, for all $k\geq k_{0}$,

$\displaystyle\sum_{t=1}^{k-2}\beta^{k-t-1}\varepsilon_{t}$
$\displaystyle=\sum_{t=1}^{T-1}\beta^{k-t-1}\varepsilon_{t}+\sum_{t=T}^{k-2}\beta^{k-t-1}\varepsilon_{t}$
$\displaystyle\leq\varepsilon_{1}\sum_{t=1}^{T-1}\beta^{k-t-1}+\varepsilon_{T}\left(\frac{\beta}{1-\beta}\right)$
$\displaystyle<\varepsilon_{1}\beta^{k-T}\sum_{t=1}^{T-1}\beta^{T-t-1}+\frac{\alpha}{2}$
$\displaystyle\leq\varepsilon_{1}\frac{\beta^{k-T}}{1-\beta}+\frac{\alpha}{2}\leq\varepsilon_{1}\frac{\beta^{k_{0}-T}}{1-\beta}+\frac{\alpha}{2}$
$\displaystyle\leq\varepsilon_{1}\frac{\beta^{N}}{1-\beta}+\frac{\alpha}{2}=\frac{\alpha}{2}+\frac{\alpha}{2}=\alpha.$

In conclusion, given $\alpha>0$, there exists $k_{0}$ such that for all $k\geq
k_{0}$,
$\sum_{t=1}^{k-2}\beta^{k-t-1}\varepsilon_{t}<\alpha\implies\lim_{k\rightarrow\infty}\sum_{t=1}^{k-2}\beta^{k-t-1}\varepsilon_{t}=0$.
Therefore,

$\displaystyle\lim_{k\rightarrow\infty}u_{k}=0.$

∎

##  V Numerical Simulations

In this section, we present two simulation studies for the proposed DC-
DistADMM algorithm. First, we solve a constrained $\ell_{1}$ regularized
distributed logistic regression problem using the proposed DC-DistADMM
algorithm and present the results. Second, we present a performance comparison
of the DC-DistADMM algorithm with the existing state-of-the art algorithms in
the literature in solving a distributed least squares problem. We present the
per-iteration residual plots for all the algorithms. Further, we provide a
comparison based on the CPU time (the amount of time required by a computer
(processor) to execute the instructions) between DC-DistADMM and the other
algorithms. We also, report the empirical distribution of the number of
communication steps required by each agent for getting a solution based on a
given (chosen same for all the agents) tolerance.

Figure 1: Plots of the constraint residual of (45) using DC-DistADMM algorithm
with for different choices of $\varepsilon_{k}$.

Graphs $\mathcal{G}(\mathcal{V},\mathcal{E})$ and Weight matrix $\mathcal{P}$:
We consider a network of $100$ agents generated using the Erdos-Renyi model
[57] with a connectivity probability of $0.2$. The weight matrix $\mathcal{P}$
is chosen using the equal neighbor model [53].

Simulation Platform: All the numerical examples in this section are
implemented in MATLAB, and run on a desktop computer with 16 GB RAM and an
Intel Core i7 processor running at 1.90 GHz.

###  V-A Constrained $\ell_{1}$ regularized distributed logistic regression

The objective function of the constrained distributed $\ell_{1}$ regularized
logistic regression problem considered here has the following form:

$\displaystyle\operatorname*{minimize}_{x}\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}\log\big{(}$
$\displaystyle
1+\text{exp}\big{(}-y_{ij}(a^{\top}_{ij}x)\big{)}\big{)}+\mu\|x\|_{1}$ (45)
subject to $\displaystyle x^{\top}x\leq r_{i},\mbox{ for all}\
i\in\mathcal{V},$

where, each agent $i\in\mathcal{V}$ has $n_{i}$ data samples
$\\{(a_{ij},y_{ij})\\}_{j=1}^{n_{i}}$, with, $a_{ij}\in\mathbb{R}^{p}$ being
the feature vector and $y_{ij}\in\\{-1,+1\\}$ is the binary outcomes (or class
labels) of the feature vector $a_{ij}$. The objective is to learn the weight
vector $x\in\mathbb{R}^{p}$ based on the available data
$\\{(a_{ij},y_{ij})\\}_{j=1}^{n_{i}},i\in\mathcal{V}$ such that $x$ is sparse.
The parameter $\mu$ enforces the sparsity in $x$.

Figure 2: Difference between $f_{i}(\hat{x}_{i}^{k})$ with DC-DistADMM
algorithm and $f^{*}$ of (45) against the number of iterations for different
choices of $\varepsilon_{k}$. Figure 3: Residual plots of solution to (45)
using DC-DistADMM algorithm for different choices of $\varepsilon_{k}$.

Further, each agent has a private constraint $x^{\top}x\leq
r_{i},i\in\mathcal{V}$. For our simulation we generate an instance of problem
(45) where each agent has $n_{i}=10^{4}$ data samples. Each feature vector
$a_{ij}\in\mathbb{R}^{15}$ and the ‘true’ weight vector
$x_{\text{true}}\in\mathbb{R}^{15}$ are generated to have approximately $40\%$
zero entries. The non-zero entries of $a_{ij}$ and $x_{\text{true}}$ are
sampled independently from a standard normal distribution. The class labels
$y_{ij}$ are generated using the equation:
$y_{ij}=\text{sign}(a_{ij}^{\top}x_{\text{true}}+\delta_{ij})$, where
$\delta_{ij}$ is a normal random variable with zero mean and variance $0.1$.
The parameter $\mu$ is set to $0.1\mu_{\text{max}}$, where $\mu_{\text{max}}$
is the critical value above which the solution $x^{*}=0$ (see [30] section
11.2 for the calculation of $\mu_{\text{max}}$). The value of $r_{i}$ in
constraints is chosen as follows: we solve the unconstrained version of (45)
with a centralized solver and denote the solution as $x_{\text{c}}^{*}$. The
constraint $r_{i}$ is set as $r_{i}=(1+\xi_{i})x_{\text{c}}^{*}$, where
$\xi_{i}$ is drawn from a uniform distribution on $[0,1]$. The optimal
solution (45) is denoted as $x^{*}$. We use the value of $\gamma=1$ for the
Augmented Lagrangian. To implement the DC-DistADMM algorithm to solve (45), we
used the fast iterative shrinkage thresholding algorithm (FISTA) [58] for the
updates (16) at each agent $i$. For the updates (17) we utilize the
$\varepsilon$-consensus protocol in Algorithm 1. We present the results of
implementation for three choices of the sequence $\\{\varepsilon_{k}\\}_{k\geq
1}$: (i) $\varepsilon_{k}=0.01$, (ii) $\varepsilon_{k}=0.01/k$ and (iii)
$\varepsilon_{k}=0.01/k^{2}$. Fig. 1 shows the plot of the per-iteration
consensus constraint residual $\|\widehat{x}^{k}-\widehat{y}^{k}\|$ for all
the three choices of the $\varepsilon_{k}$ sequence. It can be seen that the
residual decreases to a value of $10^{-6}$ within $70$ iterations for the
choice $\varepsilon_{k}=0.01/k^{2}$. Note, that the residual has a significant
decrease (to a value of $10^{-4}$, within $70$ iterations) even when a
constant $\varepsilon_{k}$ value of $0.01$ is chosen. Fig. 2 presents the
difference between the objective value at the ergodic average of the local
$x_{i}^{k}$ variables (see remark 4.1) and the optimal objective value $f^{*}$
versus the number of iterations. The plots suggest that maintaining the
variable $x_{i}^{k}$ helps achieve the rate estimates in Theorem 4. Fig. 3
gives the progress of the per-iteration solution residual
$\frac{\|x_{i}^{k}-x^{*}\|}{\|x_{i}^{0}-x^{*}\|}$ by iteration.

Figure 4: Comparison of residuals
$\frac{\|x_{i}^{k}-x^{*}\|}{\|x_{i}^{0}-x^{*}\|}$ by iteration between DC-
DistADMM with $\varepsilon_{k}=0.01$ and other algorithms.

###  V-B Distributed least squares

We focus on the following distributed least squares problem:

$\displaystyle\operatorname*{minimize}\limits_{x}\ \
\frac{1}{2}\sum_{i=1}^{n}\|A_{i}x-b_{i}\|^{2}.$

Here, each agent $i\in\mathcal{V}$ has a measured data vector
$b_{i}\in\mathbb{R}^{10^{2}}$ and a scaling matrix
$A_{i}\in\mathbb{R}^{100\times 15}$. The objective is to estimate the unknown
signal $x\in\mathbb{R}^{15}$. The entries of the matrices
$A_{i},i\in\mathcal{V}$ and the observed data $b_{i}$ are sampled
independently from a standard normal distribution $\mathcal{N}(0,1)$. The
unknown signal (or the true state) $x$ also have entries that are sampled from
an i.i.d standard normal distribution. We denote the optimal solution by
$x^{*}$.

Algorithms chosen for comparison: We compare the performance of the proposed
DC-DistADMM algorithm with the following algorithms: (i) DGD algorithm of
[10], (ii) EXTRA algorithm of [16], (iii) Push-Pull algorithm of [19], (iv)
ADMM based algorithm of [35] (which we call decentralized consensus
optimization ADMM, abbreviated as DCOADMM), and the Multi-AgentADMM algorithm
of [38]. All the algorithms are used with a constant step-size.

Figure 5: Comparison of residuals
$\frac{\|x_{i}^{k}-x^{*}\|}{\|x_{i}^{0}-x^{*}\|}$ by iteration between DC-
DistADMM with $\varepsilon_{k}=0.01/k$ and other algorithms. Figure 6:
Comparison of residuals $\frac{\|x_{i}^{k}-x^{*}\|}{\|x_{i}^{0}-x^{*}\|}$ by
iteration between DC-DistADMM with $\varepsilon_{k}=0.01/k^{2}$ and other
algorithms.

Convergence from each agent’s perspective: Fig. 4, 5 and 6 show the
trajectories of the residual $\frac{\|x_{i}^{k}-x^{*}\|}{\|x_{i}^{0}-x^{*}\|}$
against the iteration counter $k$ for
$\varepsilon_{k}=0.01,\varepsilon_{k}=0.01/k$, and
$\varepsilon_{k}=0.01/k^{2}$ respectively. For each of the plots it can be
seen that the proposed DC-DistADMM algorithm has a superior performance
compared to other algorithms. In particular, the solution residual in case of
DC-DistADMM decreases significantly faster than the all the other algorithms.
In case of $\varepsilon_{k}=0.01$, the DC-DistADMM residual decreases to a
value of $10^{-6}$ in almost $20$ iterations whereas the second best method
Push-Pull takes around $120$ iterations to reach the same residual solution
tolerance. For $\varepsilon_{k}=0.01/k$ the number of iterations taken by the
DC-DistADMM algorithm to reach a residual of $10^{-8}$ is around $30$
iterations, while Push-Pull algorithm takes around $180$ iterations. And for
the choice $\varepsilon_{k}=0.01/k^{2}$ DC-DistADMM is again the best
performing method reaching a residual value of $10^{-10}$ in around $50$
iterations while the next best method takes around five times $250$ number of
iterations for the same residual value.

Figure 7: Number of communication steps required by the proposed DC-DistADMM
algorithm to reach a residual value less than $10^{-6}$ for three different
choices of $\varepsilon_{k}$. Figure 8: Number of communication steps required
by the existing algorithms in the literature method to reach a residual value
less than $10^{-6}$.

Comparison by number of communication steps required: Here, we provide a
comparison between the proposed DC-DistADMM algorithm and other algorithms
based on the number of communication steps required to reach a residual value
of $10^{-6}$. We present the empirical distribution of the number of
communication steps over $1000$ randomly generated graphs containing $100$
nodes for all the methods. Fig. 7 and Fig. 8 show the empirical distribution
of the number of information exchanges required in case of DC-DistADMM for the
three choices of $\varepsilon_{k}$ and the other methods respectively. The DC-
DistADMM takes around $75$-$80$ communication rounds on an average when
$\varepsilon_{k}=0.01$. The average number of communication steps required for
the choice of $\varepsilon_{k}=0.01/k$ are around $100$. For the case when
$\varepsilon_{k}=0.01/k^{2}$ the number of communication exchanges needed are
on an average around $150$. The empirical distribution of the number of
communication steps suggests that the proposed DC-DistADMM algorithm has a
similar communication requirement as that of ADMM algorithm of [35] with the
constant $\varepsilon_{k}$. Further, the communication requirement in case of
$\varepsilon_{k}=0.01/k^{2}$ has a similar distribution to Push-Pull and
EXTRA. The communication requirement to reach the same residual solution is
much higher for the Multi-Agent ADMM scheme in [38] compared to all three
choices of $\varepsilon_{k}$ with the DC-DistADMM algorithm.

Comparison by CPU computation time required: Now, we present a performance
comparison between the proposed DC-DistADMM algorithm and other methods in
terms of the CPU time required to reach a solution with a residual value of
$10^{-6}$ over the same $1000$ graphs with $100$ nodes as above when executed
on a desktop computer with 16 GB RAM and an Intel Core i7 processor running at
1.90 GHz. The amount of time required by a computer (processor) to execute the
instructions of an algorithms is called the CPU time of that algorithm. Table
I provide average CPU time of the DC-DistADMM algorithm along for three
different choices along with other compared methods. Table I illustrates that
DC-DistADMM with all the three choices for $\varepsilon_{k}$ takes lesser CPU
time than other methods to reach a solution with the desired residual value.
This observation agrees with residual plots shown earlier. As the convergence
of the residual is the fastest in Figs. 4-6 the amount of CPU time required is
the least for DC-DistADMM algorithm.

TABLE I: Average CPU time (sec) ALGORITHM | CPU TIME [sec]
---|---
DC-DistADMM [$\varepsilon_{k}=0.01$] | 0.339
DC-DistADMM [$\varepsilon_{k}=0.01/k$] | 0.1781
DC-DistADMM [$\varepsilon_{k}=0.01/k^{2}$] | 0.2623
EXTRA | 0.3509
DGD | 1.0697
PushPull | 0.3786
DCOADMM | 2.18
MultiAgentADMM | 2.7281

##  VI Conclusion and Future Work

In this article, we present a novel Directed-Distributed Alternating Direction
Method of Multipliers (DC-DistADMM) algorithm to solve a constrained multi-
agent optimization problem, where the global objective function is the sum
$\tilde{f}(x)=\sum_{i=1}^{n}\tilde{f}_{i}(x)$ of $n$ convex functions, with
convex private constraints. The proposed algorithm is to the best of our
knowledge is the first ADMM based algorithm to solve distributed optimization
problems over directed graphs. The DC-DistADMM combines the techniques used in
dual optimization methods along with the ideas in the average consensus
literature. In the DC-DistADMM algorithm, each agent solves a local
constrained convex optimization problem and utilizes a finite-time
“approximate" algorithm to update its estimate of the optimal solution. We
establish that the proposed DC-DistADMM algorithm converges at a rate of
$O(1/k)$ when the individual functions are convex but not-necessarily
differentiable. We further proved a linear rate of convergence for the DC-
DistADMM algorithm when the global objective function is strongly convex and
smooth. The proposed DC-DistADMM algorithm eliminates the optimization step
involving the global variable in the standard ADMM setup and replaces it with
a less computation intensive $\varepsilon$-consensus protocol which makes it
more suitable for distributed multi-agent systems. To show the efficacy of the
DC-DistADMM algorithm we present results of numerical simulations of solving a
constrained $\ell_{1}$ regularized distributed logistic regression problem. We
further demonstrate the superior performance of the DC-DistADMMM algorithm
over the state-of-the-art methods in the literature in solving a distributed
least squares problem in terms of both CPU time and number of iterations
required to reach a residual many orders smaller while not imposing
significant communication requirements as the rest of the proposed methods.
Extension of the DC-DistADMM algorithmic framework to networks with time-
delays in communication [50] between the agents and time-varying connectivity
among the agents [59] is a future work of this article.

##  VII Appendix

###  VII-A Proof of Lemma 1

Define, $d_{i,j}$ to be length of the shortest path connecting node $i$ to
node $j$. To prove the claim we use an induction argument on $d_{i,j}$. Base
case: $d_{i,j}=1$, Given, $s\geq 0$ for all $i\in\mathcal{V}$,

$\displaystyle
R_{i}^{1}(s)=\max\limits_{j\in\mathcal{N}_{i}^{-}}\Big{\\{}\|w_{i}^{s+1}-w_{j}^{s}\|+R_{j}^{0}(s)\Big{\\}}.$

Therefore, for all $j\in\mathcal{N}_{i}^{-}$,
$w_{j}^{s}\in\mathcal{B}(w_{i}^{s+1},R_{i}^{1}(s))$. Assume the claim holds
for $d_{i,j}=k$, that is for all $j$ such that $d_{i,j}\leq k$,
$w_{j}^{s}\in\mathcal{B}(w_{i}^{s+k},R_{i}^{k}(s))$. For any node
$\ell\in\mathcal{N}_{i}^{-}$, on the path between node $i$ and $j$ with
$d_{i,j}\leq k+1$, we have $d_{\ell,j}\leq k$. By the induction hypothesis,
$w_{j}^{s}\in\mathcal{B}(w_{\ell}^{s+k},R_{\ell}^{k}(s))$. It implies,
$\|w_{\ell}^{{s}+k}-w_{j}^{s}\|\leq R_{\ell}^{k}(s)$. From (22) we have,

$\displaystyle
R_{i}^{k+1}(s)\geq\|w_{i}^{s+k+1}-w_{\ell}^{s+k}\|+R_{\ell}^{k}(s).$

Using, the triangle inequality,

$\displaystyle\|w_{i}^{s+k+1}-w_{j}^{s}\|$
$\displaystyle\leq\|w_{i}^{s+k+1}-w_{\ell}^{s+k}\|+\|w_{\ell}^{s+k}-w_{j}^{s}\|$
$\displaystyle\leq\|w_{i}^{s+k+1}-w_{\ell}^{s+k}\|+R_{\ell}^{k}(s)$
$\displaystyle\leq R_{i}^{k+1}(s).$

Therefore, for any $j$ on the path with $d_{i,j}\leq k+1$,
$w_{j}^{s}\in\mathcal{B}(w_{i}^{s+k+1},R_{i}^{k+1}(s))$. Therefore, induction
holds. When $k=\mathcal{D}$, we get the desired result.

###  VII-B Proof of Theorem 2

Define the element-wise maximum $\overline{\mathbf{w}}^{k}$ and minimum
$\underline{\mathbf{w}}^{k}$ state variable of the network over all the agents
as

$\displaystyle\overline{\mathbf{w}}^{k}$
$\displaystyle:=\Big{[}\underset{1\leq j\leq
n}{\max}\big{\\{}w_{1[j]}^{k}\big{\\}}\dots\ \underset{1\leq j\leq
n}{\max}\big{\\{}w_{n[j]}^{k}\big{\\}}\Big{]}^{\top},$
$\displaystyle\underline{\mathbf{w}}^{k}$
$\displaystyle:=\Big{[}\underset{1\leq j\leq
n}{\min}\big{\\{}w_{1[j]}^{k}\big{\\}}\dots\ \underset{1\leq j\leq
n}{\min}\big{\\{}w_{n[j]}^{k}\big{\\}}\Big{]}^{\top},$

where, $w_{i[j]}^{k}$ is the $j^{th}$ entry of $w_{i}^{k}$. It is proven in
[49], [48] that
$\lim_{m\rightarrow\infty}\overline{\mathbf{w}}^{m\mathcal{D}}=\lim_{m\rightarrow\infty}\underline{\mathbf{w}}^{m\mathcal{D}}=\widetilde{u}=\frac{1}{n}\sum_{i=1}^{n}u_{i}^{0}$.
It implies
$\lim_{m\rightarrow\infty}\|\overline{\mathbf{w}}^{m\mathcal{D}}-\underline{\mathbf{w}}^{m\mathcal{D}}\|=0$.
Proceeding in the same manner as in [48], Theorem 4.2, we get
$\widehat{R}_{i}^{m}\leq\mathcal{D}\|\overline{\mathbf{w}}^{m\mathcal{D}}-\underline{\mathbf{w}}^{m\mathcal{D}}\|$.
Taking $\lim_{m\rightarrow\infty}$ both sides we conclude for all
$i\in\mathcal{V}$, $\lim_{m\rightarrow\infty}\widehat{R}_{i}^{m}=0$. This
gives the first result. From Lemma 1,
$\max_{i,j\in\mathcal{V}}\|w^{m\mathcal{D}}_{i}-w_{j}^{m\mathcal{D}}\|\leq
2\widehat{R}_{i}^{m}$. Letting $m\rightarrow\infty$, gives the second claim.

###  VII-C Proof of Lemma 4

From the definition of $F$ and Assumption 6 it follows that $F$ is Lipschitz
differentiable with parameter $L:=\max\limits_{1\leq i\leq n}L_{f_{i}}$ for
all $x\in\operatorname*{relint}(\mathcal{X})$. For any $x=[x^{\top}_{1}\dots
x_{n}^{\top}]^{\top}\in\mathbb{R}^{np}$, define $\nabla
F(x):=[\nabla\tilde{f}^{\top}_{1}(x_{1})\dots\nabla\tilde{f}^{\top}_{n}(x_{n})]^{\top}$.
Note that for all $x\in\operatorname*{relint}(\mathcal{X}),F(x)=\tilde{F}(x)$
and $\nabla F(x)=\tilde{F}(x)$. Since, $F$ is a convex from (26) for all
$x,y\in\operatorname*{relint}(\mathcal{X})$,

$\displaystyle F(y)\geq F(x)+\nabla F^{\top}(x)(y-x).$ (46)

Furthermore, we can obtain a quadratic upper bound on $F$ at any
$y\in\operatorname*{relint}(\mathcal{X})$ as follows: for all
$x\in\operatorname*{relint}(\mathcal{X})$,

$\displaystyle F(y)\leq F(x)+\nabla F^{\top}(x)(y-x)+\frac{L}{{2}}\|y-x\|^{2}$
(47)

For any $z$, using (46) and (47),

$\displaystyle F(y)-F(x)=F(y)-F(z)+F(z)-F(x)$ $\displaystyle\hskip
32.52127pt\leq\nabla F^{\top}(y)(y-z)+\nabla
F^{\top}(x)(z-x)+\frac{L}{2}\|z-x\|^{2}$

Substituting, $z=x-\frac{1}{L}(\nabla F(x)-\nabla F(y))$ we have,

$\displaystyle F(y)-F(x)\leq\nabla F^{\top}(y)\big{(}y-x+\frac{1}{L}[\nabla
F(x)-\nabla F(y)]\big{)}$ $\displaystyle-\frac{1}{L}\nabla F^{\top}(x)(\nabla
F(x)-\nabla F(y))+\frac{1}{2L}\|\nabla F(x)-\nabla F(y)\|^{2}$
$\displaystyle=\ \nabla F^{\top}(y)(y-x)-\frac{1}{2L}\|\nabla F(x)-\nabla
F(y)\|^{2}$

Similarly, interchanging $x$ and $y$ we get,

$\displaystyle F(x)-F(y)\leq\nabla F^{\top}(x)(x-y)-\frac{1}{2L}\|\nabla
F(y)-\nabla F(x)\|^{2}$

Adding the last two inequalities we have,

$\displaystyle(\nabla F(y)-\nabla F(x))^{\top}(y-x)\geq\frac{1}{L}\|\nabla
F(y)-\nabla F(x)\|^{2}.$ (48)

Now, consider $H(x)=F(x)-\frac{\sigma}{2}\|x\|^{2}$. Notice that $H$ is a
convex function due to strong convexity of $F$. Further, since $F$ is
Lipschitz differentiable with parameter $L$ for all
$x\in\operatorname*{relint}(\mathcal{X})$, then $H$ is also Lipschitz
differentiable with parameter $L-\sigma$. Therefore, using (48) for $H$ we the
desired result.

## References

  * [1] J. B. Predd, S. B. Kulkarni, and H. V. Poor, “Distributed learning in wireless sensor networks,” _IEEE Signal Processing Magazine_ , vol. 23, no. 4, pp. 56–69, 2006.
  * [2] M. Rabbat and R. Nowak, “Distributed optimization in sensor networks,” in _Proceedings of the 3rd international symposium on Information processing in sensor networks_. ACM, 2004, pp. 20–27.
  * [3] A. Olshevsky, “Efficient information aggregation strategies for distributed control and signal processing,” _arXiv preprint arXiv:1009.6036_ , 2010.
  * [4] K. I. Tsianos, S. Lawlor, and M. G. Rabbat, “Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning,” in _2012 50th annual allerton conference on communication, control, and computing (allerton)_. IEEE, 2012, pp. 1543–1550.
  * [5] J. B. Predd, S. R. Kulkarni, and H. V. Poor, “A collaborative training algorithm for distributed learning,” _IEEE Transactions on Information Theory_ , vol. 55, no. 4, pp. 1856–1871, 2009.
  * [6] A. Nedic, “Distributed gradient methods for convex machine learning problems in networks: Distributed optimization,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 92–101, 2020.
  * [7] W. Ren, R. W. Beard, and E. M. Atkins, “Information consensus in multivehicle cooperative control,” _IEEE Control systems magazine_ , vol. 27, no. 2, pp. 71–82, 2007.
  * [8] J. N. Tsitsiklis, “Problems in decentralized decision making and computation.” Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, Tech. Rep., 1984.
  * [9] D. P. Bertsekas and J. N. Tsitsiklis, _Parallel and distributed computation: numerical methods_. Prentice hall Englewood Cliffs, NJ, 1989, vol. 23.
  * [10] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 1, p. 48, 2009.
  * [11] A. Nedic, “Asynchronous broadcast-based convex optimization over a network,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 6, pp. 1337–1351, 2010.
  * [12] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization: Convergence analysis and network scaling,” _IEEE Transactions on Automatic control_ , vol. 57, no. 3, pp. 592–606, 2011.
  * [13] J. Chen and A. H. Sayed, “Diffusion adaptation strategies for distributed optimization and learning over networks,” _IEEE Transactions on Signal Processing_ , vol. 60, no. 8, pp. 4289–4305, 2012.
  * [14] S. S. Ram, A. Nedić, and V. V. Veeravalli, “Distributed stochastic subgradient projection algorithms for convex optimization,” _Journal of optimization theory and applications_ , vol. 147, no. 3, pp. 516–545, 2010.
  * [15] R. Xin, S. Kar, and U. A. Khan, “Gradient tracking and variance reduction for decentralized optimization and machine learning,” _arXiv preprint arXiv:2002.05373_ , 2020.
  * [16] W. Shi, Q. Ling, G. Wu, and W. Yin, “Extra: An exact first-order algorithm for decentralized consensus optimization,” _SIAM Journal on Optimization_ , vol. 25, no. 2, pp. 944–966, 2015.
  * [17] A. Nedic, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” _SIAM Journal on Optimization_ , vol. 27, no. 4, pp. 2597–2633, 2017.
  * [18] R. Xin, C. Xi, and U. A. Khan, “Frost—fast row-stochastic optimization with uncoordinated step-sizes,” _EURASIP Journal on Advances in Signal Processing_ , vol. 2019, no. 1, pp. 1–14, 2019.
  * [19] S. Pu, W. Shi, J. Xu, and A. Nedic, “Push-pull gradient methods for distributed optimization in networks,” _IEEE Transactions on Automatic Control_ , 2020.
  * [20] V. Khatana, G. Saraswat, S. Patel, and M. V. Salapaka, “Gradient-consensus method for distributed optimization in directed multi-agent networks,” _arXiv preprint arXiv:1909.10070_ , 2019. [Online]. Available: https://arxiv.org/pdf/1909.10070v3.pdf
  * [21] K. Yuan, Q. Ling, and W. Yin, “On the convergence of decentralized gradient descent,” _SIAM Journal on Optimization_ , vol. 26, no. 3, pp. 1835–1854, 2016.
  * [22] K. Seaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié, “Optimal algorithms for smooth and strongly convex distributed optimization in networks,” in _Proceedings of the 34th International Conference on Machine Learning-Volume 70_. JMLR. org, 2017, pp. 3027–3036.
  * [23] A. Nedić and A. Olshevsky, “Distributed optimization over time-varying directed graphs,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 3, pp. 601–615, 2014.
  * [24] A. Olshevsky, “Linear time average consensus and distributed optimization on fixed graphs,” _SIAM Journal on Control and Optimization_ , vol. 55, no. 6, pp. 3990–4014, 2017.
  * [25] J. Wang and N. Elia, “Control approach to distributed optimization,” in _2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2010, pp. 557–561.
  * [26] A. S. Berahas, R. Bollapragada, N. S. Keskar, and E. Wei, “Balancing communication and computation in distributed optimization,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 8, pp. 3141–3155, 2018.
  * [27] D. Jakovetić, J. Xavier, and J. M. Moura, “Fast distributed gradient methods,” _IEEE Transactions on Automatic Control_ , vol. 59, no. 5, pp. 1131–1146, 2014.
  * [28] G. Qu and N. Li, “Accelerated distributed nesterov gradient descent,” _IEEE Transactions on Automatic Control_ , 2019.
  * [29] D. Gabay, “Chapter ix applications of the method of multipliers to variational inequalities,” in _Studies in mathematics and its applications_. Elsevier, 1983, vol. 15, pp. 299–331.
  * [30] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” _Foundations and Trends® in Machine Learning_ , vol. 3, no. 1, pp. 1–122, 2011. [Online]. Available: http://dx.doi.org/10.1561/2200000016
  * [31] R. Zhang and J. Kwok, “Asynchronous distributed admm for consensus optimization,” in _International conference on machine learning_ , 2014, pp. 1701–1709.
  * [32] Q. Ling and A. Ribeiro, “Decentralized linearized alternating direction method of multipliers,” in _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2014, pp. 5447–5451.
  * [33] J. F. Mota, J. M. Xavier, P. M. Aguiar, and M. Püschel, “D-admm: A communication-efficient distributed algorithm for separable optimization,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 10, pp. 2718–2723, 2013.
  * [34] E. Wei and A. Ozdaglar, “Distributed alternating direction method of multipliers,” in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_. IEEE, 2012, pp. 5445–5450.
  * [35] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin, “On the linear convergence of the admm in decentralized consensus optimization,” _IEEE Transactions on Signal Processing_ , vol. 62, no. 7, pp. 1750–1761, 2014.
  * [36] E. Wei and A. Ozdaglar, “On the $\large{O}(1/k)$ convergence of asynchronous distributed alternating direction method of multipliers,” in _2013 IEEE Global Conference on Signal and Information Processing_. IEEE, 2013, pp. 551–554.
  * [37] D. Jakovetic, J. Xavier, and J. M. Moura, “Cooperative convex optimization in networked systems: Augmented lagrangian algorithms with directed gossip communication,” _IEEE Transactions on Signal Processing_ , vol. 59, no. 8, pp. 3889–3902, 2011.
  * [38] A. Makhdoumi and A. Ozdaglar, “Convergence rate of distributed admm over networks,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 10, pp. 5082–5095, 2017.
  * [39] F. Mansoori and E. Wei, “A flexible framework of first-order primal-dual algorithms for distributed optimization,” _arXiv preprint arXiv:1912.07526_ , 2019.
  * [40] T.-H. Chang, M. Hong, and X. Wang, “Multi-agent distributed optimization via inexact consensus admm,” _IEEE Transactions on Signal Processing_ , vol. 63, no. 2, pp. 482–497, 2014.
  * [41] D. Jakovetić, J. M. Moura, and J. Xavier, “Linear convergence rate of a class of distributed augmented lagrangian algorithms,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 4, pp. 922–936, 2014.
  * [42] V. Khatana and M. V. Salapaka, “D-distadmm: A $o(1/k)$ distributed admm for distributed optimization in directed graph topologies,” _Under review, IEEE Conference on Decision and Control_ , 2020.
  * [43] R. Diestel, _Graph Theory_. Berlin, Germany: Springer-Verlag, 2006.
  * [44] R. A. Horn and C. R. Johnson, _Matrix analysis_. Cambridge university press, 2012.
  * [45] Y. Nesterov, _Lectures on convex optimization_. Springer, vol. 137.
  * [46] D. G. Luenberger, _Optimization by vector space methods_. John Wiley & Sons, 1997.
  * [47] D. P. Bertsekas, “Incremental gradient, subgradient, and proximal methods for convex optimization: A survey,” _Optimization for Machine Learning_ , vol. 2010, no. 1-38, p. 3, 2011.
  * [48] J. Melbourne, G. Saraswat, V. Khatana, S. Patel, and M. V. Salapaka, “On the geometry of consensus algorithms with application to distributed termination in higher dimension,” _in the proceedings of International Federation of Automatic Control (IFAC)_ , 2020. [Online]. Available: http://box5779.temp.domains/~jamesmel/wp-content/uploads/2019/11/Vector_Consensus__IFAC_-1.pdf
  * [49] V. Yadav and M. V. Salapaka, “Distributed protocol for determining when averaging consensus is reached,” in _45th Annual Allerton Conf_ , 2007, pp. 715–720.
  * [50] M. Prakash, S. Talukdar, S. Attree, V. Yadav, and M. V. Salapaka, “Distributed stopping criterion for consensus in the presence of delays,” _IEEE Transactions on Control of Network Systems_ , 2019.
  * [51] D. Kempe, A. Dobra, and J. Gehrke, “Gossip-based computation of aggregate information,” in _44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings._ IEEE, 2003, pp. 482–491.
  * [52] A. D. Domínguez-García and C. N. Hadjicostis, “Distributed strategies for average consensus in directed graphs,” in _2011 50th IEEE Conference on Decision and Control and European Control Conference_. IEEE, 2011, pp. 2124–2129.
  * [53] A. Olshevsky and J. N. Tsitsiklis, “Convergence speed in distributed consensus and averaging,” _SIAM Journal on Control and Optimization_ , vol. 48, no. 1, pp. 33–55, 2009.
  * [54] S. Patel, S. Attree, S. Talukdar, M. Prakash, and M. V. Salapaka, “Distributed apportioning in a power network for providing demand response services,” in _2017 IEEE International Conference on Smart Grid Communications (SmartGridComm)_. IEEE, 2017, pp. 38–44.
  * [55] S. Patel, V. Khatana, G. Saraswat, and M. V. Salapaka, “Distributed detection of malicious attacks on consensus algorithms with applications in power networks,” 2020.
  * [56] F. Bénézit, V. Blondel, P. Thiran, J. Tsitsiklis, and M. Vetterli, “Weighted gossip: Distributed averaging using non-doubly stochastic matrices,” in _2010 IEEE International Symposium on Information Theory_. IEEE, 2010, pp. 1753–1757.
  * [57] P. Erdős and A. Rényi, “On the evolution of random graphs,” _Publ. Math. Inst. Hung. Acad. Sci_ , vol. 5, no. 1, pp. 17–60, 1960.
  * [58] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” _SIAM journal on imaging sciences_ , vol. 2, no. 1, pp. 183–202, 2009.
  * [59] G. Saraswat, V. Khatana, S. Patel, and M. V. Salapaka, “Distributed finite-time termination for consensus algorithm in switching topologies,” _arXiv preprint arXiv:1909.00059_ , 2019.