Search

This paper develops a data-driven stabilization method for continuous-time linear time-invariant systems with theoretical guarantees and no need for signal derivatives. The framework, based on linear matrix inequalities (LMIs), is illustrated in the state-feedback and single-input single-output output-feedback scenarios. Similar to discrete-time approaches, we rely solely on input and state/output measurements. To avoid differentiation, we employ low-pass filters of the available signals that, rather than approximating the derivatives, reconstruct a non-minimal realization of the plant. With access to the filter states and their derivatives, we can solve LMIs derived from sample batches of the available signals to compute a dynamic controller that stabilizes the plant. The effectiveness of the framework is showcased through numerical examples.

We design a distributed feedback optimization strategy, embedded into a modular ROS 2 control architecture, which allows a team of heterogeneous robots to cooperatively monitor and encircle a target while patrolling points of interest. Relying on the aggregative feedback optimization framework, we handle multi-robot dynamics while minimizing a global performance index depending on both microscopic (e.g., the location of single robots) and macroscopic variables (e.g., the spatial distribution of the team). The proposed distributed policy allows the robots to cooperatively address the global problem by employing only local measurements and neighboring data exchanges. These exchanges are performed through an asynchronous communication protocol ruled by locally-verifiable triggering conditions. We formally prove that our strategy steers the robots to a set of configurations representing stationary points of the considered optimization problem. The effectiveness and scalability of the overall strategy are tested via Monte Carlo campaigns of realistic Webots ROS 2 virtual experiments. Finally, the applicability of our solution is shown with real experiments on ground and aerial robots.

This paper introduces a novel distributed optimization technique for networked systems, which removes the dependency on specific parameter choices, notably the learning rate. Traditional parameter selection strategies in distributed optimization often lead to conservative performance, characterized by slow convergence or even divergence if parameters are not properly chosen. In this work, we propose a systems theory tool based on the port-Hamiltonian formalism to design algorithms for consensus optimization programs. Moreover, we propose the Mixed Implicit Discretization (MID), which transforms the continuous-time port-Hamiltonian system into a discrete time one, maintaining the same convergence properties regardless of the step size parameter. The consensus optimization algorithm enhances the convergence speed without worrying about the relationship between parameters and stability. Numerical experiments demonstrate the method's superior performance in convergence speed, outperforming other methods, especially in scenarios where conventional methods fail due to step size parameter limitations.

In this paper, we investigate a data-driven framework to solve Linear Quadratic Regulator (LQR) problems when the dynamics is unknown, with the additional challenge of providing stability certificates for the overall learning and control scheme. Specifically, in the proposed on-policy learning framework, the control input is applied to the actual (unknown) linear system while iteratively optimized. We propose a learning and control procedure, termed RELEARN LQR, that combines a recursive least squares method with a direct policy search based on the gradient method. The resulting scheme is analyzed by modeling it as a feedback-interconnected nonlinear dynamical system. A Lyapunov-based approach, exploiting averaging and singular perturbations theory for nonlinear systems, allows us to provide formal stability guarantees for the whole interconnected scheme. The effectiveness of the proposed strategy is corroborated by numerical simulations, where RELEARN LQR is deployed on an aircraft control problem, with both static and drifting parameters.

This article introduces a novel framework for data-driven linear quadratic regulator (LQR) design. First, we introduce a reinforcement learning paradigm for on-policy data-driven LQR, where exploration and exploitation are simultaneously performed while guaranteeing robust stability of the whole closed-loop system encompassing the plant and the control/learning dynamics. Then, we propose Model Reference Adaptive Reinforcement Learning (MR-ARL), a control architecture integrating tools from reinforcement learning and model reference adaptive control. The approach stands on a variable reference model containing the currently identified value function. Then, an adaptive stabilizer is used to ensure convergence of the applied policy to the optimal one, convergence of the plant to the optimal reference model, and overall robust closed-loop stability. The proposed framework provides theoretical robustness certificates against real-world perturbations such as measurement noise, plant nonlinearities, or slowly varying parameters. The effectiveness of the proposed architecture is validated via realistic numerical simulations.

This paper introduces a systematic methodological framework to design and analyze distributed algorithms for optimization and games over networks. Starting from a centralized method, we identify an aggregation function involving all the decision variables (e.g., a global cost gradient or constraint) and introduce a distributed consensus-oriented scheme to asymptotically approximate the unavailable information at each agent. Then, we delineate the proper methodology for intertwining the identified building blocks, i.e., the optimization-oriented method and the consensus-oriented one. The key intuition is to interpret the obtained interconnection as a singularly perturbed system. We rely on this interpretation to provide sufficient conditions for the building blocks to be successfully connected into a distributed scheme exhibiting the convergence guarantees of the centralized algorithm. Finally, we show the potential of our approach by developing a new distributed scheme for constraint-coupled problems with a linear convergence rate.

In this paper, we propose a novel distributed algorithm for consensus optimization over networks and a robust extension tailored to deal with asynchronous agents and packet losses. Indeed, to robustly achieve dynamic consensus on the solution estimates and the global descent direction, we embed in our algorithms a distributed implementation of the Alternating Direction Method of Multipliers (ADMM). Such a mechanism is suitably interlaced with a local proportional action steering each agent estimate to the solution of the original consensus optimization problem. First, in the case of ideal networks, by using tools from system theory, we prove the linear convergence of the scheme with strongly convex costs. Then, by exploiting the averaging theory, we extend such a first result to prove that the robust extension of our method preserves linear convergence in the case of asynchronous agents and packet losses. Further, by using the notion of Input-to-State Stability, we also guarantee the robustness of the schemes with respect to additional, generic errors affecting the agents' updates. Finally, some numerical simulations confirm our theoretical findings and compare our algorithms with other distributed schemes in terms of speed and robustness.

Several interesting problems in multi-robot systems can be cast in the framework of distributed optimization. Examples include multi-robot task allocation, vehicle routing, target protection and surveillance. While the theoretical analysis of distributed optimization algorithms has received significant attention, its application to cooperative robotics has not been investigated in detail. In this paper, we show how notable scenarios in cooperative robotics can be addressed by suitable distributed optimization setups. Specifically, after a brief introduction on the widely investigated consensus optimization (most suited for data analytics) and on the partition-based setup (matching the graph structure in the optimization), we focus on two distributed settings modeling several scenarios in cooperative robotics, i.e., the so-called constraint-coupled and aggregative optimization frameworks. For each one, we consider use-case applications, and we discuss tailored distributed algorithms with their convergence properties. Then, we revise state-of-the-art toolboxes allowing for the implementation of distributed schemes on real networks of robots without central coordinators. For each use case, we discuss their implementation in these toolboxes and provide simulations and real experiments on networks of heterogeneous robots.

In this paper, we propose a distributed algorithm to control a team of cooperating robots aiming to protect a target from a set of intruders. Specifically, we model the strategy of the defending team by means of an online optimization problem inspired by the emerging distributed aggregative framework. In particular, each defending robot determines its own position depending on (i) the relative position between an associated intruder and the target, (ii) its contribution to the barycenter of the team, and (iii) collisions to avoid with its teammates. We highlight that each agent is only aware of local, noisy measurements about the location of the associated intruder and the target. Thus, in each robot, our algorithm needs to (i) locally reconstruct global unavailable quantities and (ii) predict its current objective functions starting from the local measurements. The effectiveness of the proposed methodology is corroborated by simulations and experiments on a team of cooperating quadrotors.

Distributed aggregative optimization is a recently emerged framework in which the agents of a network want to minimize the sum of local objective functions, each one depending on the agent decision variable (e.g., the local position of a team of robots) and an aggregation of all the agents' variables (e.g., the team barycentre). In this paper, we address a distributed feedback optimization framework in which agents implement a local (distributed) policy to reach a steady-state minimizing an aggregative cost function. We propose Aggregative Tracking Feedback, i.e., a novel distributed feedback optimization law in which each agent combines a closed-loop gradient flow with a consensus-based dynamic compensator reconstructing the missing global information. By using tools from system theory, we prove that Aggregative Tracking Feedback steers the network to a stationary point of an aggregative optimization problem with (possibly) nonconvex objective function. The effectiveness of the proposed method is validated through numerical simulations on a multi-robot surveillance scenario.

This paper introduces CrazyChoir, a modular Python framework based on the Robot Operating System (ROS) 2. The toolbox provides a comprehensive set of functionalities to simulate and run experiments on teams of cooperating Crazyflie nano-quadrotors. Specifically, it allows users to perform realistic simulations over robotic simulators as, e.g., Webots and includes bindings of the firmware control and planning functions. The toolbox also provides libraries to perform radio communication with Crazyflie directly inside ROS 2 scripts. The package can be thus used to design, implement and test planning strategies and control schemes for a Crazyflie nano-quadrotor. Moreover, the modular structure of CrazyChoir allows users to easily implement online distributed optimization and control schemes over multiple quadrotors. The CrazyChoir package is validated via simulations and experiments on a swarm of Crazyflies for formation control, pickup-and-delivery vehicle routing and trajectory tracking tasks. CrazyChoir is available at https://github.com/OPT4SMART/crazychoir.

We propose fully-distributed algorithms for Nash equilibrium seeking in aggregative games over networks. We first consider the case where local constraints are present and we design an algorithm combining, for each agent, (i) the projected pseudo-gradient descent and (ii) a tracking mechanism to locally reconstruct the aggregative variable. To handle coupling constraints arising in generalized settings, we propose another distributed algorithm based on (i) a recently emerged augmented primal-dual scheme and (ii) two tracking mechanisms to reconstruct, for each agent, both the aggregative variable and the coupling constraint satisfaction. Leveraging tools from singular perturbations analysis, we prove linear convergence to the Nash equilibrium for both schemes. Finally, we run extensive numerical simulations to confirm the effectiveness of our methods and compare them with state-of-the-art distributed equilibrium-seeking algorithms.

The paper deals with a well-known extremum seeking scheme by proving uniformity properties with respect to the amplitudes of the dither signal and of the cost function. Those properties are then used to show that the scheme guarantees the global minimiser to be semi-global practically stable despite the presence of local minima. Under the assumption of a globally Lipschitz cost function, it is shown that the scheme, improved through a high-pass filter, makes the global minimiser practically stable with a global domain of attraction., Comment: arXiv admin note: substantial text overlap with arXiv:2204.00580

The paper deals with a well-known extremum seeking scheme by proving uniformity properties with respect to the amplitudes of the dither signal and of the cost function. Those properties are then used to show that the scheme guarantees the global minimiser to be semi-global practically stable despite the presence of local saddle points. To achieve these results, we analyse the average system associated with the extremum seeking scheme via arguments based on the Fourier series.

This paper proposes Asynchronous Triggered Gradient Tracking, i.e., a distributed optimization algorithm to solve consensus optimization over networks with asynchronous communication. As a building block, we devise the continuous-time counterpart of the recently proposed (discrete-time) distributed gradient tracking called Continuous Gradient Tracking. By using a Lyapunov approach, we prove exponential stability of the equilibrium corresponding to agents' estimates being consensual to the optimal solution, with arbitrary initialization of the local estimates. Then, we propose two triggered versions of the algorithm. In the first one, the agents continuously integrate their local dynamics and exchange with neighbors their current local variables in a synchronous way. In Asynchronous Triggered Gradient Tracking, we propose a totally asynchronous scheme in which each agent sends to neighbors its current local variables based on a triggering condition that depends on a locally verifiable condition. The triggering protocol preserves the linear convergence of the algorithm and avoids the Zeno behavior, i.e., an infinite number of triggering events over a finite interval of time is excluded. By using the stability analysis of Continuous Gradient Tracking as a preparatory result, we show exponential stability of the equilibrium point holds for both triggered algorithms and any estimate initialization. Finally, the simulations validate the effectiveness of the proposed methods on a data analytics problem, showing also improved performance in terms of inter-agent communication.

In this paper, we deal with a network of agents that want to cooperatively minimize the sum of local cost functions depending on a common decision variable. We consider the challenging scenario in which objective functions are unknown and agents have only access to local measurements of their local functions. We propose a novel distributed algorithm that combines a recent gradient tracking policy with an extremum seeking technique to estimate the global descent direction. The joint use of these two techniques results in a distributed optimization scheme that provides arbitrarily accurate solution estimates through the combination of Lyapunov and averaging analysis approaches with consensus theory. We perform numerical simulations in a personalized optimization framework to corroborate the theoretical results.

In this paper we We propose GoPRONTO, a first-order, feedback-based approach to solve nonlinear discrete-time optimal control problems. This method is a generalized first-order framework based on incorporating the original dynamics into a closed-loop system. By exploiting this feedback-based shooting, we are able to reinterpret the optimal control problem as the minimization of a cost function, depending on a state-input curve, whose gradient can be computed by resorting to a suitable costate equation. This convenient reformulation gives room for a collection of accelerated numerical optimal control schemes. To corroborate the theoretical results, numerical simulations on the optimal control of a train of inverted pendulum-on-cart systems are shown., Comment: 27 pages, 8 figures

This paper focuses on an online version of the emerging distributed constrained aggregative optimization framework, which is particularly suited for applications arising in cooperative robotics. Agents in a network want to minimize the sum of local cost functions, each one depending both on a local optimization variable, subject to a local constraint, and on an aggregated version of all the variables (e.g., the mean). We focus on a challenging online scenario in which the cost, the aggregation functions and the constraints can all change over time, thus enlarging the class of captured applications. Inspired by an existing scheme, we propose a distributed algorithm with constant step size, named Projected Aggregative Tracking, to solve the online optimization problem. We prove that the dynamic regret is bounded by a constant term and a term related to time variations. Moreover, in the static case (i.e., with constant cost and constraints), the solution estimates are proved to converge with a linear rate to the optimal solution. Finally, numerical examples show the efficacy of the proposed approach on a robotic surveillance scenario.

In this paper, we present a distributed algorithm for solving convex, constraint-coupled, optimization problems over peer-to-peer networks. We consider a network of processors that aim to cooperatively minimize the sum of local cost functions, subject to individual constraints and to global coupling constraints. The major assumption of this work is that the cost functions are unknown and must be learned online. We propose a fully distributed algorithm, based on a primal decomposition approach, that uses iteratively refined data-driven estimations of the cost functions over the iterations. The algorithm is scalable and maintains private information of agents. We prove that, asymptotically, the distributed algorithm provides the optimal solution of the problem even though the true cost functions are never used within the algorithm. The analysis requires an in-depth exploration of the primal decomposition approach and shows that the distributed algorithm can be thought of as an epsilon-subgradient method applied to a suitable reformulation of the original problem. Finally, numerical computations cor- roborate the theoretical findings and show the efficacy of the proposed approach.

This paper deals with distributed control of microgrids composed of storages, generators, renewable energy sources, critical and controllable loads. We consider a stochastic formulation of the optimal control problem associated to the microgrid that appropriately takes into account the unpredictable nature of the power generated by renewables. The resulting problem is a Mixed-Integer Linear Program and is NP-hard and nonconvex. Moreover, the peculiarity of the considered framework is that no central unit can be used to perform the optimization, but rather the units must cooperate with each other by means of neighboring communication. To solve the problem, we resort to a distributed methodology based on a primal decomposition approach. The resulting algorithm is able to compute high-quality feasible solutions to a two-stage stochastic optimization problem, for which we also provide a theoretical upper bound on the constraint violation. Finally, a Monte Carlo numerical computation on a scenario with a large number of devices shows the efficacy of the proposed distributed control approach. The numerical experiments are performed on realistic scenarios obtained from Generative Adversarial Networks trained an open-source historical dataset of the EU.

In this paper, we consider a large-scale instance of the classical Pickup-and-Delivery Vehicle Routing Problem (PDVRP) that must be solved by a network of mobile cooperating robots. Robots must self-coordinate and self-allocate a set of pickup/delivery tasks while minimizing a given cost figure. This results in a large, challenging Mixed-Integer Linear Problem that must be cooperatively solved % without a central coordinator. We propose a distributed algorithm based on a primal decomposition approach that provides a feasible solution to the problem in finite time. An interesting feature of the proposed scheme is that each robot computes only its own block of solution, thereby preserving privacy of sensible information. The algorithm also exhibits attractive scalability properties that guarantee solvability of the problem even in large networks. To the best of our knowledge, this is the first attempt to provide a scalable distributed solution to the problem. The algorithm is first tested through Gazebo simulations on a ROS~2 platform, highlighting the effectiveness of the proposed solution. Finally, experiments on a real testbed with a team of ground and aerial robots are provided.

The paper addresses large-scale, convex optimization problems that need to be solved in a distributed way by agents communicating according to a random time-varying graph. Specifically, the goal of the network is to minimize the sum of local costs, while satisfying local and coupling constraints. Agents communicate according to a time-varying model in which edges of an underlying connected graph are active at each iteration with certain non-uniform probabilities. By relying on a primal decomposition scheme applied to an equivalent problem reformulation, we propose a novel distributed algorithm in which agents negotiate a local allocation of the total resource only with neighbors with active communication links. The algorithm is studied as a subgradient method with block-wise updates, in which blocks correspond to the graph edges that are active at each iteration. Thanks to this analysis approach, we show almost sure convergence to the optimal cost of the original problem and almost sure asymptotic primal recovery without resorting to averaging mechanisms typically employed in dual decomposition schemes. Explicit sublinear convergence rates are provided under the assumption of diminishing and constant step-sizes. Finally, an extensive numerical study on a plug-in electric vehicle charging problem corroborates the theoretical results.

This paper deals with a distributed Mixed-Integer Linear Programming (MILP) set-up arising in several control applications. Agents of a network aim to minimize the sum of local linear cost functions subject to both individual constraints and a linear coupling constraint involving all the decision variables. A key, challenging feature of the considered set-up is that some components of the decision variables must assume integer values. The addressed MILPs are NP-hard, nonconvex and large-scale. Moreover, several additional challenges arise in a distributed framework due to the coupling constraint, so that feasible solutions with guaranteed suboptimality bounds are of interest. We propose a fully distributed algorithm based on a primal decomposition approach and an appropriate tightening of the coupling constraint. The algorithm is guaranteed to provide feasible solutions in finite time. Moreover, asymptotic and finite-time suboptimality bounds are established for the computed solution. Montecarlo simulations highlight the extremely low suboptimality bounds achieved by the algorithm.

In this paper, we introduce ChoiRbot, a toolbox for distributed cooperative robotics based on the novel Robot Operating System (ROS) 2. ChoiRbot provides a fully-functional toolset to execute complex distributed multi-robot tasks, either in simulation or experimentally, with a particular focus on networks of heterogeneous robots without a central coordinator. Thanks to its modular structure, ChoiRbot allows for a highly straight implementation of optimization-based distributed control schemes, such as distributed optimal control, model predictive control, task assignment, in which local computation and communication with neighboring robots are alternated. To this end, the toolbox provides functionalities for the solution of distributed optimization problems. The package can be also used to implement distributed feedback laws that do not need optimization features but do require the exchange of information among robots. The potential of the toolbox is illustrated with simulations and experiments on distributed robotics scenarios with mobile ground robots. The ChoiRbot toolbox is available at https://github.com/OPT4SMART/choirbot.

This paper deals with a network of computing agents aiming to solve an online optimization problem in a distributed fashion, i.e., by means of local computation and communication, without any central coordinator. We propose the gradient tracking with adaptive momentum estimation (GTAdam) distributed algorithm, which combines a gradient tracking mechanism with first and second order momentum estimates of the gradient. The algorithm is analyzed in the online setting for strongly convex cost functions with Lipschitz continuous gradients. We provide an upper bound for the dynamic regret given by a term related to the initial conditions and another term related to the temporal variations of the objective functions. Moreover, a linear convergence rate is guaranteed in the static setup. The algorithm is tested on a time-varying classification problem, on a (moving) target localization problem, and in a stochastic optimization setup from image classification. In these numerical experiments from multi-agent learning, GTAdam outperforms state-of-the-art distributed optimization methods.

We present a distributed optimization algorithm for solving online personalized optimization problems over a network of computing and communicating nodes, each of which linked to a specific user. The local objective functions are assumed to have a composite structure and to consist of a known time-varying (engineering) part and an unknown (user-specific) part. Regarding the unknown part, it is assumed to have a known parametric (e.g., quadratic) structure a priori, whose parameters are to be learned along with the evolution of the algorithm. The algorithm is composed of two intertwined components: (i) a dynamic gradient tracking scheme for finding local solution estimates and (ii) a recursive least squares scheme for estimating the unknown parameters via user's noisy feedback on the local solution estimates. The algorithm is shown to exhibit a bounded regret under suitable assumptions. Finally, a numerical example corroborates the theoretical analysis.

In this paper, we consider a network of agents that has to self-assign a set of tasks while respecting resource constraints. One possible formulation is the Generalized Assignment Problem, where the goal is to find a maximum payoff while satisfying capability constraints. We propose a purely distributed branch-and-price algorithm to solve this problem in a cooperative fashion. Inspired by classical (centralized) branch-and-price schemes, in the proposed algorithm each agent locally solves small linear programs, generates columns by solving simple knapsack problems, and communicates to its neighbors a fixed number of basic columns. We prove finite-time convergence of the algorithm to an optimal solution of the problem. Then, we apply the proposed scheme to a generalized assignment scenario in which a team of robots has to serve a set of tasks. We implement the proposed algorithm in a ROS testbed and provide experiments for a team of heterogeneous robots solving the assignment problem.

The recently developed Distributed Block Proximal Method, for solving stochastic big-data convex optimization problems, is studied in this paper under the assumption of constant stepsizes and strongly convex (possibly non-smooth) local objective functions. This class of problems arises in many learning and classification problems in which, for example, strongly-convex regularizing functions are included in the objective function, the decision variable is extremely high dimensional, and large datasets are employed. The algorithm produces local estimates by means of block-wise updates and communication among the agents. The expected distance from the (global) optimum, in terms of cost value, is shown to decay linearly to a constant value which is proportional to the selected local stepsizes. A numerical example involving a classification problem corroborates the theoretical results., Comment: arXiv admin note: text overlap with arXiv:1905.04214

In this paper we deal with distributed optimal control for nonlinear dynamical systems over graph, that is large-scale systems in which the dynamics of each subsystem depends on neighboring states only. Starting from a previous work in which we designed a partially distributed solution based on a cloud, here we propose a fully-distributed algorithm. The key novelty of the approach in this paper is the design of a sparse controller to stabilize trajectories of the nonlinear system at each iteration of the distributed algorithm. The proposed controller is based on the design of a stabilizing controller for polytopic Linear Parameter Varying (LPV) systems satisfying nonconvex sparsity constraints. Thanks to a suitable choice of vertex matrices and to an iterative procedure using convex approximations of the nonconvex matrix problem, we are able to design a controller in which each agent can locally compute the feedback gains at each iteration by simply combining coefficients of some vertex matrices that can be pre-computed offline. We show the effectiveness of the strategy on simulations performed on a multi-agent formation control problem.

In this paper we consider a recently developed distributed optimization algorithm based on gradient tracking. We propose a system theory framework to analyze its structural properties on a preliminary, quadratic optimization set-up. Specifically, we focus on a scenario in which agents in a static network want to cooperatively minimize the sum of quadratic cost functions. We show that the gradient tracking distributed algorithm for the investigated program can be viewed as a sparse closed-loop linear system in which the dynamic state-feedback controller includes consensus matrices and optimization (stepsize) parameters. The closed-loop system turns out to be not completely reachable and asymptotic stability can be shown restricted to a proper invariant set. Convergence to the global minimum, in turn, can be obtained only by means of a proper initialization. The proposed system interpretation of the distributed algorithm provides also additional insights on other structural properties and possible design choices that are discussed in the last part of the paper as a starting point for future developments.

In this paper we introduce DISROPT, a Python package for distributed optimization over networks. We focus on cooperative set-ups in which an optimization problem must be solved by peer-to-peer processors (without central coordinators) that have access only to partial knowledge of the entire problem. To reflect this, agents in DISROPT are modeled as entities that are initialized with their local knowledge of the problem. Agents then run local routines and communicate with each other to solve the global optimization problem. A simple syntax has been designed to allow for an easy modeling of the problems. The package comes with many distributed optimization algorithms that are already embedded. Moreover, the package provides full-fledged functionalities for communication and local computation, which can be used to design and implement new algorithms. DISROPT is available at github.com/disropt/disropt under the GPL license, with a complete documentation and many examples.

We consider a multi-agent setting with agents exchanging information over a possibly time-varying network, aiming at minimising a separable objective function subject to constraints. To achieve this objective we propose a novel subgradient averaging algorithm that allows for non-differentiable objective functions and different constraint sets per agent. Allowing different constraints per agent simultaneously with a time-varying communication network constitutes a distinctive feature of our approach, extending existing results on distributed subgradient methods. To highlight the necessity of dealing with a different constraint set within a distributed optimisation context, we analyse a problem instance where an existing algorithm does not exhibit a convergent behaviour if adapted to account for different constraint sets. For our proposed iterative scheme we show asymptotic convergence of the iterates to a minimum of the underlying optimisation problem for step sizes of the form $ \frac{\eta}{k+1} $, $ \eta > 0 $. We also analyse this scheme under a step size choice of $ \frac{\eta}{\sqrt{k+1}} $, $ \eta > 0 $, and establish a convergence rate of $ \mathcal{O}(\frac{\ln k}{\sqrt{k}}) $ in objective value. To demonstrate the efficacy of the proposed method, we investigate a robust regression problem and an $ \ell_2 $ regression problem with regularisation.

We consider constraint-coupled optimization problems in which agents of a network aim to cooperatively minimize the sum of local objective functions subject to individual constraints and a common linear coupling constraint. We propose a novel optimization algorithm that embeds a dynamic average consensus protocol in the parallel Alternating Direction Method of Multipliers (ADMM) to design a fully distributed scheme for the considered set-up. The dynamic average mechanism allows agents to track the time-varying coupling constraint violation (at the current solution estimates). The tracked version of the constraint violation is then used to update local dual variables in a consensus-based scheme mimicking a parallel ADMM step. Under convexity, we prove that all limit points of the agents' primal solution estimates form an optimal solution of the constraint-coupled (primal) problem. The result is proved by means of a Lyapunov-based analysis simultaneously showing consensus of the dual estimates to a dual optimal solution, convergence of the tracking scheme and asymptotic optimality of primal iterates. A numerical study on optimal charging schedule of plug-in electric vehicles corroborates the theoretical results., Comment: 14 pages, 2 figures, submitted to Automatica

In this paper, we consider a network of processors aiming at cooperatively solving mixed-integer convex programs subject to uncertainty. Each node only knows a common cost function and its local uncertain constraint set. We propose a randomized, distributed algorithm working under asynchronous, unreliable and directed communication. The algorithm is based on a local computation and communication paradigm. At each communication round, nodes perform two updates: (i) a verification in which they check---in a randomized fashion---the robust feasibility of a candidate optimal point, and (ii) an optimization step in which they exchange their candidate basis (the minimal set of constraints defining a solution) with neighbors and locally solve an optimization problem. As main result, we show that processors can stop the algorithm after a finite number of communication rounds (either because verification has been successful for a sufficient number of rounds or because a given threshold has been reached), so that candidate optimal solutions are consensual. The common solution is proven to be---with high confidence---feasible and hence optimal for the entire set of uncertainty except a subset having an arbitrary small probability measure. We show the effectiveness of the proposed distributed algorithm using two examples: a random, uncertain mixed-integer linear program and a distributed localization in wireless sensor networks. The distributed algorithm is implemented on a multi-core platform in which the nodes communicate asynchronously., Comment: Submitted for publication. arXiv admin note: text overlap with arXiv:1706.00488

The presence of embedded electronics and communication capabilities as well as sensing and control in smart devices has given rise to the novel concept of cyber-physical networks, in which agents aim at cooperatively solving complex tasks by local computation and communication. Numerous estimation, learning, decision and control tasks in smart networks involve the solution of large-scale, structured optimization problems in which network agents have only a partial knowledge of the whole problem. Distributed optimization aims at designing local computation and communication rules for the network processors allowing them to cooperatively solve the global optimization problem without relying on any central unit. The purpose of this survey is to provide an introduction to distributed optimization methodologies. Principal approaches, namely (primal) consensus-based, duality-based and constraint exchange methods, are formalized. An analysis of the basic schemes is supplied, and state-of-the-art extensions are reviewed.

In this paper we deal with a network of computing agents with local processing and neighboring communication capabilities that aim at solving (without any central unit) a submodular optimization problem. The cost function is the sum of many local submodular functions and each agent in the network has access to one function in the sum only. In this \emph{distributed} set-up, in order to preserve their own privacy, agents communicate with neighbors but do not share their local cost functions. We propose a distributed algorithm in which agents resort to the Lov\`{a}sz extension of their local submodular functions and perform local updates and communications in terms of single blocks of the entire optimization variable. Updates are performed by means of a greedy algorithm which is run only until the selected block is computed, thus resulting in a reduced computational burden. The proposed algorithm is shown to converge in expected value to the optimal cost of the problem, and an approximate solution to the submodular problem is retrieved by a thresholding operation. As an application, we consider a distributed image segmentation problem in which each agent has access only to a portion of the entire image. While agents cannot segment the entire image on their own, they correctly complete the task by cooperating through the proposed distributed algorithm.