Random Coordinate Descent for Resource Allocation in Open Multiagent Systems

• 成果类型: Article
• 署名作者: de Galland, Charles Monnoyer; Vizuete, Renato; Hendrickx, Julien M.; Panteley, Elena; Frasca, Paolo
• 署名单位: Fonds de la Recherche Scientifique - FNRS; Universite Catholique Louvain; Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3394349
• 发表日期: 2024
• 页码: 7600-7613
• 关键词: Optimization; Multi-agent systems; cost function; CONVERGENCE; Open systems; resource management; COSTS; Agents and autonomous systems; distributed optimization; gradient methods; open multiagent systems

摘要

We propose a method for analyzing the distributed random coordinate descent algorithm for solving separable resource allocation problems in the context of an open multiagent system, where agents can be replaced during the process. In particular, we characterize the evolution of the distance to the minimizer in expectation by following a time-varying optimization approach which builds on two components. First, we establish the linear convergence of the algorithm in closed systems, in terms of the estimate toward the minimizer, for general graphs and appropriate step-size. Second, we estimate the change of the optimal solution after a replacement, in order to evaluate its effect on the distance between the current estimate and the minimizer. From these two elements, we derive stability conditions in open systems and establish the linear convergence of the algorithm toward a steady-state expected error. Our results enable to characterize the tradeoff between speed of convergence and robustness to agent replacements, under the assumptions that local functions are smooth, strongly convex, and have their minimizers located in a given ball. The approach proposed in this article can moreover be extended to other algorithms guaranteeing linear convergence in closed system.