A Distributed Algorithm for Resource Allocation Over Dynamic Digraphs

Abstract

This paper studies a distributed resource allocation problem for a multiagent network with a time-varying digraph. Each agent in the network is associated with a local variable (resource) and a convex cost function. The goal is to collectively minimize the total cost in a distributed fashion, subject to individual resource constraints, and collective equality constraints. 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. Also, all the parameters used in the proposed algorithm rely only on local knowledge.