论文标题
关于在多代理系统中优化的本地计算
On Local Computation for Optimization in Multi-Agent Systems
论文作者
论文摘要
多代理系统中的许多原型优化问题（例如，任务分配和网络负载共享）表现出高度局部的结构：也就是说，每个代理的决策变量仅通过目标函数或约束直接耦合到其他几个其他代理变量。然而，现有的分布式优化算法通常不会利用问题的局部性结构，要求所有代理商计算或交换完整的决策变量集。在本文中，我们开发了一个严格的“地方”概念，该概念量化了代理可以仅根据当地社区中的信息来计算其全球解决方案的一部分的程度。该概念为一种相当简单的算法提供了理论基础，在该算法中，代理单独解决了全局问题的截断子问题，其中所使用的子问题的大小取决于问题的局部性和所需的准确性。数值结果表明，对于条件良好的问题，提出的理论界限非常紧。
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.
