An Inexact Fenchel Dual Gradient Algorithm for Distributed Optimization

In this paper, we design a distributed algorithm for addressing constrained convex optimization over networks. The proposed algorithm is developed by substituting a projected gradient operation for a convex minimization step at each iteration of the Fenchel dual gradient (FDG) method derived in a prior work, so that the high computational load of FDG can be significantly alleviated. Such an algorithm can be viewed as a weighted inexact gradient method applied to the Fenchel dual problem, and therefore is referred to as Inexact Fenchel Dual Gradient (IFDG) algorithm. We provide rates of convergence to the optimal solution for IFDG when the local objective functions are strongly convex and smooth. Simulation results demonstrate that IFDG remarkably reduces the running time of FDG, yet its convergence performance is comparable to that of FDG.

I. Introduction

The growing size of optimization problems in many engineering applications arising in wireless sensor networks [1], [2], cognitive radio networks [3], and machine learning [4] motivates the development of distributed optimization algorithms, in which a network of nodes are utilized to cooperatively minimize the sum of their local objective functions subject to their local constraints and their interactions only occur among neighbors. Compared to the traditional, centralized optimization techniques, distributed optimization algorithms have better applicability to large-scale optimization problems and are more robust and scalable.