Max-Gossip Subgradient Method for Distributed Optimization
Ashwin Verma, Marcos M. Vasconcelos, Urbashi Mitra, Behrouz Touri · 2021 60th IEEE Conference on Decision and Control (CDC) · 2021
We study the problem of distributed optimization over a network of agents where the agents strive to minimize the sum of local objective functions through an exchange of information between the nodes based on an underlying communication topology. Motivated by the need for low communication algorithms with better convergence rates in broadcast settings, we propose a subgradient method based on a state-dependent gossip algorithm. The state-dependent gossip algorithm operates by averaging the edge with the maximum disagreement over the network. We prove that agents employing the state-dependent subgradient method achieve consensus on an optimal solution. By exploiting the convergence properties of a Lyapunov function, we obviate the need for results on time-normalized information flow between any node pairs.