Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method

By Tsung-Hui Chang, Angelia Nedić, Anna Scaglione. 2013

404 citations recorded by the source corpus.

Various distributed optimization methods have been developed for solving problems which have simple local constraint sets and whose objective function is the sum of local cost functions of distributed agents in a network. Motivated by emerging applications in smart grid and distributed sparse regression, this paper studies distributed optimization methods for solving general problems which have a coupled global cost function and have inequality constraints. We consider a network scenario where each agent has no global knowledge and can access only its local mapping and constraint functions. To solve this problem in a distributed manner, we propose a consensus-based distributed primal-dual perturbation (PDP) algorithm. In the algorithm, agents employ the average consensus technique to estimate the global cost and constraint functions via exchanging messages with neighbors, and meanwhile use a local primal-dual perturbed subgradient method to approach a global optimum. The proposed PDP method not only can handle smooth inequality constraints but also non-smooth constraints such as some sparsity promoting constraints arising in sparse optimization. We prove that the proposed PDP algorithm converges to an optimal primal-dual solution of the original problem, under standard problem and network assumptions. Numerical results illustrating the performance of the proposed algorithm for a distributed demand response control problem in smart grid are also presented.

Subfields: Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “The problem in (2)-(3) can be solved using the primal-dual based algorithms as in (Chang et al., 2014b; Touri and Nedic, 2009; Nedi´c and Ozdaglar, 2009), saddle point algorithms proposed in (Koppel et al., 2017; Bedi et al., 2019), and ADMM based techniques such as (Glowinski and Marroco, 1975;…”
D-FW: Communication efficient distributed algorithms for high-dimensional sparse optimization (2016, neutral): “In a distributed setting where fs(·) is kept privately, recent advances have demonstrated that the convergence to θ? can be established using an algorithm with only local communication steps that are constrained by the topology of the communication network [8–11].”
A survey of distributed optimization (2019, methodology): “To meet this challenge, a few distributed algorithms have been developed, among which discrete-time algorithms are given in Chang, Nedi ´c, and Scaglione (2014) ; Chatzipanagiotis, Dentcheva, and Zavlanos (2015) ; Chatzipanagiotis and Zavlanos (2016) ; Falsone, Margellos, Garatti, and Prandini…”
Coordinate Dual Averaging for Decentralized Online Optimization With Nonseparable Global Objectives (2015, background): “INTRODUCTION D ECENTRALIZED optimization has recently been receiving significant attention due to the emergence of large-scale distributed algorithms in machine learning, signal processing, and control applications for wireless communication networks, power networks, and sensor networks; see, for ex”
Decentralized online optimization with global objectives and local communication (2015, methodology): “We also implement the proposed algorithms on a sensor network to complement our theoretical analysis.”
Supervised Learning Under Distributed Features (2018, methodology): “Other useful approaches to solving problems of the form (3) are the Alternating Direction Method of Multipliers (ADMM) [22], [34], [35] and primal dual-methods [18], [25], [36], [37].”