A dual splitting approach for distributed resource allocation with regularization

Abstract

We deal with a class of distributed resource allocation problems where each agent attempts to minimize its own cost while respecting network-wide resource constraints as well as local capacity limits. This problem arises from many areas, such as economic dispatch, network utility maximization, and demand response. Most existing methods are centralized while few works are devoted to solving the problem in a distributed manner. The problem becomes even more challenging when there is a (nonsmooth) regularization term in the cost function. In this paper, we propose a novel distributed algorithm (termed DuSPA) to solve the above problem based on duality analysis and splitting methods. For privacy concerns, this algorithm is not required to communicate sensitive gradient information while still achieving the optimum without sacrificing the performance. We will show that the proposed algorithm converges at a nonergodic convergence rate of O(1/k) for general convex cost functions and a linear convergence rate for smooth and strongly convex cost functions, respectively. Furthermore, we apply the proposed algorithm to an economic dispatch problem to show its effectiveness.