CONSENSUS, PREDICTION AND OPTIMIZATION IN DIRECTED NETWORKS
| dc.contributor.advisor | Abed, Eyad H. | en_US |
| dc.contributor.author | Mai, Van Sy | en_US |
| dc.contributor.department | Electrical Engineering | en_US |
| dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
| dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
| dc.date.accessioned | 2017-06-22T06:13:57Z | |
| dc.date.available | 2017-06-22T06:13:57Z | |
| dc.date.issued | 2017 | en_US |
| dc.description.abstract | This dissertation develops theory and algorithms for distributed consensus in multi-agent networks. The models considered are opinion dynamics models based on the well known DeGroot model. We study the following three related topics: consensus of networks with leaders, consensus prediction, and distributed optimization. First, we revisit the problem of agreement seeking in a weighted directed network in the presence of leaders. We develop new sufficient conditions that are weaker than existing conditions for guaranteeing consensus for both fixed and switching network topologies, emphasizing the importance not only of persistent connectivity between the leader and the followers but also of the strength of the connections. We then study the problem of a leader aiming to maximize its influence on the opinions of the network agents through targeted connection with a limited number of agents, possibly in the presence of another leader having a competing opinion. We reveal fundamental properties of leader influence defined in terms of either the transient behavior or the achieved steady state opinions of the network agents. In particular, not only is the degree of this influence a supermodular set function, but its continuous relaxation is also convex for any strongly connected directed network. These results pave the way for developing efficient approximation algorithms admitting certain quality certifications, which when combined can provide effective tools and better analysis for optimal influence spreading in large networks. Second, we introduce and investigate problems of network monitoring and consensus prediction. Here, an observer, without exact knowledge of the network, seeks to determine in the shortest possible time the asymptotic agreement value by monitoring a subset of the agents. We uncover a fundamental limit on the minimum required monitoring time for the case of a single observed node, and analyze the case of multiple observed nodes. We provide conditions for achieving the limit in the former case and develop algorithms toward achieving conjectured bounds in the latter through local observation and local computation. Third, we study a distributed optimization problem where a network of agents seeks to minimize the sum of the agents' individual objective functions while each agent may be associated with a separate local constraint. We develop new distributed algorithms for solving this problem. In these algorithms, consensus prediction is employed as a means to achieve fast convergence rates, possibly in finite time. An advantage of our distributed optimization algorithms is that they work under milder assumptions on the network weight matrix than are commonly assumed in the literature. Most distributed algorithms require undirected networks. Consensus-based algorithms can apply to directed networks under an assumption that the network weight matrix is doubly stochastic (i.e., both row stochastic and column stochastic), or in some recent literature only column stochastic. Our algorithms work for directed networks and only require row stochasticity, a mild assumption. Doubly stochastic or column stochastic weight matrices can be hard to arrange locally, especially in broadcast-based communication. We achieve the simplification to the row stochastic assumption through a distributed rescaling technique. Next, we develop a unified convergence analysis of a distributed projected subgradient algorithm and its variation that can be applied to both unconstrained and constrained problems without assuming boundedness or commonality of the local constraint sets. | en_US |
| dc.identifier | https://doi.org/10.13016/M2JS0J | |
| dc.identifier.uri | http://hdl.handle.net/1903/19441 | |
| dc.language.iso | en | en_US |
| dc.subject.pqcontrolled | Electrical engineering | en_US |
| dc.subject.pquncontrolled | consensus prediction | en_US |
| dc.subject.pquncontrolled | directed network | en_US |
| dc.subject.pquncontrolled | distributed optimization | en_US |
| dc.subject.pquncontrolled | leader influence | en_US |
| dc.subject.pquncontrolled | multi-agent systems | en_US |
| dc.subject.pquncontrolled | network consensus | en_US |
| dc.title | CONSENSUS, PREDICTION AND OPTIMIZATION IN DIRECTED NETWORKS | en_US |
| dc.type | Dissertation | en_US |
Files
Original bundle
1 - 1 of 1