A Polyhedral Approximation Framework for Convex and Robust Distributed Optimization

DOI10.1109/TAC.2013.2281883zbMATH Open1360.90254arXiv1303.6092OpenAlexW2046629409WikidataQ59047401 ScholiaQ59047401MaRDI QIDQ2983262FDOQ2983262

Authors: Mathias Bürger, Frank Allgöwer, Giuseppe Notarstefano 

Publication date: 16 May 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: In this paper we consider a general problem set-up for a wide class of convex and robust distributed optimization problems in peer-to-peer networks. In this set-up convex constraint sets are distributed to the network processors who have to compute the optimizer of a linear cost function subject to the constraints. We propose a novel fully distributed algorithm, named cutting-plane consensus, to solve the problem, based on an outer polyhedral approximation of the constraint sets. Processors running the algorithm compute and exchange linear approximations of their locally feasible sets. Independently of the number of processors in the network, each processor stores only a small number of linear constraints, making the algorithm scalable to large networks. The cutting-plane consensus algorithm is presented and analyzed for the general framework. Specifically, we prove that all processors running the algorithm agree on an optimizer of the global problem, and that the algorithm is tolerant to node and link failures as long as network connectivity is preserved. Then, the cutting plane consensus algorithm is specified to three different classes of distributed optimization problems, namely (i) inequality constrained problems, (ii) robust optimization problems, and (iii) almost separable optimization problems with separable objective functions and coupling constraints. For each one of these problem classes we solve a concrete problem that can be expressed in that framework and present computational results. That is, we show how to solve: position estimation in wireless sensor networks, a distributed robust linear program and, a distributed microgrid control problem.

Full work available at URL: https://arxiv.org/abs/1303.6092

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Communication networks in operations research (90B18)

Cited In (11)

• Primal recovery from consensus-based dual decomposition for distributed convex optimization
• Distributed constraint-coupled optimization via primal decomposition over random time-varying graphs
• Cooperative fixed-time/finite-time distributed robust optimization of multi-agent systems
• Consensus-based Dantzig-Wolfe decomposition
• A Unified Framework for Continuous-Time Unconstrained Distributed Optimization
• Multi-agent control: a graph-theoretic perspective
• On the stability and convergence of a class of consensus systems with a nonlinear input
• Noise-to-state exponentially stable distributed convex optimization on weight-balanced digraphs
• Approximate cutting plane approaches for exact solutions to robust optimization problems
• Networked Systems Theory: Distributed Algorithms for Optimal Cooperation of Dynamical Systems
• A distributed economic MPC framework for cooperative control under conflicting objectives

This page was built for publication: A Polyhedral Approximation Framework for Convex and Robust Distributed Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2983262)