Event-triggered distributed optimization of multi-agent systems with time delay

1.   Introduction

Due to its extensive applications, cooperative control of multi-agent systems (MASs) has received increasing attention for the past few years, such as consensus control ^[1,2], containment control ^[3], formation control ^[4] and resource allocation ^[5,6]. Distributed optimization problem (DOP), one of the hot topics of cooperative control, has been widely studied from different aspects. In DOP, each agent has its own local objective function, which is not available to other agents. The objective function is minimized by selecting an optimal action, where the objective function is defined as a convex combination of local objective functions. Optimization theories ^{[7,8,9,10,11]} provide the fundamental tools to address DOP.

In the field of DOP, there were some studies ^[12,13] about distributed consensus-based gradient methods for convex cost functions. Recently, DOP of continuous-time MASs have been widely researched ^[14,15,16]. In ^[14], the research was mainly based on nonuniform gradient gain and finite time convergence. In ^[15], the time-varying loss function was studied. A proportional-integral-differential algorithm was introduced in ^[16].

The majority of current DOP was studied using continuous-time control algorithms. This control strategy is relatively impractical and inefficient as it results in a wastage of energy. In practice, each agent often faces limited resources and, thus, is expected to update its control signals as infrequently as possible. In order to alleviate the communication load in MASs, a discrete-time control method known as event-triggered control has been developed. This control strategy is aperiodic and neighboring agents only need to communicate at specific time instants determined by pre-designed triggering conditions, the effectiveness of which was systematically illustrated in ^{[17,18,19,20,21,22]}. In ^[17], the research studied the event-triggered DOP for nonlinear MASs in undirected and connected communication networks. In ^[18], two event-triggered control protocols were proposed to solve convex DOP under the directed graph. Moreover, in ^[19], an event-based control protocol was proposed to solve non-convex DOP. An adaptive event-triggered communication was introduced in ^[20]. In ^[21], the author explored both event-triggered and time-triggered algorithms to solve DOP. In ^[22], the paper examined the prescribed-time optimization problem of MASs under two control protocols, specifically the continuous-time protocol and its event-triggered control protocol.

All of the above results focused on networks without time delay. In fact, the hardware performance of each agent requires a certain input {{time delay}} for effective communication and processing of information. Hence, the analysis and management of time delay is crucial in understanding and improving the performance of MASs, particularly in cases where there are a large number of agents and intricate communication networks. In the works ^{[23,24,25,26]}, DOP of MASs with time delay have been studied.

Inspired by the previously discussed works, this paper investigates an event-triggered distributed optimization algorithm with time delay under an undirected communication graph. Each agent utilizes its own gradient information as well as delayed information from its neighbors and itself to search for solutions. The connection between the equilibrium point of MASs and optimal solutions are discussed. Compared with the algorithms in ^[27,28,29], our algorithm does not require continuous communication between agents and it takes into account that there is a delay in the communication between agents. The algorithm proposed here is based on event-triggered transmissions that can alleviate the communication load and decrease the frequency of controller iterates, resulting in saved network resources. Furthermore, the stability property of MASs with time delay is analyzed using the Lyapunov stability theory, and the Zeno-behavior of triggering time sequence is excluded.

The rest of this article is arranged as follows. The basic theories of graph theory and dynamic systems are provided in Section 2. Section 3 presents the main results. In Section 4, a numerical example is given, which illustrates the effectiveness of the proposed algorithm. Concluding remarks are made in Section 5.

Notations: Let $\mathbb {R}$, $\mathbb{R}^{n}$, and $\mathbb{R}^{n\times n}$ be a set of real numbers, $n$-dimensional real vectors, and $n\times n$ real matrices, respectively. Let $I_{n}\in\mathbb{R}^{n\times n}$ be the identity matrix. $\textbf{1}_{n} = [1, \cdots, 1]^T$. $A^{T}$ is the transpose of $A$. $\nabla f_{i}(x) = \frac{\partial f_{i}(x) }{\partial x}$ is gradient of the function $f_{i}(x)$. $\otimes$ is the Kronecker product. $\|A\|$ denotes the induced matrix norm and $\| \cdot \|$ represents the Euclidean norm for $x\in \mathbb{R}^{n}$. $\lambda _{max}(A)$ is the largest eigenvalue of symmetric matrix $A$.

2.   Preliminaries

In this section, the concepts related to graph theory will be introduced, and then the distributed optimization problem is presented.

2.1.   Grapy theory

Let $\mathcal{G} = \{\mathcal{V}, \mathcal{E}, \mathcal{A}\}$ be an undirected and connected graph used to model a network of $N$ agents, where $\mathcal{V} = \{1, 2, ..., N\}$ denotes the set of nodes and $\mathcal{E} = \{(i, j) \in \mathcal{V}\times \mathcal{V} \}$ denotes the set of edges. Let $\mathcal{A} = [a_{ij}]$ be the adjacency matrix of graph $\mathcal{G}$, and $a_{ij} = a_{ji} = 1$ if $(i, j) \in \mathcal{E}$ and $a_{ij} = 0$, otherwise. $\mathcal{N}_i = \{ j \in \mathcal{V} : (i, j) \in \mathcal{E}\}$ is the set of neighbors of node $i$. The degree matrix of graph $\mathcal{G}$ is denoted by $\mathcal{D} = diag\{d_{1}, d_{2}, ..., d_{N}\}$ and $d_{i} = \sum_{j \in \mathcal{N}_i}a_{ij}$. Furthermore, the Laplacian matrix $L = [l_{ij}]$ is defined as $L = \mathcal{D}-\mathcal{A}$. If graph $\mathcal{G}$ is a connected undirected graph, one can derive that the eigenvalues of matrix $L$ satisfy $0 = \lambda_1 < \lambda_2\le...\le\lambda_N$.

2.2.   Problem formulation

The following DOP is studied in this paper

where each agent $i\in\mathcal{V}$ has a local convex function $f_{i}:\mathbb{R}^{n}\rightarrow \mathbb{R}$. Each of the functions $f_{i}$ is private and accessible only to the corresponding agent $i$. The aim of each agent is to solve the optimization problem in (2.1) cooperatively, and the interaction topology among the agents is expressed by graph $\mathcal{G}$. For convenience, denote $f(x) = \sum^{N}_{i = 1} f_{i}(x_{i})$, $x = [x^{T}_{1}, ..., x^{T}_{N}]^{T}\in \mathbb{R}^{Nn}$.

Consider the MASs with each agent modeled by first-order dynamics as follows:

where $x_{i}(t)\in \mathbb{R}^{n}$ represents state vector of agent $i$, and $u_{i}(t) \in \mathbb{R}^{n}$ is the control input.

The primary objective in this article is to design distributed event-triggered optimization algorithms $u_{i}(t)$ for system (2.2), with the aim of driving the position state of $N$ agents toward the optimal solution $x^{\ast}$ of Eq (2.1). Toward this end, the following definition is proposed.

Definition 1: DOP (2.1) for MAS (2.2) is solved if

where $x^{\ast} = \arg \min_{x\in \mathbb{R}^{Nn}}f(x)$. Thus, $x^{\ast}$ is considered as the global optimal solution, which minimizes the global objective function.

The following assumptions will be used in this article.

Assumption 1: The communication topology graph $\mathcal{G}$ is undirected and connected.

Assumption 2: Each local cost function $f_{i}$ is twice continuously differentiable and $\omega_{i}$-strongly convex ($\omega_{i} > 0$) over $\mathbb{R}^{n}$. Additionally, $\triangledown f_{i}$ is $\ell_{i}$-Lipschitz ($\ell_{i} > 0$) for each $i\in\mathcal{V}$.

Remark 1: A function $f_{i}$ is said to be twice continuously differentiable and $\omega_{i}$-strongly convex if $\forall K\subset \mathbb{R}^{n}$ is a convex and compact set and if there is a positive number $\omega = \min \limits_{i\in \mathcal{V}}{\omega_{i} }$ that makes $(\nabla f_{i}(k_{1})-\nabla f_{i}(k_{2}))^{T}(k_{1}-k_{2})\geq \omega \|k_{1}-k_{2}\|^{2}$, $\forall k_{1}, k_{2} \in K$. $\triangledown f_{i}$ is $\ell_{i}$-Lipschitz with positive constant $\ell = \max \limits_{i\in \mathcal{V}}\{\ell_{i} \}$, and one has $\|\nabla f_{i}(k_{1})-\nabla f_{i}(k_{2})\|\leq \ell \|k_{1}-k_{2}\|, \forall k_{1}, k_{2}\in K$.

3.   Main results

This section presents sufficient conditions for DOP (2.1) and excludes Zeno-behavior with the designed event-triggered mechanism for any agent.

To eliminate continuous communication with neighboring agents, the following event-triggered control protocol with time delay is used:

where $\mu$, $\wp$ are positive numbers and $v_{i}$ denotes the auxiliary variable of agent $i$. The latest triggering instant of agent $j$ is denoted by $t^{j}_{k^{'}} = \arg \mathop {\min_{l\in \mathcal{N}_{i}, t\geq t^{j}_{{l}}}}\{t- t^{j}_{l}\}$, and the triggering time sequence is described recursively as follows:

and

for given constants $\kappa_{1} > 0$, $\kappa_{2} > 0$, $\gamma > 0$. $e_{i}(t) = x_{i}(t^{i}_{k})-x_{i}(t)$ is the state measurement error and $e_{i}(t)$ is equal to 0 at $t = t^{i}_{k}$. $\|\sum^{N}_{j = 1} a_{ij}(x_{i}(t^{i}_{k})-x_{j}(t^{j}_{k^{'}}))\|$ represents the error sum of the states of all agents.

Remark 2: In algorithm (3.1), the controller design is mainly divided into following three parts:

(i) The first part as state feedback for stabilizing system (2.2);

(ii) The second part $\nabla f_{i}(x_{i}(t))$ is gradient direction of the local cost function, which is used to find the optimal solution of the cost function;

(iii) The third part $v_{i}(t)$ is the state auxiliary term, which plays an important role in proving the stability of the algorithm.

With the error $e_{i}(t)$, the control protocol (3.1) can be converted into

where $\mathcal{L} = L\otimes I_{n}\in \mathbb{R}^{Nn\times Nn}$, $u(t) = [u^{T}_{1}(t), u^{T}_{2}(t), ..., u^{T}_{N}(t)]^{T}\in \mathbb{R}^{Nn}$, $v(t) = [v^{T}_{1}(t), v^{T}_{2}(t), ..., v^{T}_{N}(t)]^{T}\in \mathbb{R}^{Nn}$, $e(t-\wp) = [e^{T}_{1}(t-\wp), e^{T}_{2}(t-\wp), ..., e^{T}_{N}(t-\wp)]^{T}\in \mathbb{R}^{Nn}$ and $\nabla \tilde{f}(x(t)) = [\nabla f_{1}(x_{1}(t))^{T}, \nabla f_{2}(x_{2}(t))^{T}, ..., \nabla f_{N}(x_{N}(t))^{T}]^{T}\in \mathbb{R}^{Nn}$.

Definition 2: If there is an infinite numbers of events in a finite period of time, then the event-triggered time sequence $\{t_k^i\}$ exhibits Zeno-behavior.

Remark 3: If the event-triggering time sequence exists Zeno-behavior, it implies that there is a positive constant $T$, such that $\lim_{k\rightarrow \infty} t^{i}_{k} = T$.

Lemma 1 (Barbalat's lemma ^[30]): For all $t \geq t_{0}$, the function $y: \mathbb{R}^{+}\rightarrow \mathbb{R}$ is uniformly continuous. If

exists and is bounded, then

Lemma 2: Suppose Assumptions 1 and 2 hold and $\sum^{N}_{i = 1}v_{i}(0) = \textbf{0}_{n}$, then $(x^{\ast}, -\mu\nabla \tilde{f}(x^{\ast}))$ is an equilibrium point of system (3.1), where $x^{\ast}$ is the optimal solution of DOP (2.1).

Proof: By Assumption 1, we have $(\textbf{1}_{N}\otimes I_{n})^{T}\mathcal{L} = \textbf{0}_{Nn}\otimes I_{n}$. One can derive that

Thus, $(\textbf{1}_{N}\otimes I_{n})^{T} v(t) = (\textbf{1}_{N}\otimes I_{n})^{T} v(0) = \textbf{0}_{Nn}$. Let $(x^{\ast}, v^{\ast})$ be an equilibrium point of system (3.4), then the equilibrium point satisfies

By (3.5), we have $v^{\ast} = -\mu\nabla \tilde{f}(x^{\ast})$ and then $(\textbf{1}_{N}\otimes I_{n})^{T}\nabla \tilde{f}(x^{\ast}) = \mathbf{0}_{Nn}$, which indicates that $x^{\ast}$ is an optimal solution of DOP (2.1).

For simplicity, let us consider the case with $n = 1$. Notably, the case of $n > 1$ can also be proven using complicated calculations based on the property of the Kronecker product.

Theorem 1: Suppose that Assumptions 1 and 2 hold. Consider DOP (2.1) with the first-order MASs (2.2). The event-triggered control protocol is given by (3.4), where the triggering time sequence for each agent is determined by (3.2). Then, $x(t)$ asymptotically converges to the global minimizer $x^{\ast}$ if there are appropriate positive numbers $\mu, \beta\in (0, \frac{1}{2}(\mu\alpha _{1}\omega-\ell^{2}))$, $\kappa_{1}\in(0, \frac{1}{2\lambda_{max}(LL)})$, $\alpha_{1} > \alpha_{2} > \alpha_{3} > \alpha_{4}$ such that the following linear matrix inequalities (LMIs) are feasible:

where $\Theta_{ 1} = \frac{\mu(\alpha_{2}-\alpha_{1})}{2}I_{N-1}$, $\Theta_{ 2} = \frac{\mu\alpha_{3}}{2}I_{N-1}$, $\Theta_{3} = (\hbar-\beta) I_{N-1}$, $\Theta_{ 4} = \frac{(\alpha_{2}-\alpha_{3})}{2}{J}$, $\Theta_{ 5} = \frac{(\alpha_{3}-\alpha_{4})}{2}{J}$, $\Theta_{6} = (\beta-\beta\wp-\frac {2\kappa_{1}\lambda_{max}(L^{T}L) } {1-2\kappa_{1}\lambda_{max}(L^{T}L) })I_{N-1}$. In addition, the Zeno-behavior of the event-triggering time sequence can be excluded.

Proof: Let $\tilde{x} = x-x^{\ast}$, $\tilde{v} = v-v^{\ast}$ and $h = \nabla \tilde{f}(\tilde{x}+x^{\ast})-\nabla \tilde{f}(x^{\ast})$. The network dynamics can be rephrased as

DOP (2.1) is solved by the control protocol (3.1) if $lim_{t\rightarrow \infty} \tilde{x}(t) = \textbf{0}_{N}$.

Under Assumption 1, there is an orthogonal matrix $Q = (r, R)\in \mathbb{R}^{N\times N}$, such that

where $J\in \mathbb{R}^{(N-1)\times(N-1)}$ is Jordan matrix and $r = \frac {\textbf{1}_{N}} {\sqrt{N}}$, $R \in \mathbb{R}^{N\times (N-1)}$ satisfies $\textbf{1}^{T}_{N}R = \textbf{0}_{N-1}, R^{T}R = I_{N-1}$.

Let $\eta = Q^{T}\tilde{x}$, $\varepsilon = Q^{T}\tilde{v}$, $\delta = Q^{T}e$. Denote $\eta = (\eta_{1}, \eta^{T}_{2})^{T}$ with $\eta_{1}\in \mathbb{R}$ and $\eta_{2}\in \mathbb{R}^{N-1}$. Similarly, $\varepsilon = (\varepsilon_{1}, \varepsilon^{T}_{2})^{T}$ and $\delta = (\delta_{1}, \delta^{T}_{2})^{T}$. The systems (3.6) can be rewritten as

Denote $\Phi = (\eta_{1}, \eta^{T}_{2}, \varepsilon^{T}_{2})^{T}$ and let $V = V_{1}+V_{2}$ be the candidate Lyapunov function, where

with $\beta > 0$.

The time derivative of (3.8a) along with (3.7) is given by:

By Assumption 2, we have

Hence, it follows that

Then, considering the first two terms in $\dot{V}_{1}$, by (3.10b) and (3.11), one can deduce that

Combining (3.12), inequality (3.9) can be further transformed into

Taking the time derivation of (3.8b), it yields

According to the triggering condition (3.3), one can obtain

which means

then

where $\aleph_{1} = \frac {2\kappa_{1}\lambda_{max}(L^{T}L) } {1-2\kappa_{1}\lambda_{max}(L^{T}L) }$, $\aleph_{2} = \frac {N\kappa_{2}e^{\gamma\wp}} {1-2\kappa_{1}\lambda_{max}(L^{T}L) }$.

By (3.13)–(3.15), it follows that

where $\hbar = \frac{1}{2}(\mu\alpha _{1}\omega-\ell^{2})$, $H = [({R}^{T} h(t))^{T}, \eta_{2}^{T}(t), \varepsilon^{T}_{2}(t), \delta_{2}^{T}(t-\wp), \eta_{2}^{T}(t-\wp)]^{T}$.

According to Eq (3.16), we are able to get that

As a result, $\lim\limits_{t\rightarrow \infty}V(t)$ is bounded. Thus, (3.16) enforces that

then

By Lemma 1, $\tilde{x}(t)$ asymptotically converges to zero, namely,

In the following, it will be proven that there is no Zeno-behavior in the triggering time sequence.

Calculate the upper righthand Dini derivative of $\|e_{i}(t)\|$ for any $t\in [t^{i}_{{k}}, t^{i} _{{k+1}})$ and one obtains that

Invoking (3.15), we can get that

Since $e_{i}(t^{i}_{k}) = 0$, one can conclude that

By (3.17), since $V(t)$ is bounded, one can assume that $\| \tilde{x}(t)\|\leq \rho_{1}$ and $\| v_{i}(t)\|\leq \rho_{2}$. Moreover, combined with Assumption 2, one can assume that $\|\nabla f_{i}(x_{i}(t))\|\leq \rho_{3}$, then it holds that

The next event will be triggered only if the value of the driving error crosses the zero threshold. It yields that

If the event-triggering time sequence exhibits Zeno-behavior, we have

which is a contradiction, and, thus, Zeno-behavior does not exhibit in the triggering time sequence.

4.   A numerical example

In this section, the effectiveness of the obtained results is illustrated by a simulation example.

Consider the first-order multi-agent systems with six agents, and the topology of communication graph is depicted in Figure 1.

The strongly convex local objective functions are defined as $f_{i}(x_{i}) = 0.2(x_{i}-i)^{2}+i$ for $i = 1, ..., 6$. For any initial value $x_{i}(0)$ and the initial value $v_{i}(0)$, it satisfies $\sum^{6}_{1} v_{i}(0) = 0$. Undoubtedly, the assumptions given in this paper are satisfied. Set $\kappa_{2} = 0.5$, $\beta = 0.006$, $\gamma = 0.5$, $\mu = 0.4$, $\wp = 0.04$, $\alpha_{1} = 3.5$, $\alpha_{2} = 1.205$, $\alpha_{3} = 1.203$ and $\alpha_{4} = 1.202$. By calculation, one has $J = diag\{ 1, 2, 3, 3, 5\}$, $\Theta_{ 1} = -0.459I_{5}$, $\Theta_{ 2} = 0.2406I_{5}$, $\Theta_{3} = 0.799I_{5}$, $\Theta_{ 4} = 0.001J$, $\Theta_{ 5} = 0.0005J$, $\Theta_{6} = 0.0055I_{5}$. The range of parameter $\kappa_{1}$ can be determined that $\kappa_{1}\in (0, 0.02)$. Let $\kappa_{1} = 0.01$. The simulation results are displayed in Figures 2–7. Figure 2 depicts the state evolution trajectory of each agent. Figure 3 describes the trajectories of the event-triggered input $u_{i}(t)$. The global objective function converges to an optimal solution $24.5$, which is exhibited in Figure 4. Figure 5 illustrates the event-triggering instants for each agent. The minimum intervals between successive triggering events for agent 1 through agent 6 are as follows: $0.135$, $0.435$, $0.38$, $0.4$, $0.425$ and $0.165$. It is worth noting that all these intervals are greater than the sampling step of $0.005s$. Therefore, Zeno-behavior does not exhibit in the triggering time sequence. The gradient sum of $f_{i}(x)$ is depicted in Figure 6. The error norm of agent $1$ is presented in Figure 7.

5.   Conclusions

This article investigated a distributed optimization problem with the first-order MASs. A distributed event-triggered algorithm that allows the agents of control systems to achieve the optimal trajectory in the case of time delay was designed. The effectiveness of the algorithm was rigorously proved by using the Lyapunov stability theory. The adaptive distributed optimization problem through event-triggered communication will be discussed in future study.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is jointly sponsored by National Natural Science Foundation of China under Grant 61673080, Science and Technology Research Program of Chongqing Municipal Education Commission under Grant KJZD-K202000601, Chongqing Talent Plan under Grant cstc2021ycjh-bgzxm0044.

Conflict of interest

The authors declare there is no conflict of interest.