Distributed Non-smooth Resource Allocation Over a Network

Networked systems are common and crucial. One of the canonical problems in such systems is distributed resource allocation. From this rather broad class of problems, we consider a convex non-smooth resource allocation problem with a global resource constraint. Specifically, the objective function is separable and consists of a sum of convex functions, each associated with a node in a given network. Each component of the objective depends on a single variable local to the associated node and the sum of all local variables must remain constant at all times. For scalability, we constrain the nodes to only communicate and exchange resources with their immediate neighbors. We propose an algorithm that combines subgradient optimization with distributed averaging. Starting the algorithm from a feasible point, the nodes iteratively exchange resources with their neighbors to get close to the optimal set while satisfying the total resource constraint at all times. We show that under mild technical conditions the algorithm converges in an epsilon-sense, as long as the stepsize is chosen sufficiently small and the distributed averaging process is sufficiently accurate. We derive expressions for how the stepsize and the number of consensus iterations affect the accuracy of the final result.