#  Consensus ALADIN: A Framework for Distributed Optimization and Its
Application in Federated Learning

Xu Du, Jingzhe Wang X.Du is with the Institute of Mathematics HNAS, Henan
Academy of Science, Zhengzhou, China. E-mail<EMAIL_ADDRESS>Jingzhe
Wang is with the Department of Informatics & Networked Systems, School of
Computing and Information, University of Pittsburgh, Pittsburgh, PA, USA.
E-mail<EMAIL_ADDRESS>
###### Abstract

This paper investigates algorithms for solving distributed consensus
optimization problems that are non-convex. Since Typical ALADIN (Typical
Augmented Lagrangian based Alternating Direction Inexact Newton Method,
T-ALADIN for short)[1] is a well-performed algorithm treating distributed
optimization problems that are non-convex, directly adopting T-ALADIN to those
of consensus is a natural approach. However, T-ALADIN typically results in
high communication and computation overhead, which makes such an approach far
from efficient. In this paper, we propose a new variant of the ALADIN family,
coined consensus ALADIN (C-ALADIN for short). C-ALADIN inherits all the good
properties of T-ALADIN, such as the local linear or super-linear convergence
rate and the local convergence guarantees for non-convex optimization
problems; besides, C-ALADIN offers unique improvements in terms of
communication efficiency and computational efficiency. Moreover, C-ALADIN
involves a reduced version, in comparison with Consensus ADMM (Alternating
Direction Method of Multipliers) [3], showing significant convergence
performance, even without the help of second-order information. We also
propose a practical version of C-ALADIN, named FedALADIN, that seamlessly
serves the emerging federated learning applications, which expands the reach
of our proposed C-ALADIN. We provide numerical experiments to demonstrate the
effectiveness of C-ALADIN. The results show that C-ALADIN has significant
improvements in convergence performance.

###### Index Terms:

Distributed Consensus Optimization, Algorithm Efficiency, Convergence
Analysis, Federated Learning

††publicationid: pubid:

##  1 Introduction

In recent years, distributed optimization algorithms have received a lot of
attention due to developments in numerical optimal control [4], smart grid
[5], wireless communication[6], game theory[7], and machine learning[8]. In
the field of distributed optimization algorithm design, solving distributed
non-convex problems efficiently has always been the direction of people’s
efforts. To deal with non-convexity, in this paper, we follow this direction
and propose a novel algorithmic framework for distributed non-convex consensus
optimization.

###  1.1 The Road to Consensus ALADIN

We start with introducing distributed optimization (DO for short) problems. DO
problems are generally formulated in the fashion of mathematical programming,
where separable objectives are linearly coupled by $m$ equality constraints.
Formally, it can be described as follows:

$\begin{split}\min_{\xi_{i}\in\mathbb{R}^{n_{i}}}\;\;&\mathop{\sum}_{i=1}^{N}f_{i}(\xi_{i})\\\
\mathrm{s.t.}\;\;&\mathop{\sum}_{i=1}^{N}A_{i}\xi_{i}=b\;|\mu.\end{split}$ (1)

Here, the coupling matrices $A_{i}\in\mathbb{R}^{n_{i}\times m}$ and the
coupling parameter $b\in\mathbb{R}^{m}$ are given. The dimension $n_{i}$ of
private variables $\xi_{i}$s are potentially different. $\mu\in\mathbb{R}^{m}$
indicates the corresponding dual variable of the coupling constraints. When
the objective $f_{i}$s are convex, there are some classical algorithms that
can be used to solve it, such as dual decomposition (DD) [9, 10], and ADMM
[3]. As a special case of DO, distributed consensus (DC) optimization problems
meet all the challenges such as convergence theory for non-convex cases. The
main difference of DO and DC is that DC has a global variable to which all the
private variables will converge (detailed descriptions will be shown in
Section 2.1).

As milestone research of DC, [11] shows that Consensus ADMM [3], under some
assumptions, has a linear convergence rate for DC problems that are strongly
convex. We refer [12] as a survey paper for more details. Notice that, similar
to Consensus ADMM, current algorithms such as DGD [13], EXTRA [14] only have
convergence guarantees for convex problems in the area of DC. However, many
practical problems [4], especially those met in federated learning (FL)[15],
are non-convex. When meeting such problems, the above algorithms cannot
provide satisfactory solutions in general.

To solve such non-convex problems, in literature, T-ALADIN is a state-of-the-
art algorithm that can provide theoretical local convergence guarantee.
Technically, T-ALADIN can be regarded as a successful combination of ADMM and
sequential quadratic programming (SQP). Details can be found in Subsection
2.2. To date, T-ALADIN has several elegant successors [16, 17, 18, 19] and
already shown effectiveness in many applications [20, 16, 17, 21]. From the
above facts, to solve distributed consensus problems that are non-convex,
directly adopting T-ALADIN seems very natural. However, such a trivial
approach meets the following challenges: first, T-ALADIN will bring a large
number of constraints in the coupled QP step (details can be found in (8)),
and the dimension of the corresponding dual variable $\mu$ will be extremely
large; second, the T-ALADIN structure inevitably depends on the uploading of
the first and second order information (details can be found in(7)) from the
agents and downloading of the updated primal and dual variables, which incurs
huge communication complexity; third, in T-ALADIN, a large-scale coupled QP
has to be solved exactly, which results in heavy computation workload.

In this paper, we propose C-ALADIN for meeting the aforementioned challenges.
C-ALADIN addresses the challenges as follows: First, instead of solving a
coupled QP in T-ALADIN, a consensus QP is solved in C-ALADIN; second, we
improve the upload and download communication efficiency by designing decoding
strategies on both sides of the agents and the master. In detail, on the
uploading side, we find that the local optimizer dominates such parameters.
Such an observation, in conjunction with the approximation techniques of
Broyden–Fletcher–Goldfarb–Shanno (BFGS) [2], enable the master to recover the
Hessian approximation matrices. It avoids uploading Hessian matrices directly
from agents. We name the above techniques Consensus BFGS ALADIN. Later, in a
reduced version named Reduced Consensus ALADIN, we simply use an identity
matrix for large-scale computation problems. On the downloading side, inspired
by the KKT (Karush–Kuhn–Tucker) optimality condition of the coupled QP, we
allow the agents to recover the dual variables that are not urgently
broadcast. It can be realized by decoding such variables with the help of the
global variable; third, in C-ALADIN, the computational bottlenecks come from
solving a large-scale sparse consensus QP that plays a key role in
coordinating information. Inspired by the technique of KKT mentioned above, we
find an equivalent form of the large-scale sparse consensus QP in C-ALADIN.
Such a form can significantly release the burden on computing the
corresponding KKT matrix. Based on our proposed C-ALADIN, we then propose a
theory of convergence analysis, which works for both convex and non-convex
cases.

In order to expand the application scope of our proposed C-ALADIN algorithm
family, we next show how FL can benefit from our proposed C-ALADIN.

###  1.2 Federated Learning via Consensus ALADIN

FL, as a framework that aims to train a relatively universal model with data
from different devices without transmitting the original data directly,
involves many DC problems that are in general either convex or non-convex. In
fact, there are several existing efforts [15, 8, 22, 23, 24, 25] on solving DC
problems in FL. However, such algorithms typically suffer the bottleneck of
lacking theoretical non-convex analysis and unsatisfactory convergence rate.
To achieve both, we start adopting C-ALADIN in FL. Though C-ALADIN shows
promising convergence performance, directly integrating C-ALADIN with FL is
non-trivial. Specifically, all current members in C-ALADIN rely on uploading
the local primal variables to the master, which is not secure. Then, because
of the high-dimension property of FL, second order information can not be
used, which limits the power of Consensus BFGS ALADIN. By observing such
challenges, based on Reduced Consensus ALADIN, we design a novel variant
member of C-ALADIN, named FedALADIN, that seamlessly meets the requirements of
FL.

In summary, our key contributions of this paper are as follows:

a) We introduce the notion of consensus QP.

b) We propose a novel efficient algorithm family C-ALADIN that shows rigorous
convergence guarantee, which consists of Consensus BFGS ALADIN and Reduced
Consensus ALADIN.

c) We propose a novel proof framework to perform the convergence analysis of
C-ALADIN.

d) We propose FedALADIN for FL.

e) We perform numerical experiments on both C-ALADIN and FedALADIN. The
results say that both C-ALADIN and FedALADIN show significant improvements in
convergence performance.

###  1.3 Organization

The rest of this paper is organized as follows. In Section 2, we provide
mathematical preliminaries, including fundamentals of Consensus ADMM and
T-ALADIN. In Section 3, we present a new algorithm named C-ALADIN. Moreover,
we show that a reduced version of C-ALADIN can be applied to FL named
FedALADIN in Section 4. Later, convergence theory of C-ALADIN is established
in Section 5. In the end, we show the numerical result in Section 6 . In
Section 7, we provide a literature review. Section 8 concludes this paper.

##  2 Preliminaries

In this section, we provide formal fundamentals of Consensus ADMM and
T-ALADIN.

###  2.1 FL via Consensus ADMM

Assume that we have $N$ clients111In numerical optimization, one who solves
the sub-problem is called agent, and in FL it is called client. In this paper,
we use the two notions interchangeably.  and each of those has a local dataset
$\mathcal{D}_{i}$ where $i\in\\{1,\dots,N\\}$. Here, the loss function of
client $i$ is defined as

$f_{i}(z)=\alpha_{i}\sum_{t_{i}\in\mathcal{D}_{i}}l_{i}(z;t_{i}),$ (2)

where $l_{i}(z,t_{i}):\mathbb{R}^{n\times|t_{i}|}\rightarrow\mathbb{R}$ is a
mapping for measuring the prediction error of global variable
$z\in\mathbb{R}^{n}$. Moreover $\alpha_{i}$s are the positive weights with
$\sum_{i=1}^{N}\alpha_{i}=1$. The main goal of machine learning is to solve
the following joint optimization problem:

$\min_{z\in\mathbb{R}^{n}}F(z)=\sum_{i=1}^{N}f_{i}(z).$ (3)

However, $\mathcal{D}_{i}$s usually belongs to different clients and can not
be shared with each other. To deal with this, instead of solving Problem (3),
FL solves the reformulated Problem (4) in a distributed way.

$\begin{split}\min_{x_{i},z\in\mathbb{R}^{n}}\;\;&\sum_{i=1}^{N}f_{i}(x_{i})\\\
\quad\mathrm{s.t.}\;\;&x_{i}=z\;|\lambda_{i}.\;\end{split}$ (4)

Here $x_{i}$ denotes the local primal variable of agent $i$ and $z$ indicates
the primal global variable. By using Lagrange multiplier (dual variable)
$\lambda_{i}$, the corresponding Lagrangian function can be expressed as

$\begin{split}\mathcal{L}(x_{i},z,\lambda_{i})=&\sum_{i=1}^{N}f_{i}(x_{i})\\\
&+\sum_{i=1}^{N}\lambda_{i}^{\top}(x_{i}-z)+\sum_{i=1}^{N}\frac{\rho}{2}\|x_{i}-z\|^{2}.\end{split}$
(5)

Here, $\rho$ is a given positive penalty parameter. From (5), in the FedADMM,
the local primal and dual variables can be updated as Algorithm 1 with
learning rate $\eta_{i}$. Note that the uploaded information $w_{i}$s from
client side of Algorithm 1 is a linear combination of the local primal and the
dual variables, which is a secure way of protecting clients’ local
information.

Algorithm 1 FedADMM: Consensus ADMM for FL

Initialization: Initial guess of global model $z=0$, local model
$x_{i}^{-}=0$s and dual variables $\lambda_{i}=0$. Set Total number of rounds
$T$ and penalty parameter $\rho$.

For $t=1\dots T$ Clients: // In parallel
For $i=1\dots N$
Download $z$ from the server
Locally update $w_{i}\leftarrow\texttt{ClientUpdate}(z,i)$
Upload $w_{i}$ to the server
End

Server: $z=\frac{1}{N}\sum_{i=1}^{N}w_{i}.$
End

$\texttt{ClientUpdate}(z,i)$:
Input: Local epoch number $E_{i}$, client learning rate $\eta_{i}$.

For $e=1\dots E_{i}$

${x_{i}}=x_{i}-\eta_{i}\left(\nabla
f_{i}(x_{i})+\lambda_{i}^{\text{ADMM}}+\rho\left(x_{i}-z\right)\right)$

End

$\lambda_{i}^{\text{ADMM}}=\lambda_{i}^{\text{ADMM}}+\rho({x_{i}}-z)$.

$w_{i}=x_{i}+\frac{1}{\rho}\lambda_{i}^{\text{ADMM}}$

return: $w_{i}$

######  Remark 1.

The private variables $x_{i}$ can be updated by applying any approximation
technologies such as decentralized linearized alternating direction method of
multipliers (DLM) [26] or decentralized quadratically approximated alternating
direction method of multipliers (DQM) [27].

######  Remark 2.

As pointed out in [12, Section IV], a Consensus ADMM variation [11] was
specifically designed for solving Problem (4) instead of Problem (1) and
should be considered a relatively independent algorithm.

###  2.2 T-ALADIN in A Nutshell

T-ALADIN is the first distributed optimization algorithm that can generally
solve non-convex DO (1).

In the first step, Algorithm 2 has a similar operation as ADMM and gets new
local optimizers from each client. Later we evaluate the gradients $g_{i}$s
and positive definite Hessian matrices approximation $H_{i}$s with
$\xi_{i}^{+}$s. In the third step, we solve a large-scale QP for coordination
by using $g_{i}$s and $H_{i}$s from the second step. In the end, we send the
updated primal and dual variables to each client in the forth step.

The main difference between ADMM and T-ALADIN is that the latter updates the
global dual variable $\mu$ by solving the constrained coupled QP (Equation
(8)). Moreover, with the assumption of linearly independent constraint
qualification (LICQ) and second order sufficient condition (SOSC), Algorithm 2
has local convergence guarantees for distributed non-convex problems [28].

Note that T-ALADIN tries to collect all the good properties of SQP and ADMM.
There are two main extreme cases:

  * •

When $\rho\rightarrow\infty$, the first step of Algorithm 2 is redundant and
the whole structure is equivalent to SQP.

  * •

When $\rho\rightarrow 0$, Algorithm 2 equals a combination of DD and Newton’s
method.

Algorithm 2 Typical ALADIN

Initialization: Initial guess of primal and dual variables $(y_{i},\mu)$.
Repeat:

  1. 1.

Parallelly solve local nonlinear programming (NLP) without subsystem coupling:

${\xi_{i}}^{+}=\mathop{\arg\min}_{\xi_{i}}f_{i}(\xi_{i})+\mu^{\top}A_{i}\xi_{i}+\frac{\rho}{2}\|\xi_{i}-y_{i}\|^{2}.$
(6)

  2. 2.

Evaluate Hessian approximation and gradient from ${\xi_{i}}^{+}$:

$\left\\{\begin{array}[]{l}\begin{split}B_{i}\approx&\nabla^{2}f_{i}(\xi_{i}^{+})\succ
0,\\\ g_{i}=&\nabla f_{i}(\xi_{i}^{+}).\end{split}\end{array}\right.$ (7)

  3. 3.

Solve the coupled QP on master side:

$\begin{split}\mathop{\mathrm{\min}}_{\Delta\xi_{i}}&\quad\mathop{\sum}_{i=1}^{N}\frac{1}{2}\Delta\xi_{i}^{\top}B_{i}\Delta\xi_{i}+g_{i}^{\top}\Delta\xi_{i}\\\
\mathrm{s.t.}&\mathop{\sum}_{i=1}^{N}A_{i}(\xi_{i}^{+}+\Delta\xi_{i})=b\;|{\mu}^{+}.\end{split}$
(8)

  4. 4.

Download :

$\left\\{\begin{array}[]{l}\begin{split}\mu&\leftarrow{\mu}^{+}\\\
y_{i}&\leftarrow\xi_{i}^{+}+\Delta\xi_{i}\end{split}\end{array}\right.$ (9)

######  Remark 3.

To the best of our knowledge, although a convex LASSO problem has been solved
with T-ALADIN [18, Section 5.1], is a two objectives optimization problem.
Besides, no such concept like _consensus ALADIN_ has been formally proposed by
others.

##  3 Consensus ALADIN

In Subsection 3.1, we propose the consensus QP.In Subsection 3.2, we detail
our communication-efficient design. In Subsection 3.3, we provide our
techniques that improve computational efficiency. In Subsection 3.4, with the
techniques proposed in the above subsections, we formally describe C-ALADIN
with two variants, namely Consensus BFGS ALADIN and Reduced Consensus ALADIN.

###  3.1 From Coupled QP to Consensus QP

Remember that in Subsection 1.1, T-ALADIN is struggling with solving Problem
(4) because of the coupling equality constraints in Equation (8). Thus, the
first step towards making T-ALADIN survive in (4) is to reconstruct Equation
(8), which yields our consensus QP that is formally shown as follows:

$\begin{split}\mathop{\mathrm{\min}}_{\Delta
x_{i},z}&\quad\mathop{\sum}_{i=1}^{N}\left(\frac{1}{2}\Delta
x_{i}^{\top}B_{i}\Delta x_{i}+g_{i}^{\top}\Delta x_{i}\right)\\\
\mathrm{s.t.}&\qquad\Delta x_{i}+x_{i}^{+}=z\;|\lambda_{i}.\end{split}$ (10)

It is trivial to see that, in (10), by introducing a global variable $z$ and
coupling all $x_{i}$s to $z$. The number of coupled equality constraints will
be reduced to $O(N)$ which is lower than $O(N^{2})$ that comes from the direct
adoption of T-ALADIN (shown as Figure 2 and 2). Note that, in Equation (10),
we have one global primal variable $z$ and $N$ dual variable, which is in
contrast to the formulation of Equation (8).

Figure 1: Fully Connection
(Worst case scenario).

Figure 2: Private-master coupling.

After replacing Equation (8) with Equation (10), Algorithm 2 starts working in
a consensus fashion. We name this C-ALADIN.

######  Remark 4.

Regarding the number of coupling constraints of T-ALADIN, we want to stress
that $O(N^{2})$, corresponding to the Figure 2, describes the worst case when
directly adopting T-ALADIN in solving DC problems. As for the best case,
though T-ALADIN can work under $O(N)$ coupling constraints as those of
C-ALADIN, it needs a fine-grained design on $A_{i}$, which, from user’s
perspective, hinders the ease of practical adoption of T-ALADIN.

###  3.2 Improve the Communication Efficiency of C-ALADIN

In this subsection, we jointly improve the upload 3.2.1 and download 3.2.2
communication efficiency of C-ALADIN.

####  3.2.1 Improving Upload Communication Efficiency

In the C-ALADIN framework, instead of solving Problem (6), we solve the
following decoupled augmented loss function (11) with local dual
$\lambda_{i}$.

${x_{i}}^{+}=\mathop{\arg\min}_{x_{i}}f_{i}(x_{i})+\lambda_{i}^{\top}x_{i}+\frac{\rho}{2}\|x_{i}-z\|^{2}.$
(11)

In order to avoid uploading the gradient and Hessian approximation directly
(7), we choose to decode the first and second order information on the master
side, which is detailed in (12)

$\left\\{\begin{split}&g_{i}(x_{i}^{+})=\;\rho(z-x_{i}^{+})-\lambda_{i}\quad\text{((sub)gradient)},\\\
&s_{i}(x_{i}^{+},x_{i}^{-})=\;x_{i}^{+}-x_{i}^{-},\\\
&y_{i}(x_{i}^{+},x_{i}^{-})=\;g_{i}(x_{i}^{+})-g_{i}^{-},\\\
&B_{i}^{+}=\;B_{i}-\frac{B_{i}s_{i}s_{i}^{\top}B_{i}}{s_{i}^{\top}B_{i}s_{i}}+\frac{y_{i}y_{i}^{\top}}{s_{i}^{\top}y_{i}}\quad\text{(BFGS
update)}.\end{split}\right.$ (12)

We want to stress several key designs behind Equation (12). First, we suppose
that the augmented NLP (11) can be solved exactly. By applying Clarke sub-
differential of $f_{i}$ at $x_{i}^{+}$, we have
$g_{i}=\rho(z-x_{i}^{+})-\lambda_{i}\in\partial f_{i}$. It means that the
(sub)gradient can be decoded with $x_{i}^{+}$ without being transmitted.

Second, by applying the difference of local private variables and the local
(sub)gradients, the BFGS Hessian approximation can also be decoded by the
master. In order to ensure the positive definiteness of local BFGS matrices,
we adopted the strategy of _damped BFGS_ [2, Page 537], that is, we modify the
local gradient difference $y_{i}$

$y_{i}=y_{i}+\theta(B_{i}s_{i}-y_{i})$

with a turning parameter

$\theta=\frac{0.2(s_{i})^{\top}B_{i}s_{i}-(s_{i})^{\top}y_{i}}{(s_{i})^{\top}B_{i}s_{i}-(s_{i})^{\top}y_{i}}$

if

$(y_{i})^{\top}s_{i}\leq\frac{1}{5}(s_{i})^{\top}B_{i}s_{i}.$

Note that if $\theta=1$, $B_{i}^{+}=B_{i}$. The damping thus ensures that the
positive curvature of the Hessian in direction $s_{i}$, which is expressed in
the term $\left((s_{i})^{\top}B_{i}s_{i}\right)$, will never decrease by more
than a factor of 5. Modified versions of BFGS may also work.For example, to
solve the storage problem of the BFGS approximation Hessian, _limited memory
BFGS_ (L-BFGS) maybe a promising solution.

######  Remark 5.

If we are dealing with a single objective problem, instead of computing the
inverse of $B_{i}^{+}$ directly, we have the following closed form:

$\begin{split}(B^{k+1})^{-1}=&(B^{k})^{-1}+\frac{(s^{\top}y+y^{\top}(B^{k})^{-1}y)(ss^{\top})}{(s^{\top}y)^{2}}\\\
&-\frac{(B^{k})^{-1}ys^{\top}+sy^{\top}(B^{k})^{-1}}{s^{\top}y}.\end{split}$

It can not be applied directly if we have a summation of $B_{i}$s.

####  3.2.2 Improving Download Communication Efficiency

If we express the Lagrange function of Equation (10),

$\begin{split}\mathcal{L}^{\text{QP}}(\Delta
x_{i},z,\lambda_{i})=&\left(\sum_{i=1}^{N}\frac{1}{2}\Delta
x_{i}^{\top}B_{i}\Delta x_{i}+g_{i}^{\top}\Delta x_{i}\right)\\\
&+\left(\sum_{i=1}^{N}\lambda_{i}^{\top}(\Delta
x_{i}+x_{i}^{+}-z)\right),\end{split}$ (13)

the KKT system can be then expressed in the following three equations,

$\left\\{\begin{split}\frac{\partial\mathcal{L}^{\text{QP}}}{\partial\Delta
x_{i}}&=B_{i}\Delta x_{i}+g_{i}+\lambda_{i}=0,\\\
\frac{\partial\mathcal{L}^{\text{QP}}}{\partial\lambda_{i}}&=\Delta
x_{i}+x_{i}^{+}-z=0,\\\ \frac{\partial\mathcal{L}^{\text{QP}}}{\partial
z}&=-\sum_{i=1}^{N}\lambda_{i}=0,\end{split}\right.$ (14)

which implies $\Delta x_{i}=z-x_{i}^{+}$ and
$\lambda_{i}=B_{i}(x_{i}^{+}-z)-g_{i}$. It shows that agents can decode the
dual variable $\lambda_{i}$ with the global variable $z$ without being
transmitted.

In summary, in C-ALADIN, the agents only upload their private variables update
$x_{i}^{+}$ to the master while the master broadcast the global variable
(aggregate model) $z$. In this way, neither Hessian nor gradient needs to be
uploaded and the dual variables need not to be downloaded.

Improving the communication efficiency mentioned above is not the end. To
further enhance our algorithm, we next boost computational efficiency.

###  3.3 Improve the Computational Efficiency of C-ALADIN

To improve the computational efficiency, a trivial approach is to seek help
from existing QP solvers which is described as follows: solvers based on
active set qpOASES [29], MOSEK [30], GUROBI [31]; solvers based on interior
point methods CVXGEN [32] and OOQP [33]; solvers basd on ADMM or operator
splitting method OSQP [34].

However, such solvers ignore the special structure of our input (10).
Therefore, a customized QP solver is needed for improving the computational
efficiency. Next, we show our technical details.

The global primal variable can be updated in a cheap operation by introducing
the following theorem.

######  Theorem 1.

With the decoding of Hessian approximation and the gradients of the agents by
Equation (12), the global $z$ can be updated as Equation (15) 222Assume that
the matrix inverse operation can be applied on the master side, instead of an
inverse operation, _conjugate gradient descent_ can be also applied here. 333
Suppose that for iteration $k$ with $\text{log}_{K}(k)\in\mathbb{N}$ [19], the
Hessian matrices can be chosen optionally to upload from the agent to the
master. The decomposition of a positive definite matrix can be prepared before
the consensus QP step (10). .

$\begin{split}z^{+}_{\text{BFGS}}=\left(\sum_{i=1}^{N}B_{i}^{+}\right)^{-1}\left(\left(\sum_{i=1}^{N}B_{i}^{+}x_{i}^{+}\right)-\left(\sum_{i=1}^{N}g_{i}\right)\right).\end{split}$
(15)

###### Proof.

Linear system (14) can be expressed as the following dense form:

$\underbrace{\begin{bmatrix}\mathcal{B}&\mathbf{I}&\mathbf{0}\\\\[1.42262pt]
\mathbf{I}&\mathbf{0}&-\mathcal{I}\\\\[1.42262pt]
\mathbf{0}^{\top}&(-\mathcal{I})^{\top}&\mathbf{0}\\\\[1.42262pt]
\end{bmatrix}}_{M_{\text{KKT}}\in\mathbb{R}_{+}^{|(2N+1)n|\times|(2N+1)n|}}\begin{bmatrix}\Delta
x\\\ \mathbf{\lambda}\\\ z\end{bmatrix}=\begin{bmatrix}-\mathcal{G}\\\
-x^{+}\\\ \mathbf{0}\end{bmatrix}$ (16)

with

$\mathcal{B}=\begin{bmatrix}B_{1}&0&\cdots&0\\\ 0&B_{2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&B_{N}\end{bmatrix},\quad\mathbf{I}=\begin{bmatrix}I&0&\cdots&0\\\
0&I&\cdots&0\\\ \vdots&\vdots&\ddots&0\\\ 0&\cdots&\cdots&I\end{bmatrix},$
$\mathcal{I}=\begin{bmatrix}I&I&I&I\end{bmatrix}^{\top},$
$\begin{bmatrix}\Delta x\\\ \lambda\\\
z\end{bmatrix}=\begin{bmatrix}\begin{array}[]{c}\Delta x_{1}\\\ \Delta
x_{2}\\\ \vdots\\\ \Delta x_{N}\\\ \hline\cr\lambda_{1}\\\ \lambda_{2}\\\
\vdots\\\ \lambda_{N}\\\ \hline\cr
z\end{array}\end{bmatrix}\quad\text{and}\quad\begin{bmatrix}-\mathcal{G}\\\
-x^{+}\\\ \mathbf{0}\end{bmatrix}=\begin{bmatrix}\begin{array}[]{c}-g_{1}\\\
-g_{2}\\\ \vdots\\\ -g_{N}\\\ \hline\cr-x_{1}^{+}\\\ -x_{2}^{+}\\\ \vdots\\\
-x_{N}^{+}\\\ \hline\cr\mathbf{0}\end{array}\end{bmatrix}.$

Directly solving QP (10) is equivalent to solving linear system (16). We note
that the roadblock to making C-ALADIN computationally efficient is the heavy
computational workload, incurred by deriving the inverse of the large-scale
matrix $M_{\text{KKT}}$.

Inspired by _Schur Complement_ we have the following proof. From the first row
of Equation (16), we have

$\Delta x=-\mathcal{B}^{-1}(\lambda+\mathcal{G}).$ (17)

Then plug (17) into the second row of Equation (16) to get Equation (18).

$\mathcal{B}^{-1}(\lambda+\mathcal{G})+\mathcal{I}z=x^{+}\Rightarrow\lambda=\mathcal{B}(x^{+}-\mathcal{I}z)-\mathcal{G}.$
(18)

Next, bring Equation (18) into the third row of Equation (16), the following
equation will be obtained

$(-\mathcal{I})^{\top}\mathcal{B}(x^{+}-\mathcal{I}z)+(\mathcal{I})^{\top}\mathcal{G}=0.$
(19)

The update of global variable $z$ can be then expressed as follows from
Equation (19).

$\begin{split}z^{+}_{\text{BFGS}}=&\underbrace{\left(\mathcal{I}^{\top}\mathcal{B}\mathcal{I}\right)^{-1}}_{\mathcal{K}\in\mathbb{R}_{+}^{|n|\times|n|}}\left(\mathcal{I}^{\top}\mathcal{B}x^{+}-(\mathcal{I})^{\top}\mathcal{G}\right)\\\
=&\left(\sum_{i=1}^{N}B_{i}^{+}\right)^{-1}\left(\left(\sum_{i=1}^{N}B_{i}^{+}x_{i}^{+}\right)-\left(\sum_{i=1}^{N}g_{i}\right)\right).\end{split}$

∎

As an extension, if $B_{i}$s are set as $\rho I$, Equation (15) is reduced as

$z^{+}_{\rho}=\frac{1}{N}\sum_{i=1}^{N}\left(x_{i}^{+}-\frac{g_{i}}{\rho}\right).$
(20)

Here, the expression of (20) has almost the computation complexity as
Consensus ADMM since no inverse of aggregated Hessian matrix is needed. Both
methods of updating the global variable ((15) and (20)) avoid computing
$\Delta x_{i}$ and $\lambda_{i}$ together. In this way, the operation burden
of large-scale matrix inversion in Equation (16) is reduced.

######  Remark 6.

With Equation (20), the primal increment $\Delta x_{i}$ and dual $\lambda_{i}$
can be then decoded by the agents with

$\left\\{\begin{split}\Delta x_{i}&=z-x_{i}^{+},\\\
\lambda_{i}&=\rho(x_{i}^{+}-z)-g_{i}\end{split}\right.$ (21)

in the next iteration.

By combining the technologies proposed in the above three subsections, we
illustrate two variations of C-ALADIN in the next subsection.

###  3.4 Algorithm Structure

In this subsection, by combining our proposed techniques described in
Subsection 3.1-3.3, we propose two algorithms. Specifically, one, named
_Consensus BFGS ALADIN_ , benefits from the techniques of BFGS Hessian
approximation (with Equation (15)). The other, named _Reduced Consensus
ALADIN_ (with Equation (20)), under the scenario where the convergence rate is
degraded, can work without the second-order information. We detail Consensus
BFGS ALADIN in Algorithm 3. For _Reduced Consensus ALADIN_ , it can be easily
got from by replacing $x_{i}^{+}$, $\lambda_{i}$, $g_{i}$ and $z$ in Algorithm
3 with the ones defined by the following equation:

$\left\\{\begin{split}&\lambda_{i}=\rho(x_{i}-z)-g_{i},\\\
&{x_{i}}^{+}=\mathop{\arg\min}_{x_{i}}f_{i}(x_{i})+\lambda_{i}^{\top}x_{i}+\frac{\rho}{2}\|x_{i}-z\|^{2},\\\
&g_{i}=\rho(z-x_{i}^{+})-\lambda_{i},\\\
&z=\frac{1}{N}\sum_{i=1}^{N}\left(x_{i}^{+}-\frac{g_{i}}{\rho}\right).\end{split}\right.$
(22)

Note that, both two algorithms belong to the class of C-ALADIN.

######  Remark 7.

As a supplement, we analyze the difference between the Reduced Consensus
ALADIN and Consensus ADMM in Appendix A.

Algorithm 3 Consensus BFGS ALADIN

Initialization: choose $\rho>0$, initial guess $(\lambda_{i},z,B_{i}\succ 0)$
(or set $B_{i}=\rho I$).
Repeat:

  1. 1.

Each agent optimizes its own variable $x_{i}$ locally and transmit it to the
master

${x_{i}}^{+}=\mathop{\arg\min}_{x_{i}}f_{i}(x_{i})+\lambda_{i}^{\top}x_{i}+\frac{\rho}{2}\|x_{i}-z\|^{2}$
(23)

with $\lambda_{i}=B_{i}(x_{i}^{-}-z)-g_{i}$.

  2. 2.

Decode the gradients and Hessian of each sub-problem at the master side.
a) The master encode the (sub)gradient and BFGS Hessian from each
${x_{i}}^{+}$.

$\left\\{\begin{split}g_{i}(x_{i}^{+})=&\;\rho(z-x_{i}^{+})-\lambda_{i}\quad&\text{
(local (sub)gradient evaluation) },\\\
s_{i}(x_{i}^{+},x_{i}^{-})=&\;x_{i}^{+}-x_{i}^{-}\quad&\text{ (difference of
private variables) },\\\
y_{i}(x_{i}^{+},x_{i}^{-})=&\;g_{i}(x_{i}^{+})-g_{i}^{-}\quad&\text{(difference
of local (sub)gradient)) }.\end{split}\right.$ (24)

b) Modify the local gradient based on the following condition

$\left\\{\begin{split}&y_{i}=y_{i}+\theta(B_{i}s_{i}-y_{i})\;\text{where}\;\theta=\frac{0.2(s_{i})^{\top}B_{i}s_{i}-(s_{i})^{\top}y_{i}}{(s_{i})^{\top}B_{i}s_{i}-(s_{i})^{\top}y_{i}},&\text{if}\;(y_{i})^{\top}s_{i}\leq\frac{1}{5}(s_{i})^{\top}B_{i}s_{i}\\\
&y_{i}=y_{i},&\text{otherwise}.\end{split}\right.$

c) BFGS Hessian approximation evaluation:

$B_{i}^{+}=\;B_{i}-\frac{B_{i}s_{i}s_{i}^{\top}B_{i}}{s_{i}^{\top}B_{i}s_{i}}+\frac{y_{i}y_{i}^{\top}}{s_{i}^{\top}y_{i}}.$

  3. 3.

The master solve the following coupled QP with updated $x_{i}^{+}$, $g_{i}$
and $B_{i}$.

$\begin{split}z^{+}_{\text{BFGS}}=&\left(\sum_{i=1}^{N}B_{i}^{+}\right)^{-1}\left(\left(\sum_{i=1}^{N}B_{i}^{+}x_{i}^{+}\right)-\left(\sum_{i=1}^{N}g_{i}(x_{i}^{+})\right)\right).\end{split}$

Broadcast the global model $z$ to the agents.

In order to expand the reach of our proposed C-ALADIN, by meeting the DC
problems in FL, we next introduce a novel way of applying Reduced Consensus
ALADIN in this area.

##  4 FedALADIN

To meet the DC problems in FL, directly adopting Consensus BFGS ALADIN or
Reduced Consensus ALADIN is a straightforward approach to solving such
problems. However, we will meet the following challenges: first, since the
high dimension of private variables $x_{i}$s, we cannot benefit from the
second order information; second, existing algorithms, when solving the DC
problems in FL, does not carefully determine a training epoch, which makes the
solutions inexact. This challenge renders the failure to directly adopting our
techniques that provide exact solutions. By meeting the two challenges, in
this section, we carefully design a variant of Reduced Consensus ALADIN, named
FedALADIN, that works well for the problems in FL.

We sketch the key design of FedALADIN as follows: By following the conventions
in Algorithm 1 and observing the structure of Equation (20), each client
transmits Equation (25) instead of $x_{i}$.

$w_{i}=\left(x_{i}-\frac{g_{i}}{\rho}\right).$ (25)

Next, we detail FedALADIN in Algorithm 4. Different from Algorithm 1,
Algorithm 4 obtains the local optimizer by using the decoded $\lambda_{i}$
from the previous global model $z$. Then we evaluate the (sub)gradients with
Equation (24). Later we encode the transmitted date $w_{i}$s with Equation
(25). After receiving $w_{i}$s from each client, the server aggregates them as
FedADMM.

Algorithm 4 FedALADIN

Initialization: Initial guess of global model $z=0$, local model
$x_{i}^{-}=0$, gradient $g_{i}=0$ and dual variables $\lambda_{i}=0$. Set the
total number of rounds $T$ and penalty parameter $\rho$.

For $t=1\dots T$ Clients: // In parallel
For $i=1\dots N$
Download $z$ from the server
Locally update $w_{i}\leftarrow\texttt{ClientUpdate}(z,i)$
Upload $w_{i}$ to the server
End

Server: $z=\frac{1}{N}\sum_{i=1}^{N}w_{i}.$
End

$\texttt{ClientUpdate}(z,i)$:
Input: Local epoch number $E_{i}$, client learning rate $\eta_{i}$.
$\lambda_{i}=\rho(x_{i}^{-}-z)-g_{i}$.

For $e=1\dots E_{i}$

${x_{i}}=x_{i}-\eta_{i}\left(\nabla
f_{i}(x_{i})+\lambda_{i}+\rho\left(x_{i}-z\right)\right)$

End

$g_{i}=\nabla f_{i}(x_{i})$
$w_{i}=x_{i}-\frac{g_{i}}{\rho}$

return: $w_{i}$

Note that the major difference between FedALADIN and FedADMM is the way of
dual update. More importantly, the gradient evaluation (24) is a symmetric
operation as the dual update of Equation (45). However, FedALADIN can benefit
from the reduced QP operation compare with the former. In terms of structure,
all the existing algorithms in FL are special cases of FedALADIN.

Figure 3: Consensus ALADIN family.

In the next section, we aim to establish the global and local convergence
theory of C-ALADIN.

##  5 Convergence Analysis

In this section, we are interested in the convergence behavior of C-ALADIN,
which consists of the following three parts:

  * •

Global convergence of Reduced Consensus ALADIN for convex problems (Subsection
5.1).

  * •

Global linear convergence rate of Reduced Consensus ALADIN for Lipschitz
continuous or strongly convex problems (Subsection 5.2).

  * •

Local convergence analysis of non-convex problems with C-ALADIN (Subsection
5.3).

The following equations will be used several times in the following proof.
They are provided here for convenience.

$\displaystyle g_{i}$ $\displaystyle=\rho(z-x_{i}^{+})-\lambda_{i},$ (26)
$\displaystyle\lambda_{i}^{+}$ $\displaystyle=\rho(x_{i}^{+}-z^{+})-g_{i},$
(27) $\displaystyle\sum_{i=1}^{N}\lambda_{i}$ $\displaystyle=0,$ (28)
$\displaystyle z^{+}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left(x_{i}^{+}-\frac{g_{i}}{\rho}\right),$
(29) $\displaystyle\sum_{i=1}^{N}x_{i}^{+}$
$\displaystyle=\frac{N}{2}(z^{+}+z),$ (30) $\displaystyle 2(a-c)^{\top}(a-b)$
$\displaystyle=\|a-c\|^{2}-\|b-c\|^{2}+\|a-b\|^{2}.$ (31)

Note that, by plugging Equation (26) and (27) into (29), (30) can be obtained.
Equation (31) comes from [11].

The following lemma will also be useful in our proofs.

######  Lemma 1.

With the procedure of Algorithm 1, the local primal update has a relationship
with the local dual and global primal variables in the following way

$x_{i}^{+}=\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}+\frac{z^{+}+z}{2}.$ (32)

###### Proof.

From Equation (27),

$\begin{split}\lambda_{i}^{+}&=\rho(x_{i}^{+}-z^{+})-g_{i}\\\
&\overset{\eqref{eq:
gradient}}{=}\rho(x_{i}^{+}-z^{+})-\rho(z-x_{i}^{+})+\lambda_{i}\\\
&=\rho(2x_{i}^{+}-z^{+}-z)+\lambda_{i}\\\ \
\Longleftrightarrow\quad&x_{i}^{+}=\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}+\frac{z^{+}+z}{2}.\end{split}$

∎

###  5.1 Global Convergence of Convex Case

The following global convergence proof relies on the _Lyapunov stability
theory_ in the control community. A relationship between the former and the
latter has been clarified in Appendix B.

We assume that the sub-functions $f_{i}$s are closed, proper, and strictly
convex. For establishing the global convergence theory of Reduced Consensus
ALADIN, we introduce the following _Lyapunov function_ [35] with the global
minimizer $z^{*}$.

$\mathscr{L}(z,\lambda)=\frac{1}{\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|^{2}+\rho
N\|z-z^{*}\|^{2}.$ (33)

Note that the choice of Lyapunov function is not unique. Next, we will prove
the global convergence of Reduced Consensus ALADIN by showing that the
Lyapunov function is monotonically decreasing.

######  Theorem 2.

Suppose $f_{i}$s are strictly convex and problem (4) has an existing solution
$z^{*}$, then

$\mathscr{L}(z,\lambda)-\mathscr{L}(z^{+},\lambda^{+})\geq\alpha\left(\|x_{i}^{+}-z^{*}\|\right)\geq
0$ (34)

will hold by applying Reduced Consensus ALADIN. Here, $\alpha$ is a class
$\mathcal{K}$ function [35].

###### Proof.

See Appendix C. ∎

According to Theorem 2, the global convergence of Reduced Consensus ALADIN can
be established. In order to prove the convergence of sequence $(z,\lambda)$ to
the global optimal solution pair $(z^{*},\lambda^{*})$, we need to show the
uniqueness of it.

######  Theorem 3.

We assume that Theorem 2 holds, which yields

$\left\\{\begin{split}\lim_{k\rightarrow\infty}z^{k}&=z^{*}\\\
\lim_{k\rightarrow\infty}\lambda^{k}&=\lambda^{*},\\\ \end{split}\right.$ (35)

where $k$ denotes the index of iterations.

###### Proof.

See Appendix D. ∎

The above two theorems show the convergence of $\left(z,\lambda\right)$.
Later, we will show $x_{i}$ is also convergent in the following theorem.

######  Theorem 4.

If Theorem 2 holds, then we have $x_{i}\rightarrow z^{*}$.

###### Proof.

See Appendix E. ∎

From the above three theorems, a convergence of the sub-gradients of the
agents can be also easily established.

######  Theorem 5.

We assume that Theorem 2, 3, and 4 hold jointly. Then, $g_{i}$ converges to
$-\lambda_{i}^{*}$ globally.

###### Proof.

See Appendix F. ∎

Note that the global convergence proof only requires the strict convexity of
objectives without smoothness and strongly convexity assumptions.

C-ALADIN, same as T-ALADIN, in case $f_{i}(x_{i})$s are only convex rather
than strictly convex, guarantees that the solutions can converge to an optimal
set instead of a single optimal solution, which will be theoretically analyzed
in Theorem 6.

######  Theorem 6.

Suppose that $\mathbb{Z}^{*}$ denotes the set of optimal primal solution and
$\mathbf{\Lambda}_{i}^{*}$ represents the optimal dual set, with
$\lambda_{i}^{*}\in\mathbf{\Lambda}_{i}^{*}$, we have $z$ converge to
$\mathbb{Z}^{*}$ globally,

$\lim_{z^{*}\in\mathbb{Z}^{*}}\left\|z-z^{*}\right\|=0.$

###### Proof.

Here the second auxiliary function in Equation (56) will be reduced to

$G(\xi)=\sum_{i=1}^{N}f_{i}(\xi_{i})+\sum_{i=1}^{N}(\xi_{i}-z^{*})^{\top}\lambda_{i}^{*}$
(36)

with $\lambda_{i}^{*}\in\mathbf{\Lambda}_{i}^{*}$ that
$\mathbf{\Lambda}_{i}^{*}$ is the optimal set of each dual variables which
means that they are not unique. In this way, Theorem 3 is not used in this
case.

However, if we apply the proof of Theorem 2 again here, the monotone
decreasing of the Lyapunov function still holds. In this case, we have a
similar result as [36]. ∎

Note that, no global convergence rate of convex optimization has been
discussed in the T-ALADIN research [36]. As an additional contribution
compared with the former, in the next subsection we will find the convergence
rate of convex cases by using Reduced Consensus ALADIN with some extra
technical assumptions.

###  5.2 Global Linear Convergence Rate Analysis

Next we will prove the Q-linear convergence rate [2] by adding additional
$m_{f}$ strongly convex or $\omega_{f}$ smooth assumptions.

######  Theorem 7.

Suppose that $\sum_{i=1}^{N}f_{i}(x_{i})$ is $m_{f}$ strongly convex, and
there exists a $\delta>0$ such that

$\delta\mathscr{L}(z^{+},\lambda^{+})\leq
4m_{f}\sum_{i=1}^{N}\left\|x_{i}^{+}-z^{*}\right\|^{2},$ (37)

then C-ALADIN is Q-linearly converging to a unique optimal solution with rate
$\left(\frac{1}{\sqrt{1+\delta}}\right)$.

###### Proof.

See Appendix G. ∎

In the Reduced Consensus ALADIN, we find the condition of $m_{f}$ strongly
convex and $\omega_{f}$ smooth are symmetric. Q-linearly convergent results
can also be established later.

######  Corollary 1.

Suppose that $\sum_{i=1}^{N}f_{i}(x_{i})$ is $\omega_{f}$ smooth and convex,
we have a similar result as Theorem 7, there exists a $\delta>0$ such that

$\delta\mathscr{L}(z^{+},\lambda^{+})\leq\frac{4}{\omega_{f}}\sum_{i=1}^{N}\left\|g_{i}-g_{i}^{*}\right\|^{2},$
(38)

then Reduced Consensus ALADIN can also Q-linearly converge to a unique optimal
solution with a rate $\left(\frac{1}{\sqrt{1+\delta}}\right)$.

###### Proof.

From the definition of $\omega_{f}$ Lipschitz continuous [2]

$\|g_{i}-g_{i}^{*}\|\leq\omega_{f}\|x_{i}^{+}-z^{*}\|,$ (39)

the following inequality can be obtained

$\begin{split}\frac{1}{\omega_{f}}\sum_{i=1}^{N}\|g_{i}-g_{i}^{*}\|^{2}\leq\sum_{i=1}^{N}\left(x_{i}^{+}-z^{*}\right)^{\top}\left(g_{i}-g_{i}^{*}\right).\end{split}$
(40)

Note that the right-hand side is the same equation as that of Equation (82).
Such that, the later proof is similar to Theorem 7 and is not shown here. ∎

Therefore, Reduced Consensus ALADIN needs either $m_{f}$ strongly convex or
$\omega_{f}$ Lipschitz continuous to establish the global Q-linear convergence
theory.

In the above two sections, we show the global convergence of Reduced Consensus
ALADIN has a similar property as ADMM. But different from the latter, in the
next section we will show local convergence analysis of non-convex cases of
C-ALADIN.

###  5.3 Local Convergence Analysis of Non-convex Case

The following convergence analysis depends on the assumption that $f_{i}$s are
twice continuously differentiable in a neighborhood of a local minimizer
$z^{*}$. To benefit from the theory of SQP [2, Chapter 18], in the
corresponding convergence analysis of C-ALADIN, we introduce $\gamma$ as the
upper bound of Hessian approximation difference
$\left\|B_{i}-\nabla^{2}f_{i}(x_{i})\right\|\leq\gamma$.

######  Theorem 8.

If $f_{i}$s are non-convex, C-ALADIN can still converge with sufficient large
$\rho$ with different convergence rate in different situations of $\gamma$.

###### Proof.

See Appendix H. ∎

Next, we will show the numerical performance of C-ALADIN.

##  6 Numerical Experiments

In this section, we illustrate the numerical performance of the proposed
algorithms on both distributed optimization (Subsection 6.1) and learning
(Subsection 6.2).

###  6.1  Case Studies on Distributed Consensus Optimization

In this subsection, all the implementation of algorithms relies on
Casadi-v3.5.5 with IPOPT [37].

The first case is a convex consensus least square problem

$\begin{split}\min_{x_{i},z}\;\;&\frac{1}{2}\sum_{i=1}^{N}\|x_{i}-\zeta_{i}\|_{2}^{2}\\\
\quad\mathrm{s.t.}\;\;&\;x_{i}=z\ |\lambda_{i}.\;\end{split}$ (41)

Here, $x_{i}\in\mathbb{R}^{100}$ and $N=200$. The measured data $\zeta_{i}$s
are drawn from the Gaussian distribution $\mathcal{N}(0,25)$. In this setting,
Problem (41) has $20100$ primal variables and $20000$ dual variables, which is
a large-scale optimization problem.

Figure 4: Numerical comparison on convex case.

In our implementation, the learning rate of FedSGD $\eta_{i}$s are set as
$0.01$ while other compared algorithms can update the local primal variables
with Casadi exactly. Moreover, the hyper-parameter $\rho$ is set as $10^{2}$
for other algorithms. Note that, all the initial values of primal and dual
variables are set as zeros vectors. In the optimization framework, we assume
that all the other algorithms can be solved exactly with local optimizer.

As the same setting, a distributed non-convex optimization problem can be
easily implemented as (42). Note that, excluding the second term of the
objective function, the non-convex optimization problem is directly reduced to
the convex one (41).

$\begin{split}\min_{x_{i},z}\;\;&\sum_{i=1}^{N}\frac{1}{2}\left(\|x_{i}^{a}-\zeta_{i}^{a}\|_{2}^{2}+\|x_{i}^{b}-\zeta_{i}^{b}\|_{2}^{2}\right)\\\
&\quad\;\;+\text{log}\left(\frac{1}{2}\|(x_{i}^{a}-x_{i}^{b})^{2}-\zeta_{i}^{c}\|_{2}^{2}\right)\\\
\quad\mathrm{s.t.}\;\;&\;x_{i}=z\ |\lambda_{i}\;\end{split}$ (42)

with $x_{i}=[(x_{i}^{a})^{\top},(x_{i}^{b})^{\top}]^{\top}$.

Figure 5: Numerical comparison on on nonconvex case.

Figure (4) and (5) illustrate the numerical convergence comparison among
several numerical algorithms for Problem (41) and (42) with iteration $k$.
Consensus BFGS ALADIN performs far superior to other algorithms according to
the given two numerical optimization cases (convex and non-convex). The
performance of Reduced Consensus ALADIN is also better than other existing
distributed algorithms. We didn’t compare with all the existing algorithms
such as Douglas-Rachford splitting (DRS) since they have similar performance
as ADMM in practice. In both cases, Consensus BFGS ALADIN can get a high
accuracy ($10^{-4}$) within $20$ iterations. This shows the importance of
second order information in distributed consensus optimization.

From the above results, we can easily observe the convergence trend of all the
evaluated algorithms. We want to stress that other algorithms do not have a
generalized convergence guarantee for non-convex problems.

###  6.2 Case Studies on Federated Learning

In this subsection, we illustrate the numerical performance of the proposed
algorithm in FL. Consensus BFGS ALADIN is not compared with other algorithms
in this subsection since second-order information is rarely used in the
community of FL. For fairness, our numerical comparison relays on the
implementation of recent work [25] with released code
https://github.com/ShenglongZhou/FedADMM. Here, we mainly focus on the
convergence rate and stability of the algorithm.

Different from the standard Consensus ADMM, the hyperparameter $\rho_{i}$s in
[25] are set to a different value, which means that the learning rate of each
sub-problem will be affected differently. Same as [25], here we first compared
performance algorithms on a convex linear regression problem with local
objectives (43) and non-i.i.d. data.

$f_{i}(x)=\sum_{t\in\mathcal{D}_{i}}\frac{1}{2d_{i}}((a_{i}^{t})^{\top}x-b_{i}^{t})^{2}.$
(43)

Here $a_{i}^{t}\in\mathbb{R}^{100}$ and $b_{i}^{t}\in\mathbb{R}$ are the
$t$-th sample data of client $i$. We set $x\in\mathbb{R}^{100}$ and $N=100$.
Another example is a non-convex logistic regression with sub-objectives (44).

$f_{i}(x)=\frac{1}{|\mathcal{D}_{i}|}\sum_{t\in\mathcal{D}_{i}}\left(\text{ln}\left(1+e^{(a_{i}^{t})^{\top}x}\right)-b_{i}(a_{i}^{t})^{\top}x\right)+\frac{\lambda}{2}\|x\|^{2}.$
(44)

Here $a\in\mathbb{R}^{1024}$, $b\in\\{0,1\\}$, $\lambda=0.001$,
$x\in\mathbb{R}^{1024}$ and also with $100$ clients. Importantly, each client
has a participation rate and is set as $0.1$. The rest of the technical
details can be referred to [25, Section 5]. For fairness, we have no other
updates.

Figure 6: Linear regression with different $\rho$ (convex problem).

Figure 7: Logistic regression with different $\rho$ (nonconvex problem).

Figure (7) and (7) show the numerical comparison on the linear regression and
logistic regression problems respectively. Here, FedADMM1 represents the
method proposed by [25] that update the dual before global aggregation.
FedADMM2, follows the order as [38]. The convergence performance of the two
schemes is very different in logistic regression problem. It has to be pointed
out that, in the optimization setting, there is only a little difference in
performance between the two ADMM variations mentioned above, but in this
experiment, we can see that they behave completely differently. This once
again illustrates the fundamental difference between locally exact or
inexactly search of the local primal variables. While this paper does not
address this issue theoretically in C-ALADIN family, it still points out that
it is an open question worthy of attention.

Figure 8: Linear regression with the same $\rho$ (convex problem).

Figure 9: Logistic regression with with same $\rho$ (nonconvex problem).

For further discussion, as shown in Figure (9) and (9), we find that when the
hyperparameter $\rho$ is set to the same value ($\rho=0.5$ for linear
regression and $0.05$ for logistic regression). With a learning rate
$\eta=0.01$ for all the algorithms, the convergence performance of FedALADIN
is far better than the existing algorithms at least in these two examples. In
addition, we found that FedADMM2 is not stably converged in the first several
iterations.

##  7 Related Work

Existing distributed convex optimization algorithms can be roughly divided
into two types: primal decomposition (PD) [39, 40, 41] and DD (also called
Lagrangian decomposition). We refer [42, 43, 44, 45] as references for more
details.

PD aims to partition the problem in a lower-upper level fashion, where the
upper-level problem considers the lower-higher level problems by their optimal
value functions which means control the private variables directly. Different
from the former, the higher level problem influence the lower level ones by
using dual variables (shadow price) in the DD structure. To the best of our
knowledge, only few literature studied the theoretical comparison between PD
and DD. However, numerically, [43, 44] showed that DD performances a better
convergence rate compare with PD, however the degree of stability of
convergence is the opposite in some applications. A discussion can be found in
[46, Section I]. The efforts in PD and DD can be further categorized into the
following two fashions, namely exact search and inexact search. Exact search
comes from the optimization community while inexact search is drawn from the
FL community.

In the PD family, representative algorithms of exact search are DGD [13] and
EXTRA [14]. On the inexact search side, FedSGD [15], FedAvg [8], FedProx [22]
and FedDANE [23] were proposed.

In the DD family, current techniques, consisting of consensus ADMM [38] and
DD, only focus on distributed convex problems with exact search. In contrast,
our proposed C-ALADIN has guarantee for non-convex problems. On the inexact
search side, the state-of-the-art algorithm is FedADMM [24, 25, 47]. Our
proposed FedALADIN extends this line of work by showing a more stable
convergence performance than FedADMM.

TABLE I: Existing and our proposed algorithms for DC. Methods |  Primal Decomposition |  Dual Decomposition
---|---|---
Exact |  DGD [13], |  Consensus ADMM [3],
Search |  EXTRA [14], NIDS [48] |  DD [10], C-ALADIN
Inexact |  FedSGD[15], FedDANE [23], |  FedADMM [25, 47],
Search |  FedProx [22], FedAVG[8] |  FedALADIN

##  8 Conclusion $\&$ Outlook

This paper proposed a novel distributed consensus algorithm family, named
C-ALADIN, that is efficient in solving non-convex problems. In the framework
of C-ALADIN, we proposed efficient structure for communication and computation
efficiency. Based on the framework, depending on whether second order
information is used, two variants of C-ALADIN are proposed, named Consensus
BFGS ALADIN and Reduced Consensus ALADIN respectively. Finally, to serve the
FL community, we compare a variant of Reduced Consensus ALADIN named FedALADIN
with existing method in FL. It performs well with several case studies.

Other variants of C-ALADIN will be considered in the future to accommodate
different types of optimization problems. More importantly, the convergence
theory with local inexactly search in C-ALADIN is still lacking. Such
theoretical supplement will assist the algorithm to be applied in more complex
neural networks.

## References

  * [1] Boris Houska, Janick Frasch, and Moritz Diehl.  An augmented lagrangian based algorithm for distributed nonconvex optimization.  SIAM Journal on Optimization, 26(2):1101–1127, 2016.
  * [2] Jorge Nocedal and Stephen Wright.  Numerical optimization.  Springer Science & Business Media, New York, 2006.
  * [3] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Found. Trends Mach. Learn., 3(1):1–122, 2011.
  * [4] Moritz Diehl and Sébastien Gros.  Numerical optimal control.  Optimization in Engineering Center (OPTEC), 2011.
  * [5] Jizhong Zhu.  Optimization of power system operation.  John Wiley & Sons, 2015.
  * [6] Emil Björnson, Jakob Hoydis, Luca Sanguinetti, et al.  Massive mimo networks: Spectral, energy, and hardware efficiency.  Foundations and Trends® in Signal Processing, 11(3-4):154–655, 2017.
  * [7] Zhu Han, Dusit Niyato, Walid Saad, and Tamer Başar.  Game theory for next generation wireless and communication networks: Modeling, analysis, and design.  Cambridge University Press, 2019.
  * [8] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [9] George B Dantzig and Philip Wolfe.  Decomposition principle for linear programs.  Operations research, 8(1):101–111, 1960.
  * [10] Hugh Everett III.  Generalized lagrange multiplier method for solving problems of optimum allocation of resources.  Operations research, 11(3):399–417, 1963.
  * [11] Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin.  On the linear convergence of the admm in decentralized consensus optimization.  IEEE Transactions on Signal Processing, 62(7):1750–1761, 2014.
  * [12] Yu Yang, Xiaohong Guan, Qing-Shan Jia, Liang Yu, Bolun Xu, and Costas J Spanos.  A survey of admm variants for distributed optimization: Problems, algorithms and features.  arXiv preprint arXiv:2208.03700, 2022.
  * [13] Kun Yuan, Qing Ling, and Wotao Yin.  On the convergence of decentralized gradient descent.  SIAM Journal on Optimization, 26(3):1835–1854, 2016.
  * [14] Wei Shi, Qing Ling, Gang Wu, and Wotao Yin.  Extra: An exact first-order algorithm for decentralized consensus optimization.  SIAM Journal on Optimization, 25(2):944–966, 2015.
  * [15] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International conference on machine learning, pages 448–456. pmlr, 2015.
  * [16] A. Engelmann, Y. Jiang, T. Mühlpfordt, B. Houska, and T. Faulwasser.  Toward distributed OPF using ALADIN.  IEEE Transactions on Power Systems, 34(1):584–594, 2019.
  * [17] X. Du, A. Engelmann, Y. Jiang, T. Faulwasser, and B. Houska.  Distributed state estimation for AC power systems using Gauss-Newton ALADIN.  In In Proceedings of the 58th IEEE Conference on Decision and Control, pages 1919–1924, 2019.
  * [18] Boris Houska, Dimitris Kouzoupis, Yuning Jiang, and Moritz Diehl.  Convex optimization with aladin.  Optimization Online preprint, 2017.
  * [19] Boris Houska and Jiahe Shi.  Distributed mpc with aladin- a tutorial.  In 2022 American Control Conference (ACC), pages 358–363. IEEE, 2022.
  * [20] J. Shi, Y. Zheng, Y. Jiang, M. Zanon, R. Hult, and B. Houska.  Distributed control algorithm for vehicle coordination at traffic intersections.  In In Proceedings of the 17th European Control Conference, Limassol, Cyprus, pages 1166–1171, 2018.
  * [21] Y. Jiang, J. Su., Y. Shi, and B. Houska.  Distributed optimization for massive connectivity.  IEEE Wireless Communciation Letters, 9(9):1412–1416, 2020.
  * [22] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.  Federated optimization in heterogeneous networks.  Proceedings of Machine learning and systems, 2:429–450, 2020.
  * [23] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy.  Feddane: A federated newton-type method.  In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 1227–1231. IEEE, 2019.
  * [24] Shenglong Zhou and Geoffrey Ye Li.  Communication-efficient admm-based federated learning.  arXiv preprint arXiv:2110.15318, 2021.
  * [25] Shenglong Zhou and Geoffrey Ye Li.  Federated learning via inexact admm.  arXiv preprint arXiv:2204.10607, 2022.
  * [26] Qing Ling, Wei Shi, Gang Wu, and Alejandro Ribeiro.  Dlm: Decentralized linearized alternating direction method of multipliers.  IEEE Transactions on Signal Processing, 63(15):4051–4064, 2015\.
  * [27] Aryan Mokhtari, Wei Shi, Qing Ling, and Alejandro Ribeiro.  Dqm: Decentralized quadratically approximated alternating direction method of multipliers.  IEEE Transactions on Signal Processing, 64(19):5158–5173, 2016\.
  * [28] B. Houska, J. Frasch, and M. Diehl.  An augmented Lagrangian based algorithm for distributed nonconvex optimization.  SIAM Journal on Optimization, 26(2):1101–1127, 2016.
  * [29] Hans Joachim Ferreau, Christian Kirches, Andreas Potschka, Hans Georg Bock, and Moritz Diehl.  qpoases: A parametric active-set algorithm for quadratic programming.  Mathematical Programming Computation, 6(4):327–363, 2014.
  * [30] Mosek ApS.  Mosek optimization toolbox for matlab.  User?s Guide and Reference Manual, Version, 4:1, 2019.
  * [31] LLC Gurobi Optimization.  Gurobi optimizer reference manual, 2018.
  * [32] Jacob Mattingley and Stephen Boyd.  Cvxgen: A code generator for embedded convex optimization.  Optimization and Engineering, 13(1):1–27, 2012.
  * [33] E Michael Gertz and Stephen J Wright.  Object-oriented software for quadratic programming.  ACM Transactions on Mathematical Software (TOMS), 29(1):58–81, 2003\.
  * [34] B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd.  OSQP: an operator splitting solver for quadratic programs.  Mathematical Programming Computation, 12(4):637–672, 2020.
  * [35] Hassan K Khalil.  Nonlinear control, volume 406.  Pearson New York, 2015.
  * [36] Boris Houska and Yuning Jiang.  Distributed optimization and control with aladin.  Recent Advances in Model Predictive Control: Theory, Algorithms, and Applications, pages 135–163, 2021.
  * [37] J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl.  CasADi – a software framework for nonlinear optimization and optimal control.  Mathematical Programming Computation, 11(1):1–36, 2019.
  * [38] Stephen Boyd, Neal Parikh, and Eric Chu.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Now Publishers Inc, 2011.
  * [39] Arthur M Geoffrion.  Primal resource-directive approaches for optimizing nonlinear decomposable systems.  Operations Research, 18(3):375–403, 1970.
  * [40] Victor DeMiguel and Francisco J Nogales.  On decomposition methods for a class of partially separable nonlinear programs.  Mathematics of Operations Research, 33(1):119–139, 2008.
  * [41] Alexander Engelmann, Sungho Shin, François Pacaud, and Victor M Zavala.  Scalable primal decomposition schemes for large-scale infrastructure networks.  arXiv preprint arXiv:2212.11571, 2022.
  * [42] Stephen Boyd, Lin Xiao, Almir Mutapcic, and Jacob Mattingley.  Notes on decomposition methods.  Notes for EE364B, Stanford University, 635:1–36, 2007.
  * [43] Håkan Terelius.  Distributed multi-agent optimization via dual decomposition, 2010.
  * [44] Peter Pflaum, Mazen Alamir, and Mohamed Yacine Lamoudi.  Comparison of a primal and a dual decomposition for distributed mpc in smart districts.  In 2014 IEEE international conference on smart grid communications (SmartGridComm), pages 55–60. IEEE, 2014.
  * [45] Daniel Pérez Palomar and Mung Chiang.  A tutorial on decomposition methods for network utility maximization.  IEEE Journal on Selected Areas in Communications, 24(8):1439–1451, 2006.
  * [46] Qing Ling, Wei Shi, Gang Wu, and Alejandro Ribeiro.  Dlm: Decentralized linearized alternating direction method of multipliers.  IEEE Transactions on Signal Processing, 63(15):4051–4064, 2015\.
  * [47] Bin Wang, Jun Fang, Hongbin Li, Xiaojun Yuan, and Qing Ling.  Confederated learning: Federated learning with decentralized edge servers.  arXiv preprint arXiv:2205.14905, 2022.
  * [48] Zhi Li, Wei Shi, and Ming Yan.  A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates.  IEEE Transactions on Signal Processing, 67(17):4494–4506, 2019\.
  * [49] Dimitri P Bertsekas.  Nonlinear programming.  Journal of the Operational Research Society, 48(3):334–334, 1997\.
  * [50] Qiujiang Jin, Alec Koppel, Ketan Rajawat, and Aryan Mokhtari.  Sharpened quasi-newton methods: Faster superlinear rate and larger local convergence neighborhood.  In International Conference on Machine Learning, pages 10228–10250. PMLR, 2022.

##  Appendix A Comparison between Reduced Consensus ALADIN and Consensus ADMM

In the standard Consensus ADMM framework, there are two different cases: a)
first update the dual then aggregate (update the primal global variable), b)
first aggregate then update the dual. In this subsection we will analyze the
Reduced Consensus ALADIN from the above two perspectives. In order to
distinguish the Reduced Consensus ALADIN from the Consensus ADMM, we use
superscripts on key variables, such as $\lambda_{i}$ and $z$, to show
difference.

###  A.1 First Update the Dual then Aggregate

Algorithm 1 shows the first fashion of Consensus ADMM: first update the dual
then aggregate (45). In the optimization point of view, FedADMM is a
modification of the current fashion.

$\left\\{\begin{split}&{x_{i}}^{+}=\mathop{\arg\min}_{x_{i}}f_{i}(x_{i})+(\lambda_{i}^{\text{ADMM1}})^{\top}x_{i}+\frac{\rho}{2}\|x_{i}-z\|^{2},\\\
&(\lambda_{i}^{\text{ADMM1}})^{+}=(\lambda_{i}^{\text{ADMM1}})+\rho(x_{i}^{+}-z),\\\
&(z^{+})^{\text{ADMM1}}=\frac{1}{N}\sum_{i=1}^{N}\left(x_{i}^{+}+\frac{(\lambda_{i}^{\text{ADMM1}})^{+}}{\rho}\right).\\\
\end{split}\right.$ (45)

Here $\lambda_{i}^{\text{ADMM1}}$ denotes the dual variables of the current
Consensus ADMM fashion. From the expression of the subgradients (24), one may
find

$\lambda_{i}^{\text{ADMM1}}=-g_{i}.$ (46)

It can be noticed that the framework of Reduced Consensus ALADIN is very
similar to this order of (45) . In Reduced Consensus ALADIN, Equation (10)
boils down to

$\begin{split}(z^{+}_{\rho})^{\text{ALADIN}}=\mathop{\mathrm{\arg}\mathrm{\min}}_{\Delta
x_{i},z}&\quad\mathop{\sum}_{i=1}^{N}\left(\frac{\rho}{2}\Delta
x_{i}^{\top}\Delta x_{i}+g_{i}^{\top}\Delta x_{i}\right)\\\
\mathrm{s.t.}&\qquad\Delta
x_{i}+x_{i}^{+}=z\;|\lambda_{i}^{\text{ALADIN}}\end{split}$ (47)

which is equivalent to the same operation as that of ADMM framework (if we
ignore the auxiliary variables $\Delta x_{i}$s)

$\begin{split}(z^{+})^{\text{ADMM1}}=&\mathop{\mathrm{\arg}\mathrm{\min}}_{z}\;\mathop{\sum}_{i=1}^{N}\left(\frac{\rho}{2}\|x_{i}^{+}-z\|^{2}-(\lambda_{i}^{\text{ADMM1}})^{\top}z\right).\end{split}$
(48)

In both ways of updating the global variable $z$, Equation (47) and (48), have
the same result as Equation (20). However, the dual update is different in
C-ALADIN (49),

$\lambda_{i}^{\text{ALADIN}}=\rho(x_{i}^{-}-z)-g_{i}.$ (49)

Different from Reduced Consensus ALADIN, in the Consensus ADMM iteration (45),

$\sum_{i=1}^{N}(\lambda_{i}^{\text{ADMM1}})^{*}=0$ (50)

is guaranteed only at the optimal point. On the opposite, with Reduced
Consensus ALADIN (49),

$\sum_{i=1}^{N}\lambda_{i}^{\text{ALADIN}}=0$ (51)

is guaranteed in each iteration. Since the first version of Consensus ADMM can
not bring the latest dual update back to each agent, the updating rule of the
dual in Reduced Consensus ALADIN can be interpreted as a more efficient way
for local primal variable update. The Reduced Consensus ALADIN framework makes
better use of the consensus dual information.

###  A.2 First Aggregate then Update the Dual

As introduced in [3], Consensus ADMM can also be interpreted in another
fashion:

$\left\\{\begin{split}&{x_{i}}^{+}=\mathop{\arg\min}_{x_{i}}f_{i}(x_{i})+(\lambda_{i}^{\text{ADMM2}})^{\top}x_{i}+\frac{\rho}{2}\|x_{i}-z\|^{2},\\\
&(z^{+})^{\text{ADMM2}}=\frac{1}{N}\sum_{i=1}^{N}\left(x_{i}^{+}+\frac{\lambda_{i}^{\text{ADMM2}}}{\rho}\right),\\\
&(\lambda_{i}^{\text{ADMM2}})^{+}=(\lambda_{i}^{\text{ADMM2}})+\rho(x_{i}^{+}-z^{+}).\end{split}\right.$
(52)

With (52), Consensus ADMM can also converge for convex problems with
guarantees. In this form, the update of $\lambda_{i}^{\text{ADMM2}}$s has the
same property as Reduced Consensus ALADIN that guarantees

$\sum_{i=1}^{N}\lambda_{i}^{\text{ADMM2}}=0$ (53)

in each iteration. In this way, the dual variables can also carry sensitivity
information of the gap between the latest global variable $z$ and the local
variables $x_{i}^{+}$. However, the second version of Consensus ADMM can not
upload the latest local dual (46) back to the master because of (53). Reduced
Consensus ALADIN is more efficient for global variable aggregation compare
with (52).

Even without Hessian information updated, the Reduced Consensus ALADIN can
still inherit both of the benefits of two different Consensus ADMM variations.
In fact, it can be treated as a combination of the them. The new designed
structure provides both latest information of the dual to the agents and the
master.

##  Appendix B  Preliminaries of the Lyapunov Stability Theory

In this section, we demonstrate the intuition of proving the global
convergence of C-ALADIN (Subsection 5.1 and 5.2). Roughly, we adopt the theory
of _Lyapunov stability_ in control community [35] for nonlinear systems. The
rationale behind such is that the concept of _global convergence_ in
optimization has a similarity as _stable around the origin_ in control.

We assume that a nonlinear system is described by
$\dot{\varsigma}=\phi(\varsigma)$ where $\varsigma$ is the state variable and
$\phi(\cdot)$ is a nonlinear mapping from
$\mathbb{R}^{|\varsigma|}\rightarrow\mathbb{R}^{|\varsigma|}$ which denotes
the dynamic of a system. Here we introduce an unbounded mapping, named
Lyapunov function

$\Phi(\varsigma):\mathbb{R}^{|\varsigma|}\rightarrow\mathbb{R}$ (54)

$\Phi(\varsigma)$ has the following key properties:

  * •

$\Phi(\varsigma)$ is strictly monotonically decreasing along the trajectories
of the system, in other words $\dot{\Phi}=\nabla_{x}\Phi^{\top}\phi<0$.

  * •

$\Phi(\varsigma)>0$ if $\varsigma\neq 0$; otherwise, $\Phi(\varsigma)=0$.

With the above properties, we have the following theorem.

######  Theorem 9.

If $\Phi$ is positive definite, bounded from below, and strictly monotonically
decreasing, then $\varsigma$ is bounded and converges to $0$ (stable around
the origin) [35].

###### Proof.

We next prove that $\varsigma\rightarrow 0$ by showing the following
contradiction:

We assume that $\varsigma$ is not convergent to $0$, then we have
$\dot{\Phi}<0$. From the fundamental theorem of calculus, we then have

$\Phi(\varsigma^{0})\geq\Phi(\varsigma^{\infty})=\Phi(\varsigma^{0})+\underbrace{\int_{0}^{\infty}\dot{\Phi}(\varsigma)}_{<0}=-\infty.$
(55)

However, this shows a contradiction to the positive definiteness of and
bounded below of $\Phi$. Hence we have

$\Phi(\varsigma)\rightarrow 0\quad\text{which
implies}\quad\varsigma\rightarrow 0.$

∎

Theorem 9 states that the system under analysis is stable when the correlation
property of the related Lyapunov function holds. Note that the existence of a
Lyapunov function is only a sufficient condition to prove the stability around
the origin. However we can not confirm that the system is unstable if we can
not find a proper Lyapunov function. In our proof, if we treat the
optimization algorithms as the nonlinear dynamic $\phi(\varsigma)$ of the
control systems, and the gap between the decision variable and the optimizer
as the state $\varsigma$, then the _stable around the origin_ analysis is
equivalent to prove the _global convergence_ of optimization algorithms.

##  Appendix C Proof of Theorem 2

###### Proof.

First we introduce two auxiliary functions $\tilde{f}_{i}$ and $G(\xi)$:

$\left\\{\begin{split}\tilde{f}_{i}(\xi_{i})&=f_{i}(\xi_{i})+(\lambda_{i}+\rho(x_{i}^{+}-z))^{\top}\xi_{i}\\\
G(\xi)&=\sum_{i=1}^{N}f_{i}(\xi_{i})+\sum_{i=1}^{N}(\xi_{i}-z^{*})^{\top}\lambda_{i}^{*}.\end{split}\right.$
(56)

Assume $f_{i}$s are strictly convex, then we have

$\left\\{\begin{split}\tilde{f}_{i}(x_{i}^{+})&\leq\tilde{f}_{i}(z^{*})-\tilde{\alpha}_{i}(\|x_{i}^{+}-z^{*}\|)\\\
G(z^{*})&\leq G(x^{+})-\hat{\alpha}(\|x_{i}^{+}-z^{*}\|)\end{split}\right.$
(57)

where $\tilde{\alpha}_{i}(\cdot)$ and $\hat{\alpha}(\cdot)$ are class
$\mathcal{K}$ functions. If we sum up the first equation of (57),

$\begin{split}\sum_{i=1}^{N}\left\\{f_{i}(x_{i}^{+})-f_{i}(z^{*})\right\\}\leq&\sum_{i=1}^{N}\left\\{(\lambda_{i}^{+}+\rho(x_{i}^{+}-z))^{\top}(z^{*}-x_{i}^{+})\right\\}\\\
&-\sum_{i=1}^{N}\tilde{\alpha}_{i}(\|x_{i}^{+}-z^{*}\|).\end{split}$ (58)

Similarly, from the fact that

$\begin{split}G(z^{*})-G(z^{+})&\leq 0\\\ \end{split}$

we have

$\begin{split}\sum_{i=1}^{N}\left\\{f_{i}(z^{*})-f_{i}(x_{i}^{+})\right\\}\leq&\sum_{i=1}^{N}(x_{i}^{+}-z^{*})^{\top}\lambda_{i}^{*}\\\
&-\hat{\alpha}(\|x_{i}^{+}-z^{*}\|).\end{split}$ (59)

Combine Equations (58) and (59), we have

$\sum_{i=1}^{N}(\lambda_{i}^{+}-\lambda_{i}^{*}+\rho(x_{i}^{+}-z))^{\top}(x_{i}^{+}-z^{*})\leq-\alpha(\|x_{i}^{+}-z^{*}\|)$
(60)

where

$\alpha(\|x_{i}^{+}-z^{*}\|)=\hat{\alpha}(\|x_{i}^{+}-z^{*}\|)+\sum_{i=1}^{N}\tilde{\alpha}_{i}(\|x_{i}^{+}-z^{*}\|)\in\mathcal{K}.$

The left hand side of Equation (60) can be interpreted as

$\begin{split}&\sum_{i=1}^{N}(\lambda_{i}-\lambda_{i}^{*}+\rho(x_{i}^{+}-z))^{\top}(x_{i}^{+}-z^{*})\\\
\overset{\eqref{eq:
sum_lam}}{=}&\sum_{i=1}^{N}(\lambda_{i}-\lambda_{i}^{*})^{\top}(x_{i}^{+}-z)+\rho(x_{i}^{+}-z)^{\top}(x_{i}^{+}-z^{*})\\\
\overset{\eqref{eq:
primal}}{=}&\sum_{i=1}^{N}\left(\lambda_{i}-\lambda_{i}^{*}+\rho\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}+\frac{z^{+}+z}{2}-z^{*}\right)\right)^{\top}\\\
&\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}+\frac{z^{+}+z}{2}-z\right).\end{split}$
(61)

By trivially decomposing Equation (61), we get the following six parts

  * Part 1

$\begin{split}&\sum_{i=1}^{N}\left(\lambda_{i}-\lambda_{i}^{*}\right)^{\top}\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)\\\
\overset{\eqref{eq: quadratic
equality}}{=}&\frac{-1}{4\rho}\sum_{i=1}^{N}\left(\|\lambda_{i}-\lambda_{i}^{*}\|^{2}-\|\lambda_{i}^{+}-\lambda_{i}^{*}\|^{2}+\|\lambda_{i}-\lambda_{i}^{+}\|^{2}\right).\end{split}$
(62)

  * Part 2

$\begin{split}\sum_{i=1}^{N}\rho\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)^{\top}\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)=\frac{1}{4\rho}\sum_{i=1}^{N}\|\lambda_{i}^{+}-\lambda_{i}\|^{2}.\end{split}$
(63)

  * Part 3

$\sum_{i=1}^{N}\rho\left(\frac{z^{+}+z}{2}-z^{*}\right)^{\top}\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)\overset{\eqref{eq:
sum_lam}}{=}0.$ (64)

  * Part 4

$\sum_{i=1}^{N}\left(\lambda_{i}-\lambda_{i}^{*}\right)^{\top}\left(\frac{z^{+}-z}{2}\right)\overset{\eqref{eq:
sum_lam}}{=}0.$ (65)

  * Part 5

$\sum_{i=1}^{N}\rho\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)^{\top}\left(\frac{z^{+}-z}{2}\right)\overset{\eqref{eq:
sum_lam}}{=}0.$ (66)

  * Part 6

$\begin{split}&\rho
N\left(\frac{z^{+}+z}{2}-z^{*}\right)^{\top}\left(\frac{z^{+}-z}{2}\right)\\\
=&\frac{\rho N}{4}\|z^{+}-z^{*}\|^{2}-\frac{\rho N}{4}\|z-z^{*}\|^{2}.\\\
\end{split}$ (67)

In the end, the combination of the above six parts gives us:

$\begin{split}&\sum_{i=1}^{N}(\lambda_{i}-\lambda_{i}^{*}+\rho(x_{i}^{+}-z))^{\top}(x_{i}^{+}-z^{*})\\\
=&\frac{1}{4\rho}\sum_{i=1}^{N}\left(-\|\lambda_{i}-\lambda_{i}^{*}\|^{2}+\|\lambda_{i}^{+}-\lambda_{i}^{*}\|^{2}\right)\\\
&+\frac{\rho N}{4}\|z^{+}-z^{*}\|^{2}-\frac{\rho N}{4}\|z-z^{*}\|^{2}\\\
=&\frac{1}{4}\mathscr{L}(z^{+},\lambda^{+})-\frac{1}{4}\mathscr{L}(z,\lambda)\leq-\alpha(\|x_{i}^{+}-z^{*}\|)\leq
0.\end{split}$ (68)

This says that the introduced Lyapunov function is monotonically decreasing. ∎

##  Appendix D Proof of Theorem 3

###### Proof.

As we have proved, $\mathscr{L}(z,\lambda)\geq\mathscr{L}(z^{+},\lambda^{+})$
and $\mathscr{L}(z,\lambda)$ is bounded below.

We assume that the sequence pair $(x_{i},\lambda_{i})$ has at least two limit
points $(z^{\alpha},\lambda_{i}^{\alpha})$ and
$(z^{\beta},\lambda_{i}^{\beta})$, such that

$\left\\{\begin{split}\mathscr{L}^{\alpha}(z,\lambda)=\frac{1}{\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{\alpha}\|^{2}+\rho
N\|z-z^{\alpha}\|^{2}\\\
\mathscr{L}^{\beta}(z,\lambda)=\frac{1}{\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{\beta}\|^{2}+\rho
N\|z-z^{\beta}\|^{2}.\end{split}\right.$ (69)

We hypothesize that they may converge to different value

$\left\\{\begin{split}\lim_{k\rightarrow\infty}\mathscr{L}^{\alpha}(z,\lambda)=L^{\alpha}\\\
\lim_{k\rightarrow\infty}\mathscr{L}^{\beta}(z,\lambda)=L^{\beta}.\end{split}\right.$
(70)

Note that

$\begin{split}&\mathscr{L}^{\alpha}(z,\lambda)-\mathscr{L}^{\beta}(z,\lambda)\\\
=&\rho N\left(\|z-z^{\alpha}\|^{2}-\|z-z^{\beta}\|^{2}\right)\\\
&+\frac{1}{\rho}\sum_{i=1}^{N}\left(\|\lambda_{i}-\lambda_{i}^{\alpha}\|^{2}-\|\lambda_{i}-\lambda_{i}^{\beta}\|^{2}\right).\end{split}$
(71)

For the first part,

$\begin{split}&\rho N\left(\|z-z^{\alpha}\|^{2}-\|z-z^{\beta}\|^{2}\right)\\\
=&\rho
N\left(\left(z^{\alpha}-z^{\beta}\right)^{\top}\left(z^{\alpha}+z^{\beta}-2z\right)\right).\\\
\end{split}$ (72)

Similarly, the second part can be expressed as

$\begin{split}&\frac{1}{\rho}\sum_{i=1}^{N}\left(\|\lambda_{i}-\lambda_{i}^{\alpha}\|^{2}-\|\lambda_{i}-\lambda_{i}^{\beta}\|^{2}\right)\\\
=&\frac{1}{\rho}\sum_{i=1}^{N}\left(\left(\lambda_{i}^{\alpha}-\lambda_{i}^{\beta}\right)^{\top}\left(\lambda_{i}^{\alpha}+\lambda_{i}^{\beta}-2\lambda_{i}\right)\right).\end{split}$
(73)

Therefore,

$\begin{split}&\mathscr{L}^{\alpha}(z,\lambda)-\mathscr{L}^{\beta}(z,\lambda)\\\
=&\rho
N\left(\left(z^{\alpha}-z^{\beta}\right)^{\top}\left(z^{\alpha}+z^{\beta}-2z\right)\right)\\\
&+\frac{1}{\rho}\sum_{i=1}^{N}\left(\left(\lambda_{i}^{\alpha}-\lambda_{i}^{\beta}\right)^{\top}\left(\lambda_{i}^{\alpha}+\lambda_{i}^{\beta}-2\lambda_{i}\right)\right).\end{split}$
(74)

Suppose $(x_{i},\lambda_{i})$ converges to
$(z^{\alpha},\lambda_{i}^{\alpha})$, then we take limit on both sides

$\begin{split}&\mathscr{L}^{\alpha}-\mathscr{L}^{\beta}\\\ \rightarrow&\rho
N\left(\left(z^{\alpha}-z^{\beta}\right)^{\top}\left(z^{\alpha}+z^{\beta}-2z^{\alpha}\right)\right)\\\
&+\frac{1}{\rho}\sum_{i=1}^{N}\left(\left(\lambda_{i}^{\alpha}-\lambda_{i}^{\beta}\right)^{\top}\left(\lambda_{i}^{\alpha}+\lambda_{i}^{\beta}-2\lambda_{i}^{\alpha}\right)\right)\\\
=&-\rho
N\left\|z^{\alpha}-z^{\beta}\right\|^{2}-\frac{1}{\rho}\sum_{i=1}^{N}\left\|\lambda_{i}^{\alpha}-\lambda_{i}^{\beta}\right\|^{2}.\end{split}$
(75)

On the opposite, if $(x_{i},\lambda_{i})$ converges to
$(z^{\beta},\lambda_{i}^{\beta})$, then we take another limit

$\begin{split}&\mathscr{L}^{\alpha}-\mathscr{L}^{\beta}\rightarrow\rho
N\left\|z^{\alpha}-z^{\beta}\right\|^{2}+\frac{1}{\rho}\sum_{i=1}^{N}\left\|\lambda_{i}^{\alpha}-\lambda_{i}^{\beta}\right\|^{2}.\end{split}$
(76)

From (75) and (76),

$\rho
N\left\|z^{\alpha}-z^{\beta}\right\|^{2}+\frac{1}{\rho}\sum_{i=1}^{N}\left\|\lambda_{i}^{\alpha}-\lambda_{i}^{\beta}\right\|^{2}=0.$

This will induce $z^{\alpha}=z^{\beta}$ and
$\lambda_{i}^{\alpha}=\lambda_{i}^{\beta}$. Therefore, the limit point of
$(z,\lambda)$ is unique. The optimal solution $(z^{*},\lambda_{i}^{*})$ will
be obtained if $\mathscr{L}(z,\lambda)=0$ is touched.

∎

##  Appendix E Proof of Theorem 4

###### Proof.

We assume that $x_{i}^{0}$s starts from a small neighbor of $z^{*}$. From the
first order convergence condition of optimality of Equation (11), one may
obtain

$\left\\{\begin{array}[]{l}\begin{split}\nabla
f_{i}(x_{i}^{+})+\lambda_{i}+\rho(x_{i}^{+}-z)&=0\quad\\\ \nabla
f_{i}(z^{*})+\lambda_{i}^{*}&=0.\end{split}\end{array}\right.$ (77)

Then do minus with the two equations:

$\nabla f_{i}(z^{*})-\nabla
f_{i}(x_{i}^{+})+(\lambda_{i}^{*}-\lambda_{i})-\rho(x_{i}^{+}-z)=0.$

By rearranging the formula:

$\nabla f_{i}(z^{*})-\nabla
f_{i}(x_{i}^{+})+\rho(z^{*}-x_{i}^{+})=\rho(z^{*}-z)+(\lambda_{i}-\lambda_{i}^{*}).$
(78)

From the _second order sufficient condition_ of each sub-problems, there exist
a $\sigma$ such that

$\left(\nabla^{2}f_{i}(x_{i}^{+})+\rho I\right)\succeq\sigma I\succeq 0,$

which implies

$\|\nabla^{2}f_{i}(x_{i}^{+})+\rho I\|\succeq\sigma.$

In the end,

$\|\nabla f_{i}(z^{*})-\nabla
f_{i}(x_{i}^{+})+\rho(z^{*}-x_{i}^{+})\|\geq\sigma\|z^{*}-x_{i}^{+}\|.$ (79)

Substituting the left hand side by the right hand side of Equation (78), then
plug into Equation (79):

$\begin{split}\|\rho(z^{*}-z)+(\lambda_{i}-\lambda_{i}^{*})\|&\geq\sigma\|z^{*}-x_{i}^{+}\|\\\
\Rightarrow\frac{\rho}{\sigma}\|z-z^{*}\|+\frac{1}{\sigma}\|\lambda_{i}-\lambda_{i}^{*}\|&\geq\|x_{i}^{+}-z^{*}\|.\end{split}$
(80)

From Theorem (2) and (3) we show that the global convergence of $z$ and
$\lambda_{i}$s. Combining with the result of Equation (80) we can easily show
that the global convergence of $x_{i}$s. ∎

##  Appendix F Proof of Theorem 5

###### Proof.

From Equation (26), it’s can be seen that the expression of $g_{i}$ consistes
two parts $\rho(z-x_{i}^{+})$ and $-\lambda_{i}$. When both $z$ and
$x_{i}^{+}$ converge to $z^{*}$, $\lambda_{i}$ converge to $\lambda_{i}^{*}$,
then it easily can be seen the limit point of $g_{i}$ is $-\lambda_{i}^{*}$.

Now we can show the convergence of $g_{i}$ with the following equation.

$\begin{split}&\sum_{i=1}^{N}\left\|g_{i}-g_{i}^{*}\right\|\\\
\overset{\eqref{eq:
gradient}}{=}&\sum_{i=1}^{N}\left\|\rho(z-x_{i}^{+})-\lambda_{i}+\lambda_{i}^{*}\right\|\\\
\leq&\rho
N\left\|z-z^{*}\right\|+\sum_{i=1}^{N}\rho\left\|x_{i}^{+}-z^{*}\right\|+\left\|\lambda_{i}-\lambda_{i}^{*}\right\|.\end{split}$
(81)

From Theorem (2) and (4), all of the three parts converge globally, therefore
$\sum_{i=1}^{N}\left\|g_{i}+\lambda_{i}^{*}\right\|$ will also converge to $0$
globally. ∎

##  Appendix G Proof of Theorem 7

###### Proof.

Suppose $\sum_{i=1}^{N}f_{i}(x_{i})$ is $m_{f}$ strongly convex, then the
following inequality holds [46]

$\begin{split}m_{f}\sum_{i=1}^{N}&\left\|x_{i}^{+}-z^{*}\right\|^{2}\leq\sum_{i=1}^{N}\left(x_{i}^{+}-z^{*}\right)^{\top}\left(g_{i}-g_{i}^{*}\right)\\\
\overset{\eqref{eq:
gradient}}{=}&\sum_{i=1}^{N}\left(x_{i}^{+}-z^{*}\right)^{\top}\left(\rho\left(z-x_{i}^{+}\right)-\lambda_{i}+\lambda_{i}^{*}\right)\\\
\overset{\eqref{eq:
primal}}{=}&\sum_{i=1}^{N}\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}+\frac{z^{+}+z}{2}-z^{*}\right)^{\top}\\\
&\left(\rho\left(z-\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}-\frac{z^{+}+z}{2}\right)-\lambda_{i}+\lambda_{i}^{*}\right).\\\
\end{split}$ (82)

The above equation can be broken into nine parts:

  * Part 1

$\begin{split}\sum_{i=1}^{N}\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)^{\top}\frac{\rho}{2}(z-z^{+})\overset{\eqref{eq:
sum_lam}}{=}0.\end{split}$ (83)

  * Part 2

$\begin{split}&\sum_{i=1}^{N}\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)^{\top}\left(\frac{\lambda_{i}-\lambda_{i}^{+}}{2}\right)\\\
=&\;-\frac{1}{4\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{+}\|^{2}.\end{split}$
(84)

  * Part 3

$\begin{split}&\sum_{i=1}^{N}\left(\frac{\lambda_{i}^{+}-\lambda_{i}}{2\rho}\right)^{\top}\left(\lambda_{i}^{*}-\lambda_{i}\right)\\\
\overset{\eqref{eq: quadratic
equality}}{=}&\frac{1}{4\rho}\sum_{i=1}^{N}\left(\|\lambda_{i}-\lambda_{i}^{*}\|^{2}-\|\lambda_{i}^{+}-\lambda_{i}^{*}\|^{2}\right)\\\
&+\frac{1}{4\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{+}\|^{2}.\end{split}$
(85)

  * Part 4

$\begin{split}&\sum_{i=1}^{N}\left(\frac{z^{+}+z}{2}\right)^{\top}\frac{\rho}{2}(z-z^{+})\\\
=\;&\frac{\rho N}{4}\left(\|z\|^{2}-\|z^{+}\|^{2}\right).\end{split}$ (86)

  * Part 5

$\sum_{i=1}^{N}\left(\frac{z^{+}+z}{2}\right)^{\top}\left(\frac{\lambda_{i}-\lambda_{i}^{+}}{2}\right)\overset{\eqref{eq:
sum_lam}}{=}0.$ (87)

  * Part 6

$\sum_{i=1}^{N}\left(\frac{z^{+}+z}{2}\right)^{\top}\left(\lambda_{i}^{*}-\lambda_{i}\right)\overset{\eqref{eq:
sum_lam}}{=}0.$ (88)

  * Part 7

$\begin{split}\sum_{i=1}^{N}\left(-z^{*}\right)^{\top}\frac{\rho}{2}(z-z^{+})=\frac{\rho
N}{2}\left(\left(z^{+}\right)^{\top}z^{*}-z^{\top}z^{*}\right).\end{split}$
(89)

  * Part 8

$\sum_{i=1}^{N}\left(-z^{*}\right)^{\top}\left(\frac{\lambda_{i}-\lambda_{i}^{+}}{2}\right)\overset{\eqref{eq:
sum_lam}}{=}0.$ (90)

  * Part 9

$\sum_{i=1}^{N}\left(-z^{*}\right)^{\top}\left(\lambda_{i}^{*}-\lambda_{i}\right)\overset{\eqref{eq:
sum_lam}}{=}0.$ (91)

In the end, combine the above nine parts,

$\begin{split}m_{f}\sum_{i=1}^{N}&\left\|x_{i}^{+}-z^{*}\right\|^{2}\leq\sum_{i=1}^{N}\left(x_{i}^{+}-z^{*}\right)^{\top}\left(g_{i}-g_{i}^{*}\right)\\\
=&\frac{1}{4\rho}\sum_{i=1}^{N}\left(\|\lambda_{i}-\lambda_{i}^{*}\|^{2}-\|\lambda_{i}^{+}-\lambda_{i}^{*}\|^{2}\right)\\\
&+\frac{\rho N}{4}\left(\|z\|^{2}-2z^{\top}z^{*}+\|z^{*}\|^{2}\right)\\\
&-\frac{\rho
N}{4}\left(\|z^{+}\|^{2}-2\left(z^{+}\right)^{\top}z^{*}+\|z^{*}\|^{2}\right)\\\
=&\frac{1}{4}\mathscr{L}(z,\lambda)-\frac{1}{4}\mathscr{L}(z^{+},\lambda^{+}).\end{split}$
(92)

Following the assumption in Theorem 7, if

$\delta\mathscr{L}(z^{+},\lambda^{+})\leq
4m_{f}\sum_{i=1}^{N}\left\|x_{i}^{+}-z^{*}\right\|^{2}$

holds, with the result of (92), we have

$\mathscr{L}(z^{+},\lambda^{+})\leq\frac{1}{1+\delta}\mathscr{L}(z,\lambda).$

Later, a serial recurrence formula can be established:

$\begin{split}\rho
N\|z-z^{*}\|^{2}&\leq\frac{1}{\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|^{2}+\rho
N\|z-z^{*}\|^{2}\\\
&=\mathscr{L}(z,\lambda)\leq\left(\frac{1}{1+\delta}\right)^{k}\mathscr{L}(z^{0},\lambda^{0}).\end{split}$
(93)

Therefore we have Q-linearly converge of the global variable $z$.

$\|z-z^{*}\|\leq\frac{1}{\sqrt{\rho
N}}\left(\frac{1}{\sqrt{1+\delta}}\right)^{k}\mathscr{L}(z^{0},\lambda^{0})^{\frac{1}{2}}.$
(94)

Moreover, on the dual side we have

$\begin{split}\frac{1}{\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|^{2}&\leq\frac{1}{\rho}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|^{2}+\rho
N\|z-z^{*}\|^{2}\\\
&=\mathscr{L}(z,\lambda)\leq\left(\frac{1}{1+\delta}\right)^{k}\mathscr{L}(z^{0},\lambda^{0}),\end{split}$
(95)

which induce the convergence of the dual

$\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|^{2}\leq\rho\left(\frac{1}{1+\delta}\right)^{k}\mathscr{L}(z^{0},\lambda^{0}).$
(96)

This shows a Q-linear convergence rate of Reduced Consensus ALADIN.

∎

##  Appendix H Proof of Theorem 8

###### Proof.

First, let the result of Equation (77)-(80) holds, four different situations
of local convergence analysis of C-ALADIN can be established by combing with
SQP theory [2, Chapter 18]. First, we show the local convergence analysis of
Reduced Consensus ALADIN. As an extension, the corresponding analysis of
Consensus BFGS ALADIN is also discussed.

As mentioned in Section 3.4, Reduced Consensus ALADIN is proposed by setting
$B_{i}=\rho I$. Assume $\gamma$ is the upper bound of the Hessian
approximation distance, $\left\|\rho
I-\nabla^{2}f_{i}(x_{i})\right\|\leq\gamma$, the convergence rate analysis can
be divided into four situations. From the SQP theory of Newton Lagrange method
[49], we have different convergence rate guarantees for the first three
situations of the following four.

a) If $\left\|\rho I-\nabla^{2}f_{i}(x_{i})\right\|\leq\gamma\leq 1$, we have

$\left\\{\begin{split}N\|z^{+}-z^{*}\|&\leq\gamma\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|\\\
\sum_{i=1}^{N}\|\lambda_{i}^{+}-\lambda_{i}^{*}\|&\leq\gamma\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|.\end{split}\right.$
(97)

Conbine Equation (80) and (97), the following inequality can be obtained.

$\begin{split}&\left(\frac{\rho
N}{\sigma}\|(z^{+}-z^{*})\|+\frac{1}{\sigma}\sum_{i=1}^{N}\|(\lambda_{i}^{+}-\lambda_{i}^{*})\|\right)\\\
\leq&\frac{\left(\rho+1\right)\gamma}{\sigma}\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|\\\
\overset{\eqref{eq:
con_ALADIN_step1}}{\leq}&\frac{\left(\rho+1\right)\gamma}{\sigma}\left(\frac{\rho
N}{\sigma}\|z-z^{*}\|+\frac{1}{\sigma}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|\right).\end{split}$
(98)

This shows a local linear convergence of Reduced Consensus ALADIN.

b) If $\gamma\rightarrow 0$, we have

$\begin{split}&\left(\frac{\rho
N}{\sigma}\|(z^{+}-z^{*})\|+\frac{1}{\sigma}\sum_{i=1}^{N}\|(\lambda_{i}^{+}-\lambda_{i}^{*})\|\right)\\\
\leq&\frac{\left(\rho+1\right)\omega_{f}}{2\sigma}\left(\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|\right)^{2}\\\
\overset{\eqref{eq:
con_ALADIN_step1}}{\leq}&\frac{\left(\rho+1\right)\omega_{f}}{2\sigma}\left(\frac{\rho
N}{\sigma}\|z-z^{*}\|+\frac{1}{\sigma}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|\right)^{2},\end{split}$
(99)

where $\omega_{f}$ denotes the corresponding Lipschitz constant [2]. This
shows a quadratic convergence of C-ALADIN.

c) If
$\kappa=\frac{\left(\rho+1\right)}{\sigma}\left(\gamma+\frac{\omega_{f}}{2}\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|\right)\rightarrow
0$, we have

$\begin{split}&\left(\frac{\rho
N}{\sigma}\|(z^{+}-z^{*})\|+\frac{1}{\sigma}\sum_{i=1}^{N}\|(\lambda_{i}^{+}-\lambda_{i}^{*})\|\right)\\\
\leq&\frac{\left(\rho+1\right)}{\sigma}\left(\gamma+\frac{\omega_{f}}{2}\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|\right)\left(\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|\right)\\\
=&\;\kappa\left(\sum_{i=1}^{N}\|x_{i}^{+}-z^{*}\|\right)\\\
\overset{\eqref{eq: con_ALADIN_step1}}{\leq}&\;\kappa\left(\frac{\rho
N}{\sigma}\|z-z^{*}\|+\frac{1}{\sigma}\sum_{i=1}^{N}\|\lambda_{i}-\lambda_{i}^{*}\|\right).\end{split}$
(100)

Reduced Consensus ALADIN will show a local superlinear convergence.

d) If $\gamma$ is large, the above analysis can not be applied. Luckily, if
$\rho$ is sufficient large, Equation (11) is locally strongly convex.
Corollary (1) can be prepared here with different $\delta^{k}$ in each
iteration $k$. Therefore, assume there exist a $\bar{\delta}\geq\delta^{k}$
and satisfies Equation (38), then Reduced Consensus ALADIN can still get
Q-linearly converge with rate $\left(\frac{1}{\sqrt{1+\bar{\delta}}}\right)$.

By recovering the Hessian approximation $B_{i}$ with Equation (12), Consensus
BFGS ALADIN can touch linear or super-linear convergence rate, since
$\|B_{i}-\nabla^{2}f_{i}(x_{i})\|\rightarrow 0$ can easily hold. With the
technologies of _Sharpen BFGS_ [50], super-linear or even quadratic rate can
be obtained. ∎

######  Remark 8.

Although the SQP type algorithms has local convergence guarantees for non-
convex optimization problems, the performance depends on the initial point and
the way of combined globalization technologies. Although ALADIN inherits the
local convergence properties of SQP, the consensus globalization technologies
(i.e. Armijo line search or trust region method [2]) are not needed.