Online distributed ADMM via dual averaging

Abstract

This paper presents a convergence analysis on a distributed Alternating Direction Method of Multipliers (ADMM) algorithm which solves online convex optimization problems under linear constraints. The goal is to distributively optimize a global objective function over a network of decision makers. The global objective function is composed of convex cost functions associated with each agent. The local cost functions can be broken down into two convex functions, one of which is revealed over time to the decision makers and one known a priori. We extend an online ADMM algorithm to a distributed setting based on dual-averaging. We then explore the rate of convergence of the performance of the sequence of decisions generated by the algorithm to the best fixed decision in hindsight. This performance metric is called regret. An upper bound on the regret of the proposed algorithm is presented as a function of the underlying network topology and linear constraints. The online distributed ADMM algorithm is then applied to a formation acquisition problem.