Distributed Predefined-Time Optimization for Second-Order Systems under Detail-Balanced Graphs

Abstract

This paper studies the problem of distributed predefined-time optimization for leaderless consensus of second-order multi-agent systems under a class of weighted digraphs. The proposed framework has two main steps. In the first step, the agents communicate to perform a consensus-based distributed predefined-time optimization and to generate a constant optimal output reference for each agent. In the second step, each agent tracks its corresponding optimal output reference, using a sliding-mode controller to reach the global optimum in a predefined time, even under matched disturbances. The proposed algorithm relies explicitly on user-defined constant parameters. Numerical simulations are performed to validate the efficacy of the algorithm.

1. Introduction

With the development of distributed computing and large-scale networks during the past decade, distributed optimization has become a highly active subject. The mentioned approach is attractive due to its application in areas, such as opinion dynamics [1], resource allocation [2], smart grids [3], sensor networks [4], and machine learning [5], to name a few. In particular, special attention has been paid to consensus-based distributed algorithms in continuous time, which may facilitate the analysis [6].

Most of the vast literature on consensus-based distributed optimization, particularly in the case of Multi-Agent Systems (MAS), presents schemes with asymptotic/exponential convergence, which may impose severe limitations when the optimization time is a crucial factor, and the initial conditions of the agents are inaccurate or even unknown. A solution to these shortcomings was explored early in [7] and extended by Polyakov [8], who introduced the concept of fixed-time stability, where the convergence time is uniformly-bounded for all initial conditions. However, despite the demonstrated applicability of fixed-time stability, there are some issues related to the convergence time estimation. The main drawback is that the relationship between the system parameters and the convergence time is not explicit. Thus, finding the system parameters to enforce a desired bound for the stabilization time constitutes a challenging problem, leading to conservative estimations [9].

To deal with the scenario when the convergence time is an important restriction and the initial conditions are uncertain, a class of systems where an Upper Bound of the Settling Time (UBST) is a tunable parameter was proposed in [9] and further studied in [10,11]. Such systems are called fixed-time stable systems with predefined UBST or simply predefined-time stable systems. This concept has been applied to first-order, second-order, and nonholonomic systems [12] and even consensus problems [13] and discretization schemes [14].

Current works on distributed optimization mostly focus on leaderless first-order dynamics, covering asymptotic, finite, fixed, and predefined-time convergence (see [15,16,17,18,19,20]). On the other hand, the literature on distributed optimization for second-order systems are growing fast in recent years, but works with a predefined-time approach are scarce. For instance, Tang [21] proposed an algorithm that includes an optimal signal generator embedded in the MAS feedback loop. This approach reduces the complex optimization problem into two simpler sub-problems: first-order distributed optimization and constant reference tracking. Adibzadeh et al. [22] used the same embedded control scheme with the addition of inequality constraints. Nonetheless, both algorithms show asymptotic/exponential convergence and can be applied only on undirected graphs. Wang et al. [23] proposed an optimization algorithm for integrator chain systems based on the same idea of an optimal signal generator. The algorithm is a significant improvement compared to [21,22] due to the consideration of matched and unmatched disturbances and finite-time convergence. Although the results are satisfactory, the main drawback is that the settling time depends on the initial condition of the agents. Additionally, only undirected topologies are taken into account. A different approach is suggested by Tran et al. [24]. In this paper, the authors considered the distributed optimization problem for double integrator systems with the presence of external disturbance by using the internal model principle. However, the scheme can be applied only on undirected graphs, requiring the computation of several matrices in order to find the corresponding bounds of the gains, and its convergence is asymptotic. In Li et al. [25], the distributed predefined-time optimization problem for homogeneous and heterogeneous linear systems is studied using a Time-Base Generator (TBG) technique. However, it was applied only to undirected graphs, and no disturbance was considered. Moreover, according to Aldana-López et al. [26], this kind of algorithm with time-varying gains may present inherent performance limitations due to the lack of uniform stability and robustness to measurement noise. Moreover, due to singularities present in these time-varying gains, there is no satisfactory evidence of solutions for these systems at and after the predefined time. Motivated by the previous discussion, this paper introduces a distributed predefined-time optimization algorithm for leaderless consensus of second-order MAS when the communication topology is modeled by a detail-balanced graph, which is a particular case of directed graphs. The proposed algorithm has a first step in which the agents communicate to perform a first-order distributed optimization and to generate a constant optimal output for each agent. In the second step, each agent tracks the corresponding optimal output obtained in the first step using a sliding-mode controller, which presents robustness to matched disturbance. The algorithm relies on explicit system parameters and user-defined parameters without the requirement of time-variable gains. In comparison to the existing results in the literature, the salient features of the proposed algorithm are as follows:

• In contrast to [21,22,23,24], the proposed algorithm performs both the optimization and stabilization processes in a predefined time.
• The algorithm can be applied to undirected graphs and detail-balanced graphs. None of the discussed papers considers this extension.
• The initial optimization step of the algorithm requires fewer adjustable parameters than many other algorithms found in the literature.
• Compared to many existing works, the gradients and Hessians are not shared among agents.
• Contrary to [25], the proposed algorithm is robust in the presence of matched disturbances and does not use a TBG.

The paper is structured as follows. Section 2 introduces the essential mathematical background and important definitions. The problem statement is explained in Section 3. Then, the proposed scheme, including its proof of stability, is developed in Section 4. Section 5 discusses the validity of the proposed scheme through several simulations. Finally, conclusions and future work are presented in Section 6, and some useful lemmas can be found in Appendix A.

2. Preliminaries

2.1. Notation

Let $\mathbb{R}$ denote the set of real numbers and ${\mathbb{R}}^m$ the m-dimensional Euclidean space. For $x\in {\mathbb{R}}^m$, $x^T$ denotes its transpose, $∥x∥$ its Euclidean norm and, for $r\in {\mathbb{R}}_{+}$, $B_r\left(x\right)=\{y\in {\mathbb{R}}^m:∥y-x∥<r\}$. ${\mathbf{I}}_m$ is the identity matrix with dimensions $m\times m$, and ${\mathbf{0}}_m$ is the zero column vector of dimension m.

For a twice differentiable function $f:{\mathbb{R}}^m\to \mathbb{R}$, $\nabla f\left(\mathbf{x}\right)$ and ${\nabla }^{2}f\left(\mathbf{x}\right)$ represent the gradient and Hessian of the function, respectively. For matrices $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{B}\in {\mathbb{R}}^{p\times q}$, $\mathbf{A}\otimes \mathbf{B}\in {\mathbb{R}}^{mp\times nq}$ denotes the Kronecker product.

For any real number h, the functions ${⌊•⌉}^h:\mathbb{R}\to \mathbb{R}$ and $|⌊•⌉{|}^h:{\mathbb{R}}^m\to {\mathbb{R}}^m$ are defined as ${⌊x⌉}^h={\left|x\right|}^h\mathrm{sign}\left(x\right)$ for any $x\in \mathbb{R}\setminus \left\{0\right\}$ and $|⌊\mathbf{x}⌉{|}^h=\mathbf{x}/{\left|\left|\mathbf{x}\right|\right|}^{1-h}$ for any $\mathbf{x}\in {\mathbb{R}}^m\setminus \left\{{\mathbf{0}}_m\right\}$, respectively. Moreover, if $h>0$, ${⌊0⌉}^h=0$ and $|⌊{\mathbf{0}}_m⌉{|}^h={\mathbf{0}}_m$.

For $\alpha \in {\mathbb{R}}_{+}$, the Gamma Function $\Gamma$ is defined as $\Gamma \left(\alpha \right)={\int }_0^{\infty }{t}^{\alpha -1}{e}^{-t}dt$.

2.2. Graph Theory

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ denote a graph, where $\mathcal{V}=1,2,\dots ,N$ is the set of vertices (agents), and $\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$ is the set of edges (links). The corresponding weighted adjacency matrix is $\mathbf{A}=\left[a_{ij}\right]\in {\mathbb{R}}^{N\times N}$ with $a_{ij}>0$ if $(j,i)\in \mathcal{E}$ and $a_{ij}=0$ otherwise. No self-loops are allowed, hence $a_{ii}=0,\forall i\in \mathcal{V}$. The neighbor set of agent i is defined as ${\mathcal{N}}_i=\left\{j\in \mathcal{V}\left|\right(j,i)\in \mathcal{E}\right\}$. The Laplacian matrix ${\mathbf{L}}_{\mathcal{G}}=\left[l_{ij}\right]\in {\mathbb{R}}^{N\times N}$ associated with $\mathcal{G}$ is defined as $l_{ij}=-a_{ij}$ for $i\ne j$ and $l_{ii}={\sum }_{j=1,j\ne i}^N{a}_{ij}$. A directed graph is detail-balanced with weight vector $\mathbf{\gamma }={({\gamma }_1,{\gamma }_2,\dots ,{\gamma }_N)}^T$ if ${\gamma }_i{a}_{ij}={\gamma }_j{a}_{ji}\forall i,j=1,2,\dots ,N$. Its Laplacian matrix ${\mathbf{L}}_D$ is defined as ${\mathbf{L}}_D=\Xi {\mathbf{L}}_{\mathcal{G}}$, where $\Xi =diag[{\gamma }_1,{\gamma }_2,\dots ,{\gamma }_N]$, with eigenvalues $0={\lambda }_1\left({\mathbf{L}}_D\right)<{\lambda }_2\left({\mathbf{L}}_D\right)\le \dots \le {\lambda }_N\left({\mathbf{L}}_D\right)$ [27].

2.3. Convex Analysis

Let us recall some basic notions on convex analysis (one can refer to Boyd and Vandenberghe [28] and Hiriart-Urruty [29] for more details). A set $C\subseteq {\mathbb{R}}^m$ is convex if, for any $\mathbf{x},\mathbf{y}\in C$ and any $\alpha$ with $0\le \alpha \le 1$, $\alpha \mathbf{x}+(1-\alpha )\mathbf{y}\in C$. A function $f:{\mathbb{R}}^m\to \mathbb{R}$ is convex if its domain, denoted as dom f, is a convex set and if for all $\mathbf{x},\mathbf{y}\in \mathrm{dom}f$ and any $\alpha$ with $0\le \alpha \le 1$, $f(\alpha \mathbf{x}+(1-\alpha \left)\mathbf{y}\right)\le \alpha f\left(\mathbf{x}\right)+(1-\alpha )f\left(\mathbf{y}\right)$. A twice continuously differentiable convex function $f:{\mathbb{R}}^m\to \mathbb{R}$ is $\theta$-strongly convex with $0<\theta <\Theta$ if one of the following conditions holds

$$\frac{\theta }{2}{∥\mathbf{x}-\mathbf{y}∥}^2\le f\left(\mathbf{y}\right)-f\left(\mathbf{x}\right)-\nabla f{\left(\mathbf{x}\right)}^T(\mathbf{x}-\mathbf{y})\le \frac{\Theta }{2}{∥\mathbf{x}-\mathbf{y}∥}^2,$$

(1a)

$$\theta {\mathbf{I}}_m\le {\nabla }^{2}f\left(\mathbf{x}\right)\le \Theta {\mathbf{I}}_m.$$

(1b)

If f is a $\theta$-strongly convex function, then its minimizer ${\mathbf{x}}^{\ast }=arg{min}_{x\in {\mathbb{R}}^m}f\left(x\right)$ is unique.

2.4. Predefined-Time Stability

Consider the autonomous system

$$\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x};\mathbf{\rho }),{\mathbf{x}}_0=\mathbf{x}\left(0\right)$$

(2)

where $\mathbf{x}\in {\mathbb{R}}^m$ is the system state, $\mathbf{\rho }\in {\mathbb{R}}^b$ with $\dot{\mathbf{\rho }}=0$ represents the parameters of the system and function $\mathbf{f}:{\mathbb{R}}^m\to {\mathbb{R}}^m$ is such that the solution of (2), denoted as $\Phi (t,{\mathbf{x}}_0)$, exists and is unique. The origin $\mathbf{x}={\mathbf{0}}_m$ is the unique equilibrium point of (2).

Definition 1

(Stability notions [10]). The origin of system (2) is

• Lyapunov is stable if for any $x_0\in {\mathbb{R}}^m$, the solution $\Phi (t,x_0)$ is defined for all $t\ge 0$, and for any $ϵ>0$, there is $\delta >0$ such that for any $x_0\in {\mathbb{R}}^m$, if $x_0\in B_{\delta }\left(0\right)$ then $\Phi (t,x_0)\in B_{ϵ}\left(0\right)$ for all $t\ge 0$;
• It is finite-time stable if it is Lyapunov stable and for any $x_0\in {\mathbb{R}}^m$, there exists $0\le \tau <\infty$ such that $\Phi (t,x_0)=0$ for all $t\ge \tau$. The function $T\left(x_0\right)=inf\left\{\tau \ge 0:\Phi (t,x_0)=0,\forall t\ge \tau \right\}$ is said the settling-time function of system (2);
• It is fixed-time stable if it is finite-time stable, and the settling-time function of system (2), $T\left(x_0\right)$, is bounded on ${\mathbb{R}}^m$, i.e., there exists $T_{max}$ such that ${sup}_{x_0\in {\mathbb{R}}^m}T\left(x_0\right)\le T_{max}$;
• It is predefined-time stable if it is fixed-time stable and for any $T_c\in {\mathbb{R}}_{+}$ there exists some $\rho \in {\mathbb{R}}^b$ such that the settling-time function of system (2) satisfies

  $$\underset{x_0\in {\mathbb{R}}^m}{sup}T\left(x_0\right)\le T_c.$$

Proposition 1

([12]). If there exists a continuous, positive definite and radially unbounded function $V:{\mathbb{R}}^m\to {\mathbb{R}}_{\ge 0}$ such that the time-derivative of V along the trajectories of (2) satisfies

$$\dot{V}\left(\mathbf{x}\right)\le -\frac{1}{\alpha s{T}_c}exp\left(\alpha V{\left(\mathbf{x}\right)}^s\right)V{\left(\mathbf{x}\right)}^{1-s},$$

(3)

for $\mathbf{x}\in {\mathbb{R}}^m\setminus \left\{{\mathbf{0}}_m\right\}$ and constants $T_c:=T_c\left(\mathbf{\rho }\right)>0$, $\alpha >0,s\in (0,0.5)$, then the origin of (2) is fixed-time stable with $T_c$ as a predefined UBST.

Proposition 2

([12]). Consider the second-order system

$$\begin{array}{cc}\hfill {\dot{x}}_1\left(t\right)& =x_2\left(t\right)\hfill \\ \hfill {\dot{x}}_2\left(t\right)& =u\left(t\right)+\Delta \left(t\right)\hfill \end{array}$$

(4)

where $\mathbf{x}={(x_1,x_2)}^T\in {\mathbb{R}}^2$ is the state vector, $u\in \mathbb{R}$ is the control input, and $\Delta \left(t\right)\in \mathbb{R}$ is a disturbance with known bound $\left|\Delta \left(t\right)\right|\le \delta$.

The stabilization of system (4) in a predefined time $T_c<T_{c1}+T_{c2}$ can be performed by using the following sliding-mode controller

$$\begin{array}{cc}\hfill u=& -\frac{{\alpha }_2^{\frac{{\beta }_2{q}_2-1}{p_2}}\Gamma \left(\frac{1-{\beta }_2{q}_2}{p_2}\right)}{p_2{T}_{c2}}exp({\alpha }_2{\left|\sigma \right|}^{p_2}){⌊\sigma ⌉}^{{\beta }_2{q}_2}-{\zeta }_{ik}{⌊\sigma ⌉}^0\hfill \\ \hfill & -\left(\frac{2^{\frac{1-q_1/2}{p_1}}\Gamma \left(\frac{1-q_1/2}{p_1}\right)}{p_1{T}_{c1}}\right)(q_1+p_1{⌊x_1⌉}^{p_1}|x_1{|}^{q_1-1})exp(|x_1{|}^{p_1}){⌊\sigma ⌉}^0,\hfill \end{array}$$

(5)

where the sliding variable σ is defined as follows

$$\sigma =x_2+{⌊{⌊x_2⌉}^2+2\left(\frac{2^{\frac{1-q_1/2}{p_1}}\Gamma \left(\frac{1-q_1/2}{p_1}\right)}{p_1{T}_{c1}}\right)exp\left(\right|x_1{|}^{p_1}){⌊x_1⌉}^{q_1}⌉}^{1/2}$$

(6)

with $\zeta \ge \delta$ and the parameters $T_{c1}>0,p_1>0,1\le q_1<2,T_{c2}>0,{\alpha }_2>0,{\beta }_2>0,p_2>0,q_2>0$ such that ${\beta }_2{q}_2<1$.

3. Problem Statement

Consider a leaderless MAS with N agents whose dynamics are given by

$$\begin{array}{cc}\hfill {\dot{\mathbf{x}}}_i\left(t\right)& ={\mathbf{v}}_i\left(t\right)i=1,2,\dots ,N\hfill \\ \hfill {\dot{\mathbf{v}}}_i\left(t\right)& ={\mathbf{u}}_i\left(t\right)+{\Delta }_i\left(t\right)\hfill \end{array}$$

(7)

where ${\mathbf{x}}_i,{\mathbf{v}}_i\in {\mathbb{R}}^m$ represent the position and the velocity vectors of the i-th agent, respectively. ${\mathbf{u}}_i\left(t\right)={[u_{i1}\left(t\right),u_{i2}\left(t\right),\dots ,u_{im}\left(t\right)]}^T\in {\mathbb{R}}^m$ is the control input and ${\Delta }_i\left(t\right)={[{\Delta }_{i1}\left(t\right),{\Delta }_{i2}\left(t\right),\dots ,{\Delta }_{im}\left(t\right)]}^T\in {\mathbb{R}}^m$ is a disturbance vector with $|{\Delta }_{ik}\left(t\right)|\le {\delta }_{ik}$ for $k=1,2,\dots ,m$. Additionally, agent i is endowed with a local function $f_i\left({\mathbf{x}}_i\right):{\mathbb{R}}^m\to \mathbb{R}$ only known by itself.

The objective is to design the control input ${\mathbf{u}}_i$ for each agent that achieves leaderless consensus to the global minimizer of an objective function $F\left(\mathbf{x}\right)$, which is the sum of the local functions of the agents. The optimization process must be achieved in a predefined time $T_c>0$ using information from the neighbors. In particular, all agents face the following unconstrained optimization problem:

$$\underset{\mathbf{x}\in {\mathbb{R}}^m}{min}F\left(\mathbf{x}\right)=\underset{\mathbf{x}\in {\mathbb{R}}^m}{min}\sum _{i=1}^N{f}_i\left(\mathbf{x}\right)$$

(8)

such that

$$\underset{t\to T_c}{lim}\sum _{i=1}^N∥{\mathbf{x}}_i\left(t\right)-{\mathbf{x}}^{\ast }∥=0\mathrm{and}\sum _{i=1}^N∥{\mathbf{x}}_i\left(t\right)-{\mathbf{x}}^{\ast }∥=0\forall t\ge T_c.$$

Here ${\mathbf{x}}^{\ast }=arg{min}_{\mathbf{x}\in {\mathbb{R}}^m}F\left(\mathbf{x}\right)$.

Assumption 1.

The communication topology is described by a time-invariant detail-balanced graph.

Assumption 2.

For each agent, the local cost function $f_i$ is twice differentiable, ${\theta }_i$-strongly convex with $0<{\theta }_i<{\Theta }_i$, and $\nabla f_i\left({\mathbf{x}}_i\right)$ is Lipschitz continuous.

Assumption 3.

The global function $F\left(\mathbf{x}\right):={\sum }_{i=1}^N{f}_i\left(\mathbf{x}\right)$ is μ-strongly convex with $\mu \ge {\sum }_{i=1}^N{\theta }_i$, hence, it has a unique minimizer $x^{\ast }$.

Remark 1.

Many kinds of functions satisfy Assumptions 2 and 3, such as quadratic, fractional, trigonometric, exponential, logarithmic, and other bounded differentiable functions. Some practical examples can be found in economic dispatch, optimal rendezvous of multiple mobile robots, and machine learning [17].

4. Main Results

In this section, we divide the Distributed Predefined-Time Optimization problem into two sub-problems. First, a Zero Gradient Sum (ZGS) algorithm is proposed to solve a first-order distributed optimization problem of a virtual system associated with the outputs of original system (7) in a predefined time ${\nu }_1{T}_c+{\nu }_2{T}_c$ and to generate optimal signals to be tracked. For $t\ge {\nu }_1{T}_c+{\nu }_2{T}_c$, the optimal outputs ${\mathbf{x}}_i^{ref}$ from the virtual system (9) remain constant and can be used as a reference to be tracked in a predefined time ${\nu }_3{T}_c+{\nu }_4{T}_c$. Constants ${\nu }_k$ are used to establish the duration of each step in terms of the total optimization time $T_c$. Hence, $0<{\nu }_k<1$ and ${\sum }_k^4{\nu }_k=1$.

4.1. Distributed Predefined-Time Optimal Signal Generator (DPTOSG)

Consider the virtual system

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill {\dot{\mathbf{z}}}_i\left(t\right)& ={\mathbf{\nu }}_i\left(t\right)i\in \mathcal{V}\hfill \\ \hfill {\mathbf{x}}_i^{ref}\left(t\right)& ={\mathbf{z}}_i\left(t\right),\hfill \end{array}\end{array}$$

(9)

where ${\mathbf{z}}_i\left(t\right)={[z_{i1}\left(t\right),\dots ,z_{im}\left(t\right)]}^T\in {\mathbb{R}}^m$ is the i-th agent state, ${\mathbf{\nu }}_i\left(t\right)={[{\nu }_{i1}\left(t\right),\dots ,{\nu }_{im}\left(t\right)]}^T\in {\mathbb{R}}^m$ is the i-th agent virtual control input, and ${\mathbf{x}}_i^{ref}\left(t\right)$ is the output. The task is to design a distributed controller $v_i,i\in \mathcal{V}$ for the virtual multi-agent system (9), such that its outputs ${\mathbf{z}}_i$ reach the unique minimizer ${\mathbf{x}}^{\ast }$ of the global cost function $F\left(\mathbf{x}\right)$ in a predefined time.

The proposed two-stage controller has the form

$${\mathbf{\nu }}_i\left(t\right)=\left\{\begin{array}{c}-c_1{\left[{\nabla }^2{f}_i\left({\mathbf{z}}_i\right)\right]}^{-1}exp\left({∥\nabla f_i\left({\mathbf{z}}_i\right)∥}^s\right){\left|⌊\nabla f_i\left({\mathbf{z}}_i\right)⌉\right|}^{1-s},0\le t\le {\nu }_1{T}_c\hfill \\ \\ -2c_2{\left[{\nabla }^2{f}_i\left({\mathbf{z}}_i\right)\right]}^{-1}\sum _{j\in {\mathcal{N}}_i}exp\left({\left(c_3{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right){\left({\gamma }_i{a}_{ij}\right)}^{1-s}{\left|⌊{\mathbf{z}}_{ij}⌉\right|}^{1-2s},t>{\nu }_1{T}_c\hfill \end{array}\right.$$

(10)

with ${\mathbf{z}}_{ij}={\mathbf{z}}_i-{\mathbf{z}}_j$, $0<s<0.5$, and $c_1,c_2,c_3$ to be defined later.

Theorem 1.

If Assumptions 1–3 hold, the optimization problem (9) is solved in a predefined time ${\nu }_1{T}_c+{\nu }_2{T}_c$ with parameters

$$c_1=\frac{1}{s{\nu }_1{T}_c},c_2=\frac{c_3^{1-s}}{s{\nu }_2{T}_c},c_3\ge \frac{\overline{\Theta }}{2{\lambda }_2\left({\mathbf{L}}_D\right)}$$

where $\overline{\Theta }\ge {\max }_{i\in \mathcal{V}}{\Theta }_i$.

Proof. 

For $0\le t\le {\nu }_1{T}_c$, according to (9) and (10), the closed-loop system is

$${\dot{\mathbf{z}}}_i=-c_1{\left[{\nabla }^2{f}_i\left({\mathbf{z}}_i\right)\right]}^{-1}exp\left({∥\nabla f_i\left({\mathbf{z}}_i\right)∥}^s\right){\left|⌊\nabla f_i\left({\mathbf{z}}_i\right)⌉\right|}^{1-s}.$$

(11)

Let ${\mathbf{g}}_i\left(t\right)=\nabla f_i\left({\mathbf{z}}_i\right)$. Therefore, ${\dot{\mathbf{g}}}_i={\nabla }^2{f}_i\left({\mathbf{z}}_i\right){\dot{\mathbf{z}}}_i=-c_{1}exp\left({∥{\mathbf{g}}_i∥}^s\right){\left|⌊{\mathbf{g}}_i⌉\right|}^{1-s}$. For agent $i\in \mathcal{V}$, one can define the Lyapunov function candidate $V_i\left({\mathbf{g}}_i\right)=∥{\mathbf{g}}_i∥$. which is positive, radially unbounded, and equal to zero if and only if ${\mathbf{g}}_i={\mathbf{0}}_m$, i.e., when each agent has reached its local minimum. The time derivative of $V_i$ takes the form

$${\dot{V}}_i=\frac{{\mathbf{g}}_i^T{\dot{\mathbf{g}}}_i}{∥{\mathbf{g}}_i∥}={\left(|⌊{\mathbf{g}}_i⌉{|}^0\right)}^T{\dot{\mathbf{g}}}_i.$$

(12)

Replacing the definition of ${\dot{\mathbf{g}}}_i$ into (12) and rearranging yields

$${\dot{V}}_i=-c_{1}exp\left({∥{\mathbf{g}}_i∥}^s\right){∥{\mathbf{g}}_i∥}^{1-s}=-\frac{1}{s{\nu }_1{T}_c}exp\left(V_i^s\right)V_i^{1-s},$$

(13)

due to ${\left(|⌊{\mathbf{g}}_i⌉{|}^0\right)}^T|⌊{\mathbf{g}}_i⌉{|}^{1-s}={\parallel {\mathbf{g}}_i\parallel }^{1-s}$. This corresponds to a fixed-time stable system with ${\nu }_1{T}_c$ as the UBST and $\alpha =1$, as shown in Proposition 1.

For $t>{\nu }_1{T}_c$, according to equations (9) and (10), the closed-loop system becomes:

$$\begin{array}{cc}\hfill {\dot{\mathbf{z}}}_i& =-2c_2{\left[{\nabla }^2{f}_i\left({\mathbf{z}}_i\right)\right]}^{-1}\sum _{j\in {\mathcal{N}}_i}exp\left({\left(c_3{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right){\left({\gamma }_i{a}_{ij}\right)}^{1-s}{\left|⌊{\mathbf{z}}_{ij}⌉\right|}^{1-2s}\hfill \\ \hfill & =-2c_2{\left[{\nabla }^2{f}_i\left({\mathbf{z}}_i\right)\right]}^{-1}\sum _{j\in {\mathcal{N}}_i}\frac{exp\left({\left(c_3{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right)}{{\left({\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s}{\gamma }_i{a}_{ij}{\mathbf{z}}_{ij}.\hfill \end{array}$$

(14)

Consider the following Lyapunov function

$$V\left(\mathbf{z}\right)=\sum _{i=1}^N{f}_i\left({\mathbf{x}}^{\ast }\right)-f_i\left({\mathbf{z}}_i\right)-\nabla f_i{\left({\mathbf{z}}_i\right)}^T({\mathbf{x}}^{\ast }-{\mathbf{z}}_i),$$

(15)

with $\mathbf{z}={\left[{\mathbf{z}}_1^T,\dots ,{\mathbf{z}}_N^T\right]}^T$. Applying equations (1a) and (1b), $V\left(\mathbf{z}\right)\ge {\sum }_{i=1}^N\frac{{\theta }_i}{2}{∥{\mathbf{z}}_i\left(t\right)-{\mathbf{x}}^{\ast }∥}^2\ge 0$, which is positive, radially unbounded, and equal to zero if and only if ${\mathbf{z}}_i={\mathbf{x}}^{\ast }$, i.e., when consensus is achieved. The derivative of (15) along the closed-loop system (14) becomes

$$\dot{V}=\sum _{i=1}^N{({\mathbf{z}}_i-{\mathbf{x}}^{\ast })}^T{\nabla }^2{f}_i\left({\mathbf{z}}_i\right){\dot{\mathbf{z}}}_i=\sum _{i=1}^N{\mathbf{z}}_i^T{\nabla }^2{f}_i\left({\mathbf{z}}_i\right){\dot{\mathbf{z}}}_i-{\mathbf{x}}^{\ast T}\sum _{i=1}^N{\nabla }^2{f}_i\left({\mathbf{z}}_i\right){\dot{\mathbf{z}}}_i$$

(16)

Since the graph is detail-balanced (Assumption 1), one has

$$\sum _{i=1}^N{\nabla }^2{f}_i\left({\mathbf{z}}_i\right){\dot{\mathbf{z}}}_i=-2c_2\sum _{i=1}^N\sum _{j\in {\mathcal{N}}_i}\frac{exp\left({\left(c_3{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right)}{{\left({\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s}{\gamma }_i{a}_{ij}{\mathbf{z}}_{ij}=0.$$

(17)

Therefore, (16) becomes

$$\dot{V}=\sum _{i=1}^N{\mathbf{z}}_i^T{\nabla }^2{f}_i\left(\mathbf{z}\right){\dot{z}}_i=-2c_2\sum _{i=1}^N\sum _{j\in {\mathcal{N}}_i}\frac{exp\left({\left(c_3{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right)}{{\left({\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s}{\gamma }_i{a}_{ij}{\mathbf{z}}_i^T{\mathbf{z}}_{ij}.$$

(18)

By applying Lemma A1 on (18) and multiplying by $N^2$ on top and bottom, one gets

$$\begin{array}{cc}\hfill \dot{V}& =-c_2\sum _{i=1}^N\sum _{j\in {\mathcal{N}}_i}\frac{exp\left({\left(c_3{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right)}{{\left({\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s}{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\hfill \\ \hfill & =-c_2\frac{N^2}{N^2}\sum _{i=1}^N\sum _{j\in {\mathcal{N}}_i}exp\left({\left(c_3{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right){\left({\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^{1-s}\hfill \end{array}$$

(19)

From Lemmas A2 and A3, (19) takes the form

$$\dot{V}\le -c_2{N}^{2}exp\left({\left(\frac{c_3}{N^2}\sum _{i=1}^N\sum _{j\in {\mathcal{N}}_i}{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^s\right){\left(\frac{1}{N^2}\sum _{i=1}^N\sum _{j\in {\mathcal{N}}_i}{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2\right)}^{1-s}.$$

(20)

Since ${\sum }_{i=1}^N{\sum }_{j\in {\mathcal{N}}_i}{\gamma }_i{a}_{ij}{∥{\mathbf{z}}_{ij}∥}^2=2{\mathbf{z}}^T({\mathbf{L}}_D\otimes {\mathbf{I}}_m)\mathbf{z}$

$$\dot{V}\le -c_2{N}^{2}exp\left({\left(\frac{2c_3}{N^2}{\mathbf{z}}^T({\mathbf{L}}_D\otimes {\mathbf{I}}_m)\mathbf{z}\right)}^s\right){\left(\frac{2}{N^2}{\mathbf{z}}^T({\mathbf{L}}_D\otimes {\mathbf{I}}_m)\mathbf{z}\right)}^{1-s}.$$

(21)

Following the procedure in [20], Lyapunov functions $V(\mathbf{z}$) and ${\mathbf{L}}_D$ of the network are related by the expression

$$V\le \frac{\overline{\Theta }}{{\lambda }_2\left({\mathbf{L}}_D\right)}{\mathbf{z}}^T({\mathbf{L}}_D\otimes {\mathbf{I}}_m)\mathbf{z},$$

(22)

After replacing (22) in (21) and rearranging some terms, one has

$$\dot{V}\le -\frac{{\left(c_3\frac{2{\lambda }_2\left({\mathbf{L}}_D\right)}{\overline{\Theta }}\right)}^{1-s}}{s{\nu }_2{T}_c}{N}^{2s}exp\left(N^{-2s}{\left(c_3\frac{2{\lambda }_2\left({\mathbf{L}}_D\right)}{N^2\overline{\Theta }}V\right)}^s\right)V^{1-s}.$$

(23)

Finally, according to the definition of $c_3$, (23) reduces to:

$$\dot{V}\le -\frac{1}{\alpha s{\nu }_2{T}_c}exp\left(\alpha V^s\right)V^{1-s},$$

(24)

where $\alpha =N^{-2S}$. This corresponds to a fixed-time stable system with ${\nu }_2{T}_c$ as UBST, according to Proposition 1. □

As can be seen, the DPTOSG problem is solved in a predefined time ${\nu }_1{T}_c+{\nu }_2{T}_c$.

Corollary 1.

If Assumptions 2 and 3 hold and the topology corresponds to an undirected connected graph, the DPTOSG problem is solved in predefined-time ${\nu }_1{T}_c+{\nu }_2{T}_c$ under the controller (10) by setting ${\gamma }_1={\gamma }_2=\cdots ={\gamma }_N=1$.

Proof. 

In this case, $L_D=L_{\mathcal{G}}$ and the proof can be carried out in a similar fashion as shown in Theorem 1. Hence, it is not included to avoid redundancy. □

Remark 2.

Note that Algorithm (10) does not depend explicitly on the number of agents, contrary to similar works in the literature, such as Lin et al. [30], Gong et al. [18], and Ma et al. [20].

4.2. Predefined-Time Reference Tracking—PTRT

We define a tracking error vector for agent i as ${\mathbf{e}}_i^1={\mathbf{x}}_i-{\mathbf{x}}_i^{ref}$ and since ${\mathbf{x}}_i^{ref}$ is constant $\forall t\ge {\nu }_1{T}_c+{\nu }_2{T}_c$, the derivatives ${\dot{\mathbf{x}}}_i^{ref}={\ddot{\mathbf{x}}}_i^{ref}={\mathbf{0}}_m$. Hence system (7) can be reformulated in terms of the tracking error as

$$\begin{array}{cc}\hfill {\dot{\mathbf{e}}}_i^1\left(t\right)& ={\mathbf{v}}_i\left(t\right)={\mathbf{e}}_i^{2}i=1,2,\dots ,N\hfill \\ \hfill {\dot{\mathbf{e}}}_i^2\left(t\right)& ={\mathbf{u}}_i\left(t\right)+{\Delta }_i\left(t\right)\hfill \end{array}$$

(25)

Now, it is possible to stabilize system (25) in a predefined time ${\nu }_3{T}_c+{\nu }_4{T}_c$ using the controller established in Proposition 2, as follows

$${\mathbf{u}}_i=\left\{\begin{array}{c}{\mathbf{0}}_m,t\le {\nu }_1{T}_c+{\nu }_2{T}_c\hfill \\ [u_{i1},\dots ,u_{im}{]}^T,t>{\nu }_1{T}_c+{\nu }_2{T}_c\hfill \end{array}\right.$$

(26)

with

$$\begin{array}{c}{u}_{ik}=-\frac{{\alpha }_2^{\frac{{\beta }_2{q}_2-1}{p_2}}\Gamma \left(\frac{1-{\beta }_2{q}_2}{p_2}\right)}{p_2{\nu }_4{T}_c}exp({\alpha }_2|{\sigma }_{ik}{|}^{p_2}){⌊{\sigma }_{ik}⌉}^{{\beta }_2{q}_2}-{\zeta }_{ik}{⌊{\sigma }_{ik}⌉}^0\hfill \\ \hfill -\left(\frac{2^{\frac{1-q_1/2}{p_1}}\Gamma \left(\frac{1-q_1/2}{p_1}\right)}{p_1{\nu }_3{T}_c}\right)(q_1+p_1{⌊e_{ik}^1⌉}^{p_1}|e_{ik}^1{|}^{q_1-1})exp(|e_{ik}^1{|}^{p_1}){⌊{\sigma }_{ik}⌉}^0\end{array}$$

(27)

where the sliding variable ${\sigma }_{ik}$ is defined as

$${\sigma }_{ik}=e_{ik}^2+{⌊{⌊e_{ik}^2⌉}^2+2\left(\frac{2^{\frac{1-q_1/2}{p_1}}\Gamma \left(\frac{1-q_1/2}{p_1}\right)}{p_1{\nu }_3{T}_c}\right)exp\left(\right|e_{ik}^1{|}^{p_1}){⌊e_{ik}^1⌉}^{q_1}⌉}^{1/2}$$

and $k=1,\dots ,m$. Finally, the whole distributed predefined-time optimization process (i.e., DPTOSG + PTRT) is completed in a predefined time $T_c$. A basic graphical representation of the proposed scheme can be found in Figure 1.

5. Numerical Example

Consider a two-dimensional MAS with three agents whose dynamics are given by (7) with ${\mathbf{x}}_i={[x_{i1},x_{i2}]}^T,{\mathbf{v}}_i={[v_{i1},v_{i2}]}^T,{\mathbf{u}}_i={[u_{i1},u_{i2}]}^T$ and ${\Delta }_i={[6sin(i\ast t),6sin(i\ast t)]}^T$. The communication topology is described by the graph depicted in Figure 2. One can easily see that Assumption 1 is fulfilled, with $\mathbf{\gamma }={[1.5,1.2,1.0]}^T$.

The local cost function for each agent is defined as

$$f_i\left({\mathbf{x}}_i\right)={(x_{i1}-i)}^2+{(x_{i2}+i)}^2.$$

(28)

The global minimizer is ${\mathbf{x}}^{\ast }={[2,-4]}^T$, with $F\left({\mathbf{x}}^{\ast }\right)=10$. The algebraic connectivity of the graph is ${\lambda }_2\left({\mathbf{L}}_D\right)=0.7608$, the maximum upper-bound strong-convexity parameter is $\overline{\Theta }={\Theta }_i=2$, and in order to guarantee predefined-time stability, parameter $c_3$ is fixed to $1.4>\frac{\overline{\Theta }}{2{\lambda }_2\left({\mathbf{L}}_D\right)}$. The total predefined time is $T_c=12$. The rest of the parameters for controller (10) are defined as $s=0.3$ and ${\nu }_1={\nu }_2=1/12$. The initial position of the agents ${\mathbf{x}}_{io}$ in the original system is randomly selected between $[-5,5]$ for both coordinates and, without any loss of generality, the initial velocity ${\mathbf{v}}_{io}={[0,0]}^T$. The initial condition of the virtual system is ${\mathbf{z}}_{io}={[0,0]}^T$. For controller (26), the parameters are kept identical for all agents and fixed as $p_1=p_2=0.3,q_1=q_2=1.5,{\alpha }_2={\beta }_2=1,{\mathbf{\zeta }}_i={[6,6]}^T,{\nu }_3=3/4$ and ${\nu }_4=1/12$.

Figure 3 shows the trajectories of the virtual system (9) through time according to the topology in Figure 2. For $t\le {\nu }_1{T}_c$, the controller leads all agents to their local function’s minimizer regardless of the initial conditions. This is performed to guarantee that ${\sum }_{i=1}^N\nabla f_i\left({\mathbf{z}}_i\right)={\mathbf{0}}_m$, which is an important requirement when designing ZGS algorithms (see [31]). For $t>{\nu }_1{T}_c$, the controller forces all agents to achieve consensus and reach the global function’s minimizer before the predefined time ${\nu }_1{T}_c+{\nu }_2{T}_c$.

Figure 4 shows the behavior of the original MAS with respect to time. According to the initial conditions, where velocities were chosen equal to zero, notice that all agents remain in their initial position up to $t={\nu }_1{T}_c+{\nu }_2{T}_c$, when the DPTOSG is taking place. For $t>{\nu }_1{T}_c+{\nu }_2{T}_c$, agents obtain the optimal output signal and proceed to track it in predefined time ${\nu }_3{T}_c+{\nu }_4{T}_c$ in spite of the non-vanishing disturbance. Evidently, the complete optimization process is performed before $T_c$. The trajectories described by the agents in a 2-D plane can be found in Figure 5. The quasi-linear displacement toward the optimum indicates the effectiveness of the disturbance rejection. Finally, the behavior of system (25) is depicted in Figure 6. Note that both tracking errors in position (a) and velocity (b) are zero before $T_c$ regardless of the disturbance.

6. Conclusions and Future Work

This paper has introduced a robust predefined-time control framework to solve the problem of leaderless distributed optimization for second-order MAS under detail-balanced graphs. The control framework presents two main steps. Initially, a first-order Distributed Predefined-time Optimal Signal Generator is designed to provide optimal reference outputs for the agents. Agents are not required to share information about their gradients or Hessians during this step, which is an essential difference compared to several algorithms found in the literature. Secondly, the outputs obtained in the first step are tracked in a predefined time using a robust sliding-mode controller. This scheme leads all agents to the global function’s minimizer, even in the presence of matched disturbances. Future work will focus on relaxing the strongly-convex condition and the extension to directed graphs and high-order systems.