Research On Distributed Approaches For Optimal Resource Allocations Over Directed Networks

The resource allocation problem(RAP)deals with how to allocate available resources to a number of users,called nodes(agents).The goal is to minimize the total cost when allocating the total resource(resources)to nodes.Many optimization problems in the financial markets,smart grids,wireless sensor networks,military ad hoc networks,and cloud systems,can be modelled as a RAP.Besides,in examples include economic dispatch problems,power regulation and take or pay fuel supply problems,the resources allocated to nodes are real numbers,we call it as the RAP without integer constraints.Moveover,in many other practical examples(e.g.,joint replen-ishment problem,software-testing resources allocation),the resources allocated to nodes can only be integer numbers,this is so called the integer resource allocation problem(iRAP).Although many centralized optimization algorithms exist for this problem,it is desired to design distributed algorithms for solving the RAP due to significant communications overhead required for collect-ing information from all the nodes in large-scale networks and lacking of robustness(by requiring individual nodes to provide information).Besides.communications between some nodes in the wireless network may be unidirectional due to the heterogeneous nature of the wireless communi-cation nodes(e.g.,the packet loss,the communication interference)or due to the use of directional antennas.Thus,in this paper,we design distributed algorithms for the rRAP and the iRAP with convex objective functions,subject to individual resource(state)constraints,equality constraints over directed graphs(digraphs)based on only locally available information.For the RAP without integer constraints,we consider a multi-agent network with a time-varying digraph,since the dynamics of digraphs appear naturally due to the communication links disconnection caused by external interference and due to the error of local synchronous clocks.The main challenge of the problem is due to the local information structure imposed by the time-varying digraph that should be considered as part of the problem formulation.This paper develops a nonnegative surplus based distributed optimization algorithm.It is shown that the proposed distributed algorithm converges to the global minimizer provided that the time-varying digraph is jointly strongly connected.For the iRAP,we first consider a multi-agent network with a global synchronous clock and a static digraph.With the global synchronous clock,its desirable to design a fast convergent dis-tributed algorithm for the iRAP.As a preliminary work,we propose a novel min-heap and opti-mization relaxation based centralized algorithm and prove that it has a computational complexity of O(nlogn + nlog D)when the resource constraints of individual agents are[0.D],which outper-forms the best known multi-phase algorithm with O(nlogn log D).By extending the centralized algorithm,we present a consensus based distributed optimization algorithm to solve the same prob-lem by utilizing the algorithm for solving RAP.It is shown that the proposed distributed algorithm converges to a global minimizer provided that the digraph is strongly connected.At last,since the implementation of distributed algorithms are simplified and the costs as-sociated with synchronization is eliminated by operating nodes in an asynchronous manner,we propose a novel nonnegative surplus based asynchronous distributed optimization algorithm for iRAP.It is shown that the proposed asynchronous distributed algorithm converges to an global minimizer provided that the directed graph is strongly connected and randomly "gossip".Also,all the parameters used in the distributed algorithm rely only on local knowledge.For these algorithms,simulation results are presented in each chapter to illustrate the results.