Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays. (2nd November 2022)

• Record Type: Journal Article
• Authors: Latafat, Puya; Patrinos, Panagiotis
• Is Part Of: Optimization methods and software. Volume 37:Number 6(2022)
• Page Start: 2052
• Page End: 2079
• Publication Date: 2022-11-02
• Subjects: Asynchronous algorithms -- primal-dual algorithms -- distributed optimization -- message passing; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.2023524
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We consider algorithms for solving structured convex optimization problems over a network of agents with communication delays. It is assumed that each agent performs its local updates using possibly outdated information from its neighbours under the assumption that the delay with respect to each neighbour is bounded but otherwise arbitrary. The private objective of each agent is represented by the sum of two possibly nonsmooth functions one of which is composed with a linear mapping. The global optimization problem is the aggregate of local cost functions and a common Lipschitz-differentiable function. When the coupling between agents is represented only through the common function, the V\~u-Condat primal-dual algorithm is studied. In the case when the linear maps introduce additional coupling between agents a new algorithm is developed. Moreover, a randomized variant of this algorithm is presented that allows the agents to wake up at random and independently from one another. The convergence of the proposed algorithms is established under strong convexity assumptions.