Exponential Convergence of Augmented Primal-dual Gradient Algorithms for Partially Strongly Convex Functions

2024/10/03 by Mengmou Li, Li, Mengmou, Masaaki Nagahara +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2410.02192

openalex publication_date 2024/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the augmented primal-dual gradient algorithms can achieve global exponential convergence with partially strongly convex functions. In particular, the objective function only needs to be strongly convex in the subspace satisfying the equality constraint and can be generally convex elsewhere, provided the global Lipschitz condition for the gradient is satisfied. This condition implies that states outside the equality subspace will converge towards it exponentially fast. The analysis is then applied to distributed optimization, where the partially strong convexity can be relaxed to the restricted secant inequality condition, which is not necessarily convex. This work unifies global exponential convergence results for some existing centralized and distributed algorithms.

Related

• Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Condition
• Aug-PDG: Linear Convergence of Convex Optimization with Inequality Constraints
• Linear Convergence of Primal-Dual Gradient Methods and their Performance\n in Distributed Optimization
• Distributed dual gradient methods and error bound conditions
• On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems