Distributed primal-dual methods for online constrained optimization

Abstract

This paper introduces a decentralized primal-dual method for online distributed optimization involving global constraints. We employ a consensus-based framework and exploit the decomposability of the constraints in dual domain. At each stage, each agent commits to an adaptive decision pertaining only to the past and locally available information, and incurs a new cost function reflecting the change in the environment. We show that the algorithm achieves a regret of order O(√T) at any node with the time horizon T, in scenarios when the underlying communication topology is time-varying and jointly-connected.