Accelerated distributed online aggregative optimization over unbalanced digraphs

Abstract

This paper investigates online distributed aggregative optimization of multi-agent systems over directed graphs characterized by row-stochastic mixing matrices, where each agent possesses a time-varying cost function determined by its individual decision variable and a global aggregative variable. To address this problem, we first propose a novel accelerated distributed algorithm incorporating gradient tracking and dynamic consensus mechanisms. Then, the designed algorithm integrates heavy-ball momentum to enhance convergence speed, and the linear convergence rate is rigorously analyzed as well. Finally, the theoretical results are validated in the multi-robot target tracking scenarios to show the effectiveness of the algorithm.

Keywords

distributed aggregative optimization directed graphs gradient tracking online learning dynamic regret

Introduction

In the past decades, distributed optimization (Yang et al., 2020) of multi-agent systems (MASs) has attracted lots of attention due to its broad applications, such as unmanned vehicles (Zhao et al., 2023) and smart grids (Braun et al., 2016). The objective of distributed optimization is to design an algorithm such that agents can cooperatively minimize the sum of local cost functions determined by its own decision variable. Recently, considering the cooperative feature and global performance of MASs, scholars developed a novel distributed optimization framework, called distributed aggregative optimization (DAO) (Li et al., 2021). Typically different from the distributed optimization issues, each cost function in DAO contains an extra global aggregative variable to perform some kind of aggregation of all the local variables, which is significant in many scenarios (e.g. improving the efficiency of machine learning computations, optimizing resource allocation, and so on). As a note, many DAO methods (Chen et al., 2024) have been conducted successively.

With similar research interests in distributed optimization, how to relax the requirements of graphs for DAO problems has attracted much attention. For instance, Chen et al. (2023) and Huang et al. (2025) studied the DAO problem over an undirected graph. To overcome the undirected assumption of graphs, few DAO strategies Xi et al. (2018) were proposed for MASs under weight-balanced digraphs. Apart from the connectivity of graphs, the DAO methods for MASs with time-varying characteristics were widely investigated as well. To be specific, Reisizadeh et al. (2022) proposed a two-time-scale decentralized gradient descent algorithm for a broad class of lossy sharing of information over time-varying graphs. Sun et al. (2016) studied nonconvex distributed optimization in a setting where the communication between nodes is modeled as a time-varying sequence of arbitrary digraphs. Carnevale et al. (2022) studied distributed optimization in multi-agent networks where the communications between nodes are modeled as a time-varying digraph. Rahili and Ren (2016) addressed a time-varying distributed convex optimization problem for continuous-time MASs. Moreover, considering an MAS that cost functions and constraints are both time-varying, the distributed optimization issues were solved in the literature (Zhang et al., 2021). However, most of the existing time-varying DAO results are only suitable for undirected graphs or weight-balanced digraphs. Therefore, to our knowledge, how to construct an online DAO framework for MASs with a time-varying aggregative cost function under weight-balanced digraphs is still an open issue.

As a note, in practical scenarios, the distributed optimization tasks are generally expected to be accomplished as soon as possible, which means the convergence speed is an important performance indicator (Liu et al., 2025) of a distributed algorithm. To accelerate convergence speed, Pan et al. (2023) proposed an accelerated Nash-equilibrium learning algorithm by integrating a momentum term into a gradient descent step by harnessing the smoothness of cost functions. Song et al. (2020) integrated the heavy-ball method with a consensus-based gradient method to seek the Nash equilibrium with an improved convergence rate.

Motivated by the aforementioned observations, this paper proposes an accelerated online DAO algorithm for MASs over unbalanced digraphs. The main contributions are as follows:

We first investigate the online DAO for MASs with time-varying aggregative cost functions over unbalanced digraphs, and a novel DAO algorithm framework is constructed using gradient tracking and dynamic consensus mechanisms.

By adopting the heavy-ball momentum technique, the convergence speed of the proposed DAO algorithm is enhanced. In addition, the linear convergence rate is rigorously analyzed as well.

Compared with the DAO algorithms (Carnevale et al., 2022; Chen et al., 2023; Huang et al., 2025; Rahili and Ren, 2016; Reisizadeh et al., 2022; Sun et al., 2016; Xi et al., 2018; Zhang et al., 2021) designed for undirected graphs or weight-balanced digraphs, the assumption of balanced is eliminated in this paper. Typically different from the accelerated DAO methods (Liu et al., 2025; Pan et al., 2023; Song et al., 2020), the proposed DAO strategies are suitable for MASs with time-varying cost functions.

The rest of this paper is organized as follows. Section “Preliminaries and problem formulation” introduces the formal problem formulation along with the necessary assumptions on the objective functions and the constraint sets. In Section “Algorithm design and convergency analysis,” the DAO algorithm is illustrated, and the convergence rate of the algorithm is rigorously analyzed. The simulation examples are conducted in Section “Numeric simulations” to demonstrate the efficacy and performance of the algorithm, and the conclusions are drawn in Section “Conclusions.”

Preliminaries and problem formulation

Notations

Let $R^{N}$ represent an N-dimensional real vector space. We use $X = COL (x_{1}, x_{2}, . . ., x_{N}) \in R^{N}$ to denote a stacked vector, where $x_{i} \in R^{n_{i}}$ . Vector X is positive if all entries are positive. Let diag(A) denote a diagonal matrix whose diagonal elements correspond to those of the matrix A where $A \in R^{N * N}$ . Let $∥ . ∥$ represent the standard Euclidean norm for vectors and matrices, and $ρ (A)$ denotes the spectral radius of a matrix. We use ⊗ to denote the Kronecker product, $I_{N}$ to denote the N-dimensional identity matrix, and $1_{N}$ to denote the N-dimensional vector of all ones. Furthermore, let $\nabla f$ denote the gradient (first-order derivative) of a function f, and let $\nabla_{1} f (X, Y)$ and $\nabla_{2} f (X, Y)$ denote the partial derivatives of a function f with respect to its first and second arguments, respectively. For a closed, convex, and compact set X, we define the projection of a vector y onto X as $P_{X} [y] = argmi n_{x \in X} ∥ x - y ∥$ . The distance from a point y to the set X is given by $dist (y, X) = mi n_{x \in X} ∥ x - y ∥$ .

Graph theory

Let $G = (V, E)$ denote a weighted directed graph, where $V = v_{1}, v_{2}, . ., v_{n}$ is the vertex set and $E \in V \times V$ represents the set of directed edges. A directed edge $(i, j) \in ε$ exists if agent j can receive information from the agent i. In this case, i is an in-neighbor of j, and j is an out-neighbor of i. For each vertex $i \in V$ , the set of in-neighbors is denoted by $N_{i}^{in} = {j \in V | (j, i) \in ε}$ , and the set of out-neighbors is denoted by $N_{i}^{out} = {j \in V | (i, j) \in ε}$ . The cardinality of a set is denoted by $| . |$ . The graph is said to be balanced if, for every vertex $i \in V$ , $N_{i}^{in} = N_{i}^{out}$ .

Problem formulation

In this paper, we consider a DAO problem over a strongly connected digraph (not necessarily balanced), formulated as

\begin{matrix} \begin{matrix} \min_{x_{t} \in X_{t}} F_{t} (x_{t}) = \sum_{i = 1}^{N} f_{i, t} (x_{i, t}, σ_{t} (x_{t})) \end{matrix} \end{matrix}

(1)

with

\begin{matrix} σ_{t} (x_{t}) = \frac{1}{N} \sum_{i = 1}^{N} ϕ_{i, t} (x_{i, t}) \end{matrix}

where $x_{t} = col (x_{1, t}, x_{2, t}, . . ., x_{N, t}) \in R^{Nq}$ is the global decision variable, and $x_{i, t} \in R^{q}$ denotes the local variable of the agent i. Each agent i possesses a private time-varying cost function $ϕ_{i, t} (.) : R^{q} \to R^{d}$ , and $σ_{t} (x) : R^{q} \to R^{d}$ is the aggregative function. $f_{i, t} : R^{q} \times R^{d} \to R$ represents the feature function for each agent i at time t. All agents communicate over a digraph, and agent i only has access to its own $x_{i}, ϕ_{i, t} (x_{i}), f_{i, t}$ , and local information from its neighbors at each time t. Assume that, at every time t, $x_{t}^{*}$ is the optimal solution of the feature equation $f_{i, t}$ . Given a time horizon $T > 1$ , the objective of the MAS is to minimize the dynamic regret defined as

\begin{matrix} \begin{matrix} R_{T} = \sum_{t = 0}^{T} f_{t} (x_{t}, σ_{t} (x_{t})) - \sum_{t = 0}^{T} f_{t} (x_{t}^{*}, σ_{t} (x_{t}^{*})) \end{matrix} \end{matrix}

(2)

In addition, we use $f_{t} (x_{t}, σ_{t} (x_{t})) = \sum_{i = 1}^{N} f_{i, t} (x_{i, t}, σ_{t} (x_{t}))$ to represent the global equation, where $σ_{t} (x_{t}) \in R^{d}$ . The derivatives of the first and second variables of $f_{t}$ are defined as

\begin{matrix} \nabla_{1} f_{t} (x_{t}, σ_{t} (x_{t})) \\ = col (\nabla_{1} f_{1, t} (x_{1, t}, σ_{t} (x_{1, t})), . . ., \nabla_{1} f_{N, t} (x_{N, t}, σ_{t} (x_{N, t}))) \\ \nabla_{2} f_{t} (x_{t}, s σ_{t} (x_{t})) \\ = col (\nabla_{2} f_{1, t} (x_{1, t}, σ_{t} (x_{1, t})), . . ., \nabla_{2} f_{N, t} (x_{N, t}, σ_{t} (x_{N, t}))) \end{matrix}

We define $ϕ_{t} (x_{t}) = col (ϕ_{1, t} (x_{1, t}), . . ., ϕ_{N, t} (x_{N, t}))$ and

\begin{matrix} \begin{matrix} \nabla ϕ_{t} (x_{t}) = [\begin{matrix} \nabla ϕ_{1, t} (x_{1, t}) & . . . & 0 \\ 0 & . . . & 0 \\ 0 & . . . & \nabla ϕ_{N, t} (x_{V, t}) \end{matrix}] \end{matrix} \end{matrix}

(3)

The derivative of a global variable is

\begin{matrix} \begin{matrix} \nabla f_{t} (x_{t}, σ_{t} (x_{t})) = & \nabla_{1} f_{t} (x_{t}, 1_{N} \otimes σ_{t} (x_{t})) + \nabla ϕ_{t} (x_{t}) 1_{N} \\ \otimes \sum_{i = 1}^{N} \nabla_{2} f_{i, t} (x_{i, t}, σ_{t} (x_{i, t})) \end{matrix} \end{matrix}

(4)

The DAO problems are investigated under following assumptions:

Assumption 1. (Chen et al., 2024) This directed graph is strongly connected, and the weighted adjacency matrix $A = [a_{i, j}]$ of the graph is row-stochastic. In addition,

\begin{matrix} a_{i, j} = {\begin{matrix} > 0, & j \in N_{i}^{out} \cup i \\ 0, & otherwise \end{matrix}, \sum_{j = 1}^{N} a_{i, j} = 1, \forall i \in V \end{matrix}

That is, A is a row-stochastic matrix.

Assumption 2. At any time $t > 0$ , the feasible set $X_{t}$ is non-empty, closed, and convex. Moreover, for each $t > 0$ , the function $f_{t} (x_{t}, y_{t})$ is differentiable and satisfies the following properties:

$f_{t} (x_{t}, y_{t})$ is μ-strongly convex, i.e., for any $x_{t}, x_{t}^{'} \in R^{Nq}$ and $y_{t}, y_{t}^{'} \in R^{Nd}$

\begin{matrix} \begin{matrix} f (x_{t}^{'}, y_{t}^{'}) - f (x_{t}, y_{t}) & \geq \nabla_{x} f {(x_{t}, y_{t})}^{T} (x_{t}^{'} - x_{t}) \\ + \nabla_{y} f {(x_{t}, y_{t})}^{T} (y_{t}^{'} - y_{t}) \\ + \frac{μ}{2} (∥ x_{t}^{'} - x_{t} ∥^{2} + ∥ y_{t}^{'} - y_{t} ∥^{2}) \end{matrix} \end{matrix}

$\nabla f_{t} (x_{t}, y_{t})$ is also $L_{1}$ -Lipschitz continuous, i.e., for any $x_{t}, x_{t}^{'} \in R^{Nq}$ and $y_{t}, y_{t}^{'} \in R^{Nd}$

\begin{matrix} ∥ \nabla f_{t} (x_{t}, y_{t}) - \nabla f_{t} (x_{t}^{'}, y_{t}^{'})) ∥ \leq L_{1} (∥ x_{t} - x_{t}^{'} ∥ + ∥ y_{t} - y_{t}^{'} ∥) \end{matrix}

$\nabla_{2} f_{t} (x_{t}, y_{t})$ is $L_{2}$ -Lipschitz continuous, i.e., for any $x_{t}, x_{t}^{'} \in R^{Nq}$ and $y_{t}, y_{t}^{'} \in R^{Nd}$

\begin{matrix} ∥ \nabla_{2} f_{t} (x_{t}, y_{t}) - \nabla_{2} f_{t} (x_{t}^{'}, y_{t}^{'})) ∥ \leq L_{2} (∥ x_{t} - x_{t}^{'} ∥ + ∥ y_{t} - y_{t}^{'} ∥) \end{matrix}

Remark 1. The convexity (and strong convexity) assumption in Assumption 2 is standard in distributed aggregative optimization literature, especially in multi-robot coordination and economic dispatch problems, where cost functions typically represent quadratic tracking errors, energy consumption, or resource allocation penalties. For example, Carnevale et al. (2022) made the same assumption about the objective function $f_{t} (x_{t}, σ_{t} (x_{t}))$ . More similar assumptions can be found in Zhang et al. (2021) and Braun et al. (2016), and cover many practical scenarios. Future works may develop new fundamental theory to address DAO issues for non-convex settings.

Assumption 3. At any time $t > 0$ , the aggregative function $ϕ_{t} (x_{t})$ is $L_{3}$ differentiable, and for all $x_{t} \in X_{t}$ , it satisfies $∥ \nabla ϕ_{t} (x_{t}) ∥ \leq L_{3}$ .

In addition, before the algorithms design, we first present some necessary lemmas as follows:

Lemma 1. Based on Assumption 2 (Li et al., 2021), when $α \in (0, 1 ∕ L_{1}]$ , for $x_{t}, x_{t}^{'} \in R^{Nq}$

\begin{matrix} ∥ x_{t} - α \nabla f_{t} (x_{t}, σ_{t} (x_{t})) - (x_{t}^{'} - α \nabla f_{t} (x_{t}^{'}, σ_{t} (x_{t}^{'})) ∥ \\ \leq (1 - μα) ∥ x_{t} - x_{t}^{'} ∥ \end{matrix}

Lemma 2. Under Assumption 1, there exists a constant $p \in (0, 1)$ such that

\begin{matrix} ∥ A σ - A^{\infty} σ ∥ \leq p ∥ σ - A^{\infty} σ ∥ \end{matrix}

for any $σ \in R^{Nd}$ , where A is a row-stochastic matrix (Chen et al., 2024), $A = A \otimes 1_{d}, p = ∥ A - \frac{1_{N} * 1_{N}^{d}}{N} ∥$ . Moreover, there exists a constant $k \in (0, 1)$ such that

\begin{matrix} ∥ A - I_{Nd} ∥ \leq k \end{matrix}

Lemma 3. For a nonnegative matrix $Z \in R^{N \times N}$ (Horn and Johnson, 2012), if there exists a positive vector $X \in R^{N}$ and a constant $λ > 0$ such that $ZX < λX$ , then $ρ (Z) < λ$ .

Lemma 4. For $S_{t}$ generated by (5c) (Xi et al., 2018), there exist a constant $δ \in (0, 1)$ and $λ \in (0, 1)$ such that for any $t > 0$ , $∥ S_{t} - S_{\infty} ∥ \leq δ λ^{t}$ .

Lemma 5. for $S_{t}$ generated by (5c) (Xi et al., 2018),

(1) for any $t > 0$ , $∥ {[{\tilde{S}}_{t}]}^{- 1} - {[{\tilde{S}}_{\infty}]}^{- 1} ∥ \leq {\tilde{s}}^{2} δ λ^{t}$ .

(2) for any $t > 0$ , $∥ {[{\tilde{S}}_{t + 1}]}^{- 1} - {[{\tilde{S}}_{\infty}]}^{- 1} ∥ \leq 2 {\tilde{s}}^{2} δ λ^{t}$

Algorithm design and convergency analysis

Algorithm design

In this section, we propose an accelerated online DAO algorithm for MASs over digraphs to realize (1).

Algorithm 1. Projected Aggregative Tracking Method with Heavy Ball
initialization:
$x_{i, - 1} = 0_{q}, x_{i, 0} \in X_{0}, s_{i, 0} = e_{i},$
$σ_{i, 0} = ϕ_{i, 0} (x_{i, 0}), y_{i, 0} = \nabla_{2} f_{i, 0} (x_{i, 0}, σ_{t} (x_{i, 0}))$
for t = 1,2,…,do
${\tilde{x}}_{i, t} = P_{X_{i, t}} [x_{i, t} - α (\nabla_{1} f_{i, t} (x_{i, t}, σ_{i, t}) +$
$\nabla ϕ_{i, t} (x_{i, t}) y_{i, t}) + β (x_{i, t} - x_{i, t - 1})]$ (1.1)
$x_{i, t + 1} = x_{i, t} + m ({\tilde{x}}_{i, t} - x_{i, t})$ (1.2)
$s_{i, t + 1} = \sum_{j = 1}^{N} a_{i, j} s_{j, t}$ (1.3)
$σ_{i, t + 1} = \sum_{j = 1}^{N} a_{i, j} σ_{j, t} + \frac{ϕ_{i, t + 1} (x_{i, t + 1})}{{[s_{i, t + 1}]}_{i}}$
$- \frac{ϕ_{i, t} (x_{i, t})}{{[s_{i, t}]}_{i}}$ (1.4)
$y_{i, t + 1} = \sum_{j = 1}^{N} a_{i, j} y_{j, t} + \frac{\nabla_{2} f_{i, t + 1} (x_{i, t + 1}, σ_{i, t + 1})}{{[s_{i, t + 1}]}_{i}}$
$- \frac{\nabla_{2} f_{i, t} (x_{i, t}, σ_{i, t})}{{[s_{i, t}]}_{i}}$ (1.5)
end for

Here, $x_{i, t} \in R^{q}, σ_{i, t} \in R^{d}, y_{i, t} \in R^{d}, {[s_{i, t}]}_{i}$ represents the ith component of $s_{i, t}$ . To accelerate the convergence of the algorithm, we introduce an auxiliary historical variable $x_{i, t} - x_{i, t - 1}$ . The constants $α > 0, β > 0$ , and $m > 0$ denote step-size parameters. (1.3) is designed to estimate the left Perron eigenvector $π = {(π_{1}, π_{2}, . . ., π_{N})}^{T}$ of the row-stochastic adjacency matrix A, where $\sum_{i = 1}^{N} π_{i} = 1$ . The variables $σ_{i, t}$ and $y_{i, t}$ are introduced to estimate $σ_{t} (x_{t})$ and $\sum_{i = 1}^{N} \nabla_{2} f_{i, t} (x_{i, t}, σ_{i, t})$ respectively.

Suppose that

\begin{matrix} σ_{t} & = col {σ_{1, t}, σ_{2, t}, . . ., σ_{N, t}} \in R^{Nd}, \\ y_{t} & = col {y_{1, t}, y_{2, t}, . . ., y_{N, t}} \in R^{Nd}, \\ s_{t} & = col {s_{1, t}, s_{2, t}, . . ., s_{N, t}} \in R^{N \times N}, \\ {\tilde{s}}_{t} & = diag (s_{t}), S_{t} = s_{t} \otimes I_{q}, {\tilde{S}}_{t} = {\tilde{s}}_{t} \otimes I_{q} . \end{matrix}

Then, the above algorithm can be written in the following stack form

\begin{matrix} {\tilde{x}}_{t} = P_{x_{t}} [x_{t} - α (\nabla_{1} f_{t} (x_{t}, σ_{t}) + \nabla ϕ_{t} (x_{t}) y_{t}) + β (x_{t} - x_{t - 1})] \end{matrix}

(5a)

\begin{matrix} x_{t + 1} = x_{t} + m ({\tilde{x}}_{t} - x_{t}) \end{matrix}

(5b)

\begin{matrix} S_{t + 1} = A S_{t} \end{matrix}

(5c)

\begin{matrix} σ_{t + 1} = A σ_{t} + {[{\tilde{S}}_{t + 1}]}^{- 1} ϕ_{t + 1} (x_{t + 1}) - {[{\tilde{S}}_{t}]}^{- 1} ϕ_{t} (x_{t}) \end{matrix}

(5d)

\begin{matrix} y_{t + 1} = A y_{t} + {[{\tilde{S}}_{t + 1}]}^{- 1} \nabla_{2} f_{t + 1} (x_{t + 1}, σ_{t + 1}) - {[{\tilde{S}}_{t}]}^{- 1} \nabla_{2} f_{t} (x_{t}, σ_{t}) \end{matrix}

(5e)

Remark 2. Under Assumption 1, the adjacency matrix A is primitive. By the Perron–Frobenius theorem, there exists a unique positive left eigenvector $π = {(π_{1}, π_{2}, . . ., π_{N})}^{T}$ such that $A^{\infty} = \lim_{t \to \infty} A^{t} = 1_{N} π, A^{\infty} = \lim_{t \to \infty} A^{t} = 1_{N} π \otimes I_{d}$ , where $πA = π$ and $\sum_{i = 1}^{N} π_{i} = 1$ .

From (5c), it can be deduced that $S_{t + 1} = A S_{t} = A^{t} S_{0}$ , so $S_{\infty} = A^{\infty} = 1_{N} π \otimes I_{d}$ . It is obvious that there exists an upper bound ŝ and $\tilde{s}$ such that $ŝ = su p_{t > 0} ∥ S_{t} ∥$ and $\tilde{s} = su p_{t > 0} ∥ {[{\tilde{S}}_{t}]}^{- 1} ∥$ .

First, Let’s define the weighted averages with respect to the Perron vector π as follows: ${\bar{σ}}_{t} = \sum_{i = 1}^{N} π_{i} σ_{i, t}, ȳ_{t} = \sum_{i = 1}^{N} π_{i} y_{i, t}$ . Suppose, $x_{t}^{*}, S_{t}^{*}, σ_{t}^{*}, y_{t}^{*}$ are the optimal solutions to the problem. The stack vector $z_{t}$ is defined as follows:

\begin{matrix} z_{t} = [\begin{matrix} ∥ x_{t + 1} - x_{t + 1}^{*} ∥ \\ ∥ x_{t + 1} - x_{t} ∥ \\ ∥ σ_{t + 1} - 1_{N} \otimes {\bar{σ}}_{t + 1} ∥ \\ ∥ y_{t + 1} - 1_{N} \otimes ȳ_{t + 1} ∥ \end{matrix}] \end{matrix}

where $∥ x_{t + 1} - x_{t + 1}^{*} ∥$ , $∥ x_{t + 1} - x_{t} ∥$ , $∥ σ_{t + 1} - 1_{N} \otimes {\bar{σ}}_{t + 1} ∥$ , and $∥ y_{t + 1} - 1_{N} \otimes ȳ_{t + 1} ∥$ represent the margin norm between the optimal value, the gap norm between each state, the norm of the aggregate variable tracking error, and the norm of the gradient variable tracking error, respectively. Moreover, two important vectors which will be used later are defined as follows:

\begin{matrix} u_{t} = [\begin{matrix} \sup_{x_{t} \in R^{Nq}, σ_{t} \in R^{Nd}} ∥ \nabla_{2} f_{t + 1} (x_{t}, σ_{t}) - \nabla_{2} f_{t} (x_{t}, σ_{t}) ∥ \\ \sup_{x_{t} \in R^{Nq}} ∥ ϕ_{t + 1} (x_{t}) - ϕ_{t} (x_{t}) ∥ \\ \sup_{x_{t} \in R^{Nq}} ∥ x_{t + 1}^{*} - x_{t}^{*} ∥ \\ \sup_{x_{t} \in R^{Nq}} ∥ x_{t}^{*} - x_{t - 1}^{*} ∥ \end{matrix}] \\ ξ_{t} = [\begin{matrix} ∥ ϕ_{t} (x_{t}) ∥ \\ ∥ \nabla_{2} f_{t} (x_{t}, σ_{t}) ∥ \\ 0 \\ 0 \end{matrix}] \end{matrix}

Convergence analysis

Three necessary lemmas of convergence analysis are first given as follows:

Lemma 6. Following equations hold:

1. $A^{\infty} σ_{t} = A^{\infty} {[{\tilde{S}}_{t}]}^{- 1} ϕ_{t} (x_{t})$ .

2. $A^{\infty} y_{t} = A^{\infty} {[{\tilde{S}}_{t}]}^{- 1} \nabla_{2} f_{t} (x_{t}, σ_{t})$

Proof. Multiplying both sides of (5d) by $A^{\infty}$ , we can obtain that

\begin{matrix} A^{\infty} σ_{t + 1} = & A^{\infty} σ_{t} + A^{\infty} {[{\tilde{S}}_{t + 1}]}^{- 1} ϕ_{t + 1} (x_{t + 1}) \\ - A^{\infty} {[{\tilde{S}}_{t}]}^{- 1} ϕ_{t} (x_{t}) \end{matrix}

Then,

\begin{matrix} A^{\infty} σ_{t + 1} - A^{\infty} {[{\tilde{S}}_{t + 1}]}^{- 1} ϕ_{t + 1} (x_{t + 1}) & = A^{\infty} σ_{t} - A^{\infty} {[{\tilde{S}}_{t}]}^{- 1} ϕ_{t} (x_{t}) \\ = A^{\infty} σ_{0} - A^{\infty} {[{\tilde{S}}_{0}]}^{- 1} ϕ_{0} (x_{0}) \end{matrix}

Under initial conditions $σ_{0} = ϕ_{0} (x_{0}) and S_{0} = I_{Nq}$ , it follows that $A^{\infty} σ_{t} = A^{\infty} {[{\tilde{S}}_{t}]}^{- 1} ϕ_{t} (x_{t})$ . With the similar analysis, $A^{\infty} y_{t} = A^{\infty} {[{\tilde{S}}_{t}]}^{- 1} \nabla_{2} f_{t} (x_{t}, σ_{t})$ can be easily proven. □

Lemma 7. Each component of vector $z_{t}$ satisfies following inequalities

\begin{matrix} ∥ x_{t + 1} - x_{t + 1}^{*} ∥ \leq & m (1 - μα) ∥ x_{t} - x_{t}^{*} ∥ + L_{1} mα ∥ σ_{t} - 1_{N} \otimes {\bar{σ}}_{t} ∥ \\ + L_{1} {\tilde{s}}^{3} δ λ^{t} mα ∥ ϕ_{t} (x_{t}) ∥ + L_{3} mα ∥ y_{t} - 1_{N} \otimes ȳ_{t} ∥ \\ + L_{3} {\tilde{s}}^{3} δ λ^{t} mα ∥ \nabla_{2} f_{t} (x_{t}, σ_{t}) ∥ + mβ ∥ x_{t} - x_{t - 1} ∥ \\ + mβ ∥ x_{t}^{*} - x_{t - 1}^{*} ∥, \end{matrix}

(6)

\begin{matrix} ∥ x_{t + 1} - x_{t} ∥ \leq & m (2 - μα) ∥ x_{t} - x_{t}^{*} ∥ + L_{1} mα ∥ σ_{t} - 1_{N} \otimes {\bar{σ}}_{t} ∥ \\ + L_{1} {\tilde{s}}^{3} δ λ^{t} mα ∥ ϕ_{t} (x_{t}) ∥ + L_{3} mα ∥ y_{t} - 1_{N} \otimes ȳ_{t} ∥ \\ + L_{3} {\tilde{s}}^{3} δ λ^{t} mα ∥ \nabla_{2} f_{t} (x_{t}, σ_{t}) ∥ + mβ ∥ x_{t} - x_{t - 1} ∥ \\ + mβ ∥ x_{t}^{*} - x_{t - 1}^{*} ∥, \end{matrix}

(7)

\begin{matrix} ∥ σ_{t + 1} - 1_{N} \otimes {\bar{σ}}_{t + 1} ∥ \leq & (p + w \tilde{s} L_{1} L_{3} mα) ∥ σ_{t} - 1_{N} \otimes {\bar{σ}}_{t} ∥ \\ + w \tilde{s} L_{3} m (2 - μα) ∥ x_{t} - x_{t}^{*} ∥ \\ + (w L_{1} L_{3} {\tilde{s}}^{4} δ λ^{t} mα + 2 w {\tilde{s}}^{2} δ λ^{t}) ∥ ϕ_{t} (x_{t}) ∥ \\ + w \tilde{s} L_{3}^{2} mα ∥ y_{t} - 1_{N} \otimes ȳ_{t} ∥ \\ + w L_{3}^{2} {\tilde{s}}^{4} δ λ^{t} mα ∥ \nabla_{2} f_{t} (x_{t}, σ_{t}) ∥ \\ + w \tilde{s} L_{3} mβ ∥ x_{t} - x_{t - 1} ∥ \\ + w \tilde{s} L_{3} mβ ∥ x_{t}^{*} - x_{t - 1}^{*} ∥ \\ + w \tilde{s} ∥ ϕ_{t + 1} (x_{t}) - ϕ_{t} (x_{t}) ∥, \end{matrix}

(8)

and

\begin{matrix} ∥ y_{t + 1} - 1_{N} \otimes ȳ_{t + 1} ∥ \leq & (p + b_{1} L_{3} mα) ∥ y_{t} - 1_{N} \otimes ȳ_{t} ∥ \\ + b_{1} m (2 - μα) ∥ x_{t} - x_{t}^{*} ∥ \\ + (b_{1} L_{1} mα + w \tilde{s} L_{2} k)) ∥ σ_{t} - 1_{N} \otimes {\bar{σ}}_{t} ∥ \\ + w {\tilde{s}}^{2} L_{2} δ λ^{t} (L_{1} {\tilde{s}}^{2} mα + L_{1} L_{3} {\tilde{s}}^{3} mα + 2) \\ ∥ ϕ_{t} (x_{t}) ∥ \\ + w {\tilde{s}}^{2} δ λ^{t} (L_{3} {\tilde{s}}^{2} mα + L_{2} L_{3}^{2} {\tilde{s}}^{3} mα + 2) \\ ∥ \nabla_{2} f_{t} (x_{t}, σ_{t}) ∥ \\ + b_{1} mβ ∥ x_{t} - x_{t - 1} ∥ + b_{1} mβ ∥ x_{t}^{*} - x_{t - 1}^{*} ∥ \\ + w {\tilde{s}}^{2} L_{2} ∥ ϕ_{t + 1} (x_{t}) - ϕ_{t} (x_{t}) ∥ \\ + w \tilde{s} ∥ \nabla_{2} f_{t + 1} (x_{t}, σ_{t}) - \nabla_{2} f_{t} (x_{t}, σ_{t}) ∥ \end{matrix}

(9)

Proof. The proof is provided in Appendix 1. □

Lemma 8. By organizing the above coefficients, we can obtain $z_{t + 1} \leq Π z_{t} + B_{t} u_{t} + C_{t} ξ_{t}$ ,

where

\begin{matrix} Π = [\begin{matrix} 1 - mμα & mβ & L_{1} mα & L_{3} mα \\ m (2 - μα) & mβ & L_{1} mα & L_{3} mα \\ w \tilde{s} L_{3} m (2 - μα) & w \tilde{s} L_{3} mβ & p + w \tilde{s} L_{1} L_{3} mα & w \tilde{s} L_{3}^{2} mα \\ b_{1} m (2 - μα) & b_{1} mβ & b_{1} L_{1} mα + w \tilde{s} L_{2} k & p + b_{1} L_{3} mα \end{matrix}] \end{matrix}

\begin{matrix} B_{t} = [\begin{matrix} 0 & 0 & 1 & mβ \\ 0 & 0 & 0 & mβ \\ 0 & w \tilde{s} & 0 & w \tilde{s} L_{3} mβ \\ w \tilde{s} & w {\tilde{s}}^{2} L_{2} & 0 & b_{1} mβ \end{matrix}] \end{matrix}

\begin{matrix} C_{t} = [\begin{matrix} L_{1} {\tilde{s}}^{3} δ λ^{t} mα & L_{1} {\tilde{s}}^{3} δ λ^{t} mα & 0 & 0 \\ L_{1} {\tilde{s}}^{3} δ λ^{t} mα & L_{1} {\tilde{s}}^{3} δ λ^{t} mα & 0 & 0 \\ w L_{1} L_{3} {\tilde{s}}^{4} δ λ^{t} mα + 2 w {\tilde{s}}^{2} δ λ^{t} & w L_{3}^{2} {\tilde{s}}^{4} δ λ^{t} mα & 0 & 0 \\ w {\tilde{s}}^{2} L_{2} δ λ^{t} (L_{1} {\tilde{s}}^{2} mα + L_{1} L_{3} {\tilde{s}}^{3} mα + 2) & w {\tilde{s}}^{2} δ λ^{t} (L_{3} {\tilde{s}}^{2} mα + L_{2} L_{3} {\tilde{s}}^{3} mα + 2) & 0 & 0 \end{matrix}] \end{matrix}

Proof. Above conclusion can be easily derived via simple calculation. □

Theorem 1. There exists a positive vector $X = (x_{1}, x_{2}, x_{3}, x_{4})$ and $α, β, m$ which satisfy that

\begin{matrix} x_{1} > \frac{L_{1} x_{3} + L_{3} x_{4}}{μ}, x_{2} > 0, x_{3} > 0 \\ m < \min {\frac{x_{2}}{2 x_{1}}, \frac{(1 - p) x_{3}}{2 w \tilde{s} L_{3} x_{1}}, \frac{(1 - p) x_{4} - w \tilde{s} L_{2} k x_{3}}{2 b_{1} x_{1}}}, \\ x_{4} > \frac{w \tilde{s} L_{2} k x_{3}}{1 - p}, α > 0 . \\ 0 < β < \min {\frac{μα x_{1} - L_{1} x_{3} L_{3} x_{4} α}{x_{2}}, \\ \frac{x_{2} + m (μα - 2) x_{1} - L_{1} x_{3} mα - L_{3} x_{4} mα}{m x_{2}}, \\ \frac{x_{3} + ω \tilde{s} L_{3} x_{1} m (μα - 2) - (p + ω \tilde{s} L_{1} L_{3} mα) x_{3} - ω \tilde{s} L_{3}^{2} x_{4} mα}{ω \tilde{s} L_{3} m x_{2}}, \\ \frac{x_{4} + b_{1} x_{1} m (μα - 2) - (b_{1} L_{1} mα + ω \tilde{s} L_{2} k) x_{3} - (ρ + b_{1} L_{3} mα) x_{4}}{b_{1} m x_{2}}} \end{matrix}

So that $ρ (Π) < 1$ .

Proof. By Lemma 3, if there exits a positive vector $X = (x_{1}, x_{2}, x_{3}, x_{4})$ , so that $Π X < X$ , then $ρ (Π) < 1$ . The inequalities are equal to:

\begin{matrix} 0 < β x_{2} < μα x_{1} - (L_{1} x_{3} + L_{3} x_{4}) α \\ 0 < mβ x_{2} < x_{2} + m (μα - 2) x_{1} - L_{1} x_{3} mα - L_{3} x_{4} mα \\ 0 < w \tilde{s} L_{3} mβ x_{2} < x_{3} + w \tilde{s} L_{3} x_{1} m (μα - 2) - (p + w \tilde{s} L_{1} L_{3} mα) x_{3} \\ - w \tilde{s} L_{3}^{2} x_{4} mα \\ 0 < b_{1} mβ x_{2} < x_{4} + b_{1} x_{1} m (μα - 2) - (b_{1} L_{1} mα + w \tilde{s} L_{2} k) x_{3} \\ - (p + b_{1} L_{3} mα) x_{4} \end{matrix}

Take first inequality as an example, since β and $x_{2}$ are both positive, the first less-than sign is easily obtained. By introducing the range of β and $x_{1}$ ,i.e., $0 < β < \frac{μα x_{1} - L_{1} x_{3} L_{3} x_{4} α}{x_{2}}$ and $x_{1} > \frac{L_{1} x_{3} + L_{3} x_{4}}{μ}$ , the second less-than sign can be obtained as well. With the similar analysis as mentioned above, other inequalities can also be proved by introducing parameter ranges in 1, which completes the proof. □

Regret analysis

In this section, the regret analysis of the proposed Algorithm 1 is presented. Suppose that $∥ u_{t} ∥$ and $∥ ξ_{t} ∥$ are both bounded, i.e., there exist constants C and D such that $∥ u_{t} ∥ < C$ and $∥ ξ_{t} ∥ < D$ . Then, we have following results

Theorem 2. There exists a constant $φ_{1} > 0$ , such that

\begin{matrix} R_{T} \leq & \frac{L_{1}}{2} (\frac{1 - p^{2 (T + 1)}}{1 - p^{2}} {∥ z_{0} ∥}^{2} + \frac{2 φ_{1} ∥ z_{0} ∥}{1 - p} (\frac{1 - p^{T}}{1 - p} - \\ \frac{1 - p^{2 (T + 1)}}{1 - p^{2}}) + \frac{(1 - 2 p) φ_{1}^{2}}{1 - p^{2}} T + \frac{1 - p^{2 (T + 1)}}{1 - p^{2}}) \end{matrix}

(10)

Proof. It is seen from Lemma 8 that $z_{t + 1} \leq Π z_{t} + B_{t} u_{t} + C_{t} ξ_{t}$ . Expanding this expression, we can get:

\begin{matrix} z_{t} \leq & Π^{t} z_{0} + \sum_{i = 0}^{t - 1} Π^{i} B_{t - 1 - i} u_{t - 1 - i} + \sum_{i = 0}^{t - 1} Π^{i} C_{t - 1 - i} ξ_{t - 1 - i} \end{matrix}

Taking the modulus on both sides

\begin{matrix} \begin{matrix} ∥ z_{t} ∥ \leq & ∥ Π^{t} z_{0} ∥ + \sum_{i = 0}^{t - 1} ∥ Π^{i} B_{t - 1 - i} ∥ ∥ u_{t - 1 - i} ∥ \\ + \sum_{i = 0}^{t - 1} ∥ Π^{i} C_{t - 1 - i} ∥ ∥ ξ_{t - 1 - i} ∥ \end{matrix} \end{matrix}

Because $∥ u_{t} ∥$ and $∥ ξ_{t} ∥$ are bounded, then

\begin{matrix} \begin{matrix} ∥ z_{t} ∥ \leq ∥ Π^{t} z_{0} ∥ + \sum_{i = 0}^{t - 1} ∥ Π^{i} (C B_{t - 1 - i} + D C_{t - 1 - i}) ∥ \end{matrix} \end{matrix}

Let $p = \max {ρ (Π), λ}$ , then $p \in (0, 1)$ . According to Xi et al. (2018), for some $φ_{1} > 0, 0 < i < t - 1$ , and $t > M$ , we have $∥ Π^{t} ∥ \leq φ_{1} p^{t}, ∥ Π^{i} (C B_{t - 1 - i} + D C_{t - 1 - i}) ∥ \leq φ_{1} p^{t}$ .

Then, $∥ z_{t} ∥ \leq p^{t} ∥ z_{0} ∥ + \sum_{i = 0}^{t - 1} φ_{1} p^{i}$ . Squaring both sides, we have

\begin{matrix} {∥ z_{t} ∥}^{2} & \leq p^{2 t} {∥ z_{0} ∥}^{2} + 2 p^{t} φ_{1} ∥ z_{0} ∥ \sum_{i = 0}^{t - 1} p^{i} + φ_{i}^{2} (\sum_{i = 0}^{t - 1} p^{i})^{2} \\ = p^{2 t} {∥ z_{0} ∥}^{2} + 2 p^{t} φ_{1} ∥ z_{0} ∥ \frac{1 - p^{t}}{1 - p} + φ_{1}^{2} (\frac{1 - p^{t}}{1 - p})^{2} \\ = p^{2 t} {∥ z_{0} ∥}^{2} + 2 φ_{1} ∥ z_{0} ∥ \frac{p^{t} - p^{2 t}}{1 - p} + φ_{1}^{2} \frac{1 - 2 p + p^{2 t}}{1 - p} \end{matrix}

(11)

According to Assumption 2, $f_{t} (x_{t}, y_{t})$ is $L_{1}$ smooth, so it holds that $f_{t} (x_{t}, σ_{t} (x_{t})) - f_{t} (x_{t}^{*}, σ_{t} (x_{t}^{*})) \leq \frac{L_{1}}{2} {∥ x_{t} - x_{t}^{*} ∥}^{2}$

Then,

\begin{matrix} R_{T} & = \sum_{t = 0}^{T} f_{t} (x_{t}, σ_{t} (x_{t})) - \sum_{t = 0}^{T} f_{t} (x_{t}^{*}, σ_{t} (x_{t}^{*})) \\ \leq \sum_{t = 0}^{T} \frac{L_{1}}{2} {∥ x_{t} - x_{t}^{*} ∥}^{2} \\ \leq \sum_{t = 0}^{T} \frac{L_{1}}{2} {∥ z_{t} ∥}^{2} \end{matrix}

(12)

By inserting (11) into (12), Theorem 2 is proven. □

Based on Theorem 2, the convergence rate of average regret satisfies

\begin{matrix} \lim_{T \to \infty} R_{T} ∕ T = \frac{L_{1}}{2} \frac{(1 - 2 p) φ_{1}^{2}}{{(1 - p)}^{2}} \end{matrix}

Remark 3. That is, our algorithm achieves linear convergence for aggregative optimization over directed graphs with row-stochastic matrices. In addition, since the computation complexities of $\nabla_{1} f_{i, t}$ , $\nabla_{2} f_{i, t}$ , $\nabla ϕ_{i, t} (x_{i, t})$ ( $O (qd)$ ), one heavy-ball term, $P_{X_{i, t}}$ , $s_{i, j}$ , σ and y are $O (G_{i})$ , $O (G_{i})$ , $O (qd)$ , $O (q)$ , $O (Π)$ , $O (| N_{i}^{out} | * N)$ , $O (| N_{i}^{out} | * d)$ and $O (| N_{i}^{out} | * d)$ , respectively, we have

\begin{matrix} Com p^{PATM - HB} & = O (G_{i} + G_{i} + qd + Π + q) + O (| N_{i}^{out} | \\ * (N + 2 d)) \end{matrix}

By contrast, the presented result “heavy-ball nonlinear perturbation-based gradient-tracking (HBNP-GT)” in Doostmohammadian and Rabiee (2025) performs exponential convergence, and the computation complexity is

\begin{matrix} Com p^{HBNP - GT} = O (| N_{i}^{out} | * q) + O (G_{i}) . \end{matrix}

Based on above analysis, the introduction of heavy-ball momentum term in this paper does not alter the order of the computational or communication complexity since the momentum term only incurs a constant additional cost $O (q)$ associated with storing a previous iterate and performing basic vector operations. Moreover, our result is suitable for MASs with time-varying cost function under row-stochastic and switching graphs, which is typically different from result (Doostmohammadian and Rabiee, 2025).

As a note, it is seen that the proposed PATM-HB algorithm has polynomial per-iteration complexity with respect to the network size N. However, the scalability of the network is inherently constrained by the Perron vector estimation mechanism, which may limit the applicability of algorithm in large-scale scenario or strict communication constraints.

Theorem 3. Let

\begin{matrix} γ_{t} = \sup_{x \in R^{N}} | dist (x_{t}, X_{t + 1}) - dist (x_{t}, X_{t}) |, \end{matrix}

then we have

\begin{matrix} dist (x_{t}, X_{t}) & \leq {(1 - m)}^{t} dist (x_{0}, X_{0}) + \sum_{i = 0}^{t - 1} {(1 - m)}^{t - i} γ^{i} \end{matrix}

Proof.

\begin{matrix} dist (x_{t + 1}, X_{t + 1}) & \overset{(a)}{=} dist (x_{t} + m ({\tilde{x}}_{t} - x_{t}), X_{t + 1}) \\ \overset{(b)}{\leq} dist (x_{t} + m ({\tilde{x}}_{t} - x_{t}), X_{t}) + γ_{t} \end{matrix}

(13)

where in (a), we substitute (5b) into left side, and in (b), we subtract the term $γ_{t} = \sup_{x \in R^{N}} | dist (x_{t}, X_{t + 1}) - dist (x_{t}, X_{t}) |$ .

\begin{matrix} dist (x_{t} + m ({\tilde{x}}_{t} - x_{t}), X_{t}) = \min_{y \in X_{t}} | x_{t} + m ({\tilde{x}}_{t} - x_{t}) - y | \end{matrix}

(14)

Let $o_{t} \in X_{t}$ , $| x_{t} - o_{t} | = dist (x_{t}, X_{t})$ , then we add and extract the term $(1 - m) o_{t}$ in the (14)

\begin{matrix} dist (x_{t} + m ({\tilde{x}}_{t} - x_{t}), X_{t}) & = dist (x_{t} + m ({\tilde{x}}_{t} - x_{t}) + (1 - m) o_{t} \\ - (1 - m) o_{t}, X_{t}) \\ = dist ((1 - m) (x_{t} - o_{t}) + m {\tilde{x}}_{t} \\ + (1 - m) o_{t}, X_{t}) \\ = \min_{y \in X_{t}} | (1 - m) (x_{t} - o_{t}) + m {\tilde{x}}_{t} \\ + (1 - m) o_{t} - y | \end{matrix}

\begin{matrix} \leq (1 - m) | x_{t} - o_{t} | + \min_{y \in X_{t}} | m {\tilde{x}}_{t} \\ + (1 - m) o_{t} - y | \\ = (1 - m) dist (x_{t}, X_{t}) + dist (m {\tilde{x}}_{t} \\ + (1 - m) o_{t}, X_{t}) \end{matrix}

(15)

Due to ${\tilde{x}}_{t}, o_{t} \in X_{t}$ , then $m {\tilde{x}}_{t} + (1 - m) o_{t} \in X_{t}$ , so $dist (m {\tilde{x}}_{t} + (1 - m) o_{t}, X_{t}) = 0$ . Substituting (14) and (15) into (13), we can get

\begin{matrix} dist (x_{t + 1}, X_{t + 1}) \leq (1 - m) dist (x_{t}, X_{t}) + γ_{t} \end{matrix}

(16)

The elements of (16) are always positive, then

\begin{matrix} dist (x_{t}, X_{t}) & \leq {(1 - m)}^{t} dist (x_{0}, X_{0}) + \sum_{i = 0}^{t - 1} {(1 - m)}^{t - i} γ^{i} \end{matrix}

□

Remark 4. (Doostmohammadian et al., 2025) addressed the distributed optimization issue of communication delay under strongly connected digraphs by introducing an augmented consensus formulation to transform the time-delay system into a higher-dimensional non-time-delay system, and proves

\begin{matrix} ρ (\bar{C}) \leq ρ {(C)}^{\frac{1}{1 + τ}} < 1 \end{matrix}

where $\bar{C}$ is the augmented matrix of C. However, our result cannot be directly extended to the case with time delay since the considered graph is row-stochastic and switching graphs (see Assumption 1). Future work may investigate aggregative optimization for the systems with time delay by reconstructing the gradient tracking algorithm and conducting spectral analysis again.

Moreover, some practical DAO problems may subject to coupling resource constraints. To handle above situation, we extend the accelerated distributed online aggregative optimization framework by incorporating a primal–dual mechanism. To be specific, consider the following constrained aggregative optimization problem:

\begin{matrix} \begin{matrix} \min_{x_{t} \in X_{t}} F_{t} (x_{t}) = \sum_{i = 1}^{N} f_{i, t} (x_{i, t}, σ_{t} (x_{t})) \\ s . t . g_{t} (σ_{t} (x_{t})) \leq 0 \end{matrix} \end{matrix}

(17)

where $g_{t} (.)$ represents a convex resource constraint. By introducing the Lagrange multiplier $λ_{t} \in R_{+}^{m}$ as shown in Turan et al. (2020), a potential solution is first to transform the above problem into the following unconstrained formulation

\begin{matrix} \begin{matrix} \min_{x_{t} \in X_{t}} \max_{λ_{t} \geq 0} G_{t} (x_{t}, λ_{t}) = \sum_{i = 1}^{N} f_{i, t} (x_{i, t}, σ_{t} (x_{t})) + λ_{t} g (σ_{t} (x_{t})), \end{matrix} \end{matrix}

(18)

then the proposed algorithm may be applied to solve the constrained optimization issue.

Numeric simulations

This section presents numerical experiments to validate the effectiveness of the proposed algorithm. The experimental scenario involves a defense robot positioning task, where five factories are distributed at fixed locations. Each factory is assigned one robot, and the objective is to optimize the collective positioning strategy under communication constraints.

The objective of the robot positioning task is to select five optimal locations such that the total distance from each robot to its assigned factory is minimized, while also reducing the dispersion of the robots relative to the factory centers. The five robots are unable to communicate arbitrarily; instead, they can only exchange information according to a predefined directed communication graph, as illustrated in Figure 1.

Figure 1.

Communication graph.

The adjacency matrix A =

\begin{matrix} [\begin{matrix} 0.5 & 0.5 & 0 & 0 & 0 \\ 0 & 0.2 & 0.3 & 0.5 & 0 \\ 0 & 0 & 0.5 & 0.5 & 0 \\ 0 & 0 & 0.3 & 0.3 & 0.4 \\ 0.4 & 0 & 0 & 0.1 & 0.5 \end{matrix}] \end{matrix}

The fixed locations of the five factories are given as $b_{1} = (1, 1), b_{2} = (2, 3), b_{3} = (3, 1), b_{4} = (4, 3.5)$ , and $b_{5} = (4.5, 3.3)$ . The objective function for each agent is formulated as

\begin{matrix} f_{t} (x_{t}, σ_{t}) = \frac{a_{1}}{2} {∥ x_{t} - b_{t} ∥}^{2} + \frac{a_{2}}{2 N} {∥ σ_{t} (x_{t}) - b_{t} ∥}^{2}, \end{matrix}

where $σ_{t} (x_{t}) = \frac{\sum_{i = 0}^{N} ϕ_{i, t} (x_{t})}{N}$ , $ϕ_{i, t} (x_{i . t}) = a_{3} x_{i, t} + a_{t}$ . As a note, $a_{t}$ models a dynamic disturbance or environmental factor that influences the protective performance of the robots $a_{t} = rcol (\cos (\frac{t}{2 π} g), \sin (\frac{t}{2 π} g))$ . Each robot must select a construction site from a time-varying feasible set defined as $X_{t} = {x \in R^{2} | 0 < x < G_{t}}$ , $G_{t} = col (10 - 5 e^{- t}, 10 - 5 e^{- t})$ .

In this experiment, we set $a_{1} = 1$ , $a_{2} = 1$ . For the parameters in the proposed algorithm, we choose $α = 0.8$ , $β = 0.8$ , and $m = 0.5$ . As clearly illustrated in Figure 2, the average regret converges consistently to a constant value over time, demonstrating the stability and effectiveness of the algorithm in both static and time-varying settings.

Figure 2.

Evolution of average regret with parameters $α = 0.8$ , $β = 0.8$ and $m = 0.5$ .

We define the optimality gap as $ξ_{t} = ∥ x_{t} - b_{t} ∥$ and the variation of the optimality gap over time is plotted below in Figure 3.

Figure 3.

Evolution of optimal gap for $α = 0.8$ , $β = 0.8$ , and $m = 0.5$ .

To highlight the effect of our gradient tracking method, we set $α = 0.2$ , $β = 0.8$ , and $m = 0.2$ to observe the speed of convergence. This result is shown in Figure 4.

Figure 4.

Evolution of average regret with parameters $α = 0.2$ , $β = 0.8$ and $m = 0.2$ .

In this situation, the variation of the optimality gap over time is plotted in Figure 5.

Figure 5.

Evolution of optimal gap for $α = 0.2$ , $β = 0.8$ , and $m = 0.2$ .

From the simulation results, it is seen that as the weight of tracking term decreases, the convergence speed slows down.

Here, we provide a simulation example the A-DAGT algorithm with heavy-ball term in Chen et al. (2024). By setting $α = 0.01$ , $β = 0.5$ , and $β_{hb} = 0.2$ , the speed of convergence is shown in Figure 6.

Figure 6.

Evolution of average regret with parameters $α = 0.01$ , $β = 0.5$ , and $β_{hb} = 0.2$ for A-DAGT algorithm with heavy-ball term.

To compare with the projected aggregative tracking algorithm in Carnevale et al. (2022), we assume that the objective function is the aforementioned $ϕ_{i, t} (x_{i . t})$ , while imposing no restrictions on the graph, which is defined as an undirected graph. Then, we let $α = 0.6$ and $β = 0.5$ . The speed of convergence is shown in Figure 7.

Figure 7.

Evolution of average regret with parameters $α = 0.6$ , $β = 0.5$ , and $β_{hb} = 0.2$ for the projected aggregative tracking algorithm in Carnevale et al. (2022).

Based on the above simulation result, by adjusting the parameters $α, β$ , and m, our algorithm can achieve the same convergence rate as the A-DAGT algorithm with the above two algorithms.

In what follows, an extra simulation is conducted for an optimal resource allocation setting. To be specific, consider eight fixed terminals with resource demand $b_{i} \in R^{2}$ , and a central server who needs to allocate resource $x_{t} \in R^{2}$ to these terminals, where the feasible range of each terminal is $X_{t} = {x \in R^{2} | 0 < x < G_{t}}$ , and an aggregative term $σ_{t} (x_{t})$ is introduced to reflect the user’s experience. The eight robotics can exchange information in such a communication graph Figure 8.

Figure 8.

Communication graph for eight terminals.

The adjacency matrix is:

\begin{matrix} [\begin{matrix} 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.5 & 0.3 & 0 & 0 & 0.2 & 0 & 0 \\ 0 & 0 & 0.5 & 0.5 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.3 & 0.7 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.4 & 0.6 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.6 & 0.2 & 0.2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.4 & 0.6 \\ 0.5 & 0 & 0 & 0 & 0 & 0 & 0 & 0.5 \end{matrix}] \end{matrix}

In the above setting, the objective function is formulated as:

\begin{matrix} f_{t} (x_{t}, σ_{t}) = {∥ x_{t} - b ∥}^{2} + {∥ σ_{t} (x_{t}) - b ∥}^{2}, s . t . x_{t} \in X_{t}, \end{matrix}

where $b_{1} = (10, 10)$ , $b_{2} = (4, 5)$ , $b_{3} = (3, 16)$ , $b_{4} = (3.5, 15)$ , $b_{5} = (7, 18)$ , $b_{6} = (2, 18)$ , $b_{7} = (2.5, 6.5)$ , $b_{8} = (5, 10)$ , $G_{t} = col (10 + 8 * \frac{1}{1 + t}, 10 + 8 * \frac{1}{1 + t})$ , and $σ_{t} (x_{t}) = \sum_{i = 1}^{5} \frac{1}{5} (x_{i, t} + \frac{1}{1 + t} (1, 1))$ . Let $α = 0.2$ , $β = 0.8$ , and $m = 0.5$ , the average regret and the variation of optimality gap are plotted in Figures 9 and 10, respectively. Clearly, the proposed algorithm (5a) to (5e) still works in optimal resource allocation setting.

Figure 9.

Evolution of average regret with parameters $α = 0.2$ , $β = 0.8$ , and $m = 0.5$ for resource allocation problem.

Figure 10.

Evolution of optimal gap with parameters $α = 0.2$ , $β = 0.8$ , and $m = 0.5$ for resource allocation problem.

Conclusions

This paper has investigated online DAO of MASs over directed graphs characterized by row-stochastic mixing matrices, where each agent possesses a time-varying cost function determined by its individual decision variable and a global aggregative variable. First, we have proposed a novel accelerated distributed algorithm incorporating gradient tracking and dynamic consensus mechanisms. Then, the designed algorithm has integrated heavy-ball momentum to enhance convergence speed, and the linear convergence rate has been rigorously analyzed as well. In final, the theoretical results have been validated in the multi-robot target tracking scenarios to show the effectiveness of algorithm.

Footnotes

Appendix 1 Acknowledgements

The author thanks the anonymous reviewers and the Associate Editor for their valuable comments and suggestions, which helped improve the quality of this manuscript.

ORCID iD

Jiahui Fang

Ethical considerations

This article does not contain any studies with human or animal participants. There are no human participants in this article and informed consent is not required.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

Declaration of conflicting interests

The author declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Data availability statement

The data that support the findings of this study are available from the corresponding author upon reasonable request.

References

Braun

Grüne

Kellett

, et al. (2016) A distributed optimization algorithm for the predictive control of smart grids. IEEE Transactions on Automatic Control 61(12): 3898–3911.

Carnevale

Camisa

Notarstefano

(2022) Distributed online aggregative optimization for dynamic multirobot coordination. IEEE Transactions on Automatic Control 68(6): 3736–3743.

Chen

Wen

Fang

, et al. (2024) Achieving linear convergence in distributed aggregative optimization over directed graphs. IEEE Transactions on Systems, Man, and Cybernetics: Systems 54(7): 4529–4541.

Chen

Wang

, et al. (2023) Distributed aggregative optimization via finite-time dynamic average consensus. IEEE Transactions on Network Science and Engineering 10(6): 3223–3231.

Doostmohammadian

Rabiee

(2025) Momentum-based accelerated algorithm for distributed optimization under sector-bound nonlinearity. arXiv. https://doi.org/10.48550/arXiv.2506.22855

Doostmohammadian

Ramesh

Aghasi

(2025) Delay-tolerant augmented-consensus-based distributed directed optimization. Systems & Control Letters 205: 106260.

Horn

Johnson

(2012) Matrix analysis. Cambridge University Press.

Huang

Yang

, et al. (2025) Distributed aggregative optimization algorithm for solving multi-robot formation problem. IEEE Transactions on Control of Network Systems 12(3): 2102–2114.

Xie

Hong

(2021) Distributed aggregative optimization over multi-agent networks. IEEE Transactions on Automatic Control 67(6): 3165–3171.

10.

Liu

Chen

Cai

, et al. (2025) Accelerated distributed aggregative optimization. IEEE Transactions on Automatic Control 70(9): 5792–5807.

11.

Pan

, et al. (2023) Distributed Nash equilibrium learning for average aggregative games: Harnessing smoothness to accelerate the algorithm. IEEE Systems Journal 17(3): 4855–4865.

12.

Rahili

Ren

(2016) Distributed continuous-time convex optimization with time-varying cost functions. IEEE Transactions on Automatic Control 62(4): 1590–1605.

13.

Reisizadeh

Touri

Mohajer

(2022) Distributed optimization over time-varying graphs with imperfect sharing of information. IEEE Transactions on Automatic Control 68(7): 4420–4427.

14.

Song

, et al. (2020) Distributed heavy-ball Nash equilibrium seeking algorithm in aggregative games. In: 2020 39th Chinese control conference (CCC), Shenyang, China, 27–29 July 2020, pp.5019–5024. IEEE.

15.

Sun

Scutari

Palomar

(2016) Distributed nonconvex multiagent optimization over time-varying networks. In: 2016 50th Asilomar conference on signals, systems and computers, Pacific Grove, CA, 6–9 November 2016, pp.788–794. IEEE.

16.

Turan

Uribe

Wai

, et al. (2020) Resilient primal–dual optimization algorithms for distributed resource allocation. IEEE Transactions on Control of Network Systems 8(1): 282–294.

17.

Mai

Xin

, et al. (2018) Linear convergence in optimization over directed graphs with row-stochastic matrices. IEEE Transactions on Automatic Control 63(10): 3558–3565.

18.

Yang

Pan

Zhang

, et al. (2020) Distributed optimization for multi-agent systems with time delay. IEEE Access 8: 123019–123025.

19.

Zhang

Dall’Anese

Hong

(2021) Online proximal-ADMM for time-varying constrained convex optimization. IEEE Transactions on Signal and Information Processing over Networks 7: 144–155.

20.

Zhao

Han

, et al. (2023) A review of unmanned vehicle distribution optimization models and algorithms. Journal of Traffic and Transportation Engineering 10(4): 548–559.