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

Hao Yu, Michael J. Neely

Published 2015-12-28Version 1

This paper considers convex programs with a general (possibly non-differentiable) convex object function and Lipschitz continuous convex inequality constraint functions and proposes a simple parallel algorithm with $O(1/t)$ convergence rate. Similar to the classical dual subgradient algorithm or the ADMM algorithm, the new algorithm has a distributed implementation when the object and constraint functions are decomposable. However, the new algorithm has faster $O(1/t)$ convergence rate compared with the best known $O(1/\sqrt{t})$ convergence rate for the dual subgradient algorithm with averaged primals; and can solve convex programs with nonlinear constraints, which can not be handled by the ADMM algorithm. The new algorithm is applied to multipath network utility maximization problem such that a decentralized flow control algorithm with fast $O(1/t)$ convergence rate is obtained. The $O(1/t)$ convergence rate is further verified by numerical experiments.