On the Sublinear Regret of Distributed Primal-Dual Algorithms for Online Constrained Optimization

摘要: This paper introduces consensus-based primal-dual methods for distributed online optimization where the time-varying system objective function $f_t(\mathbf{x})$ is given as sum of local agents' functions, i.e., $f_t(\mathbf{x}) = \sum_i f_{i,t}(\mathbf{x}_i)$, and constraint $\mathbf{g}(\mathbf{x})$ $\mathbf{g}(\mathbf{x}) \mathbf{g}_i (\mathbf{x}_i) \preceq \mathbf{0}$. At each stage, agent commits to an adaptive decision pertaining only past locally available information, incurs a new cost reflecting change in environment. Our algorithm uses weighted averaging iterates keep estimates global constraints dual variables. We show that achieves regret order $O(\sqrt{T})$ with time horizon $T$, scenarios when underlying communication topology jointly-connected. The measured regard value well violation. Numerical results routing wireless multi-hop networks uncertain channel rates are provided illustrate performance proposed algorithm.