Distributed Dual Subgradient Algorithms With Iterate-Averaging Feedback for Convex Optimization With Coupled Constraints

This article considers a general model of distributed convex optimization with possibly local constraints, coupled equality constraints, and coupled inequality constraints, where the coupled equality constraints are affine and the coupled inequality constraints can be nonaffine. To solve this problem, we present two algorithms. The first algorithm is similar to a dual subgradient algorithm that requires a center node in the network. The main advantage of the first algorithm is that it achieves the optimal convergence rate O([1/root k]). Moreover, it does not require additional treatment for the primal recovery. These merits are achieved by using an iterate-averaging feedback technique on the basis of the dual subgradient method. The second algorithm further removes the requirement of a center node by employing consensus tracking iterates. As a result, the second algorithm is fully distributed at the price of achieving an O([lnk/root k]) convergence rate.

Automated summary

This article discusses two algorithms for distributed convex optimization, with the first achieving optimal convergence rate by requiring a center node, and the second achieving full distribution at a slightly lower convergence rate by using consensus tracking iterates.