Search

We propose an inexact decentralized dual gradient tracking method (iDDGT) for decentralized optimization problems with a globally coupled equality constraint. Unlike existing algorithms that rely on either the exact dual gradient or an inexact one obtained through single-step gradient descent, iDDGT introduces a new approach: utilizing an inexact dual gradient with controllable levels of inexactness. Numerical experiments demonstrate that iDDGT achieves significantly higher computational efficiency compared to state-of-the-art methods. Furthermore, it is proved that iDDGT can achieve linear convergence over directed graphs without imposing any conditions on the constraint matrix. This expands its applicability beyond existing algorithms that require the constraint matrix to have full row rank and undirected graphs for achieving linear convergence.

This work focuses on a class of general decentralized constraint-coupled optimization problems. We propose a novel nested primal-dual gradient algorithm (NPGA), which can achieve linear convergence under the weakest known condition, and its theoretical convergence rate surpasses all known results. More importantly, NPGA serves not only as an algorithm but also as a unified algorithmic framework, encompassing various existing algorithms as special cases. By designing different network matrices, we can derive numerous versions of NPGA and analyze their convergences by leveraging the convergence results of NPGA conveniently, thereby enabling the design of more efficient algorithms. Finally, we conduct numerical experiments to compare the convergence rates of NPGA and existing algorithms, providing empirical evidence for the superior performance of NPGA.

In this work, we study the classical distributed optimization problem over digraphs, where the objective function is a sum of smooth local functions. Inspired by the implicit tracking mechanism proposed in our earlier work, we develop a unified algorithmic framework from a pure primal perspective, i.e., UGT, which is essentially a generalized gradient tracking method and can unify most existing distributed optimization algorithms with constant step-sizes. It is proved that two variants of UGT can both achieve linear convergence if the global objective function is strongly convex. Finally, the performance of UGT is evaluated by numerical experiments.

A class of distributed optimization problem with a globally coupled equality constraint and local constrained sets is studied in this paper. For its special case where local constrained sets are absent, an augmented primal-dual gradient dynamics is proposed and analyzed, but it cannot be implemented distributedly since the violation of the coupled constraint needs to be used. Benefiting from the brand-new comprehending of a classical distributed unconstrained optimization algorithm, the novel implicit tracking approach is proposed to track the violation distributedly, which leads to the birth of the \underline{i}mplicit tracking-based \underline{d}istribut\underline{e}d \underline{a}ugmented primal-dual gradient dynamics (IDEA). A projected variant of IDEA, i.e., Proj-IDEA, is further designed to deal with the general case where local constrained sets exist. With the aid of the Lyapunov stability theory, the convergences of IDEA and Pro-IDEA over undigraphs and digraphs are analyzed respectively. As far as we know, Proj-IDEA is the first constant step-size distributed algorithm which can solve the studied problem without the need of the strict convexity of local cost functions. Besides, if local cost functions are strongly convex and smooth, IDEA can achieve exponential convergence with a weaker condition about the coupled constraint. Finally, numerical experiments are taken to corroborate our theoretical results.

This paper studies the consensus problem for multiagent systems with transmission constraints. A novel model of multiagent systems is proposed where the information transmissions between agents are disturbed by irregular distortions or interferences (named transmission constraint functions), and this model is universal which can be applied in many cases, such as interval consensus and discarded consensus. In the transmission-constrained consensus problem, we obtain the necessary and sufficient condition that agents can converge to state consensus. Furthermore, a more general case is studied in which the system reaches an equilibrium. Based on some techniques of algebraic topology and stability theory, the existence, uniqueness and stability of the system equilibrium point can be proven, which means the system can reach an asymptotically stable equilibrium. Moreover, the state values of the equilibrium are only decided by the network structure and transmission constraint functions, but not the agents' initial states. Finally, numerical simulations are presented to illustrate the proposed theorems and corollaries.

We study the statistical properties of observables of scale-free networks in the degree-thresholding renormalization (DTR) flows. For BA scale-free networks with different sizes, we find that their structural and dynamical observables have similar scaling behavior in the DTR flow. The finite-size scaling analysis confirms this view and reveals a scaling function with a single scaling exponent that collectively captures the changes of these observables. Furthermore, for the scale-free network with a single initial size, we use its DTR snapshots as the original networks in the DTR flows, then perform a similar finite-size scaling analysis. Interestingly, the initial network and its snapshots share the same scaling exponent as the BA synthetic network. Our findings have important guiding significance for analyzing the structure and dynamic behavior of large-scale networks. Such as, in large-scale simulation scenarios with high time complexity, the DTR snapshot could serve as a substitute or guide for the initial network and then quickly explore the scaling behavior of initial networks.

Recently, the concept of geometric renormalization group provides a good approach for studying the structural symmetry and functional invariance of complex networks. Along this line, we systematically investigate the finite-size scaling of structural and dynamical observables in geometric renormalization flows of synthetic and real evolutionary networks. Our results show that these observables can be well characterized by a certain scaling function. Specifically, we show that the critical exponent implied by the scaling function is independent of these observables but only depends on the small-world properties of the network, namely, all networks located in the small-world phase have a uniform scaling exponent, while those located in the non-small-world phase and in their critical regions have another uniform scaling. More importantly, we perform extensive experiments on real evolutionary networks with small-world characteristics, and our results show that these observables also have uniform scaling in their geometric renormalization flows. Therefore, in a sense this exponent can be used as an effective measure for classifying universal small-world and non-small-world network models.

A multi-unmanned surface vessel (USV) formation control system is established on a novel platform composed of three 1.2 meter-long hydraulic jet propulsion surface vessels, a differential GPS reference station, and inter-vessel Zigbee communication modules. The system is also equipped with an upper level collective multi-USV protocol and a lower level vessel dynamics controller. The system is capable of chasing and surrounding a target vessel. The results are supported by rigorous theoretical analysis in terms of asymptotical surrounding behavior and trajectory regulation. Extensive experiments are conducted to demonstrate the effectiveness and efficiency of the proposed hardware and software architectures., Comment: 8 pages, 6 figures