Search

This paper considers the problem of approximating the "maximal" region of attraction (the set that contains all asymptotically stable sets) of any given set of locally exponentially stable nonlinear Ordinary Differential Equations (ODEs) with a sufficiently smooth vector field. Given a locally exponential stable ODE with a differentiable vector field, we show that there exists a globally Lipschitz continuous converse Lyapunov function whose 1-sublevel set is equal to the maximal region of attraction of the ODE. We then propose a sequence of d-degree Sum-of-Squares (SOS) programming problems that yields a sequence of polynomials that converges to our proposed converse Lyapunov function uniformly from above in the L1 norm. We show that each member of the sequence of 1-sublevel sets of the polynomial solutions to our proposed sequence of SOS programming problems are certifiably contained inside the maximal region of attraction of the ODE, and moreover, we show that this sequence of sublevel sets converges to the maximal region of attraction of the ODE with respect to the volume metric. We provide numerical examples of estimations of the maximal region of attraction for the Van der Pol oscillator and a three dimensional servomechanism.

We propose a method for verifying that a given feasible point for a polynomial optimization problem is globally optimal. The approach relies on the Lasserre hierarchy and the result of Lasserre regarding the importance of the convexity of the feasible set as opposed to that of the individual constraints. By focusing solely on certifying global optimality and relaxing the Lasserre hierarchy using necessary conditions for positive semidefiniteness based on matrix determinants, the proposed method is implementable as a computationally tractable linear program. We demonstrate this method via application to several instances of polynomial optimization, including the optimal power flow problem used to operate electric power systems., Comment: 6 pages, 4 figures

The paper addresses the model reduction problem by least squares moment matching for continuous-time, linear, time-invariant systems. The basic idea behind least squares moment matching is to approximate a transfer function by ensuring that the interpolation conditions imposed by moment matching are satisfied in a least squares sense. This idea is revisited using invariance equations and steady-state responses to provide a new time-domain characterization of least squares moment matching. The characterization, in turn, is then used to obtain a parameterized family of models achieving least squares moment matching. The theory is illustrated by a worked-out numerical example., Comment: Submitted to the 60th Conference on Decision and Control (CDC)

In this paper we investigate a relaxed concept of controllability, known in the literature as herdability, namely the capability of a system to be driven towards the(interior of the) positive orthant. Specifically, we investigate herdability for linear time-invariant systems, both from an algebraic perspective and based on the graph representing the systems interactions. In addition, we focus on linear state-space models corresponding to matrix pairs (A;B) in which the matrix B is a selection matrix that determines the leaders in the network, and we show that the weights that followers give to the leaders do not affect the herdability of the system. We then focus on the herdability problem for systems with a single leader in which interactions are symmetric and the network topology is acyclic, in which case an algorithm for the leader selection is provided. In this context, under some additional conditions on the mutual distances, necessary and sufficient conditions for the herdability of the overall system are given.

Optimal transport (OT) is a powerful geometric tool for comparing two distributions and has been employed in various machine learning applications. In this work, we propose a novel OT formulation that takes feature correlations into account while learning the transport plan between two distributions. We model the feature-feature relationship via a symmetric positive semi-definite Mahalanobis metric in the OT cost function. For a certain class of regularizers on the metric, we show that the optimization strategy can be considerably simplified by exploiting the problem structure. For high-dimensional data, we additionally propose suitable low-dimensional modeling of the Mahalanobis metric. Overall, we view the resulting optimization problem as a non-linear OT problem, which we solve using the Frank-Wolfe algorithm. Empirical results on the discriminative learning setting, such as tag prediction and multi-class classification, illustrate the good performance of our approach., Comment: Accepted to IEEE CDC 2021

This paper proposes a data-driven framework to solve time-varying optimization problems associated with unknown linear dynamical systems. Making online control decisions to regulate a dynamical system to the solution of an optimization problem is a central goal in many modern engineering applications. Yet, the available methods critically rely on a precise knowledge of the system dynamics, thus mandating a preliminary system identification phase before a controller can be designed. In this work, we leverage results from behavioral theory to show that the steady-state transfer function of a linear system can be computed from data samples without any knowledge or estimation of the system model. We then use this data-driven representation to design a controller, inspired by a gradient-descent optimization method, that regulates the system to the solution of a convex optimization problem, without requiring any knowledge of the time-varying disturbances affecting the model equation. Results are tailored to cost functions satisfy the Polyak-\L ojasiewicz inequality.

This paper studies the problem of finding the median of N distinct numbers distributed across networked agents. Each agent updates its estimate for the median from noisy local observations of one of the N numbers and information from neighbors. We consider an undirected random network that is connected on average, and a noisy observation sequence that has finite variance and almost surely decaying bias. We present a consensus+innovations algorithm with clipped innovations. Under some regularity assumptions on the network and observation model, we show that each agent's local estimate converges to the set of median(s) almost surely at an asymptotic sublinear rate. Numerical experiments demonstrate the effectiveness of the presented algorithm., 8 pages, 3 figures, IEEE CDC 2021

In this paper, we propose an adaptive control law for completely unknown scalar linear systems based on Lie-bracket approximation methods. We investigate stability and convergence properties for the resulting Lie-bracket system, compare our proposal with existing Nussbaum-type solutions and demonstrate our results with an example. Even though we prove global stability properties of the Lie-bracket system, the stability properties of the proposed dynamics remain open, making the proposed control law an object of further studies. We elaborate the difficulties of establishing stability results by investigating connections to partial stability as well as studying the corresponding Chen-Fliess expansion., This is the extended version of our conference paper for CDC2021 with additional calculation steps

We study extensions of the classical SIR model of epidemic spread. First, we consider a single population modified SIR epidemics model in which the contact rate is allowed to be an arbitrary function of the fraction of susceptible and infected individuals. This allows one to model either the reaction of individuals to the information about the spread of the disease or the result of government restriction measures, imposed to limit social interactions and contain contagion. We study the effect of both smooth dependancies of the contact rate for which we prove the existence of a threshold phenomenon that generalizes the well-known dichotomy associated to the reproduction rate parameter in the classical SIR model, and discontinuous feedback terms, which can be studied using tools from sliding mode control. Finally, we consider network SIR models involving different subpopulations that interact on a contact graph and present some preliminary simulations of modified versions of the classic SIR network., 6 pages. 4 figures. Accepted to the 2021 60th IEEE Conference on Decision and Control (CDC)

Constrained submodular set function maximization problems often appear in multi-agent decision-making problems with a discrete feasible set. A prominent example is the problem of multi-agent mobile sensor placement over a discrete domain. However, submodular set function optimization problems are known to be NP-hard. In this paper, we consider a class of submodular optimization problems that consists of maximization of a monotone and submodular set function subject to a uniform matroid constraint over a group of networked agents that communicate over a connected undirected graph. Our objective is to obtain a distributed suboptimal polynomial-time algorithm that enables each agent to obtain its respective policy via local interactions with its neighboring agents. Our solution is a fully distributed gradient-based algorithm using the multilinear extension of the submodular set functions and exploiting a maximum consensus scheme. This algorithm results in a policy set that when the team objective function is evaluated at worst case the objective function value is in $1-1/e-O(1/T)$ of the optimal solution. An example demonstrates our results.

Scaled relative graphs were recently introduced to analyze the convergence of optimization algorithms using two dimensional Euclidean geometry. In this paper, we connect scaled relative graphs to the classical theory of input/output systems. It is shown that the Nyquist diagram of an LTI system on $L_2$ is the convex hull of its scaled relative graph under a particular change of coordinates. The SRG may be used to visualize approximations of static nonlinearities such as the describing function and quadratic constraints, allowing system properties to be verified or disproved. Interconnections of systems correspond to graphical manipulations of their SRGs. This is used to provide a simple, graphical proof of the classical incremental passivity theorem., Accepted to the 2021 IEEE Conference on Decision and Control

In this work, stabilization of an axonal growth in a neuron associated with the dynamics of tubulin concentration is proposed by designing a boundary control. The dynamics are given by a parabolic Partial Differential Equation (PDE) of the tubulin concentration, with a spatial domain of the axon's length governed by an Ordinary Differential Equation (ODE) coupled with the tubulin concentration in the growth cone. We propose a novel backstepping method for the coupled PDE-ODE dynamics with a moving boundary, and design a control law for the tubulin concentration flux in the soma. Through employing the Lyapunov analysis to a nonlinear target system, we prove a local exponential stability of the closed-loop system under the proposed control law in the spatial $H_1$-norm., Comment: Accepted for CDC 2021

Polyhedral Lyapunov functions can approximate any norm arbitrarily well. Because of this, they are used to study the stability of linear time varying and linear parameter varying systems without being conservative. However, the computational cost associated with using them grows unbounded as the size of their representation increases. Finding them is also a hard computational problem. Here we present an algorithm that attempts to find polyhedral functions while keeping the size of the representation fixed, to limit computational costs. We do this by measuring the gap from contraction for a given polyhedral set. The solution is then used to find perturbations on the polyhedral set that reduce the contraction gap. The process is repeated until a valid polyhedral Lyapunov function is obtained. The approach is rooted in linear programming. This leads to a flexible method capable of handling additional linear constraints and objectives, and enables the use of the algorithm for control synthesis.

Adaptive control is subject to stability and performance issues when a learned model is used to enhance its performance. This paper thus presents a deep learning-based adaptive control framework for nonlinear systems with multiplicatively-separable parametrization, called adaptive Neural Contraction Metric (aNCM). The aNCM approximates real-time optimization for computing a differential Lyapunov function and a corresponding stabilizing adaptive control law by using a Deep Neural Network (DNN). The use of DNNs permits real-time implementation of the control law and broad applicability to a variety of nonlinear systems with parametric and nonparametric uncertainties. We show using contraction theory that the aNCM ensures exponential boundedness of the distance between the target and controlled trajectories in the presence of parametric uncertainties of the model, learning errors caused by aNCM approximation, and external disturbances. Its superiority to the existing robust and adaptive control methods is demonstrated using a cart-pole balancing model., Comment: IEEE Conference on Decision and Control (CDC), Preprint Version. Accepted July, 2021

This work proposes a distributed algorithm for solving empirical risk minimization problems, called L-DQN, under the master/worker communication model. L-DQN is a distributed limited-memory quasi-Newton method that supports asynchronous computations among the worker nodes. Our method is efficient both in terms of storage and communication costs, i.e., in every iteration the master node and workers communicate vectors of size $O(d)$, where $d$ is the dimension of the decision variable, and the amount of memory required on each node is $O(md)$, where $m$ is an adjustable parameter. To our knowledge, this is the first distributed quasi-Newton method with provable global linear convergence guarantees in the asynchronous setting where delays between nodes are present. Numerical experiments are provided to illustrate the theory and the practical performance of our method.

This paper introduces the notion of an Input Constrained Control Barrier Function (ICCBF), as a method to synthesize safety-critical controllers for non-linear control affine systems with input constraints. The method identifies a subset of the safe set of states, and constructs a controller to render the subset forward invariant. The feedback controller is represented as the solution to a quadratic program, which can be solved efficiently for real-time implementation. Furthermore, we show that ICCBFs are a generalization of Higher Order Control Barrier Functions, and thus are applicable to systems of non-uniform relative degree. Simulation results are presented for the adaptive cruise control problem, and a spacecraft rendezvous problem., 8 pages, 3 figures, submitted to Conference on Decision and Control 2021

In this paper, we introduce complexity-aware planning for finite-horizon deterministic finite automata with rewards as outputs, based on Kolmogorov complexity. Kolmogorov complexity is considered since it can detect computational regularities of deterministic optimal policies. We present a planning objective yielding an explicit trade-off between a policy's performance and complexity. It is proven that maximising this objective is non-trivial in the sense that dynamic programming is infeasible. We present two algorithms obtaining low-complexity policies, where the first algorithm obtains a low-complexity optimal policy, and the second algorithm finds a policy maximising performance while maintaining local (stage-wise) complexity constraints. We evaluate the algorithms on a simple navigation task for a mobile robot, where our algorithms yield low-complexity policies that concur with intuition., Comment: Accepted to CDC 2021

We consider a distributed stochastic optimization problem that is solved by a decentralized network of agents with only local communication between neighboring agents. The goal of the whole system is to minimize a global objective function given as a sum of local objectives held by each agent. Each local objective is defined as an expectation of a convex smooth random function and the agent is allowed to sample stochastic gradients for this function. For this setting we propose the first accelerated (in the sense of Nesterov's acceleration) method that simultaneously attains optimal up to a logarithmic factor communication and oracle complexity bounds for smooth strongly convex distributed stochastic optimization. We also consider the case when the communication graph is allowed to vary with time and obtain complexity bounds for our algorithm, which are the first upper complexity bounds for this setting in the literature.

Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs) are popular tools for enforcing safety and stability of a controlled system, respectively. They are commonly utilized to build constraints that can be incorporated in a min-norm quadratic program (CBF-CLF-QP) which solves for a safety-critical control input. However, since these constraints rely on a model of the system, when this model is inaccurate the guarantees of safety and stability can be easily lost. In this paper, we present a Gaussian Process (GP)-based approach to tackle the problem of model uncertainty in safety-critical controllers that use CBFs and CLFs. The considered model uncertainty is affected by both state and control input. We derive probabilistic bounds on the effects that such model uncertainty has on the dynamics of the CBF and CLF. We then use these bounds to build safety and stability chance constraints that can be incorporated in a min-norm convex optimization-based controller, called GP-CBF-CLF-SOCP. As the main theoretical result of the paper, we present necessary and sufficient conditions for pointwise feasibility of the proposed optimization problem. We believe that these conditions could serve as a starting point towards understanding what are the minimal requirements on the distribution of data collected from the real system in order to guarantee safety. Finally, we validate the proposed framework with numerical simulations of an adaptive cruise controller for an automotive system., The first two authors contributed equally. Accepted for publication in IEEE 60th Conference on Decision and Control (CDC 2021)

We consider the setting where the nodes of an undirected, connected network collaborate to solve a shared objective modeled as the sum of smooth functions. We assume that each summand is privately known by a unique node. NEAR-DGD is a distributed first order method which permits adjusting the amount of communication between nodes relative to the amount of computation performed locally in order to balance convergence accuracy and total application cost. In this work, we generalize the convergence properties of a variant of NEAR-DGD from the strongly convex to the nonconvex case. Under mild assumptions, we show convergence to minimizers of a custom Lyapunov function. Moreover, we demonstrate that the gap between those minimizers and the second order stationary solutions of the original problem can become arbitrarily small depending on the choice of algorithm parameters. Finally, we accompany our theoretical analysis with a numerical experiment to evaluate the empirical performance of NEAR-DGD in the nonconvex setting.

The least squares problem with L1-regularized regressors, called Lasso, is a widely used approach in optimization problems where sparsity of the regressors is desired. This formulation is fundamental for many applications in signal processing, machine learning and control. As a motivating problem, we investigate a sparse data predictive control problem, run at a cloud service to control a system with unknown model, using L1-regularization to limit the behavior complexity. The input-output data collected for the system is privacy-sensitive, hence, we design a privacy-preserving solution using homomorphically encrypted data. The main challenges are the non-smoothness of the L1-norm, which is difficult to evaluate on encrypted data, as well as the iterative nature of the Lasso problem. We use a distributed ADMM formulation that enables us to exchange substantial local computation for little communication between multiple servers. We first give an encrypted multi-party protocol for solving the distributed Lasso problem, by approximating the non-smooth part with a Chebyshev polynomial, evaluating it on encrypted data, and using a more cost effective distributed bootstrapping operation. For the example of data predictive control, we prefer a non-homogeneous splitting of the data for better convergence. We give an encrypted multi-party protocol for this non-homogeneous splitting of the Lasso problem to a non-homogeneous set of servers: one powerful server and a few less powerful devices, added for security reasons. Finally, we provide numerical results for our proposed solutions.

We consider the stochastic shortest path planning problem in MDPs, i.e., the problem of designing policies that ensure reaching a goal state from a given initial state with minimum accrued cost. In order to account for rare but important realizations of the system, we consider a nested dynamic coherent risk total cost functional rather than the conventional risk-neutral total expected cost. Under some assumptions, we show that optimal, stationary, Markovian policies exist and can be found via a special Bellman's equation. We propose a computational technique based on difference convex programs (DCPs) to find the associated value functions and therefore the risk-averse policies. A rover navigation MDP is used to illustrate the proposed methodology with conditional-value-at-risk (CVaR) and entropic-value-at-risk (EVaR) coherent risk measures.

In this paper, we investigate when system identification is statistically easy or hard, in the finite sample regime. Statistically easy to learn linear system classes have sample complexity that is polynomial with the system dimension. Most prior research in the finite sample regime falls in this category, focusing on systems that are directly excited by process noise. Statistically hard to learn linear system classes have worst-case sample complexity that is at least exponential with the system dimension, regardless of the identification algorithm. Using tools from minimax theory, we show that classes of linear systems can be hard to learn. Such classes include, for example, under-actuated or under-excited systems with weak coupling among the states. Having classified some systems as easy or hard to learn, a natural question arises as to what system properties fundamentally affect the hardness of system identifiability. Towards this direction, we characterize how the controllability index of linear systems affects the sample complexity of identification. More specifically, we show that the sample complexity of robustly controllable linear systems is upper bounded by an exponential function of the controllability index. This implies that identification is easy for classes of linear systems with small controllability index and potentially hard if the controllability index is large. Our analysis is based on recent statistical tools for finite sample analysis of system identification as well as a novel lower bound that relates controllability index with the least singular value of the controllability Gramian., Under review

In this paper we describe a parameterized family of first-order distributed optimization algorithms that enable a network of agents to collaboratively calculate a decision variable that minimizes the sum of cost functions at each agent. These algorithms are self-healing in that their correctness is guaranteed even if they are initialized randomly, agents drop in or out of the network, local cost functions change, or communication packets are dropped. Our algorithms are the first single-Laplacian methods to exhibit all of these characteristics. We achieve self-healing by sacrificing internal stability, a fundamental trade-off for single-Laplacian methods., Comment: Corrected equation (40) by changing "min" to "max", results unaffected

In this paper, we study multi-agent systems with decentralized resource allocations. Agents have local demand and resource supply, and are interconnected through a network designed to support sharing of the local resource; and the network has no external resource supply. It is known from classical welfare economics theory that by pricing the flow of resource, balance between the demand and supply is possible. Agents decide on the consumed resource, and perhaps further the traded resource as well, to maximize their payoffs considering both the utility of the consumption, and the income from the trading. When the network supply and demand are balanced, a competitive equilibrium is achieved if all agents maximize their individual payoffs, and a social welfare equilibrium is achieved if the total agent utilities are maximized. First, we consider multi-agent systems with static local allocations, and prove from duality theory that under general convexity assumptions, the competitive equilibrium and the social welfare equilibrium exist and agree. Compared to similar results in the literature based on KKT arguments, duality theory provides a direct way for connecting the two notions and for a more general (e.g. nonsmooth) class of utility functions. Next, we show that the agent utility functions can be prescribed in a family of socially admissible functions, under which the resource price at the competitive equilibrium is kept below a threshold. Finally, we extend the study to dynamical multi-agent systems where agents are associated with dynamical states from linear processes, and we prove that the dynamic the competitive equilibrium and social welfare equilibrium continue to exist and coincide with each other.

We consider a zeroth-order distributed optimization problem, where the global objective function is a black-box function and, as such, its gradient information is inaccessible to the local agents. Instead, the local agents can only use the values of the objective function to estimate the gradient and update their local decision variables. In this paper, we also assume that these updates are done asynchronously. To solve this problem, we propose an asynchronous zeroth-order distributed optimization method that relies on a one-point residual feedback to estimate the unknown gradient. We show that this estimator is unbiased under asynchronous updating, and theoretically analyze the convergence of the proposed method. We also present numerical experiments that demonstrate that our method outperforms two-point methods under asynchronous updating. To the best of our knowledge, this is the first asynchronous zeroth-order distributed optimization method that is also supported by theoretical guarantees.

Accurate quantification of safety is essential for the design of autonomous systems. In this paper, we present a methodology to characterize the exact probabilities associated with invariance and recovery in safe control. We consider a stochastic control system where control barrier functions, gradient-based methods, and barrier certificates are used to constrain control actions and validate safety. We derive the probability distributions of the minimum and maximum barrier function values during any time interval and the first entry and exit times to and from any super level sets of the barrier function. These distributions are characterized by deterministic convection-diffusion equations, and the approach used is generalizable to other safe control methods based on barrier functions. These distributions can be used to characterize various quantities associated with invariance and recovery, such as the safety margin, the probability of entering and recovering from safe and unsafe regions, and the mean and tail distributions of failure and recovery times.

International audience; In this paper, we are interested in the estimation of Particle Size Distributions (PSDs) during a batch crystallization process in which particles of two different shapes coexist and evolve simultaneously. The PSDs are estimated thanks to a measurement of an apparent Chord Length Distribution (CLD), a measure that we model for crystals of spheroidal shape. Our main result is to prove the approximate observability of the infinite-dimensional system in any positive time. Under this observability condition, we are able to apply a Back and Forth Nudging (BFN) algorithm to reconstruct the PSD.

Distributed resource allocation is a central task in network systems such as smart grids, water distribution networks, and urban transportation systems. When solving such problems in practice it is often important to have non-asymptotic feasibility guarantees for the iterates, since overall-location of resources easily causes systems to break down. In this paper, we develop a distributed resource reallocation algorithm where every iteration produces a feasible allocation. The algorithm is fully distributed in the sense that nodes communicate only with neighbors over a given communication network. We prove that under mild conditions the algorithm converges to a point arbitrarily close to the optimal resource allocation. Numerical experiments demonstrate the competitive practical performance of the algorithm.

This paper addresses the issue of data injection attacks on control systems. We consider attacks which aim at maximizing system disruption while staying undetected in the finite horizon. The maximum possible disruption caused by such attacks is formulated as a non-convex optimization problem whose dual problem is a convex semi-definite program. We show that the duality gap is zero using S-lemma. To determine the optimal attack vector, we formulate a soft-constrained optimization problem using the Lagrangian dual function. The framework of dynamic programming for indefinite cost functions is used to solve the soft-constrained optimization problem and determine the attack vector. Using the Karush-Kuhn-Tucker conditions, we also provide necessary and sufficient conditions under which the obtained attack vector is optimal to the primal problem., Accepted to the Conference on Decision and Control 2021

Generalized Polynomial Chaos (gPC) theory has been widely used for representing parametric uncertainty in a system, thanks to its ability to propagate uncertainty evolution. In an optimal control context, gPC can be combined with several optimization techniques to achieve a control policy that handles effectively this type of uncertainty. Such a suitable method is Differential Dynamic Programming (DDP), leading to an algorithm that inherits the scalability to high-dimensional systems and fast convergence nature of the latter. In this paper, we expand this combination aiming to acquire probabilistic guarantees on the satisfaction of nonlinear constraints. In particular, we exploit the ability of gPC to express higher order moments of the uncertainty distribution - without any Gaussianity assumption - and we incorporate chance constraints that lead to expressions involving the state covariance. Furthermore, we demonstrate that by implementing our algorithm in a receding horizon fashion, we are able to compute control policies that effectively reduce the accumulation of uncertainty on the trajectory. The applicability of our method is verified through simulation results on a differential wheeled robot and a quadrotor that perform obstacle avoidance tasks., Comment: 7 pages, 3 figures, for CDC 2021

In this paper, a robust optimization framework is developed to train shallow neural networks based on reachability analysis of neural networks. To characterize noises of input data, the input training data is disturbed in the description of interval sets. Interval-based reachability analysis is then performed for the hidden layer. With the reachability analysis results, a robust optimization training method is developed in the framework of robust least-square problems. Then, the developed robust least-square problem is relaxed to a semidefinite programming problem. It has been shown that the developed robust learning method can provide better robustness against perturbations at the price of loss of training accuracy to some extent. At last, the proposed method is evaluated on a robot arm model learning example.

This paper addresses the problem of robust control of a linear discrete-time system subject to bounded disturbances and to measurement and control budget constraints. Using Q-parameterization and a polytope containment method, we prove that the co-design of an affine feedback controller, a measurement schedule and a control schedule can be exactly formulated as a mixed integer linear program with 2 binary variables per time step. As a consequence, this problem can be solved efficiently, even when an exhaustive search for measurement and control times would have been impossible in a reasonable amount of time., Published in the 60th IEEE Conference in Decision and Control (2021). 8 pages, 4 figures, 1 table

Actuator placement is a fundamental problem in control design for large-scale networks. In this paper, we study the problem of finding a set of actuator positions by minimizing a given metric, while satisfying a structural controllability requirement and a constraint on the number of actuators. We first extend the classical forward greedy algorithm for applications to graphs that are not necessarily strongly connected. We then improve this greedy algorithm by extending its horizon. This is done by evaluating the actuator position set expansions at the further steps of the classical greedy algorithm. We prove that this new method attains a better performance, when this evaluation considers the final actuator position set. Moreover, we study the problem of minimal backup placements. The goal is to ensure that the system stays structurally controllable even when any of the selected actuators goes offline, with minimum number of backup actuators. We show that this problem is equivalent to the well-studied NP-hard hitting set problem. Our results are verified by a numerical case study.

This paper presents necessary and sufficient conditions under which a linear system of relative degree either one or two is state feedback equivalent to a negative imaginary (NI) system. More precisely, we show for a class of linear time-invariant strictly proper systems, that such a system can be rendered minimal and NI using full state feedback if and only if it is controllable and weakly minimum phase. A strongly strict negative imaginary state feedback equivalence result is also provided. The NI state feedback equivalence result is then applied in a robust stabilization problem for an uncertain system with a strictly negative imaginary uncertainty., Comment: 12 pages, 2 figures

Safety is one of the fundamental problems in robotics. Recently, one-step or multi-step optimal control problems for discrete-time nonlinear dynamical system were formulated to offer tracking stability using control Lyapunov functions (CLFs) while subject to input constraints as well as safety-critical constraints using control barrier functions (CBFs). The limitations of these existing approaches are mainly about feasibility and safety. In the existing approaches, the feasibility of the optimization and the system safety cannot be enhanced at the same time theoretically. In this paper, we propose two formulations that unifies CLFs and CBFs under the framework of nonlinear model predictive control (NMPC). In the proposed formulations, safety criteria is commonly formulated as CBF constraints and stability performance is ensured with either a terminal cost function or CLF constraints. Slack variables with relaxing technique are introduced on the CBF constraints to resolve the tradeoff between feasibility and safety so that they can be enhanced at the same. The advantages about feasibility and safety of proposed formulations compared with existing methods are analyzed theoretically and validated with numerical results., Accepted to 2021 Conference on Decision and Control (CDC 2021)

In many real world problems, we are faced with the problem of selecting the best among a finite number of alternatives, where the best alternative is determined based on context specific information. In this work, we study the contextual Ranking and Selection problem under a finite-alternative-finite-context setting, where we aim to find the best alternative for each context. We use a separate Gaussian process to model the reward for each alternative, and derive the large deviations rate function for both the expected and worst-case contextual probability of correct selection. We propose the GP-C-OCBA sampling policy, which uses the Gaussian process posterior to iteratively allocate observations to maximize the rate function. We prove its consistency and show that it achieves the optimal convergence rate under the assumption of a non-informative prior. Numerical experiments show that our algorithm is highly competitive in terms of sampling efficiency, while having significantly smaller computational overhead., Comment: 25 pages, 4 figures. Preliminary version to be published at the Proceedings of the 2021 Winter Simulation Conference. Full version is currently under review

Unbalance issues in low-voltage distribution networks (LVDN) can be worsened by increasing penetration of residential PV generation if unevenly distributed among three phases. To address this issue, the phase-switching device (PSD) provides a viable and efficient method by dynamically switching customers to other phases. This paper further investigates how to optimize residential phase connections by controlling PSDs efficiently. The optimization problem is formulated as a mixed-integer non-convex programming (MINCP) problem considering relevant operational requirements of an LVDN based on the exact formulation of unbalanced three-phase optimal power flow (UTOPF). Unlike most heuristic algorithms and the linearization techniques in our previous work, this paper proposes to solve the MINCP problem via an iteration-based algorithm after exact reformulations and reasonable approximations of some constraints. The proposed method is tested in a real LVDN and compared with the approach of Zhao et al. based on the well-known linear UTOPF formulation. Case studies based on the European low-voltage test feeder demonstrate the proposed method's efficiency in mitigating the network unbalance while ensuring network security and flexibility to deal with more controllable resources., Comment: The paper has been submitted to and accepted by IEEE PES Innovative Smart Grid Technologies Conference Asia (ISGT Asia 2021)

Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics, including image segmentation, shape matching, or the computation of geodesic distances on discrete surfaces. Traditionally, the concept of a shortest path is considered for graphs with scalar edge weights, which makes it possible to compute the length of a path by adding up the individual edge weights. Yet, graphs with scalar edge weights are severely limited in their expressivity, since oftentimes edges are used to encode significantly more complex interrelations. In this work we compensate for this modelling limitation and introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges. To this end, we define a meaningful way for quantifying the path length for matrix-valued edges, and we propose a simple yet effective algorithm to compute the respective shortest path. While our formalism is universal and thus applicable to a wide range of settings in vision, graphics and beyond, we focus on demonstrating its merits in the context of 3D multi-shape analysis., published at 3DV

Actuator placement is an active field of research, which has received significant attention for its applications in complex dynamical networks. In this article, we study the problem of finding a set of actuator placements minimizing the metric that measures the average energy consumed for state transfer by the controller, while satisfying a structural controllability requirement and a cardinality constraint on the number of actuators allowed. As no computationally efficient methods are known to solve such combinatorial set function optimization problems, two greedy algorithms, forward and reverse, are proposed to obtain approximate solutions. We first show that the constraint sets these algorithms explore can be characterized by matroids. We then obtain performance guarantees for the forward and reverse greedy algorithms applied to the general class of matroid optimization problems by exploiting properties of the objective function such as the submodularity ratio and the curvature. Finally, we propose feasibility check methods for both algorithms based on maximum flow problems on certain auxiliary graphs originating from the network graph. Our results are verified with case studies over large networks. ISSN:0018-9286 ISSN:1558-2523

This paper considers linear discrete-time systems with additive disturbances, and designs a Model Predictive Control (MPC) law incorporating a dynamic feedback gain to minimise a quadratic cost function subject to a single chance constraint. The feedback gain is selected online and we provide two selection methods based on minimising upper bounds on predicted costs. The chance constraint is defined as a discounted sum of violation probabilities on an infinite horizon. By penalising violation probabilities close to the initial time and assigning violation probabilities in the far future with vanishingly small weights, this form of constraints allows for an MPC law with guarantees of recursive feasibility without a boundedness assumption on the disturbance. A computationally convenient MPC optimisation problem is formulated using Chebyshev's inequality and we introduce an online constraint-tightening technique to ensure recursive feasibility. The closed loop system is guaranteed to satisfy the chance constraint and a quadratic stability condition. With dynamic feedback gain selection, the closed loop cost is reduced and conservativeness of Chebyshev's inequality is mitigated. Also, a larger feasible set of initial conditions can be obtained. Numerical simulations are given to show these results., Comment: 15 pages, 3 figures

We present Neural Stochastic Contraction Metrics (NSCM), a new design framework for provably-stable robust control and estimation for a class of stochastic nonlinear systems. It uses a spectrally-normalized deep neural network to construct a contraction metric, sampled via simplified convex optimization in the stochastic setting. Spectral normalization constrains the state-derivatives of the metric to be Lipschitz continuous, thereby ensuring exponential boundedness of the mean squared distance of system trajectories under stochastic disturbances. The NSCM framework allows autonomous agents to approximate optimal stable control and estimation policies in real-time, and outperforms existing nonlinear control and estimation techniques including the state-dependent Riccati equation, iterative LQR, EKF, and the deterministic neural contraction metric, as illustrated in simulation results., Comment: IEEE CONTROL SYSTEMS LETTERS (L-CSS), preprint version, accepted Dec. 2020 (DOI: 10.1109/LCSYS.2020.3046529). https://ieeexplore.ieee.org/document/9302618

In recent years, the quantum computing community has seen an explosion of novel methods to implement non-trivial quantum computations on near-term hardware. An important direction of research has been to decompose an arbitrary entangled state, represented as a unitary, into a quantum circuit, that is, a sequence of gates supported by a quantum processor. It has been well known that circuits with longer decompositions and more entangling multi-qubit gates are error-prone for the current noisy, intermediate-scale quantum devices. To this end, there has been a significant interest to develop heuristic-based methods to discover compact circuits. We contribute to this effort by proposing QuantumCircuitOpt (QCOpt), a novel open-source framework which implements mathematical optimization formulations and algorithms for decomposing arbitrary unitary gates into a sequence of hardware-native gates. A core innovation of QCOpt is that it provides optimality guarantees on the quantum circuits that it produces. In particular, we show that QCOpt can find up to 57% reduction in the number of necessary gates on circuits with up to four qubits, and in run times less than a few minutes on commodity computing hardware. We also validate the efficacy of QCOpt as a tool for quantum circuit design in comparison with a naive brute-force enumeration algorithm. We also show how the QCOpt package can be adapted to various built-in types of native gate sets, based on different hardware platforms like those produced by IBM, Rigetti and Google. We hope this package will facilitate further algorithmic exploration for quantum processor designers, as well as quantum physicists.

The limitations of centralized optimization methods in managing power distribution systems operations motivate distributed control and optimization algorithms. However, the existing distributed optimization algorithms are inefficient in managing fast varying phenomena, resulting from highly variable distributed energy resources (DERs). Related online distributed control methods are equally limited in their applications. They require thousands of time-steps to track the network-level optimal solutions, resulting in slow performance. We have previously developed an online distributed controller that leverages the system's radial topology to achieve network-level optimal solutions within a few time steps. However, it requires solving a node-level nonlinear programming problem at each time step. This paper analyzes the solution space for the node-level optimization problem and derives the analytical closed-form solutions for the decision variables. The theoretical analysis of the node-level optimization problem and obtained closed-form optimal solutions eliminate the need for embedded optimization solvers at each distributed agent and significantly reduce the computational time and optimization costs.

Optimal power flow (OPF) is the fundamental mathematical model in power system operations. Improving the solution quality of OPF provide huge economic and engineering benefits. The convex reformulation of the original nonconvex alternating current OPF (ACOPF) model gives an efficient way to find the global optimal solution of ACOPF but suffers from the relaxation gaps. The existence of relaxation gaps hinders the practical application of convex OPF due to the AC-infeasibility problem. We evaluate and improve the tightness of the convex ACOPF model in this paper. Various power networks and nodal loads are considered in the evaluation. A unified evaluation framework is implemented in Julia programming language. This evaluation shows the sensitivity of the relaxation gap and helps to benchmark the proposed tightness reinforcement approach (TRA). The proposed TRA is based on the penalty function method which penalizes the power loss relaxation in the objective function of the convex ACOPF model. A heuristic penalty algorithm is proposed to find the proper penalty parameter of the TRA. Numerical results show relaxation gaps exist in test cases especially for large-scale power networks under low nodal power loads. TRA is effective to reduce the relaxation gap of the convex ACOPF model., 5 pages accepted by 2021 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT Europe)

The Opportunistic Spectrum Access (OSA) model has been developed for the secondary users (SUs) to exploit the stochastic dynamics of licensed channels for file transfer in an opportunistic manner. Common approaches to design channel sensing strategies for throughput-oriented applications tend to maximize the long-term throughput, with the hope that it provides reduced file transfer time as well. In this paper, we show that this is not correct in general, especially for small files. Unlike prior delay-related works that seldom consider the heterogeneous channel rate and bursty incoming packets, our work explicitly considers minimizing the file transfer time of a single file consisting of multiple packets in a set of heterogeneous channels. We formulate a mathematical framework for the static policy, and extend to dynamic policy by mapping our file transfer problem to the stochastic shortest path problem. We analyze the performance of our proposed static optimal and dynamic optimal policies over the policy that maximizes long-term throughput. We then propose a heuristic policy that takes into account the performance-complexity tradeoff and an extension to online implementation with unknown channel parameters, and also present the regret bound for our online algorithm. We also present numerical simulations that reflect our analytical results., The shorter version appears in WiOpt 2021

The scale of deep learning nowadays calls for efficient distributed training algorithms. Decentralized momentum SGD (DmSGD), in which each node averages only with its neighbors, is more communication efficient than vanilla Parallel momentum SGD that incurs global average across all computing nodes. On the other hand, the large-batch training has been demonstrated critical to achieve runtime speedup. This motivates us to investigate how DmSGD performs in the large-batch scenario. In this work, we find the momentum term can amplify the inconsistency bias in DmSGD. Such bias becomes more evident as batch-size grows large and hence results in severe performance degradation. We next propose DecentLaM, a novel decentralized large-batch momentum SGD to remove the momentum-incurred bias. The convergence rate for both non-convex and strongly-convex scenarios is established. Our theoretical results justify the superiority of DecentLaM to DmSGD especially in the large-batch scenario. Experimental results on a variety of computer vision tasks and models demonstrate that DecentLaM promises both efficient and high-quality training.

Rank and cardinality penalties are hard to handle in optimization frameworks due to non-convexity and discontinuity. Strong approximations have been a subject of intense study and numerous formulations have been proposed. Most of these can be described as separable, meaning that they apply a penalty to each element (or singular value) based on size, without considering the joint distribution. In this paper we present a class of non-separable penalties and give a recipe for computing strong relaxations suitable for optimization. In our analysis of this formulation we first give conditions that ensure that the globally optimal solution of the relaxation is the same as that of the original (unrelaxed) objective. We then show how a stationary point can be guaranteed to be unique under the RIP assumption (despite non-convexity of the framework).

This paper presents ConVex optimization-based Stochastic steady-state Tracking Error Minimization (CV-STEM), a new state feedback control framework for a class of Ito stochastic nonlinear systems and Lagrangian systems. Its innovation lies in computing the control input by an optimal contraction metric, which greedily minimizes an upper bound of the steady-state mean squared tracking error of the system trajectories. Although the problem of minimizing the bound is non-convex, its equivalent convex formulation is proposed utilizing state-dependent coefficient parameterizations of the nonlinear system equation. It is shown using stochastic incremental contraction analysis that the CV-STEM provides a sufficient guarantee for exponential boundedness of the error for all time with L2-robustness properties. For the sake of its sampling-based implementation, we present discrete-time stochastic contraction analysis with respect to a state- and time-dependent metric along with its explicit connection to continuous-time cases. We validate the superiority of the CV-STEM to PID, H-infinity, and baseline nonlinear controllers for spacecraft attitude control and synchronization problems., IEEE Transactions on Automatic Control, Preprint version, Oct. 2020

In distributed predictive control structures, communication among agents is required to achieve a consensus and approach an optimal global behavior. Such negotiation mechanisms are sensitive to attacks on these exchanges. This paper proposes a monitoring scheme that detects and mitigates these attacks' effects in a resource allocation framework. The performance of the proposed method is illustrated through simulations of the temperature control of multiple rooms under power scarcity.