A Polyhedral Approximation Framework for Convex and Robust Distributed Optimization

DOI10.1109/TAC.2013.2281883MaRDI QIDQ2983262zbMATH OpenOpenAlexWikidataFDO

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)

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

Mathematics Subject Classification ID

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

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.

Cited in

(12)

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

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)