Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDC-DistADMM: ADMM Algorithm for Contsrained Distributed Optimization over Directed Graphs
121
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This article focuses on multi-agent distributed optimization problems with a common decision variable, a global linear equality constraint, and local set constraints over directed interconnection topologies. We propose a novel ADMM based distributed algorithm to solve the above problem. During every iteration of the algorithm, each agent solves a local convex optimization problem and utilizes a finite-time ``approximate consensus protocol to update its local estimate of the optimal solution. The proposed algorithm is the first ADMM based algorithm with convergence guarantees to solve distributed multi-agent optimization problems where the interconnection topology is directed. We establish two strong explicit convergence rate estimates for the proposed algorithm to the optimal solution under two different sets of assumptions on the problem data. Further, we evaluate our proposed algorithm by solving two non-linear and non-differentiable constrained distributed optimization problems over directed graphs. Additionally, we provide a numerical comparison of the proposed algorithm with other state-of-the-art algorithms to show its efficacy over the existing methods in the literature.
rate research
Read More
In this paper we study the distributed average consensus problem in multi-agent systems with directed communication links that are subject to quantized information flow. Specifically, we present and analyze a distributed averaging algorithm which operates exclusively with quantized values (i.e., the information stored, processed and exchanged between neighboring agents is subject to deterministic uniform quantization) and relies on event-driven updates (e.g., to reduce energy consumption, communication bandwidth, network congestion, and/or processor usage). The main idea of the proposed algorithm is that each node (i) models its initial state as two quantized fractions which have numerators equal to the nodes initial state and denominators equal to one, and (ii) transmits one fraction randomly while it keeps the other stored. Then, every time it receives one or more fractions, it averages their numerators with the numerator of the fraction it stored, and then transmits them to randomly selected out-neighbors. We characterize the properties of the proposed distributed algorithm and show that its execution, on any static and strongly connected digraph, allows each agent to reach in finite time a fixed state that is equal (within one quantisation level) to the average of the initial states. We extend the operation of the algorithm to achieve finite-time convergence in the presence of a dynamic directed communication topology subject to some connectivity conditions. Finally, we provide examples to illustrate the operation, performance, and potential advantages of the proposed algorithm. We compare against state-of-the-art quantized average consensus algorithms and show that our algorithms convergence speed significantly outperforms most existing protocols.
In this paper, we study the problem of consensus-based distributed optimization where a network of agents, abstracted as a directed graph, aims to minimize the sum of all agents cost functions collaboratively. In existing distributed optimization approaches (Push-Pull/AB) for directed graphs, all agents exchange their states with neighbors to achieve the optimal solution with a constant stepsize, which may lead to the disclosure of sensitive and private information. For privacy preservation, we propose a novel state-decomposition based gradient tracking approach (SD-Push-Pull) for distributed optimzation over directed networks that preserves differential privacy, which is a strong notion that protects agents privacy against an adversary with arbitrary auxiliary information. The main idea of the proposed approach is to decompose the gradient state of each agent into two sub-states. Only one substate is exchanged by the agent with its neighbours over time, and the other one is kept private. That is to say, only one substate is visible to an adversary, protecting the privacy from being leaked. It is proved that under certain decomposition principles, a bound for the sub-optimality of the proposed algorithm can be derived and the differential privacy is achieved simultaneously. Moreover, the trade-off between differential privacy and the optimization accuracy is also characterized. Finally, a numerical simulation is provided to illustrate the effectiveness of the proposed approach.
We investigate a distributed optimization problem over a cooperative multi-agent time-varying network, where each agent has its own decision variables that should be set so as to minimize its individual objective subject to local constraints and global coupling constraints. Based on push-sum protocol and dual decomposition, we design a distributed regularized dual gradient algorithm to solve this problem, in which the algorithm is implemented in time-varying directed graphs only requiring the column stochasticity of communication matrices. By augmenting the corresponding Lagrangian function with a quadratic regularization term, we first obtain the bound of the Lagrangian multipliers which does not require constructing a compact set containing the dual optimal set when compared with most of primal-dual based methods. Then, we obtain that the convergence rate of the proposed method can achieve the order of $mathcal{O}(ln T/T)$ for strongly convex objective functions, where $T$ is the iterations. Moreover, the explicit bound of constraint violations is also given. Finally, numerical results on the network utility maximum problem are used to demonstrate the efficiency of the proposed algorithm.
Wireless sensor network has recently received much attention due to its broad applicability and ease-of-installation. This paper is concerned with a distributed state estimation problem, where all sensor nodes are required to achieve a consensus estimation. The weighted least squares (WLS) estimator is an appealing way to handle this problem since it does not need any prior distribution information. To this end, we first exploit the equivalent relation between the information filter and WLS estimator. Then, we establish an optimization problem under the relation coupled with a consensus constraint. Finally, the consensus-based distributed WLS problem is tackled by the alternating direction method of multiplier (ADMM). Numerical simulation together with theoretical analysis testify the convergence and consensus estimations between nodes.
In this report, we study decentralized stochastic optimization to minimize a sum of smooth and strongly convex cost functions when the functions are distributed over a directed network of nodes. In contrast to the existing work, we use gradient tracking to improve certain aspects of the resulting algorithm. In particular, we propose the~textbf{texttt{S-ADDOPT}} algorithm that assumes a stochastic first-order oracle at each node and show that for a constant step-size~$alpha$, each node converges linearly inside an error ball around the optimal solution, the size of which is controlled by~$alpha$. For decaying step-sizes~$mathcal{O}(1/k)$, we show that~textbf{texttt{S-ADDOPT}} reaches the exact solution sublinearly at~$mathcal{O}(1/k)$ and its convergence is asymptotically network-independent. Thus the asymptotic behavior of~textbf{texttt{S-ADDOPT}} is comparable to the centralized stochastic gradient descent. Numerical experiments over both strongly convex and non-convex problems illustrate the convergence behavior and the performance comparison of the proposed algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
