Frequency-Domain Analysis of Distributed Optimization: Fundamental Convergence Rate and Optimal Algorithm Synthesis

• 成果类型: Article
• 署名作者: Zhang, Shiqi; Wu, Wuwei; Li, Zhongkui; Chen, Jie; Georgiou, Tryphon T.
• 署名单位: City University of Hong Kong; Peking University; University of California System; University of California Irvine
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3413854
• 发表日期: 2024
• 页码: 8539-8554
• 关键词: convergence; optimization; interpolation; Heuristic algorithms; Distributed algorithms; Stability criteria; Frequency-domain analysis; distributed optimization; Frequency-domain methods; gradient-based algorithms; Nevanlinna-Pick interpolation; robust and H-infinity control

摘要

The design of optimization algorithms has long been a matter of art, and it calls for the systematic development of methods in which algorithms can be analyzed, designed, and benchmarked with regard to their key attributes such as efficiency, complexity, and robustness. This article answers this need by providing a frequency-domain framework for algorithm analysis and synthesis, with a particular emphasis on distributed optimization problems. We propose a general class of gradient-based distributed algorithms that can be viewed as interconnected dynamical systems consisting of a linear time-invariant subsystem and a Lur'e-type nonlinear component, thereby enabling analysis and synthesis of such algorithms from a robust control perspective via the usage of the circle criterion and the Zames-Falb theorem. By linking the convergence of an algorithm with the absolute stability of a corresponding Lur'e system, optimization of the algorithmic convergence rate is recast as a Nevanlinna-Pick interpolation problem akin to an H-infinity optimal control problem. Solutions to such interpolation problems lead to a variety of gradient-based algorithms with optimal and suboptimal convergence rates, and algorithmic complexity judiciously controlled.