A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programs

2015/12/28 by Hao Yu, Yu, Hao, Michael J. Neely +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1512.08370

openalex publication_date 2015/12/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper considers convex programs with a general (possibly non-differentiable) convex objective function and Lipschitz continuous convex inequality constraint functions. A simple algorithm is developed and achieves an O(1/t) convergence rate. Similar to the classical dual subgradient algorithm and the ADMM algorithm, the new algorithm has a parallel implementation when the objective and constraint functions are separable. However, the new algorithm has a faster O(1/t) convergence rate compared with the best known O(1/√(t)) convergence rate for the dual subgradient algorithm with primal averaging. Further, it can solve convex programs with nonlinear constraints, which cannot be handled by the ADMM algorithm. The new algorithm is applied to a multipath network utility maximization problem and yields a decentralized flow control algorithm with the fast O(1/t) convergence rate.

Citations

• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers

Related

• A Primal-Dual Parallel Method with O(1/ε) Convergence for Constrained Composite Convex Programs
• A Primal-Dual Type Algorithm with the O(1/t) Convergence Rate for Large Scale Constrained Convex Programs
• Parallel and Distributed Methods for Nonconvex Optimization-Part I: Theory
• Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs
• Double Averaging and Gradient Projection: Convergence Guarantees for Decentralized Constrained Optimization