Decentralized Online Convex Optimization in Networked Systems

arXiv2207.05950MaRDI QIDQ6404795FDOQ6404795

Authors: Judy Gan, Guannan Qu, Yash Kanoria, Adam Wierman 

Publication date: 13 July 2022

Abstract: We study the problem of networked online convex optimization, where each agent individually decides on an action at every time step and agents cooperatively seek to minimize the total global cost over a finite horizon. The global cost is made up of three types of local costs: convex node costs, temporal interaction costs, and spatial interaction costs. In deciding their individual action at each time, an agent has access to predictions of local cost functions for the next $k$ time steps in an $r$-hop neighborhood. Our work proposes a novel online algorithm, Localized Predictive Control (LPC), which generalizes predictive control to multi-agent systems. We show that LPC achieves a competitive ratio of $1+ildeO(h{o}_T^k)+ildeO(h{o}_S^r)$ in an adversarial setting, where $h{o}_T$ and $h{o}_S$ are constants in $(0,1)$ that increase with the relative strength of temporal and spatial interaction costs, respectively. This is the first competitive ratio bound on decentralized predictive control for networked online convex optimization. Further, we show that the dependence on $k$ and $r$ in our results is near optimal by lower bounding the competitive ratio of any decentralized online algorithm.

This page was built for publication: Decentralized Online Convex Optimization in Networked Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404795)