A fast dual gradient method for separable convex optimization via smoothing

Abstract

This paper considers a class of separable convex optimization problems with linear coupled constraints arising in many applications. Based on a novel smoothing technique, a simple fast dual gradient method is presented to solve the class of problems. Then the convergence of the proposed method is proved and the computational complexity bound of the method for achieving an approximately optimal solution is given explicitly. An improved iteration complexity bound is obtained when the objective function of the problem is strongly convex. Our algorithm is simple and fast, which can be implemented in a parallel fashion. Numerical experiments on a network utility maximization problem to illustrate the effectiveness of the proposed algorithm.