解决多智能体系统中大规模优化问题的高性能算法

Big data motivates people to increasingly rely on multi-agent systems for solving large-scale engineering problems, including large-scale optimization. To date, all the existing distributed algorithms for large-scale optimization over multi-agent systems suffer from one or more of the following drawbacks: limited problem scope, lack of convergence rate guarantee, and synchronicity in implementation. This project is intended to develop a collection of high-performance asynchronous distributed algorithms that are able to overcome the aforementioned drawbacks. These algorithms should enable multi-agent systems to solve general large-scale convex constrained optimization problems in an efficient, robust, and flexible way. In addition, the underlying topologies of multi-agent systems are allowed to be time-varying. To this end, we plan to design a number of new coordinate descent algorithms, which are able to solve a dual problem and thus obtain a primal optimal solution in an asynchronous and distributed fashion via novel dual decomposition techniques for time-varying networks. The proposed algorithms are expected to achieve convergence rates of the same order as those of some classical centralized optimization methods when solving the same problem. To further enhance the algorithm performance, we will design a distributed feedback control mechanism, which allows each agent to use local information as feedback to control and plan its own behavior. This can lead to faster convergence or lower complexity of the algorithms.

大数据的兴起促使人们越来越多地依赖多智能体系统以解决大规模的工程问题，例如大规模优化。目前，针对多智能体系统中大规模优化问题的分布式算法尚存在适用范围不广，缺乏收敛速度，或要求智能体同步进行更新等不足。本项目将设计一系列能够克服上述不足的高性能异步分布式算法。这些算法能够使多智能体系统高效、可靠、灵活地解决一般的大规模凸约束优化问题，并允许多智能体系统具有动态的网络拓扑结构。为构建出这样的算法，我们将设计多个全新的坐标下降法。利用针对时变网络的新型对偶分解技术使坐标下降法以异步、分布式的方式解决一个对偶问题，从而获取原始问题的最优解。并且，在解决同样的问题时，我们的异步分布式算法将与一些经典的集中式优化算法具有同量级的收敛速度。为进一步提升算法的性能，我们将设计一类分布式反馈控制机制，使智能体能够以本地信息作为反馈来控制、规划自身的行为，从而加速算法的收敛或者降低算法的复杂度。

多智能体系统的发展使得分布式优化得到了日益增长的关注。分布式优化要求多智能体系统中相互连接的智能体通过合作解决一个大规模的优化问题，而优化问题的数据则遍布于整个系统。到目前为止，已有大量的分布式优化算法被提出。这些算法允许智能体仅凭借本地信息作为反馈去控制自身的行为，以此逐渐逼近问题的最优解。然而，现有的分布式优化算法仍存在一些关键的局限性，比如缺少理论收敛速度的保障、局限的问题假设条件、无法适用于时变网络拓扑结构和异步通信、过高的计算和通信成本等等。在本项目中，我们基于多种不同的工具，包括Fenchel对偶性、坐标下降法、平滑化技术、二阶近似、虚拟队列方法等，设计了多种高性能的分布式算法，以解决多智能体系统中几类常见的凸优化问题。这些算法能够克服一个或多个上述已有算法的缺陷。我们为算法提供了大量收敛性结果，其中大部分要强于已有工作的收敛性结果，甚至有些收敛速度能与集中式方法同阶。此外，我们获取的收敛速度能够明确体现问题假设、网络条件、算法参数和智能体状态对于收敛速度的影响。这可以帮助智能体通过本地信息交互自主决定计算、通信相关的参数，以保证理想的收敛性能。我们还对学习和控制应用中常见的数值问题进行了大量仿真，展示了算法极具竞争力的实际性能表现。