In this thesis we describe dualities in directed as well as undirected graphs based on tools such as width-parameters, obstructions and substructures. We mainly focus on directed graphs and their ...structure. In the context of a long open conjecture that bounds the monotonicity costs of a version of the directed cops and robber game, we introduce new width-measures based on directed separations that are closely related to DAG-width. We identify a tangle-like obstruction for which we prove a duality theorem. Johnson, Reed, Robertson, Seymour and Thomas introduced the width measure directed treewidth as a generalisation of treewidth for directed graphs. We introduce a new width measure, the cyclewidth, which is parametrically equivalent to directed treewidth. Making use of the connection between directed graphs and bipartite graphs with perfect matchings we characterise the digraphs of low cyclewidth. Generalising the seminal work by Robertson and Seymour resulting in a global structure theorem for undirected graphs, there is the goal of obtaining a structure theorem, based on directed treewidth, describing the structure of the directed graphs excluding a fixed butterfly minor. Working in this direction we present a new flat wall theorem for directed graphs which we believe to provide a better base for a directed structure theorem than the existing ones. On undirected graphs we present several results on induced subgraphs in the graphs themselves or the square graph of their linegraph. These results range from general statements about all graphs to the consideration of specific graph classes such as the one with exactly two moplexes.
In this article, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost ...functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider new distributed gradient-based methods where each node maintains two estimates, namely an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the gradients is pushed to the neighbors, whereas the information about the decision variable is pulled from the neighbors, hence giving the name "push-pull gradient methods." The methods utilize two different graphs for the information exchange among agents and, as such, unify the algorithms with different types of distributed architecture, including decentralized (peer to peer), centralized (master-slave), and semicentralized (leader-follower) architectures. We show that the proposed algorithms and their many variants converge linearly for strongly convex and smooth objective functions over a network (possibly with unidirectional data links) in both synchronous and asynchronous random-gossip settings. In particular, under the random-gossip setting, "push-pull" is the first class of algorithms for distributed optimization over directed graphs. Moreover, we numerically evaluate our proposed algorithms in both scenarios, and show that they outperform other existing linearly convergent schemes, especially for ill-conditioned problems and networks that are not well balanced.
Asynchronous Gradient Push Assran, Mahmoud S.; Rabbat, Michael G.
IEEE transactions on automatic control,
2021-Jan., 2021-1-00, 20210101, Letnik:
66, Številka:
1
Journal Article
Recenzirano
Odprti dostop
We consider a multiagent framework for distributed optimization where each agent has access to a local smooth strongly convex function, and the collective goal is to achieve consensus on the ...parameters that minimize the sum of the agents' local functions. We propose an algorithm wherein each agent operates asynchronously and independently of the other agents. When the local functions are strongly convex with Lipschitz-continuous gradients, we show that the iterates at each agent converge to a neighborhood of the global minimum, where the neighborhood size depends on the degree of asynchrony in the multiagent network. When the agents work at the same rate, convergence to the global minimizer is achieved. Numerical experiments demonstrate that asynchronous gradient push can minimize the global objective faster than the state-of-the-art synchronous first-order methods, is more robust to failing or stalling agents, and scales better with the network size.
Directed cycles with zero weight in Zpk Letzter, Shoham; Morrison, Natasha
Journal of combinatorial theory. Series B,
September 2024, Letnik:
168
Journal Article
Recenzirano
Odprti dostop
For a finite abelian group A, define f(A) to be the minimum integer such that for every complete digraph Γ on f vertices and every map w:E(Γ)→A, there exists a directed cycle C in Γ such that ...∑e∈E(C)w(e)=0. The study of f(A) was initiated by Alon and Krivelevich (2021). In this article, we prove that f(Zpk)=O(pk(logk)2), where p is prime, with an improved bound of O(klogk) when p=2. These bounds are tight up to a factor which is polylogarithmic in k.
An aggregative game with local constraint sets is studied in this article, where each player's cost function is dependent on the aggregation function that is unavailable to all players. To compute ...the Nash equilibrium (NE) point of the game in a distributed manner, the players are endowed with several auxiliary state variables that are used to estimate the aggregation function by exchanging their estimates with local neighbors on a directed graph. In the two cases with strongly connected weight-balanced and weight-unbalanced directed graphs, respectively, NE seeking strategies are proposed by the interconnection of projected gradient-play with average consensus dynamics. The proposed algorithms are proved to be able to reach the NE point by using tools from variational inequality theory and Lyapunov stability theory. Finally, an example is simulated to demonstrate the theoretical results.
This article studies a distributed average tracking (DAT) problem, in which a collection of agents work collaboratively, subject to local communication, to track the average of a set of reference ...signals, each of which is available to a single agent. Our primary objective is to seek a design methodology for DAT under possibly weight-unbalanced directed networks-the most general and thus most challenging case from the network topology perspective, which has few results in the literature. For this purpose, we propose a distributed algorithm based on a chain of two integrators that are coupled with a distributed estimator. It is found that the convergence depends on not only the network topology but also the deviations among the reference signal accelerations. Another primary interest of this article stems from the dynamics perspective-a point perceived as a main source of control design difficulty for multiagent systems. Indeed, we devise a nonlinear algorithm that is capable of achieving DAT under weight-unbalanced directed networks for agents subject to high-order integrator dynamics. The results show that the convergence to the vicinity of the average of the reference signals is guaranteed as long as the signals' states and control inputs are all bounded. Both algorithms are robust to initialization errors, i.e., DAT is insured even if the agents are not correctly initialized, enabling the potential applications in a wider spectrum of application domains.
This study investigates the adaptive bipartite event-triggered time-varying output formation tracking for heterogeneous linear multi-agent systems (MASs) under signed directed communication topology. ...Both cooperative communication and antagonistic communication among agents are considered. The fully distributed bipartite compensator based on the novel composite event-triggered transmission mechanism is first put forward to estimate the state of the leader. Compared with the existing methods, our compensator can save communication resources using event-triggered transmission mechanism; is independent of the global information of the network graph; and is applicable for the signed directed graph. With the developed compensator, the distributed control protocol is designed to achieve the time-varying output formation tracking. Moreover, the case that the networked systems subject to external disturbances is also considered. To estimate the state of leader with disturbance, the fully distributed bipartite compensator based on an innovative composite event-triggered mechanism is presented. And the novel distributed control protocol is proposed to address the output formation tracking issue for linear MASs with heterogeneous dynamics and external disturbances. It is shown that the Zeno-behavior can be excluded in both transmission mechanisms. Finally, the effectiveness of the developed control methods is illustrated through three simulation examples.
We emphasize that the dimensions of the equality and inequality constraints in 1 do not necessarily need to be the same. In particular, the developed method and the presented analysis works for m 1 ≠ ...m 2 . Thus, footnote 1 on page number 5368 in Section II-B, "Problem Formulation" is not needed.
This article studies the distributed observer-based event-triggered bipartite tracking control problem for stochastic nonlinear multiagent systems with input saturation. First, different from ...conventional observers, we construct a novel distributed reduced-order observer to estimate unknown states for the stochastic nonlinear systems. Then, an event-triggered mechanism with relative threshold is introduced to reduce the burden of communication. In addition, the bipartite tracking controller is proposed for stochastic multiagent systems by using fuzzy logic systems and the backstepping approach. Meanwhile, it is proved that the designed method can guarantee that all the signals in the closed-loop systems are bounded in probability, and the distributed consensus tracking errors can converge to a small neighborhood of the origin via the Lyapunov stability theory. Finally, a simulation example is given to prove the effectiveness of the designed scheme.
PDF
