1,721,190 research outputs found
OPT4SMART (Distributed Optimization Methods for Smart Cyber-Physical Networks)
No full textThe combination of embedded electronics and communication capability in almost any mobile or portable device has turned this century into the age of cyber-physical networks. Smart communicating devices with their sensing, computing and control capabilities promise to make our cities, transportation systems, factories and living environments more intelligent, energy-efficient, safe and secure. This extremely complex system has raised a number of new challenges involving ICT disciplines. In particular, a novel peer-to-peer distributed computational model is appearing as a new opportunity in which a service is built-up cooperatively by peers, rather than by a unique provider that knows and owns all data. The interdisciplinary "Optimization Community" is facing this revolution sharing a common need: to find new theories, methodologies and tools to optimize over this complex network system. With this in mind, OPT4SMART has a twofold objective. First, to provide a comprehensive theoretical framework to solve distributed optimization problems over peer-to-peer networks. Second, to develop effective numerical tools, based on this framework, to solve estimation, learning, decision and control problems in cyber-physical networks. To achieve this twofold objective, we will take a systems-theory perspective. Specific problems from these four areas will be abstracted to a common mathematical set-up, and addressed by means of interdisciplinary methodologies arising from a synergic combination of optimization, controls, and graph theories. In particular, OPT4SMART will face the challenge of solving optimization problems under severe communication limitations, very-large-scale problem and data size, and real-time computational constraints. The expected result will be a combination of strong theoretical methods and effective numerical toolboxes available to people in Engineering, Computer Science, Mathematics and other areas, who are facing optimization in cyber-physical networks
A Bayesian Framework for Distributed Estimation of Arrival Rates in Asynchronous Networks
Full text linkIn this paper, we consider a network of agents monitoring a spatially distributed arrival process. Each node measures the number of arrivals seen at its monitoring point in a given time interval with the objective of estimating the unknown local arrival rate. We propose an asynchronous distributed approach based on a Bayesian model with unknown hyperparameter, where each node computes the minimum mean-square error (MMSE) estimator of its local arrival rate in a distributed way. As a result, the estimation at each node “optimally” fuses the information from the whole network through a distributed optimization algorithm. Moreover, we propose an ad-hoc distributed estimator, based on a consensus algorithm for time-varying and directed graphs, which exhibits reduced complexity and exponential convergence. We analyze the performance of the proposed distributed estimators, showing that they i) are reliable even in presence of limited local data and ii) improve the estimation accuracy compared to the purely decentralized setup. Finally, we provide a statistical characterization of the proposed estimators. In particular, for the ad-hoc estimator, we show that as the number of nodes goes to infinity its mean square error converges to the optimal one. Numerical Monte Carlo simulations confirm the theoretical characterization and highlight the appealing performances of the estimators
An optimal control approach to the design of periodic orbits for mechanical systems with impacts
Full text linkIn this paper we study the problem of designing periodic orbits for a special class of hybrid systems, namely mechanical systems with underactuated continuous dynamics and impulse events. We approach the problem by means of optimal control. Specifically, we design an optimal control based strategy that combines trajectory optimization, dynamics embedding, optimal control relaxation and root finding techniques. The proposed strategy allows us to design, in a numerically stable manner, trajectories that optimize a desired cost and satisfy boundary state constraints consistent with a periodic orbit. To show the effectiveness of the proposed strategy, we perform numerical computations on a compass biped model with torso
A randomized primal distributed algorithm for partitioned and big-data non-convex optimization
Full text linkIn this paper we consider a distributed opti- mization scenario in which the aggregate objective function to minimize is partitioned, big-data and possibly non-convex. Specifically, we focus on a set-up in which the dimension of the decision variable depends on the network size as well as the number of local functions, but each local function handled by a node depends only on a (small) portion of the entire optimiza- tion variable. This problem set-up has been shown to appear in many interesting network application scenarios. As main paper contribution, we develop a simple, primal distributed algorithm to solve the optimization problem, based on a randomized descent approach, which works under asynchronous gossip communication. We prove that the proposed asynchronous algorithm is a proper, ad-hoc version of a coordinate descent method and thus converges to a stationary point. To show the effectiveness of the proposed algorithm, we also present numerical simulations on a non-convex quadratic program, which confirm the theoretical results
Randomized Block Proximal Methods for Distributed Stochastic Big-Data Optimization
Full text linkIn this article, we introduce a class of novel distributed algorithms for solving stochastic big-data convex optimization problems over directed graphs. In the addressed set-up, the dimension of the decision variable can be extremely high and the objective function can be nonsmooth. The general algorithm consists of two main steps: a consensus step and an update on a single block of the optimization variable, which is then broadcast to neighbors. Three special instances of the proposed method, involving particular problem structures, are then presented. In the general case, the convergence of a dynamic consensus algorithm over random row stochastic matrices is shown. Then, the convergence of the proposed algorithm to the optimal cost is proven in expected value. Exact convergence is achieved when using diminishing (local) stepsizes, whereas approximate convergence is attained when constant stepsizes are employed. The convergence rate is shown to be sublinear and an explicit rate is provided in the case of constant stepsizes. Finally, the algorithm is tested on a distributed classification problem, first on synthetic data and, then, on a real, high-dimensional, text dataset
A Hierarchical Bayes Approach for Distributed Binary Classification in Cyber-Physical and Social Networks
No full textIn this paper we consider a network of agents that can evaluate each other according to an interaction graph modeling some physical interconnection or social relationship. Each agent provides a score for its (out-)neighboring agents in the interaction graph. The goal is to design a distributed protocol, run by the agents themselves, to group the network nodes into two classes (binary classification) on the basis of the evaluation outcomes. We propose a hierarchical Bayesian framework in which the agents' belonging to one of the two classes is assumed to be a probabilistic event with unknown parameter. Exploiting such a hierarchical framework, we are able to design a distributed classification scheme in which nodes cooperatively classify their own state. We characterize the solution for a fault-diagnosis context in cyber-physical systems, and for an opinion-classification/community-discovery setup in social networks
Randomized dual proximal gradient for large-scale distributed optimization
Full text linkIn this paper we consider distributed optimization problems in which the cost
function is separable (i.e., a sum of possibly non-smooth functions all
sharing a common variable) and can be split into a strongly convex term and a
convex one. The second term is typically used to encode constraints or to
regularize the solution. We propose an asynchronous, distributed optimization
algorithm over an undirected topology, based on a proximal gradient update on
the dual problem. We show that by means of a proper choice of primal
variables, the dual problem is separable and the dual variables can be stacked
into separate blocks. This allows us to show that a distributed
gossip update can be obtained by means of a randomized block-coordinate
proximal gradient on the dual function
Minimum-Time Trajectory Generation for Quadrotors in Constrained Environments
Full text linkIn this paper, we present a novel strategy to compute minimum-time trajectories for quadrotors in constrained environments. In particular, we consider the motion in a given flying region with obstacles and take into account the physical limitations of the vehicle. Instead of approaching the optimization problem in its standard time-parameterized formulation, the proposed strategy is based on an appealing reformulation. Transverse coordinates, expressing the distance from a frame path, are used to parameterize the vehicle position and a spatial parameter is used as independent variable. This reformulation allows us to: (1) obtain a fixed horizon problem and (2) easily formulate (fairly complex) position constraints. The effectiveness of the proposed strategy is proven by numerical computations on two different illustrative scenarios. Moreover, the optimal trajectory generated in the second scenario is experimentally executed with a real nanoquadrotor in order to show its feasibility
- …
