Hierarchically Distributed Optimization with a Flexible and Complexity-Reducing Algorithm

In this paper, the authors consider distributed convex optimization over hierarchical networks. The authors exploit the hierarchical architecture to design specialized distributed algorithms so that the complexity can be reduced compared with that of non-hierarchically distributed algorithms. To this end, the authors use local agents to process local functions in the same manner as other distributed algorithms that take advantage of multiple agents’ computing resources. Moreover, the authors use pseudocenters to directly integrate lower-level agents’ computation results in each iteration step and then share the outcomes through the higher-level network formed by pseudocenters. The authors prove that the complexity of the proposed algorithm exponentially decreases with respect to the total number of pseudocenters. To support the proposed decomposition-composition method for agents and pseudocenters, the authors develop a class of operators. These operators are generalizations of the widely-used subgradient based operator and the proximal operator and can be used in distributed convex optimization. Additionally, these operators are closed with respect to the addition and composition operations; thus, they are suitable to guide hierarchically distributed design and analysis. Furthermore, these operators make the algorithm flexible since agents with different local functions can adopt suitable operators to simplify their calculations. Finally, numerical examples also illustrate the effectiveness of the method.