# On the Perturbed Projection-Based Distributed Gradient-Descent Algorithm: A Fully-Distributed Adaptive Redesign

Tarek Bazizi, Mohamed Maghenem, Paolo Frasca, Antonio Loría, and Elena Panteley

**Abstract**— In this work, we revisit a classical distributed gradient-descent algorithm, introducing an interesting class of perturbed multi-agent systems. The state of each subsystem represents a local estimate of a solution to the global optimization problem. Thereby, the network is required to minimize local cost functions, while gathering the local estimates around a common value. Such a complex task suggests the interplay of consensus-based dynamics with gradient-descent dynamics. The latter descent dynamics involves the projection operator, which is assumed to provide corrupted projections of a specific form, reminiscent of existing (fast) projection algorithms. Hence, for the resulting class of perturbed networks, we are able to adaptively tune some gains in a fully distributed fashion, to approach the optimal consensus set up to arbitrary-desired precision.

## I. INTRODUCTION

In recent years, distributed optimization has gained a significant attention due to various applications, including resource sharing/allocation [1], sensor networks [2], and electric power systems [3], among others. Distributed optimization aims at minimizing a global cost function by distributing the computation across multiple agents (computation units). Each agent disposes of its own local cost function and the sum of the local cost functions represents the global cost function. The agents exploit only their own local cost function and interact with neighbor agents to coordinate and track a minimum value for the global cost function.

In the literature, various algorithms have been developed to address distributed optimization problems [4]. In the discrete-time setting, [5] introduces a distributed version of the gradient-descent algorithm with a decreasing step-size, allowing the gradient influence to gradually vanish in time, which allows the network to achieve synchronization. This approach is extended to fixed step-sizes in [6]–[8] to avoid harming the convergence to the optimal solution. Additionally, [9] and [10] propose an algorithm, in which every agent admits a distinct but fixed step-size. Other methods based on a dual formulation, such as distributed ADMM, are also considered in [11].

In the continuous-time setting, using Lyapunov stability theory, distributed proportional-integral algorithms are considered in [12], [13], to mitigate the synchronization error. Furthermore, given that each agent knows its own local cost

function only, [14]–[17] assume that each agent can reconstruct the set of minima of its local cost function (the local optimal set). Thereby, transforming the local optimization problems into minimizing the distance with respect to the local optimal set. This approach removes the need to have differentiable local cost functions, and requires the local optimal sets to be convex. In [16] and [17], the projections to the local sets are corrupted by numerical perturbations. The first approach assumes that the erroneous projection belongs to a restricted triangular area including the actual projection. The second approach assumes that the perturbed projection lies within the boundary of the local optimal set. Both approaches characterize these errors using the angle created by the actual and the erroneous projections, assuming this error to decrease over time.

In this work, we revisit the class of distributed gradient-descent algorithms studied in the aforementioned literature. That is, we consider a multi-agent system, in which each subsystem dynamically updates its state to minimize a local cost function, while ensuring that the network collectively approaches a common minimizer. This complex task involves the interplay of a consensus-based dynamics, governed by a strongly-connected directed graph, and a gradient-descent dynamics. The latter descent dynamics involves a projection operator, which is assumed to provide perturbed projections as typical in (fast) projection algorithms [18]. Thanks to our approach, we are able to adaptively tune some consensus and descent gains, so that the solutions of the resulting class of perturbed networks approach the optimal consensus set up to arbitrary-desired precision. Different from the existing works [16], [17], the designed gains are dynamically updated and are not predefined off-line as time-varying signals. Furthermore, their design, inspired by [19], is fully distributed, in the sense that it requires solely the knowledge of desired precision. Neither the graph properties, size, nor the magnitude of the perturbation are required to be known.

The rest of this paper is organized as follows. Preliminaries are in Section II. The problem formulation is in Section III. The main result is in Section IV. Finally, numerical simulations are in Section V. Due to space constraints, some proofs and intermediate results are omitted and can be found in [20].

**Notation.** For $v \in \mathbb{R}^N$, $v^\top$ denotes its transpose, $|v|$ denotes its Euclidean norm, and $\text{diag}\{v\} = \text{diag}\{v_1, v_2, ..., v_N\} \in \mathbb{R}^{N \times N}$ denotes the diagonal matrix whose $i$-th diagonal element is $v_i$, the $i$-th element of $v$. For a set $K \subset \mathbb{R}^N$, $|v|_K := \min\{|x - y| : y \in K\}$ denotes the distance of $x$ to the set $K$. For a symmetric positive semi-definite matrix $Q \in \mathbb{R}^{N \times N}$, $\lambda_i(Q)$ denotes

<footnote>T. Bazizi and P. Frasca are with Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, GIPSA-lab, 38000 Grenoble, France. M. Maghenem is with Univ. Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, 38000 Grenoble, France. A. Loría and E. Panteley are with L2S, CNRS, Gif-sur-Yvette, France.</footnote>
the ith smallest eigenvalue of Q. We use $\mathbb{D}^N$ to denote the set of diagonal matrices of dimension $N$, and we let $\mathbb{B}^N := \{D \in \mathbb{D}^N : |D_{ii}| \le 1 \ \forall i \in \{1, 2, ..., N\}\}$. A class $\mathcal{K}$ function $\alpha : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ is continuous, increasing, and $\alpha(0) = 0$. A class $\mathcal{K}_{\infty}$ function $\alpha : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ satisfies $\alpha \in \mathcal{K}$ and $\alpha(s) \to \infty$ as $s \to \infty$. A class $\mathcal{L}$ function $\sigma : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ is continuous, non-increasing, and $\sigma(s) \to \infty$ as $s \to \infty$. A class $\mathcal{KL}$ function $\beta : \mathbb{R}_{\ge 0} \times \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ satisfies $\beta(\cdot, \cdot) \in \mathcal{K}$ for any fixed $t \ge 0$ and $\tilde{\beta}(s, \cdot) \in \mathcal{L}$ for any fixed $s \ge 0$. By $\mathbf{1}_N := [1 \ 1 \ ... \ 1]^\top$, we denote the vector of dimension $N$ whose entries are equal to 1. For a continuously differentiable function $g : \mathbb{R}^N \to \mathbb{R}$, $\nabla g : \mathbb{R}^N \to \mathbb{R}^N$ denotes the gradient of $g$. Finally, we use $\mathbb{B}$ to denote the closed unit ball centered at the origin.

## II. PRELIMINARIES

### A. The projection map

Consider a closed subset $K \subset \mathbb{R}^n$ and let $x \in \mathbb{R}^n$. The projection of $x$ on $K$ is given by

$$ \Pi_K(x) := \operatorname{argmin}\{|x - y| : y \in K\}. \quad (1) $$

When $K$ is convex, it is shown in [21, Page 23-24] that

$$ |\Pi_K(x) - \Pi_K(y)| \le |x - y| \quad \forall x, y \in \mathbb{R}^n. \quad (2) $$

Moreover, under the convexity of the set $K$, the map $\Pi_K(x)$ is a singleton, $x \mapsto |x|_K^2 := |x - \Pi_K(x)|^2$ is continuously differentiable, and

$$ \nabla |x|_K^2 = 2(x - \Pi_K(x)) \quad \forall x \in \mathbb{R}^n. \quad (3) $$

Additionally, given $x, y \in \mathbb{R}^n$ and $A \subseteq B \subset \mathbb{R}^n$ closed and convex, it holds that [14]

$$ (x - \Pi_B(x))^{\top}(\Pi_A(x) - \Pi_B(x)) \le 0, \quad (4) $$

$$ -(x - \Pi_B(x))^{\top}(x - \Pi_A(x)) \le -|x|_B^2. \quad (5) $$

### B. Graph theory

A directed graph, or di-graph, $\mathcal{G}(\mathcal{V}, \mathcal{E})$ is characterized by a set of nodes $\mathcal{V} := \{1, 2, ..., N\}$ and a set of directed edges $\mathcal{E}$. The set of edges $\mathcal{E}$ consists of ordered pairs of the form $(k, i)$, which indicates a directed link from node $k$ to node $i$. We consider directed graphs with no self-arcs. Note that when there exists a directed edge $(k, i) \in \mathcal{E}$, then node $k$ is called an in-neighbor of node $i$. We use $\mathcal{N}_i \subset \{1, 2, ..., N\} \setminus \{i\}$ to denote the indexes of the in-neighbors of agent $i$. Furthermore, we assign a weight $a_{ik} \ge 0$ to each edge $(k, i)$. That is, $a_{ik} = 0$ if $(k, i) \notin \mathcal{E}$. The Laplacian matrix is denoted by $L := D - A$, where $D := \text{diag}\{d_1, d_2, ..., d_N\}$ with $d_i := \sum_{j=1}^N a_{ij}$ for all $i \in \{1, 2, ..., N\}$ is the diagonal part of $L$, and $A := [a_{ij}]$ is the adjacency matrix of $\mathcal{G}$. The directed graph $\mathcal{G}$ is strongly connected if, for any two distinct nodes $i$ and $j$, there is a path from $i$ to $j$.

## III. PROBLEM FORMULATION

Consider the unconstrained optimization problem

$$ \min_{y \in \mathbb{R}^n} \sum_{i=1}^{N} f_i(y), \quad (6) $$

where each $f_i : \mathbb{R}^n \to \mathbb{R}$ is assumed to be convex.

In distributed optimization approaches, different computation units are used to collaboratively solve (6). In particular, every $f_i$ is assumed to be known to a single unit only. Hence, a key step consists in recasting (6) into the constraint-coupled optimization problem

$$ \min_{x \in \mathbb{R}^{nN}} \sum_{i=1}^{N} f_i(x_i), \quad x := [x_1^{\top} \ x_2^{\top} \ ... \ x_N^{\top}], \quad (7) $$

s.t. $x_i = x_j$ for all $i, j \in \mathcal{V}$.

Furthermore, for every $i \in \{1, 2, ..., N\}$, we use $X_i \subset \mathbb{R}^n$ to denote the set of points where the cost function $f_i$ reaches its minimum. Note that every $X_i$ is convex since so is the corresponding function $f_i$. Now, by assuming that

$$ X_o := \bigcap_{i=1}^{N} X_i \neq \emptyset, \quad (8) $$

we can further recast (6) into the quadratic-cost optimization problem

$$ \min_{x \in \mathbb{R}^{nN}} \frac{1}{2} \sum_{i=1}^{N} |x_i|^2_{X_i} \quad (9) $$

s.t. $x_i = x_j$ for all $i, j \in \mathcal{V}$.

### A. A Class of Networked Systems

According to [14], [16], and [17], we can solve (6) by solving (9) dynamically through a distributed gradient-descent algorithm. More specifically, we can design a network of multi-agent systems, where the state of each subsystem, denoted by $x_i$, represents a local estimate of a solution to (6). The design of this network must achieve two concurrent goals: 1 - Every agent minimizes the corresponding local cost function. 2- The local minimizers, generated by the agents, converge to a common value.

To achieve the first goal, a gradient-descent dynamics minimizing the quadratic cost function $\frac{1}{2} |\cdot|_{X_i}^2$ is added, thanks to the continuous differentiability of $\frac{1}{2} |\cdot|_{X_i}^2$; see (3). To achieve the second goal, an interconnection protocol, governed by the directed graph $\mathcal{G}(\mathcal{V}, \mathcal{E})$, is needed. The following graph assumption is made.

**Assumption 1:** The graph $\mathcal{G}$ is strongly connected. •

In summary, every agent $i \in \mathcal{V}$ updates dynamically its local solution to (6), denoted by $x_i$, according to

$$ \dot{x}_i = \gamma_i \alpha_i \sum_{j=1}^{N} a_{ij}(x_j - x_i) - \alpha_i(x_i - \tilde{\Pi}_{X_i}(x_i)), \quad (10) $$

where, for each $i \in \mathcal{V}$, $\gamma_i > 0$ and $\alpha_i > 0$ are, respectively, the coupling and the descent gains that we will adaptively design later. Furthermore, for each $i \in \mathcal{V}$, the map $\tilde{\Pi}_{X_i}$:
$\mathbb{R}^n \to \mathbb{R}^n$ represents a corrupted (numerical) estimate of the projection map $\Pi_{X_i}$ introduced in (1), and is given by

$$ \tilde{\Pi}_{X_i}(x_i) := \Pi_{X_i}(x_i) + \zeta_i p_i(x_i), \quad (11) $$

where $\zeta_i \in (0, 1)$ indicates the precision of the numerical projection, and $p_i : \mathbb{R}^n \to \mathbb{R}^n$ stands for the worst-case projection error, verifying the following assumption.

**Assumption 2:** There exists $\bar{p} > 0$ such that

$$ \sup_{y \in \mathbb{R}^n} |p_i(y)| \le \bar{p} \quad \forall i \in \mathcal{V}. $$

**Remark 1:** Approximate projections verifying (11) and Assumption 2 are consistent with various iterative (fast) projection algorithms; see [18] and [22]. In those algorithms, higher precisions (i.e., small values of $\zeta_i$) are achieved at the price of larger number of iterations. Furthermore, the worst-case projection $p_i$ is usually unknown but bounded and can result from solving dual problems [18].

Our framework is based on the key assumption that we are able to tune every projection precision $\zeta_i$ to guarantee

$$ \zeta_i \le 1/\alpha_i \quad \forall i \in \mathcal{V}, $$

where $\alpha_i$ is the gradient-descent gain introduced in (10). As a consequence, we recover the class of perturbed multi-agent systems of the form

$$ \begin{gathered} \dot{x}_i = \gamma_i \alpha_i \sum_{j=1}^{N} a_{ij}(x_j - x_i) - \alpha_i (x_i - \Pi_{X_i}(x_i)) + p_i(x_i) \\ \forall i \in \mathcal{V}. \end{gathered} \quad (12) $$

**Remark 2:** In the particular setting where

$$ \gamma := \gamma_1 \alpha_1 = \dots = \gamma_N \alpha_N > 0, $$

the networked system in (12) belongs to the class of networks studied in [23], where the term $-\alpha_i(x_i - \Pi_{X_i}(x_i))$ is replaced by a general function $f_i(x_i)$ such that $u_i \mapsto x_i$, under $\dot{x}_i = f_i(x_i) + u_i$, defines a semi-passive map. See also [24], [25] for the unperturbed case. The goal in the aforementioned works is restrained to guaranteeing boundedness and ultimate boundedness of the network's solutions, as well as practical synchronization, i.e., showing that, for every $\varepsilon > 0$, there exists $\gamma^* > 0$ such that, for each $\gamma \ge \gamma^*$,

$$ \lim_{t \to +\infty} |x_i(t) - x_j(t)| \le \varepsilon \quad \forall i, j \in \mathcal{V}. $$

In fact, adapting the Lyapunov-based approach in [23]–[25] to our setting is key to asymptotically fulfill the constraint in (9) up to a desired precision $\varepsilon$.

## B. Adaptive design

A dynamical way to solve (6) is by guaranteeing asymptotic convergence towards the optimal consensus set

$$ \mathcal{A} := \{x \in X_1 \times \dots \times X_N : x_1 = \dots = x_N\} $$

for the multi-agent system (12). In the unperturbed case, when $p \equiv 0$, this problem is solved in [14] for any $\alpha_1, \gamma_1, \dots, \alpha_N, \gamma_N > 0$. However, it is out of reach in the

presence of the perturbation $p$. Instead, through a fully-distributed adaptive design of the sequence $\{(\gamma_i, \alpha_i)\}_{i=1}^N$, we establish in this work convergence of the solutions to an arbitrarily-small neighborhood of the set $\mathcal{A}$. More specifically, we address the following problem.

**Problem 1:** Given $\varepsilon > 0$, we design $\{(\gamma_i, \alpha_i)\}_{i=1}^N$ as

$$ \dot{\gamma}_i = h_i(x_i, \gamma_i, \{(x_j, \gamma_j)\}_{j \in \mathcal{N}_i}, \varepsilon), \quad (13) $$

$$ \dot{\alpha}_i = g_i(x_i, \alpha_i, \{(x_j, \alpha_j)\}_{j \in \mathcal{N}_i}, \varepsilon), \quad (14) $$

so that the multi-agent system (12) under (13)-(14) achieves

$$ \lim_{t \to +\infty} |x(t)|_{\mathcal{A}_s} \le \varepsilon, \quad \mathcal{A}_s := \{x_i = x_j \ \forall i, j \in \mathcal{V}\}, \quad (15) $$

$$ \lim_{t \to +\infty} |x(t)|_{\mathcal{A}_o} \le \varepsilon, \quad \mathcal{A}_o := X_1 \times \dots \times X_N, \quad (16) $$

and, at the same time,

$$ \max\{|\gamma_i|_{\infty}, |\alpha_i|_{\infty}\} < \infty \quad \forall i \in \mathcal{V}. \quad (17) $$

**Remark 3:** It is important to note that verifying (15)-(16) does not necessarily lead to

$$ \lim_{t \to +\infty} |x(t)|_{\mathcal{A}} \le \varepsilon, $$

even though $\mathcal{A} = \mathcal{A}_s \cap \mathcal{A}_o$. However, since both functions

$$ x \mapsto |x|_{\mathcal{A}}^2 \quad \text{and} \quad x \mapsto \max\{|x|_{\mathcal{A}_o}^2, |x|_{\mathcal{A}_s}^2\} $$

are continuous, positive definite with respect to the compact set $\mathcal{A}$, and radially unbounded, we conclude, according to [26], the existence of $\rho \in \mathcal{K}$ such that

$$ |x|_{\mathcal{A}} \le \rho(\max\{|x|_{\mathcal{A}_s}, |x|_{\mathcal{A}_o}\}) \quad \forall x \in \mathbb{R}^{n_N}. $$

Furthermore, the function $\rho$ would be linear, according to [27, Theorem 1], provided that there exists $\delta > 0$ such that

$$ \max_{y \in \mathcal{A}} |y|_{\mathbb{R}^{n_N} \setminus \mathcal{A}_o} > \delta. $$

In particular, by solving Problem 1, we only guarantee that

$$ \lim_{t \to +\infty} |x(t)|_{\mathcal{A}} \le \rho(\varepsilon), $$

Hence, according to our framework, guaranteeing convergence of $x$ to an arbitrarily-small neighborhood of $\mathcal{A}$ requires the knowledge of the function $\rho$.

Different from the existing literature [16], [17], the design of $\{(\gamma_i, \alpha_i)\}_{i=1}^N$ required in Problem 1 is adaptive and does not rely on predefined time-varying exogenous signals. Furthermore, the design we propose is fully distributed, in the sense that it requires solely the knowledge of the precision $\varepsilon$. Neither the graph spectrum, size, nor the magnitude of the perturbation $p$ are needed to be known.
IV. MAIN RESULT

We propose to dynamically update the sequence
$\{(\gamma_i, \alpha_i)\}_{i=1}^N$ according to

$$
\begin{align}
\dot{\gamma}_i ={}& k_\gamma \sum_{j \in \mathcal{N}_i} a_{ij}(\gamma_j - \gamma_i) \nonumber \\
& + \frac{1}{2} \mathrm{dsat}_\epsilon (|x_i|_{X_i}) + \frac{1}{2} \mathrm{dsat}_\epsilon \left( \sum_{j \in \mathcal{N}_i} |x_j - x_i| \right), \tag{18}
\end{align}
$$

$$
\begin{align}
\dot{\alpha}_i ={}& k_\alpha \sum_{j \in \mathcal{N}_i} a_{ij}(\alpha_j - \alpha_i) \nonumber \\
& + \frac{1}{2} \mathrm{dsat}_\epsilon (|x_i|_{X_i}) + \frac{1}{2} \mathrm{dsat}_\epsilon \left( \sum_{j \in \mathcal{N}_i} |x_j - x_i| \right), \tag{19}
\end{align}
$$

where $k_\alpha, k_\gamma > 0$ are free design parameters, and the
function $dsat_\epsilon : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ is given by

$$
\mathrm{dsat}_{\epsilon}(a) := \frac{1 + |a - \epsilon| - |a - \epsilon - 1|}{2} \quad \forall a \ge 0. \quad (20)
$$

Remark 4: The function dsat_ε is non-negative and bounded from above by 1, vanishes on [0, ε], and linear on [ε, ε + 1].

The adaptive design in (18)-(19) is inspired by [19], where
a synchronization problem for heterogeneous multi-agent
systems is addressed. Roughly speaking, using boundedness
of dsat_ε, we can show that the γis (resp., the αis), after some
time, must remain close to their convex combination γs :=
∑N i=1 vᵢγᵢ (resp., αs := ∑N i=1 vᵢαᵢ), for some {vᵢ}N i=1 ⊂
(0, 1) with ∑N i=1 vᵢ = 1. Hence, for all i ∈ V, we can write
γᵢ = γs + ŷᵢ (resp., αᵢ = αs + ȳᵢ), for a bounded residual ŷᵢ
(resp., ȳᵢ). As a result, by accommodating the study in [23]
in the presence of ŷᵢ (resp., ȳᵢ), see Remark 2, we guarantee
convergence of t ↦ x(t) to the set A_s + εB provided that γs
and αs exceed specific values. At the same time, the analysis
of ˙γs and ˙αs allows us to conclude that a necessary condition
for γs and αs to stop increasing is that the solution t ↦ x(t)
reaches the set A_s + εB. Thereby, we must fulfill (15) at
some point. We might still witness the increase of αs and
γs until convergence of t ↦ x(t) to A_o + εB is additionally
achieved. Indeed, we show, via leveraging some Lyapunov-
based tools, that the latter convergence property must occur
for finite values of αs and γs. Thereby, we guarantee both
boundedness of {(αᵢ, γᵢ)}N i=1 and (16).

We are now ready to state our main result.

**Theorem 1:** Under Assumptions 1-2, the multi-agent system in (12) under (18)-(19) solves Problem 1. □

*Proof:* We start introducing the vector $v \in \mathbb{R}^N$ such that $v^\top L = 0$ and $v^\top \mathbf{1}_N = 1$. Under Assumption 1, we conclude that such a vector $v$ is unique and that its entries are positive; see [23, Lemma 1].

The proof of Theorem 1 is based on two steps.

Step 1 (Verifying (15)): We do so using the following four
intermediate results.

(I) We show that the design in (18)-(19) forces the matrices

$$
\Gamma := \operatorname{diag}\{\gamma_1, \dots, \gamma_N\} \text{ and } \Theta := \operatorname{diag}\{\alpha_1, \dots, \alpha_N\}
$$

to reach and remain within the set

$$
\mathcal{D} := \{ D \in \mathbb{D}^N : D \in d_s I_N + d_e \mathbb{B}^N, d_s := \mathbf{1}_N^\top D v \}
$$

for some $d_e > 0$ and after some time $T_e \ge 0$. See [20, Lemma 1].

(II) We show global uniform (in Γ and Θ) boundedness (GUB) of trajectories. That is, we show the existence of γ₀ > 0 and α₀ > 1 such that, for every r₀ > 0, there exists R := R(r₀, γ₀, α₀) ≥ r₀ such that, for all Γ, Θ : Dⁿ → D with

$$
\begin{equation}
\begin{aligned}
\gamma_s(t) &:= (\mathbf{1}_N^\top \Gamma(t)v) \ge \gamma_o \quad \forall t \ge 0, \\
\alpha_s(t) &:= (\mathbf{1}_N^\top \Theta(t)v) \ge \alpha_o \quad \forall t \ge 0,
\end{aligned}
\tag{21}
\end{equation}
$$

we have

$$
|x(0)| \le r_o \implies |x(t)| \le R \quad \forall t \ge 0.
$$

See [20, Lemma 3].

(III) We show global uniform (in Γ and Θ) ultimate bound-
ness (GUUB). That is, we guarantee the existence of
γ₀ > 0, α₀ > 1, and r = r(γ₀, α₀) > 0 such that, for
all r₀ > 0, there exists T = T(r₀, γ₀, α₀) ≥ 0 such that,
for all Γ, Θ : Dⁿ → D with γs(t) ≥ γ₀ and αs(t) ≥ α₀
for all t ≥ 0, we have

$$
|x(0)| \le r_o \implies |x(t)| \le r \quad \forall t \ge T.
$$

See [20, Lemma 3].

(IV) We show global practical synchronization. That is, we guarantee the existence β₁, β₂ ∈ KŁ and α* > α₀ > 1 such that, for any ε > 0, there exists γ*(ε) > γ₀ > 0 such that, for all Γ, Θ : Dⁿ → D with γs(t) ≥ γ* and αs(t) ≥ α* for all t ≥ 0, we have

$$
|x(t)|_{A_s}^2 \le \frac{\varepsilon}{2} + \beta_1 (|x(0)|_{A_s}, \alpha^* t) + \frac{\beta_2 (|x(0)|, \alpha^* t)}{\gamma^*} \quad (22)
$$

for each $(x(0), t) \in \mathbb{R}^{nN} \times \mathbb{R}_{\ge 0}$. See [20, Lemma 4].

To complete the proof of (15), we reason on the time interval $[T_e, +\infty)$. Indeed, one can easily show that the solutions cannot blow up on the interval $[0, T_e]$. Next, using property (I), we conclude that

$$
(\Gamma(t), \Theta(t)) \in \mathcal{D} \times \mathcal{D} \quad \forall t \ge T_e.
$$

Furthermore, we note that

$$
\dot{\alpha}_s = \dot{\gamma}_s = \frac{1}{2} \sum_{i=1}^{N} v_i \left[ \mathrm{dsat}_{\epsilon} \left( \sum_{j \in \mathcal{N}_i} |x_j - x_i| \right) + \mathrm{dsat}_{\epsilon} (|x_i|_{X_i}) \right] \geq 0.
$$

Hence, the variables $\gamma_s$ and $\alpha_s$ are doomed to increase if
the solution $t \mapsto x(t)$ remains away from $(A_s + \varepsilon \mathbb{B}) \cap
(A_o + \varepsilon \mathbb{B})$. However, using property (IV), we conclude that
once $\gamma_s$ passes the value $\gamma^*$ and $\alpha_s$ passes $\alpha^*$, the solution
$t \mapsto x(t)$ must enter and remain within $A_s + \varepsilon \mathbb{B}$, leading to

$$
\dot{\alpha}_s = \dot{\gamma}_s = \frac{1}{2} \sum_{i=1}^{N} v_i \mathrm{dsat}_{\epsilon}(|x_i|_{X_i}) \geq 0. \quad (23)
$$
Step 2 (Verifying (16) and (17)): To do so, we use the following property, established in [20, Lemma 5].

(V) We show global practical optimality. That is, given $\varepsilon > 0$, we guarantee the existence of $\alpha^{**}(\varepsilon) \ge \alpha^*$ and $\gamma^{**}(\varepsilon) \ge \gamma^*(\varepsilon)$ such that, for all $r_o > 0$, there exists $T_o = T_o(r_o, \alpha^{**}, \gamma^{**}) \ge 0$ such that, for all $\Gamma, \Theta: \mathbb{D}^N \to \mathcal{D}$ with $\gamma_s(t) \ge \gamma^{**}(\varepsilon)$ and $\alpha_s(t) \ge \alpha^{**}(\varepsilon)$ for all $t \ge 0$ and for all solution $t \mapsto x(t)$ with $|x(0)| \le r_o$, we have

$$|x_i(t)|_{X_i} \le \varepsilon \quad \forall t \ge T_o, \quad \forall i \in \mathcal{V}. \quad (24)$$

As in Step 1, we reason on the time interval $[T_e, +\infty)$ since, after property (I), we have

$$(\Gamma(t), \Theta(t)) \in \mathcal{D} \times \mathcal{D} \quad \forall t \ge T_e.$$

Furthermore, after Step 1, we conclude the existence of $T'_e \ge T_e$, after which, $\alpha_s$ and $\gamma_s$ are governed by (23). Hence, either $\alpha_s$ and $\gamma_s$ remain bounded implying that $x(t) \to \mathcal{A}_o + \varepsilon\mathbb{B}$, otherwise, there exists $T''_e \ge T'_e$, after which, $\alpha_s$ and $\gamma_s$ must be larger than $\alpha^{**}$ and $\gamma^{**}$, respectively. Hence, using property (V), we conclude that

$$|x_i(t)|_{X_i} \le \varepsilon \quad \forall t \ge T_e'' + T_o(|x(T_e'')|, \alpha^{**}, \gamma^{**}), \quad \forall i \in \mathcal{V}.$$

This verifies (16) and lead to

$$\dot{\alpha}_s(t) = \dot{\gamma}_s(t) = 0 \quad \forall t \ge T_e'' + T_o(|x(T_e'')|, \alpha^{**}, \gamma^{**}),$$

which guarantees boundedness of $(\alpha_s, \gamma_s)$.

## V. SIMULATIONS

Consider the optimization problem in (7) with $N = 3$ and $n = 2$. For each $i \in \{1, 2, 3\}$, the set of minimizers of the local cost function $f_i$ is given by

$$X_i := \{y \in \mathbb{R}^n : (y - c_i)^\top Q_q(y - c_i) \le 1, q \in \{1, 2, 3\}\},$$

where

$$Q_1 := \begin{bmatrix} 1/3 & -1/3 \\ -1/3 & 7/9 \end{bmatrix}, Q_2 := \begin{bmatrix} 1/3 & 1/3 \\ 1/3 & 7/9 \end{bmatrix}, Q_3 := \frac{7}{10} I_2.$$

Furthermore, $c_1 := (0, 0)$, $c_2 := (0, 1)$, and $c_3 := (1, 0)$.

The Laplacian matrix of the considered communication graph is given by

$$L := \begin{bmatrix} 1 & -1 & 0 \\ 0 & 2 & -2 \\ -1 & -\frac{1}{2} & \frac{3}{2} \end{bmatrix}.$$

Given $i \in \{1, 2, 3\}$, the projection map $\tilde{\Pi}_{X_i}$ is computed via solving the constrained optimization problem

$$\min |x_i - w|^2 \text{ s.t. } w \in X_i$$

using the algorithm in [18]. The latter algorithm is shown to approximate the true projection to arbitrarily-desired precision. Such precision is adjustable at the expense of increasing the computation time. In particular, given a precision $\zeta_i > 0$, the algorithm in [18] provides, in $O(\log(1/\zeta_i))$ steps, an approximation $\tilde{\Pi}_{X_i}(x_i)$ that verifies

$$|x_i - \tilde{\Pi}_{X_i}(x_i)|^2 \le |x_i - \Pi_{X_i}(x_i)|^2 + \zeta_i p_i(x_i).$$

<figure><img src="image_1.png" /><figcaption>Fig. 1. First two coordinates of the phase portrait of system (12) under (18)-(19) for the example system in Section V.</figcaption></figure>

For some $y \mapsto \{p_i(y)\}_{i=1}^3$ verifying Assumption 2.

For the proposed adaptive design of $\{\gamma_1, \gamma_2, \gamma_3\}$ and $\{\alpha_1, \alpha_2, \alpha_3\}$ in (18) and (19), we use the precision $\varepsilon = 0.3$, the adaptation gains $k_\gamma = 10$, $k_\alpha = 1$, and the projection precisions to verify

$$\alpha_i \zeta_i \le 1 \quad \forall i \in \{1, 2, 3\}. \quad (25)$$

The resulting trajectories are simulated on the interval $[0, 5]$ with discretization step $\Delta t := 10^{-2}$. The agents are initialized at $x_1(0) = [3 \quad 4]^\top$, $x_2(0) = [5 \quad 3/2]^\top$, and $x_3(0) = [-3 \quad 4]^\top$, and the gains are initially set to

$$\Gamma(0) := \begin{bmatrix} -3/25 & 0 & 0 \\ 0 & 2/3 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad \Theta(0) := \begin{bmatrix} 1/4 & 0 & 0 \\ 0 & -3/2 & 0 \\ 0 & 0 & 1/2 \end{bmatrix}.$$

From the phase portrait depicted in Figure 1, the three agents converge towards a neighborhood of the intersection set $X_o := X_1 \cap X_2 \cap X_3$. Furthermore, as shown in Figure 2, the weights $\gamma_1, \gamma_2, \gamma_3, \alpha_1, \alpha_2$, and $\alpha_3$ become positive after some adaptation time and converge to some constant values. This validates the conclusions of Theorem 1.

Due to the explicit form of the sets $X_1, X_2$, and $X_3$, we are able to analytically compute the exact projections and compare them with there approximations using the considered algorithm: the projection errors are shown to be non-null, see Figure 3, and to increase if we relax the projection precision $\zeta_1, \zeta_2$ and $\zeta_3$ while satisfying

$$\alpha_i \zeta_i \le 300 \quad \forall i \in \{1, 2, 3\}. \quad (26)$$

Finally, we can see in Figure 4 that, under (26), the conclusions of Theorem 1 remain valid, although the projection errors are larger than under (25).

## VI. CONCLUSION

This work proposed an adaptive and a fully-distributed redesign of an existing distributed gradient-descent algorithm. The approach allowed us to handle a class of bounded perturbation that can be the result of using approximate (fast) projection algorithms. As a result, we are able to approach a solution to the global optimization problem up to arbitrary small precisions. In the future, we aim to relax the convexity of the local sets $(X_1, \dots, X_N)$ while using proximal methods, and assess the network's behavior when $\bigcap_{i=1}^N X_i = \emptyset$.
<figure><img src="image_2.png" /><figcaption>Fig. 2. Evolution of $\Gamma$ and $\Theta$ according to (18) and (19).</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 3. Projection errors with $\alpha_i\zeta_i \le 1$.</figcaption></figure>

REFERENCES

[1] M. Doostmohammadian, A. Aghasi, M. Pirani, E. Nekouei, H. Zarrabi, R. Keypour, A. I. Rikos, and K. H. Johansson, "Survey of distributed algorithms for resource allocation over multi-agent systems," *Annual Reviews in Control*, vol. 59, p. 100983, Jan. 2025.

[2] M. Rabbat and R. Nowak, "Distributed optimization in sensor networks," in *Third International Symposium on Information Processing in Sensor Networks, 2004. IPSN 2004*, pp. 20–27, 2004.

[3] D. K. Molzahn, F. Dörfler, H. Sandberg, S. H. Low, S. Chakrabarti, R. Baldick, and J. Lavaei, "A survey of distributed optimization and control algorithms for electric power systems," *IEEE Transactions on Smart Grid*, vol. 8, no. 6, pp. 2941–2962, 2017.

[4] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, "A survey of distributed optimization," *Annual Reviews in Control*, vol. 47, pp. 278–305, 2019.

[5] A. Nedic and A. Ozdaglar, "Distributed subgradient methods for multi-agent optimization," *IEEE Transactions on Automatic Control*, vol. 54, no. 1, pp. 48–61, 2009.

<figure><img src="image_4.png" /><figcaption>Fig. 4. Projection errors with $\alpha_i\zeta_i \le 300$.</figcaption></figure>

[6] 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.

[7] A. Nedić, 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.

[8] T. Yang, Y. Wan, H. Wang, and Z. Lin, "Global optimal consensus for discrete-time multi-agent systems with bounded controls," *Automatica*, vol. 97, pp. 182–185, 2018.

[9] A. Nedić, A. Olshevsky, W. Shi, and C. A. Uribe, "Geometrically convergent distributed optimization with uncoordinated step-sizes," in *2017 American Control Conference (ACC)*, pp. 3950–3955, 2017.

[10] J. Xu, S. Zhu, Y. C. Soh, and L. Xie, "Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes," in *2015 54th IEEE Conference on Decision and Control (CDC)*, pp. 2055–2060, 2015.

[11] 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.

[12] J. Wang and N. Elia, "Control approach to distributed optimization," in *2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton)*, pp. 557–561, 2010.

[13] B. Gharesifard and J. Cortés, "Distributed continuous-time convex optimization on weight-balanced digraphs," *IEEE Transactions on Automatic Control*, vol. 59, pp. 781–786, Mar. 2014.

[14] G. Shi, K. H. Johansson, and Y. Hong, "Reaching an Optimal Consensus: Dynamical Systems That Compute Intersections of Convex Sets," *IEEE Transactions on Automatic Control*, vol. 58, pp. 610–622, Mar. 2013.

[15] P. Lin, W. Ren, H. Wang, and U. M. Al-Saggaf, "Multiagent rendezvous with shortest distance to convex regions with empty intersection: Algorithms and experiments," *IEEE Transactions on Cybernetics*, vol. 49, no. 3, pp. 1026–1034, 2019.

[16] Y. Lou, G. Shi, K. H. Johansson, and Y. Hong, "Approximate projected consensus for convex intersection computation: Convergence analysis and critical error angle," *IEEE Transactions on Automatic Control*, vol. 59, pp. 1722–1736, July 2014.

[17] Y. Lou, Y. Hong, and S. Wang, "Distributed continuous-time approximate projection protocols for shortest distance optimization problems," *Automatica*, vol. 69, pp. 289–297, 2016.

[18] I. Usmanova, M. Kamgarpour, A. Krause, and K. Levy, "Fast projection onto convex smooth constraints," in *International Conference on Machine Learning*, pp. 10476–10486, PMLR, 2021.

[19] Z. Chen and Y. Yan, "Adaptive autonomous synchronization of a class of heterogeneous multiagent systems," *IEEE Transactions on Automatic Control*, vol. 70, no. 3, pp. 2066–2073, 2025.

[20] T. Bazizi, M. Maghenem, P. Frasca, A. Loria, and E. Panteley, "On the perturbed projection-based distributed gradient-descent algorithm: A fully-distributed adaptive redesign (extended version)," *arXiv preprint arXiv:2509.03443*, 2025.

[21] J.-P. Aubin and A. Cellina, *Differential Inclusions: Set-Valued Maps and Viability Theory*, vol. 264 of *Grundlehren der mathematischen Wissenschaften*. Berlin, Heidelberg: Springer Berlin Heidelberg, 1984.

[22] S. Grünewälder, "Compact convex projections," *Journal of Machine Learning Research*, vol. 18, no. 219, pp. 1–43, 2018.

[23] A. Lazri, M. Maghenem, E. Panteley, and A. Loria, "Practical synchronization of perturbed networks of semi-passive systems," in *Proceedings of the 63rd IEEE Conference on Decision and Control*, (Milan, Italy), 2024.

[24] M. Maghenem, E. Panteley, and E. Loria, "Singular-perturbations-based analysis of dynamic consensus in directed networks of heterogeneous nonlinear systems," *IEEE Transactions on Automatic Control*, vol. 69, no. 7, pp. 4475–4490, 2024.

[25] E. Panteley and A. Loria, "Synchronization and dynamic consensus of heterogeneous networked systems," *IEEE Transactions on Automatic Control*, vol. 62, no. 8, pp. 3758–3773, 2017.

[26] C. M. Kellett, "A compendium of comparison function results," *Mathematics of Control, Signals, and Systems*, vol. 26, pp. 339–374, 2014.

[27] A. Hoffmann, "The distance to the intersection of two convex sets expressed by the distances to each of them," *Mathematische Nachrichten*, vol. 157, no. 1, pp. 81–98, 1992.