Distributed Optimization Over Unbalanced Graph: Integration of Surplus-Based Method and Push-DIGing Method
Shu Liang, Songsong Cheng, Kaixiang Peng · 2019
Distributed optimization is of essential importance in networked systems. Most of the literature either assume the information exchange over undirected graphs, or require that the underlying directed network topology provides balanced weights to the agents. In this paper, a novel distributed algorithm is proposed to solve convex optimization problems over unbalanced graphs. The algorithm is based on in-degrees and out-degrees of the graph, but uses less variables than the push-DIGing algorithm. Also, our algorithm reduces to the surplus-based algorithm for average consensus problems and is equivalent to the DIGing algorithm when the graph is undirected. As a result, our algorithm can be regarded as an integration of the surplus-based method and push-DIGing method. The effectiveness of the proposed algorithm is illustrated by a numerical example, while the convergence analysis is currently in processing.