Distributed convex optimization with identical constraints
Shahin Nikookhoy, Jie Lu, Choon Yik Tang · 2011
This paper presents a gossip-style, distributed asynchronous algorithm that solves constrained optimization problems over networks with time-varying topologies, where the objective function is a sum of uniformly strictly convex local objective functions belonging to nodes in the network, and the inequality and equality constraint functions are convex and identical to every node. Referred to as Pairwise Equalizing (PE), the algorithm operates by forcing the nodes' estimates of the unknown minimizer to asymptotically achieve consensus while satisfying a conservation condition derived from the Karush-Kuhn-Tucker condition. We show that as long as the gossiping pattern is sufficiently rich, PE achieves asymptotic convergence and solves the problem. The proposed algorithm represents an alternative to the existing subgradient algorithms and generalizes our earlier algorithm for problems without constraints.