Search

We propose decentralized primal-dual methods for cooperative multi-agent consensus optimization problems over both static and time-varying communication networks, where only local communications are allowed. The objective is to minimize the sum of agent-specific convex functions over conic constraint sets defined by agent-specific nonlinear functions; hence, the optimal consensus decision should lie in the intersection of these private sets. Under the strong convexity assumption, we provide convergence rates for sub-optimality, infeasibility, and consensus violation in terms of the number of communications required; examine the effect of underlying network topology on the convergence rates., A preliminary result of this paper was presented in arXiv:1706.07907 by Hamedani and Aybat. In this paper, we generalize our results to the setting where agent-specific constraints are defined by nonlinear functions rather than linear ones which greatly improves the modeling capability. This generalization requires a more complicated analysis which is studied in this separate arXiv submission

CAV platooning technology has received considerable attention in the past few years, driven by the next generation smart transportation systems. Unlike most of the existing platooning methods that focus on linear vehicle dynamics of CAVs, this paper considers nonlinear vehicle dynamics and develops fully distributed optimization based CAV platooning control schemes via the model predictive control (MPC) approach for a possibly heterogeneous CAV platoon. The nonlinear vehicle dynamics leads to several major difficulties in distributed algorithm development and control analysis and design. Specifically, the underlying MPC optimization problem is nonconvex and densely coupled. Further, the closed loop dynamics becomes a time-varying nonlinear system subject to external perturbations, making closed loop stability analysis rather complicated. To overcome these difficulties, we formulate the underlying MPC optimization problem as a locally coupled, albeit nonconvex, optimization problem and develop a sequential convex programming based fully distributed scheme for a general MPC horizon. Such a scheme can be effectively implemented for real-time computing using operator splitting methods. To analyze the closed loop stability, we apply various tools from global implicit function theorems, stability of linear time-varying systems, and Lyapunov theory for input-to-state stability to show that the closed loop system is locally input-to-state stable uniformly in all small coefficients pertaining to the nonlinear dynamics. Numerical tests on homogeneous and heterogeneous CAV platoons demonstrate the effectiveness of the proposed fully distributed schemes and CAV platooning control.

In this paper, we consider a community energy storage (CES) system that is shared by various electricity consumers who want to charge and discharge the CES throughout a given time span. We study the problem facing the manager of such a CES who must schedule the charging, discharging, and capacity reservations for numerous users. Moreover, we consider the case where requests to charge/discharge the CES arrive in an online fashion and the CES manager must immediately allocate charging power and energy capacity to fulfill the request or reject the request altogether. The objective of the CES manager is to maximize the total value gained by all of the users of the CES while accounting for the operational constraints of the CES. We discuss an algorithm titled \textsc{CommunityEnergyScheduling} that acts as a pricing mechanism based on online primal-dual optimization as a solution to the CES manager's problem. The online algorithm estimates the dual variables (prices) in real-time to allow for requests to be allocated or rejected immediately as they arrive. Furthermore, the proposed method promotes charging and discharging cancellations to reduce the CES's usage at popular times and is able to handle the inherent stochastic nature of the requests to charge/discharge stemming from randomness in users' net load patterns and weather uncertainties. Additionally, we are able to show that the algorithm is able to handle any adversarially chosen request sequence and will always yield total welfare within a factor of 1/a of the offline optimal welfare., 15 pages

This paper presents a computation-efficient stochastic dynamic programming algorithm for solving energy storage price arbitrage considering variable charge and discharge efficiencies. We formulate the price arbitrage problem using stochastic dynamic programming and model real-time prices as a Markov process. Then we propose an analytical solution algorithm using a piecewise linear approximation of the value-to-go function. Our solution algorithm achieves extreme computation performance and solves the proposed arbitrage problem for one operating day in less than one second on a personal computer. We demonstrate our approach using historical price data from four price zones in New York Independent System Operator, with case studies comparing the performance of different stochastic models and storage settings. Our results show that the proposed method captures 50% to 90% of arbitrage profit compared to perfect price forecasts. In particular, our method captures more than 80% of arbitrage profit in three out of the four price zones when considering batteries with more than two-hour duration and realistic degradation cost.

Gossip protocols are popular methods for average consensus problems in distributed computing. We prove new convergence guarantees for a variety of such protocols, including path, clique, and synchronous pairwise gossip. These arise by exploiting the connection between these protocols and the block randomized Kaczmarz method for solving linear systems. Moreover, we extend existing convergence results for block randomized Kaczmarz to allow for a more general choice of blocks, rank-deficient systems, and provide a tighter convergence rate guarantee. We furthermore apply this analysis to inconsistent consensus models and obtain similar guarantees. An extensive empirical analysis of these methods is provided for a variety of synthetic networks., 21 pages, 19 figures

We study the convergence properties of an overlapping Schwarz decomposition algorithm for solving nonlinear optimal control problems (OCPs). The algorithm decomposes the time domain into a set of overlapping subdomains, and solves all subproblems defined over subdomains in parallel. The convergence is attained by updating primal-dual information at the boundaries of overlapping subdomains. We show that the algorithm exhibits local linear convergence, and that the convergence rate improves exponentially with the overlap size. We also establish global convergence results for a general quadratic programming, which enables the application of the Schwarz scheme inside second-order optimization algorithms (e.g., sequential quadratic programming). The theoretical foundation of our convergence analysis is a sensitivity result of nonlinear OCPs, which we call "exponential decay of sensitivity" (EDS). Intuitively, EDS states that the impact of perturbations at domain boundaries (i.e. initial and terminal time) on the solution decays exponentially as one moves into the domain. Here, we expand a previous analysis available in the literature by showing that EDS holds for both primal and dual solutions of nonlinear OCPs, under uniform second-order sufficient condition, controllability condition, and boundedness condition. We conduct experiments with a quadrotor motion planning problem and a PDE control problem to validate our theory; and show that the approach is significantly more efficient than ADMM and as efficient as the centralized solver Ipopt., 16 pages

The distributed optimization problem is set up in a collection of nodes interconnected via a communication network. The goal is to find the minimizer of a global objective function formed by the addition of partial functions locally known at each node. A number of methods are available for addressing this problem, having different advantages. The goal of this work is to achieve the maximum possible convergence rate. As the first step towards this end, we propose a new method which we show converges faster than other available options. As with most distributed optimization methods, convergence rate depends on a step size parameter. As the second step towards our goal we complement the proposed method with a fully distributed method for estimating the optimal step size that maximizes convergence speed. We provide theoretical guarantees for the convergence of the resulting method in a neighborhood of the solution. Also, for the case in which the global objective function has a single local minimum, we provide a different step size selection criterion together with theoretical guarantees for convergence. We present numerical experiments showing that, when using the same step size, our method converges significantly faster than its rivals. Experiments also show that the distributed step size estimation method achieves an asymptotic convergence rate very close to the theoretical maximum.

We propose a fully distributed control system architecture, amenable to in-vehicle implementation, that aims to safely coordinate connected and automated vehicles (CAVs) at road intersections. For control purposes, we build upon a fully distributed model predictive control approach, in which the agents solve a nonconvex optimal control problem (OCP) locally and synchronously, and exchange their optimized trajectories via vehicle-to-vehicle (V2V) communication. To accommodate a fast solution of the nonconvex OCPs, we apply the penalty convex-concave procedure which solves a convexified version of the original OCP. For experimental evaluation, we complement the predictive controller with a localization layer, being in charge of self-localization, and an estimator, which determines joint collision points with other agents. Experimental tests reveal the efficacy of the proposed control system architecture., Accepted and final version as submitted to IEEE Transactions on Intelligent Transportation Systems

Finite-dimensional observer-based controller design for PDEs is a challenging problem. Recently, such controllers were introduced for the 1D heat equation, under the assumption that one of the observation or control operators is bounded. This paper suggests a constructive method for such controllers for 1D parabolic PDEs with both (observation and control) operators being unbounded. We consider the Kuramoto-Sivashinsky equation (KSE) under either boundary or in-domain point measurement and boundary actuation. We employ a modal decomposition approach via dynamic extension, using eigenfunctions of a Sturm-Liouville operator. The controller dimension is defined by the number of unstable modes, whereas the observer dimension $N$ may be larger than this number. We suggest a direct Lyapunov approach to the full-order closed-loop system, which results in an LMI whose elements and dimension depend on $N$. The value of $N$ and the decay rate are obtained from the LMI. We extend our approach to internal stabilization with guaranteed $L^2$-gain and input-to-state stabilization. We prove two crucial properties of the derived LMIs. First, We prove that the LMIs are always feasible provided $N$ and the $L^2$ or ISS gains are large enough, thereby obtaining guarantees for our approach. Moreover, for the case of stabilization, we show that feasibility of the LMI for some $N$ implies its feasibility for $N+1$ (i.e., enlarging $N$ in the LMI cannot deteriorate the resulting decay rate of the closed-loop system). Numerical examples demonstrate the efficiency of the method.

This article develops an adaptive observation-based efficient reinforcement learning (RL) approach for systems with uncertain drift dynamics. A novel concurrent learning adaptive extended observer (CL-AEO) is first designed to jointly estimate the system state and parameter. This observer has a two-time-scale structure and does not require any additional numerical techniques to calculate the state derivative information. The idea of concurrent learning (CL) is leveraged to use the recorded data, which leads to a relaxed verifiable excitation condition for the convergence of parameter estimation. Based on the estimated state and parameter provided by the CL-AEO, a simulation of experience-based RL scheme is developed to online approximate the optimal control policy. Rigorous theoretical analysis is given to show that the practical convergence of the system state to the origin and the developed policy to the ideal optimal policy can be achieved without the persistence of excitation (PE) condition. Finally, the effectiveness and superiority of the developed methodology are demonstrated via comparative simulations.

This paper proposes a method for enlarging the region of attraction of Linear Model Predictive Controllers (MPC) when tracking piecewise-constant references in the presence of pointwise-in-time constraints. It consists of an add-on unit, the Feasibility Governor (FG), that manipulates the reference command so as to ensure that the optimal control problem that underlies the MPC feedback law remains feasible. Offline polyhedral projection algorithms based on multi-objective linear programming are employed to compute the set of feasible states and reference commands. Online, the action of the FG is computed by solving a convex quadratic program. The closed-loop system is shown to satisfy constraints, be asymptotically stable, exhibit zero-offset tracking, and display finite-time convergence of the reference.

Thermostatically controlled loads (TCLs) can provide ancillary services to the power network by aiding existing frequency control mechanisms. TCLs are, however, characterized by an intrinsic limit cycle behavior which raises the risk that these could synchronize when coupled with the frequency dynamics of the power grid, i.e. simultaneously switch, inducing persistent and possibly catastrophic power oscillations. To address this problem, schemes with a randomized response time in their control policy have been proposed in the literature. However, such schemes introduce delays in the response of TCLs to frequency feedback that may limit their ability to provide fast support at urgencies. In this paper, we present a deterministic control mechanism for TCLs such that those switch when prescribed frequency thresholds are exceeded in order to provide ancillary services to the power network. For the considered scheme, we provide analytic conditions which ensure that synchronization is avoided. In particular, we show that as the number of loads tends to infinity, there exist arbitrarily long time intervals where the frequency deviations are arbitrarily small. Our analytical results are verified with simulations on the Northeast Power Coordinating Council (NPCC) 140-bus system, which demonstrate that the proposed scheme offers improved frequency response compared to conventional implementations., Comment: 10 pages, 5 figures, 1 table

The emerging edge computing paradigm promises to provide low latency and ubiquitous computation to numerous mobile and Internet of Things (IoT) devices at the network edge. How to efficiently allocate geographically distributed heterogeneous edge resources to a variety of services is a challenging task. While this problem has been studied extensively in recent years, most of the previous work has largely ignored the preferences of the services when making edge resource allocation decisions. To this end, this paper introduces a novel bilevel optimization model, which explicitly takes the service preferences into consideration, to study the interaction between an EC platform and multiple services. The platform manages a set of edge nodes (ENs) and acts as the leader while the services are the followers. Given the service placement and resource pricing decisions of the leader, each service decides how to optimally divide its workload to different ENs. The proposed framework not only maximizes the profit of the platform but also minimizes the cost of every service. When there is a single EN, we derive a simple analytic solution for the underlying problem. For the general case with multiple ENs and multiple services, we present a Karush Kuhn Tucker based solution and a duality based solution, combining with a series of linearizations, to solve the bilevel problem. Extensive numerical results are shown to illustrate the efficacy of the proposed model.

Stochastic optimization methods have become a class of popular optimization tools in machine learning. Especially, stochastic gradient descent (SGD) has been widely used for machine learning problems such as training neural networks due to low per-iteration computational complexity. In fact, the Newton or quasi-newton methods leveraging second-order information are able to achieve a better solution than the first-order methods. Thus, stochastic quasi-Newton (SQN) methods have been developed to achieve the better solution efficiently than the stochastic first-order methods by utilizing approximate second-order information. However, the existing SQN methods still do not reach the best known stochastic first-order oracle (SFO) complexity. To fill this gap, we propose a novel faster stochastic quasi-Newton method (SpiderSQN) based on the variance reduced technique of SIPDER. We prove that our SpiderSQN method reaches the best known SFO complexity of $\mathcal{O}(n+n^{1/2}\epsilon^{-2})$ in the finite-sum setting to obtain an $\epsilon$-first-order stationary point. To further improve its practical performance, we incorporate SpiderSQN with different momentum schemes. Moreover, the proposed algorithms are generalized to the online setting, and the corresponding SFO complexity of $\mathcal{O}(\epsilon^{-3})$ is developed, which also matches the existing best result. Extensive experiments on benchmark datasets demonstrate that our new algorithms outperform state-of-the-art approaches for nonconvex optimization., Comment: 11 pages, accepted for publication by TNNLS. arXiv admin note: text overlap with arXiv:1902.02715 by other authors

International audience; We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively $\alpha$-homogeneous rewards. We show that its empirical process, which can be written as a stochastic approximation recursion with Markov noise, has the same probability law as a certain vertex reinforced random walk. We use this equivalence to show that for $\alpha > 0$, the asymptotic outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting $\alpha \to \infty$ slowly.

Cooperative formation and control of autonomous vehicles (AVs) promise increased efficiency and safety on public roads. In mixed traffic flow consisting of AVs and human-driven vehicles (HDVs), the prevailing platooning of multiple AVs is not the only choice for cooperative formation. In this paper, we investigate how different formations of AVs impact traffic performance from a set-function optimization perspective. We first reveal a stability invariance property and a diminishing improvement property of noncooperative formation when AVs adopt typical Adaptive Cruise Control (ACC) strategies. Then, we focus on the case of cooperative formation where the AV controllers are cooperatively designed %redesign the control strategies of AVs in different formations and investigate the optimal formation of multiple AVs using set-function optimization. Two predominant optimal formations, i.e., uniform distribution and platoon formation, emerge from extensive numerical experiments. Interestingly, platooning might have the least potential to improve traffic performance when HDVs have poor string stability behavior. These results suggest more opportunities for cooperative formation of AVs, beyond platooning, in practical mixed traffic flow., 16 pages, 13 figures, 1 table. arXiv admin note: text overlap with arXiv:2004.00397

Preference-based global optimization algorithms minimize an unknown objective function only based on whether the function is better, worse, or similar for given pairs of candidate optimization vectors. Such optimization problems arise in many real-life examples, such as finding the optimal calibration of the parameters of a control law. The calibrator can judge whether a particular combination of parameters leads to a better, worse, or similar closed-loop performance. Often, the search for the optimal parameters is also subject to unknown constraints. For example, the vector of calibration parameters must not lead to closed-loop instability. This paper extends an active preference learning algorithm introduced recently by the authors to handle unknown constraints. The proposed method, called C-GLISp, looks for an optimizer of the problem only based on preferences expressed on pairs of candidate vectors, and on whether a given vector is reported feasible and/or satisfactory. C-GLISp learns a surrogate of the underlying objective function based on the expressed preferences, and a surrogate of the probability that a sample is feasible and/or satisfactory based on whether each of the tested vectors was judged as such. The surrogate functions are used iteratively to propose a new candidate vector to test and judge. Numerical benchmarks and a semi-automated control calibration task demonstrate the effectiveness of C-GLISp, showing that it can reach near-optimal solutions within a small number of iterations., Comment: A MATLAB and a Python implementation of C-GLISp is available at http://cse.lab.imtlucca.it/~bemporad/glis

We present a novel data-driven model predictive control (MPC) approach to control unknown nonlinear systems using only measured input-output data with closed-loop stability guarantees. Our scheme relies on the data-driven system parametrization provided by the Fundamental Lemma of Willems et al. We use new input-output measurements online to update the data, exploiting local linear approximations of the underlying system. We prove that our MPC scheme, which only requires solving strictly convex quadratic programs online, ensures that the closed loop (practically) converges to the (unknown) optimal reachable equilibrium that tracks a desired output reference while satisfying polytopic input constraints. As intermediate results of independent interest, we extend the Fundamental Lemma to affine systems and we derive novel robustness bounds w.r.t. noisy data for the open-loop optimal control problem, which are directly transferable to other data-driven MPC schemes in the literature. The applicability of our approach is illustrated with a numerical application to a continuous stirred tank reactor.

We optimize a general model of bioprocesses, which is nonconvex due to the microbial growth in the biochemical reactors. We formulate a convex relaxation and give conditions guaranteeing its exactness in both the transient and steady state cases. When the growth kinetics are modeled by the Monod function under constant biomass or the Contois function, the relaxation is a second-order cone program, which can be solved efficiently at large scales. We implement the model on a numerical example based on a wastewater treatment system.

We study the problem of eco-routing for Plug-In Hybrid Electric Vehicles (PHEVs) to minimize the overall energy consumption cost. We propose an algorithm which can simultaneously calculate an energy-optimal route (eco-route) for a PHEV and an optimal power-train control strategy over this route. In order to show the effectiveness of our method in practice, we use a HERE Maps API to apply our algorithms based on traffic data in the city of Boston with more than 110,000 links. Moreover, we validate the performance of our eco-routing algorithm using speed profiles collected from a traffic simulator (SUMO) as input to a high-fidelity energy model to calculate energy consumption costs. Our results show significant energy savings (around 12%) for PHEVs with a near real-time execution time for the algorithm., arXiv admin note: text overlap with arXiv:1810.01443

We consider the optimal control of input-queued switches under a cost-weighted variant of MaxWeight scheduling, for which we establish theoretical properties that include showing the algorithm exhibits optimal heavy-traffic queue-length scaling. Our results are expected to be of theoretical interest more broadly than input-queued switches.

This paper investigates the practical engineering problem of traffic sensors placement on stretched highways with ramps. Since it is virtually impossible to install bulky traffic sensors on each highway segment, it is crucial to find placements that result in optimized network-wide, traffic observability. Consequently, this results in accurate traffic density estimates on segments where sensors are not installed. The substantial contribution of this paper is the utilization of control-theoretic observability analysis -- jointly with integer programming -- to determine traffic sensor locations based on the nonlinear dynamics and parameters of traffic networks. In particular, the celebrated asymmetric cell transmission model is used to guide the placement strategy jointly with observability analysis of nonlinear dynamic systems through Gramians. Thorough numerical case studies are presented to corroborate the proposed theoretical methods and various computational research questions are posed and addressed. The presented approach can also be extended to other models of traffic dynamics.

Mobile energy resources (MERs) have received increasing attention due to their effectiveness in boosting the power system resilience in a flexible way. In this paper, a novel mobility model for MERs is proposed, which can support the routing of MERs to provide various services for the power system. Two key points, the state transitions and travel time of MERs, are formulated by linear constraints. The feasibility of the proposed model, especially its advantages in model size and computational efficiency for the routing of MERs among many nodes with a small time span, is demonstrated by a series of tests., Accepted by IEEE Transactions on Smart Grid

Renewable resources are starting to constitute a growing portion of the total generation mix of the power system. A key difference between renewables and traditional generators is that many renewable resources are managed by individuals, especially in the distribution system. In this paper, we study the capacity investment and pricing problem, where multiple renewable producers compete in a decentralized market. It is known that most deterministic capacity games tend to result in very inefficient equilibria, even when there are a large number of similar players. In contrast, we show that due to the inherent randomness of renewable resources, the equilibria in our capacity game becomes efficient as the number of players grows and coincides with the centralized decision from the social planner's problem. This result provides a new perspective on how to look at the positive influence of randomness in a game framework as well as its contribution to resource planning, scheduling, and bidding. We validate our results by simulation studies using real world data., Appears in IEEE Transactions on Sustainable Computing

The effects of model parameter uncertainty on traffic flow control problems have recently drawn research attention. While the uncertainty in fundamental diagram related parameters has been investigated in the past, few articles have focused on network parameters uncertainty, including turning ratio uncertainty. To fill this gap, this article proposes a robust control model to deal with the uncertainties in the turning ratio by using distributionally robust chance constraints. The model allows one to compute the optimal control action that maximizes some objective, under all possible distributions of network parameters. We then apply this robust control framework to both a freeway network and an urban network, and evaluate the impact of uncertainty on optimal control inputs, over the test networks. The case studies show that compared to non-robust control, the proposed robust model can reduce congestion brought by the uncertainties and improve the overall throughput., Accepted for publication on IEEE Transactions on Intelligent Transportation Systems

Although transmission of a data packet containing sensory information in a networked control system improves the quality of regulation, it has indeed a price from the communication perspective. It is, therefore, rational that such a data packet be transmitted only if it is valuable in the sense of a cost-benefit analysis. Yet, the fact is that little is known so far about this valuation of information and its connection with traditional event-triggered communication. In the present article, we study this intrinsic property of networked control systems by formulating a rate-regulation tradeoff between the packet rate and the regulation cost with an event trigger and a controller as two distributed decision makers, and show that the valuation of information is conceivable and quantifiable grounded on this tradeoff. In particular, we characterize an equilibrium in the rate-regulation tradeoff, and quantify the value of information $\text{VoI}_k$ there as the variation in a so-called value function with respect to a piece of sensory information that can be communicated to the controller at each time $k$. We prove that, for a multi-dimensional Gauss-Markov process, $\text{VoI}_k$ is a symmetric function of the discrepancy between the state estimates at the event trigger and the controller, and that a data packet containing sensory information at time $k$ should be transmitted to the controller only if $\text{VoI}_k$ is nonnegative. Moreover, we discuss that $\text{VoI}_k$ can be computed with arbitrary accuracy, and that it can be approximated by a closed-form quadratic function with a performance guarantee.

Energy disaggregation, known in the literature as Non-Intrusive Load Monitoring (NILM), is the task of inferring the energy consumption of each appliance given the aggregate signal recorded by a single smart meter. In this paper, we propose a novel two-stage optimization-based approach for energy disaggregation. In the first phase, a small training set consisting of disaggregated power profiles is used to estimate the parameters and the power states by solving a mixed integer programming problem. Once the model parameters are estimated, the energy disaggregation problem is formulated as a constrained binary quadratic optimization problem. We incorporate penalty terms that exploit prior knowledge on how the disaggregated traces are generated, and appliance-specific constraints characterizing the signature of different types of appliances operating simultaneously. Our approach is compared with existing optimization-based algorithms both on a synthetic dataset and on three real-world datasets. The proposed formulation is computationally efficient, able to disambiguate loads with similar consumption patterns, and successfully reconstruct the signatures of known appliances despite the presence of unmetered devices, thus overcoming the main drawbacks of the optimization-based methods available in the literature.

Zonal pricing is a well-suited mechanism to incentivize grid-supporting behavior of profit-maximizing producers and consumers operating on a large-scale power system. In zonal electricity markets, local system operators create individual price zones, which provide appropriate price signals depending on local grid conditions such as an excess or shortage of electrical energy in certain regions. In this paper, a real-time zonal pricing controller for AC power networks is presented that ensures frequency and voltage stability as well as Pareto efficiency of the resulting closed-loop equilibria. Based on a dynamic network model that takes line losses and power exchange with adjacent price zones into account, distributed continuous-time control laws are derived which require only neighbor-to-neighbor communication. Application to a real-time congestion management strategy illustrates how spatially and temporally differentiated prices enable grid-supportive operation of the participants without interventions by a superordinate control authority. Effectiveness of different zonal pricing concepts compared to an isolated grid operation is demonstrated through simulations on the IEEE-57 bus system.

This paper proposes methods for identification of large-scale networked systems with guarantees that the resulting model will be contracting -- a strong form of nonlinear stability -- and/or monotone, i.e. order relations between states are preserved. The main challenges that we address are: simultaneously searching for model parameters and a certificate of stability, and scalability to networks with hundreds or thousands of nodes. We propose a model set that admits convex constraints for stability and monotonicity, and has a separable structure that allows distributed identification via the alternating directions method of multipliers (ADMM). The performance and scalability of the approach is illustrated on a variety of linear and non-linear case studies, including a nonlinear traffic network with a 200-dimensional state space., Comment: Preprint of full paper accepted for publication in IEEE Trans. Automatic Control

We consider a robust state space filtering problem in the case that the transition probability density is unknown and possibly degenerate. The resulting robust filter has a Kalman-like structure and solves a minimax game: the nature selects the least favorable model in a prescribed ambiguity set which also contains non-Gaussian probability densities, while the other player designs the optimum filter for the least favorable model. It turns out that the resulting robust filter is characterized by a Riccati-like iteration evolving on the cone of the positive semidefinite matrices. Moreover, we study the convergence of such iteration in the case that the nominal model is with constant parameters on the basis of the contraction analysis in the same spirit of Bougerol. Finally, some numerical examples show that the proposed filter outperforms the standard Kalman filter.

In this article, we investigate the problem of practical output regulation, i.e., to design a controller that brings the system output in the vicinity of a desired target value while keeping the other variables bounded. We consider uncertain systems that are possibly nonlinear and the uncertainty of their linear parts is modeled element wise through a parametric family of matrix boxes. An optimization-based design procedure is proposed that delivers a continuous-time control and estimates the maximal regulation error. We also analyze an event-triggered emulation of this controller, which can be implemented on a digital platform, along with an explicit estimate of the regulation error.

Designing feasible control strategies for opinion dynamics in complex social systems has never been an easy task. It requires a control protocol which 1) is not enforced on all individuals in the society, and 2) does not exclusively rely on specific opinion values shared by the social system. Thanks to the recent studies on noise-induced consensus in opinion dynamics, the noise-based intervention strategy has emerged as the only one meeting both of the above requirements, yet its underlying general theory is still lacking. In this paper, we perform rigorous theoretical analysis and simulations of a noise-based control strategy for opinion formation in which only a fraction of individuals is affected by randomly generated noise. We found that irrespective of the number of noise-driven individuals, including the case of only one single noise-affected individual, the system can attain a quasi-consensus in finite time, and the critical noise strength can be obtained. Our results highlight the efficiency of noise-driven mechanisms for the control of complex social dynamics., arXiv admin note: text overlap with arXiv:1711.01432

We study first-order optimization algorithms under the constraint that the descent direction is quantized using a pre-specified budget of $R$-bits per dimension, where $R \in (0 ,\infty)$. We propose computationally efficient optimization algorithms with convergence rates matching the information-theoretic performance lower bounds for: (i) Smooth and Strongly-Convex objectives with access to an Exact Gradient oracle, as well as (ii) General Convex and Non-Smooth objectives with access to a Noisy Subgradient oracle. The crux of these algorithms is a polynomial complexity source coding scheme that embeds a vector into a random subspace before quantizing it. These embeddings are such that with high probability, their projection along any of the canonical directions of the transform space is small. As a consequence, quantizing these embeddings followed by an inverse transform to the original space yields a source coding method with optimal covering efficiency while utilizing just $R$-bits per dimension. Our algorithms guarantee optimality for arbitrary values of the bit-budget $R$, which includes both the sub-linear budget regime ($R < 1$), as well as the high-budget regime ($R \geq 1$), while requiring $O\left(n^2\right)$ multiplications, where $n$ is the dimension. We also propose an efficient relaxation of this coding scheme using Hadamard subspaces that requires a near-linear time, i.e., $O\left(n \log n\right)$ additions.Furthermore, we show that the utility of our proposed embeddings can be extended to significantly improve the performance of gradient sparsification schemes. Numerical simulations validate our theoretical claims. Our implementations are available at https://github.com/rajarshisaha95/DistOptConstrComm., 41 pages, 26 figures, 1 table. This work has been accepted for publication in the IEEE Journal on Selected Areas in Information Theory (JSAIT), Spl. issue on Distributed Coding and Computation

The concept of dissipativity, as introduced by Jan Willems, is one of the cornerstones of systems and control theory. Typically, dissipativity properties are verified by resorting to a mathematical model of the system under consideration. In this paper, we aim at assessing dissipativity by computing storage functions for linear systems directly from measured data. As our main contributions, we provide conditions under which dissipativity can be ascertained from a finite collection of noisy data samples. Three different noise models will be considered that can capture a variety of situations, including the cases that the data samples are noise-free, the energy of the noise is bounded, or the individual noise samples are bounded. All of our conditions are phrased in terms of data-based linear matrix inequalities, which can be readily solved using existing software packages.

A central notion in systems theory is dissipativity, which has been introduced by Jan Willems with the explicit goal of arriving at a fundamental understanding of the stability properties of feedback interconnections. In robust control, the framework of integral quadratic constraints (IQCs) builds on the seminal contributions of Yakubovich and Zames in the 1960's. It provides a technique for analyzing the stability of an interconnection of some linear system in feedback with a whole class of systems, also refereed to as uncertainty. In this paper we survey the key ideas of exploiting dissipativity and integral quadratic constraints for the computational analysis of robust stability and performance properties of uncertain interconnections in terms of linear matrix inequalities. In particular for dynamic supply rates, the paper revolves around the notion of finite-horizon integral quadratic constraints with a terminal cost. We reveal that this provides a seamless link between the general IQC theorem and dissipativity theory that has been established only rather recently.

In this paper, we propose a dual set membership filter for nonlinear dynamic systems with unknown but bounded noises, and it has three distinctive properties. Firstly, the nonlinear system is translated into the linear system by leveraging a semi-infinite programming, rather than linearizing the nonlinear function. In fact, the semi-infinite programming is to find an ellipsoid bounding the nonlinear transformation of an ellipsoid, which aims to compute a tight ellipsoid to cover the state. Secondly, the duality result of the semi-infinite programming is derived by a rigorous analysis, then a first order Frank-Wolfe method is developed to efficiently solve it with a lower computation complexity. Thirdly, the proposed filter can take advantage of the linear set membership filter framework and can work on-line without solving the semidefinite programming problem. Furthermore, we apply the dual set membership filter to a typical scenario of mobile robot localization. Finally, two illustrative examples in the simulations show the advantages and effectiveness of the dual set membership filter., 26 pages, 9 figures

Efficient testing and vaccination protocols are critical aspects of epidemic management. To study the optimal allocation of limited testing and vaccination resources in a heterogeneous contact network of interacting susceptible, recovered, and infected individuals, we present a degree-based testing and vaccination model for which we use control-theoretic methods to derive optimal testing and vaccination policies. Within our framework, we find that optimal intervention policies first target high-degree nodes before shifting to lower-degree nodes in a time-dependent manner. Using such optimal policies, it is possible to delay outbreaks and reduce incidence rates to a greater extent than uniform and reinforcement-learning-based interventions, particularly on certain scale-free networks., 13 pages, 8 figures, Submitted to IEEE Transactions on Network Science and Engineering

This paper proposes a dynamic valuation framework to determine the opportunity value of battery capacity degradation in grid applications based on the internal degradation mechanism and utilization scenarios. The proposed framework follows a dynamic programming approach and includes a piecewise linear value function approximation solution that solves the optimization problem over a long planning horizon. The paper provides two case studies on price arbitrage and frequency regulation using real market and system data to demonstrate the broad applicability of the proposed framework. Results show that the battery lifetime value is critically dependent on both the external market environment and its internal state of health. On the grid service side, results show that second-life batteries can provide more than 50% of the value compared to new batteries, and frequency regulation provides two times more revenue than price arbitrage throughout the battery lifetime.

Brockett's minimum attention functional \cite{Brockett} has been proposed as one means of capturing the cost of control implementation--regarded here as the rate of change of the control with respect to both state and time--for general nonlinear control systems, with applications ranging from human motor control to robotics. The main challenge in forging the minimum attention paradigm into a practical control design methodology is that the existence of solutions is not always assured, and finding numerical solutions is also difficult. In this paper we prove that, under the assumption of a control that is the sum of a time-varying feedforward term and a time-varying feedback term linear in the state, existence of a solution can be guaranteed. Under these assumptions we appeal to the Liouville equation representation of a nonlinear control system and derive the associated first-order optimality conditions. The one-shot method is then used to prove the existence of a solution and also to iteratively compute a solution. Our methodology is illustrated with an example involving a two degree-of-freedom robot arm., 6 pages, 4 figures

This paper deals with the simultaneous estimation of the attitude, position and linear velocity for vision-aided inertial navigation systems. We propose a nonlinear observer on $SO(3)\times \mathbb{R}^{15}$ relying on body-frame acceleration, angular velocity and (stereo or monocular) bearing measurements of some landmarks that are constant and known in the inertial frame. Unlike the existing local Kalman-type observers, our proposed nonlinear observer guarantees almost global asymptotic stability and local exponential stability. A detailed uniform observability analysis has been conducted and sufficient conditions are derived. Moreover, a hybrid version of the proposed observer is provided to handle the intermittent nature of the measurements in practical applications. Simulation and experimental results are provided to illustrate the effectiveness of the proposed state observer., Accepted for publication in IEEE Transaction on Automatic Control. 16 pages, 6 figures

Optimal sensor and actuator selection is a central challenge in high-dimensional estimation and control. Nearly all subsequent control decisions are affected by these sensor/actuator locations, and optimal placement amounts to an intractable brute-force search among the combinatorial possibilities. In this work, we exploit balanced model reduction and greedy optimization to efficiently determine sensor and actuator selections that optimize observability and controllability. In particular, we determine locations that optimize scalar measures of observability and controllability via greedy matrix QR pivoting on the dominant modes of the direct and adjoint balancing transformations. Pivoting runtime scales linearly with the state dimension, making this method tractable for high-dimensional systems. The results are demonstrated on the linearized Ginzburg-Landau system, for which our algorithm approximates known optimal placements computed using costly gradient descent methods., Comment: 8 pages, 6 figures

Jointly achieving safety and efficiency in human-robot interaction (HRI) settings is a challenging problem, as the robot's planning objectives may be at odds with the human's own intent and expectations. Recent approaches ensure safe robot operation in uncertain environments through a supervisory control scheme, sometimes called "shielding", which overrides the robot's nominal plan with a safety fallback strategy when a safety-critical event is imminent. These reactive "last-resort" strategies (typically in the form of aggressive emergency maneuvers) focus on preserving safety without efficiency considerations; when the nominal planner is unaware of possible safety overrides, shielding can be activated more frequently than necessary, leading to degraded performance. In this work, we propose a new shielding-based planning approach that allows the robot to plan efficiently by explicitly accounting for possible future shielding events. Leveraging recent work on Bayesian human motion prediction, the resulting robot policy proactively balances nominal performance with the risk of high-cost emergency maneuvers triggered by low-probability human behaviors. We formalize Shielding-Aware Robust Planning (SHARP) as a stochastic optimal control problem and propose a computationally efficient framework for finding tractable approximate solutions at runtime. Our method outperforms the shielding-agnostic motion planning baseline (equipped with the same human intent inference scheme) on simulated driving examples with human trajectories taken from the recently released Waymo Open Motion Dataset.

This article proposes a second-order conic programming (SOCP) approach to solve distributionally robust two-stage linear programs over 1-Wasserstein balls. We start from the case with distribution uncertainty only in the objective function and then explore the case with distribution uncertainty only in constraints. The former program is exactly reformulated as a tractable SOCP problem, whereas the latter one is proved to be generally NP-hard as it involves a norm maximization problem over a polyhedron. However, it reduces to an SOCP problem if the extreme points of the polyhedron are given as a prior. This motivates the design of a constraint generation algorithm with provable convergence to approximately solve the NP-hard problem. Moreover, the least favorable distribution achieving the worst case cost is given as an ``empirical'' distribution by simply perturbing each original sample for both cases. Finally, experiments illustrate the advantages of the proposed model in terms of the out-of-sample performance and computational complexity.

We address Bayesian persuasion between a sender and a receiver with state-dependent quadratic cost measures for general classes of distributions. The receiver seeks to make mean-square-error estimate of a state based on a signal sent by the sender while the sender signals strategically in order to control the receiver's estimate in a certain way. Such a scheme could model, e.g., deception and privacy, problems in multi-agent systems. Existing solution concepts are not viable since here the receiver has continuous action space. We show that for finite state spaces, optimal signaling strategies can be computed through an equivalent linear optimization problem over the cone of completely positive matrices. We then establish its strong duality to a copositive program. To exemplify the effectiveness of this equivalence result, we adopt sequential polyhedral approximation of completely-positive cones and analyze its performance numerically. We also quantify the approximation error for a quantized version of a continuous distribution and show that a semi-definite program relaxation of the equivalent problem could be a benchmark lower bound for the sender's cost for large state spaces.

In this work, we study a class of mean-field linear quadratic Gaussian (LQG) problems. Under suitable conditions, explicit solutions of the distribution-dependent optimal control problems are obtained. Riccati systems are derived by directly solving the associated master equations. Some extensions on controls with partial observations are also considered., 13 pages

Pulsed fluidic actuators play a central role in the fluid flow experimental control strategy to achieve better performances of aeronautic devices. In this paper, we demonstrate, through an experimental test bench, how the interpolatory-based Loewner Data-Driven Control (L-DDC) framework is an appropriate tool for accurately controlling the outflow velocity of this family of actuators. L-DDC combines the concept of ideal controller with the Loewner framework in a single data-driven rationale, appropriate to experimental users. The contributions of the paper are, first, to emphasise the simplicity and versatility of such a data-driven rationale in a constrained experimental setup, and second, to solve some practical fluid engineers concerns by detailing the complete workflow and key ingredients for successfully implementing a pulsed fluidic actuator controller from the data acquisition to the control implementation and validation stages., Comment: 20 pages, 7 figures

Specific low-bitrate coding strategies are examined through their effect on LQ control performance. By limiting the subject to these methods, we are able to identify principles underlying coding for control; a subject of significant recent interest but few tangible results. In particular, we consider coding the quantized output signal deploying period-two codes of differing delay-versus-accuracy tradeoff. The quantification of coding performance is via the LQ control cost. The feedback control system comprises the coder-decoder in the path between the output and the state estimator, which is followed by linear state-variable feedback, as is optimal in the memoryless case. The quantizer is treated as the functional composition of an infinitely-long linear staircase function and a saturation. This permits the analysis to subdivide into estimator computations, seemingly independent of the control performance criterion, and an escape time evaluation, which ties the control back into the choice of quantizer saturation bound. An example is studied which illustrates the role of the control objective in determining the efficacy of coding using these schemes. The results mesh well with those observed in signal coding. However, the introduction of a realization-based escape time is a novelty departing significantly from mean square computations., 12-page submission to IEEE TCNS

Time-of-use (ToU) pricing is widely used by the electricity utility to shave peak load. Such a pricing scheme provides users with incentives to invest in behind-the-meter energy storage and to shift peak load towards low-price intervals. However, without considering the implication on energy storage investment, an improperly designed ToU pricing scheme may lead to significant welfare loss, especially when users over-invest the storage, which leads to new energy consumption peaks. In this paper, we will study how to design a social-optimum ToU pricing scheme by explicitly considering its impact on storage investment. We model the interactions between the utility and users as a two-stage optimization problem. To resolve the challenge of asymmetric information due to users' private storage cost, we propose a ToU pricing scheme based on different storage types and the aggregate demand per type. Each user does not need to reveal his private cost information. We can further compute the optimal ToU pricing with only a linear complexity. Simulations based on real-world data show that the suboptimality gap of our proposed ToU pricing, compared with the social optimum achieved under complete information, is less than 5%.

Identifying the multiple critical components in power systems whose absence together has severe impact on system performance is a crucial problem for power systems known as $(N-x)$ contingency analysis. However, the inherent combinatorial feature of the $N-x$ contingency analysis problem incurs by the increase of $x$ in the $(N-x)$ term, making the problem intractable for even relatively small test systems. We present a new framework for identifying the $N-x$ contingencies that captures both topology and physics of the network. Graph theory provides many ways to measure power grid graphs, i.e., buses as nodes and lines as edges, allowing researchers to characterize system structure and optimize algorithms. This article proposes a scalable approach based on the group betweenness centrality concept that measures the impact of multiple components in the electric power grid as well as line outage distribution factors that find the lines whose loss has the highest impact on the power flow in the network. The proposed approach is a quick and efficient solution for identifying the most critical lines in power networks. The proposed approach is validated using various test cases, and results show that the proposed approach is able to quickly identify multiple contingencies that result in violations.

Flexible load at the demand-side has been regarded as an effective measure to cope with volatile distributed renewable generations. To unlock the demand-side flexibility, this paper proposes a peer-to-peer energy sharing mechanism that facilitates energy exchange among users while preserving privacy. We prove the existence and partial uniqueness of the energy sharing market equilibrium and provide a centralized optimization to obtain the equilibrium. The centralized optimization is further linearized by a convex combination approach, turning into a multi-parametric linear program (MP-LP) with renewable output deviations being the parameters. The flexibility requirement of individual users is calculated based on this MP-LP. To be specific, an adaptive vertex generation algorithm is established to construct a piecewise linear estimator of the optimal total cost subject to a given error tolerance. Critical regions and optimal strategies are retrieved from the obtained approximate cost function to evaluate the flexibility requirement. The proposed algorithm does not rely on the exact characterization of optimal basis invariant sets and thus is not influenced by model degeneracy, a common difficulty faced by existing approaches. Case studies validate the theoretical results and show that the proposed method is scalable., Comment: 11 pages, 10 figures