A Contraction Analysis of Primal-Dual Dynamics in Distributed and Time-Varying Implementations

• 成果类型: Article
• 署名作者: Cisneros-Velarde, Pedro; Jafarpour, Saber; Bullo, Francesco
• 署名单位: University of California System; University of California Santa Barbara
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3103865
• 发表日期: 2022
• 页码: 3560-3566
• 关键词: convergence; optimization; Heuristic algorithms; trajectory; linear programming; STANDARDS; Time-varying systems; Contraction theory; Distributed algorithms; Least Squares; primal-dual (PD); time-varying optimization

摘要

In this article, we provide an overarching analysis of primal-dual dynamics associated with linear equality-constrained optimization problems using contraction analysis. For the well-known standard version of the problem, we establish convergence under convexity and the contracting rate under strong convexity. Then, for a canonical distributed optimization problem, we use partial contractivity to establish global exponential convergence of its primal-dual dynamics. As an application, we propose a new distributed solver for the least-squares problem with the same convergence guarantees. Finally, for time-varying versions of both centralized and distributed primal-dual dynamics, we exploit their contractive nature to establish bounds on their tracking error. To support our analyses, we introduce novel results on contraction theory.