Linear-speed interior-path algorithms for distributed control of information networks

Abstract

Many network-based problems are naturally distributed optimization problems. Examples include routing and flow control in wireless sensor networks, congestion pricing on the Internet, and resource allocation in distributed data-processing systems. Most of the distributed solutions provided by existing work utilize algorithms based on the sub-gradient method. Although stability and asymptotic optimality of these algorithms have been extensively studied and confirmed in the literature, the practical convergence speed of these algorithms attracted little attention. Our simulation results show that sometimes it is far below what it is expected to be. This paper presents a generic formulation for distributed optimization that can model all above-mentioned problems, and proposes two classes of distributed algorithms: one using a simple coordinator and the other using network consensus. These algorithms are based on the barrier method and are closely related to the interior-point method for non-distributed optimization problems. Using new techniques, we prove that our distributed algorithms converge linearly to the optimal solution. Simulation experiments demonstrate that the actual convergence speed of these algorithms is much faster than existing distributed algorithms. We further investigate how their algorithmic parameters affect the convergence speed. © 2010 Elsevier B.V. All rights reserved.