Distributed Optimization of Clique-Wise Coupled Problems

This study addresses a distributed optimization with a novel class of coupling of variables, called clique-wise coupling. A clique is a node set of a complete subgraph of an undirected graph. This setup is an extension of pairwise coupled optimization problems (e.g., consensus optimization) and allows us to handle coupling of variables consisting of more than two agents systematically. To solve this problem, we propose a clique-based linearized ADMM algorithm, which is proved to be distributed. Additionally, we consider objective functions given as a sum of nonsmooth and smooth convex functions and present a more flexible algorithm based on the FLiP-ADMM algorithm. Moreover, we provide convergence theorems of these algorithms. Notably, all the algorithmic parameters and the derived condition in the theorems depend only on local information, which means that each agent can choose the parameters in a distributed manner. Finally, we apply the proposed methods to a consensus optimization problem and demonstrate their effectiveness via numerical experiments.