Distributed Partitioned Big-Data Optimization via Asynchronous Dual Decomposition
It addresses scalability and redundancy issues in distributed optimization for networks where decision variable dimension scales with network size and cost/constraints have graph-induced sparsity.
The paper proposes an asynchronous distributed algorithm for partitioned big-data optimization in peer-to-peer networks, exploiting problem sparsity to allow each node to store only a local portion of the decision variable and solve a small-scale local problem, improving scalability and reducing redundancy.
In this paper we consider a novel partitioned framework for distributed optimization in peer-to-peer networks. In several important applications the agents of a network have to solve an optimization problem with two key features: (i) the dimension of the decision variable depends on the network size, and (ii) cost function and constraints have a sparsity structure related to the communication graph. For this class of problems a straightforward application of existing consensus methods would show two inefficiencies: poor scalability and redundancy of shared information. We propose an asynchronous distributed algorithm, based on dual decomposition and coordinate methods, to solve partitioned optimization problems. We show that, by exploiting the problem structure, the solution can be partitioned among the nodes, so that each node just stores a local copy of a portion of the decision variable (rather than a copy of the entire decision vector) and solves a small-scale local problem.