Distributed random convex programming via constraints consensus

DOI10.1137/120885796MaRDI QIDQ5494890zbMATH OpenOpenAlexFDO

Authors Luca Carlone, Vaibhav Srivastava, Francesco Bullo, Giuseppe Calafiore

Publication date 30 July 2014

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

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

zbMATH Keywords

classificationconstraints consensusdistributed constraints removaldistributed optimizationdistributed random convex programmingestimationrandom model predictive control

Mathematics Subject Classification ID

Distributed algorithms (68W15) Randomized algorithms (68W20) Convex programming (90C25)

Abstract: This paper discusses distributed approaches for the solution of random convex programs (RCP). RCPs are convex optimization problems with a (usually large) number N of randomly extracted constraints; they arise in several applicative areas, especially in the context of decision under uncertainty, see [2],[3]. We here consider a setup in which instances of the random constraints (the scenario) are not held by a single centralized processing unit, but are distributed among different nodes of a network. Each node "sees" only a small subset of the constraints, and may communicate with neighbors. The objective is to make all nodes converge to the same solution as the centralized RCP problem. To this end, we develop two distributed algorithms that are variants of the constraints consensus algorithm [4],[5]: the active constraints consensus (ACC) algorithm, and the vertex constraints consensus (VCC) algorithm. We show that the ACC algorithm computes the overall optimal solution in finite time, and with almost surely bounded communication at each iteration. The VCC algorithm is instead tailored for the special case in which the constraint functions are convex also w.r.t. the uncertain parameters, and it computes the solution in a number of iterations bounded by the diameter of the communication graph. We further devise a variant of the VCC algorithm, namely quantized vertex constraints consensus (qVCC), to cope with the case in which communication bandwidth among processors is bounded. We discuss several applications of the proposed distributed techniques, including estimation, classification, and random model predictive control, and we present a numerical analysis of the performance of the proposed methods. As a complementary numerical result, we show that the parallel computation of the scenario solution using ACC algorithm significantly outperforms its centralized equivalent.

Recommendations

• Networked parallel algorithms for robust convex optimization via the scenario approach
• Random convex programs
• Uncertain convex programs: randomized solutions and confidence levels
• Fully Distributed Algorithms for Convex Optimization Problems
• Random block coordinate descent methods for linearly constrained optimization over networks

Cited in

(7)

• A consensus algorithm based on collective neurodynamic system for distributed optimization with linear and bound constraints
• A resilient convex combination for consensus-based distributed algorithms
• Robust Distributed Consensus Using Total Variation
• On the optimal parameter of the composite Laplacian quadratics function
• Networked parallel algorithms for robust convex optimization via the scenario approach
• Distributed Multiagent Convex Optimization Over Random Digraphs
• Distributed proximal‐gradient algorithms for nonsmooth convex optimization of second‐order multiagent systems

This page was built for publication: Distributed random convex programming via constraints consensus

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