On Local Computation for Optimization in Multi-Agent Systems
This work addresses optimization in multi-agent systems, such as task allocation and network load-sharing, by exploiting local structure, though it appears incremental as it builds on existing distributed methods.
The paper tackles the problem of distributed optimization in multi-agent systems by developing a rigorous notion of locality to quantify how agents can compute solutions based on local information, resulting in a simple algorithm with theoretical bounds that are shown to be tight for well-conditioned problems.
A number of prototypical optimization problems in multi-agent systems (e.g., task allocation and network load-sharing) exhibit a highly local structure: that is, each agent's decision variables are only directly coupled to few other agent's variables through the objective function or the constraints. Nevertheless, existing algorithms for distributed optimization generally do not exploit the locality structure of the problem, requiring all agents to compute or exchange the full set of decision variables. In this paper, we develop a rigorous notion of "locality" that quantifies the degree to which agents can compute their portion of the global solution based solely on information in their local neighborhood. This notion provides a theoretical basis for a rather simple algorithm in which agents individually solve a truncated sub-problem of the global problem, where the size of the sub-problem used depends on the locality of the problem, and the desired accuracy. Numerical results show that the proposed theoretical bounds are remarkably tight for well-conditioned problems.