An Accelerated Distributed Optimization with Equality and Inequality Coupling Constraints

Abstract

This paper studies distributed convex optimization with both affine equality and nonlinear inequality couplings through the duality analysis. We first formulate the dual of the coupling-constraint problem and reformulate it as a consensus optimization problem over a connected network. To efficiently solve this dual problem and hence the primal problem, we design an accelerated linearized algorithm that, at each round, a look-ahead linearization of the separable objective is combined with a quadratic penalty on the Laplacian constraint, a proximal step, and an aggregation of iterations. On the theory side, we prove non-ergodic rates for both the primal optimality error and the feasibility error. On the other hand, numerical experiments show a faster decrease of optimality error and feasibility residual than augmented-Lagrangian tracking and distributed subgradient baselines under the same communication budget.