Improved Convergence Rates for Distributed Resource Allocation

Angelia Nedich1, Alexander Olshevsky2, Wei Shi1

  • 1Arizona State University
  • 2Boston University

Details

Category

Invited Session

Sessions

10:00 - 12:00 | Mon 17 Dec | Flash | MoA05

Distributed Optimization for Networked Systems I

Full Text

Abstract

In this paper, we develop a class of decentralized algorithms for solving a convex resource allocation optimization problem over a connected network. By observing a connection between the resource allocation and the consensus optimization, we propose a novel class of algorithms for solving the resource allocation problem with improved convergence guarantees. Specifically, we introduce an algorithm for solving the resource allocation problem with an o(1/k) convergence rate when the agents' objective functions are generally convex and per agent local constraints are allowed; we then introduce a gradient-based algorithm for the case when per agent local constraints are absent and show that such scheme achieves geometric convergence with an improved scalability. We also provide a projection-gradient-based algorithm which can handle smooth objective and simple constraints more efficiently.

Additional Information

No information added

Video

No videos found