Distributed Subgradient Projection Algorithm over Directed Graphs

Abstract

We propose a distributed algorithm, termed the Directed-Distributed Projected Subgradient (D-DPS), to solve a constrained optimization problem over a multi-agent network, where the goal of agents is to collectively minimize the sum of locally known convex functions. Each agent in the network owns only its local objective function, constrained to a commonly known convex set. We focus on the circumstance when communications between agents are described by a directed network. The D-DPS augments an additional variable for each agent, to overcome the asymmetry caused by the directed communication network. The convergence analysis shows that D-DPS converges at a rate of $O(\frac{\ln k}{\sqrt{k}})$, where k is the number of iterations.

References in corpus (5)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Convex Optimization for Big Data
• On the Linear Convergence of Distributed Optimization over Directed Graphs
• On the Distributed Optimization over Directed Networks
• Random block coordinate descent methods for linearly constrained optimization over networks

Cited by in corpus (2)

• On the Linear Convergence of Distributed Optimization over Directed Graphs
• Linear convergence in optimization over directed graphs with row-stochastic matrices