Gossip-based distributed hierarchical algorithm for multi-cluster constrained optimisation

摘要

This study develops a gossip-based distributed hierarchical algorithm to solve the constrained convex optimisation problem over a multi-cluster network. Different from the existing works with incremental communication approach, a gossip protocol is applied to achieve inter-cluster information exchange. At each iteration, only two neighbour clusters are randomly woken up to exchange their new updates while others keep their latest information, which relaxes the restrictions on the inter-cluster communication topology. Technically, to investigate the intra-cluster consensus, a new analysing approach is exploited and some different techniques including the non-expansiveness of projection operator and the supermartingale convergence results are employed, based on which it is proved that estimates of all agents in the multi-cluster network jointly converge to the optimal solution with probability one. A numerical example on constrained lasso regression is provided to validate the theoretical results.