Double Averaging and Gradient Projection: Convergence Guarantees for Decentralized Constrained Optimization

作     者：Shahriari-Mehr, Firooz Panahi, Ashkan 

作者机构：Chalmers Univ Technol Dept Comp Sci & Engn SE-41296 Gothenburg Sweden Univ Gothenburg SE-41296 Gothenburg Sweden 

出 版 物：《IEEE TRANSACTIONS ON AUTOMATIC CONTROL》 (IEEE Trans Autom Control)

年 卷 期：2025年第70卷第5期

页      面：3433-3440页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 

基　　金：Wallenberg AI  Autonomous Systems  and Software Program (WASP) - Knut and Alice Wallenberg Foundation 

主　　题：Convergence Optimization Directed graphs Linear programming Standards Convex functions Optimization methods Lyapunov methods Computer architecture Vectors Constrained optimization convergence analysis convex optimization distributed optimization 

摘      要：We consider a generic decentralized constrained optimization problem over static, directed communication networks, where each agent has exclusive access to only one convex, differentiable, local objective term and one convex constraint set. For this setup, we propose a novel decentralized algorithm, called double averaging and gradient projection (DAGP). We achieve global optimality through a novel distributed tracking technique we call distributed null projection. Further, we show that DAGP can be used to solve unconstrained problems with nondifferentiable objective terms with a problem reduction scheme. Assuming only smoothness of the objective terms, we study the convergence of DAGP and establish sublinear rates of convergence in terms of feasibility, consensus, and optimality, with no extra assumption (e.g., strong convexity). For the analysis, we forego the difficulties of selecting Lyapunov functions by proposing a new methodology of convergence analysis, which we refer to as aggregate lower-bounding. To demonstrate the generality of this method, we also provide an alternative convergence proof for the standard gradient descent algorithm with smooth functions.