This research extends an occupation measure framework to analyze and quantify the safety of dynamical systems. A motivating application of trajectory analysis is in peak estimation, which finds the extreme values of a state function along trajectories. Examples of peak estimation include finding the maximum height of a wave, voltage on a power line, speed of a vehicle, and infected population in an epidemic. Peak estimation can be applied towards safety quantification, such as by measuring the safety of a trajectory by its distance of closest approach to an unsafe set.
A finite-dimensional but nonconvex peak estimation problem can be converted into an infinite-dimensional linear program (LP) in measures, which is in turn bounded by a convergent sequence of semidefinite programs. The LP is posed in terms of an initial, a terminal, and an occupational measure, where the occupation measure contains all possible information about the dynamical systems’ trajectories. This research applies measure-based methods towards safety quantification (e.g. distance estimation, control effort needed to crash), hybrid systems, bounded-uncertain systems (including for data-driven analysis), stochastic systems, and time-delay systems. The modularity of this measure-based framework allows for multiple problem variations to be applied simultaneously (e.g., distance estimation under time-delays), and for optimization models to be synthesized using MATLAB. Solving these optimization problems results in certifiable guarantees on system performance and behavior.

Journal Articles

TAC

Bounding the Distance to Unsafe Sets with Convex Optimization

This work proposes an algorithm to bound the minimum distance between points on trajectories of a dynamical system and points on an unsafe set. Prior work on certifying safety of trajectories includes barrier and density methods, which do not provide a margin of proximity to the unsafe set in terms of distance. The distance estimation problem is relaxed to a Monge-Kantorovich type optimal transport problem based on existing occupation-measure methods of peak estimation. Specialized programs may be developed for polyhedral norm distances (e.g. L1 and Linfinity) and for scenarios where a shape is traveling along trajectories (e.g. rigid body motion). The distance estimation problem will be correlatively sparse when the distance objective is separable.

LCSS

Robust Data-Driven Safe Control using Density Functions

This paper presents a tractable framework for data-driven synthesis of robustly safe control laws. Given noisy experimental data and some priors about the structure of the system, the goal is to synthesize a state feedback law such that the trajectories of the closed loop system are guaranteed to avoid an unsafe set even in the presence of unknown but bounded disturbances (process noise). The main result of the paper shows that for polynomial dynamics, this problem can be reduced to a tractable convex optimization by combining elements from polynomial optimization and the theorem of alternatives. This optimization provides both a rational control law and a density function safety certificate. These results are illustrated with numerical examples.

Conference Articles

IFAC

Superstabilizing Control of Discrete-Time ARX Models under Error in Variables

This paper applies a polynomial optimization based framework towards the superstabilizing control of an Autoregressive with Exogenous Input (ARX) model given noisy data observations. The recorded input and output values are corrupted with L-infinity bounded noise where the bounds are known. This is an instance of Error in Variables (EIV) in which true internal state of the ARX system remains unknown. The consistency set of ARX models compatible with noisy data has a bilinearity between unknown plant parameters and unknown noise terms. The requirement for a dynamic compensator to superstabilize all consistent plants is expressed using polynomial nonnegativity constraints, and solved using sum-of-squares (SOS) methods in a converging hierarchy of semidefinite programs in increasing size. The computational complexity of this method may be reduced by applying a Theorem of Alternatives to eliminate the noise terms. Effectiveness of this method is demonstrated on control of example ARX models.

Preprints

Quantifying the Safety of Trajectories using Peak-Minimizing Control

This work quantifies the safety of trajectories of a dynamical system by the perturbation intensity required to render a system unsafe (crash into the unsafe set). Computation of this measure of safety is posed as a peak-minimizing optimal control problem. Convergent lower bounds on the minimal peak value of controller effort are computed using polynomial optimization and the moment-Sum-of-Squares hierarchy. The crash-safety framework is extended towards data-driven safety analysis by measuring safety as the maximum amount of data corruption required to crash into the unsafe set.

Peak Value-at-Risk Estimation for Stochastic Differential Equations using Occupation Measures

This paper proposes an algorithm to upper-bound maximal quantile statistics of a state function over the course of a Stochastic Differential Equation (SDE) system execution. This chance-peak problem is posed as a nonconvex program aiming to maximize the Value-at-Risk (VaR) of a state function along SDE state distributions. The VaR problem is upper-bounded by an infinite-dimensional Second-Order Cone Program in occupation measures through the use of one-sided Cantelli or Vysochanskii-Petunin inequalities. These upper bounds on the true quantile statistics may be approximated from above by a sequence of Semidefinite Programs in increasing size using the moment-Sum-of-Squares hierarchy when all data is polynomial. Effectiveness of this approach is demonstrated on example stochastic polynomial dynamical systems.

Peak Estimation of Time Delay Systems using Occupation Measures

This work proposes a method to compute the maximum value obtained by a state function along trajectories of a Delay Differential Equation (DDE). An example of this task is finding the maximum number of infected people in an epidemic model with a nonzero incubation period. The variables of this peak estimation problem include the stopping time and the original history (restricted to a class of admissible histories). The original nonconvex DDE peak estimation problem is approximated by an infinite-dimensional Linear Program (LP) in occupation measures, inspired by existing measure-based methods in peak estimation and optimal control. This LP is approximated from above by a sequence of Semidefinite Programs (SDPs) through the moment-Sum of Squares (SOS) hierarchy. Effectiveness of this scheme in providing peak estimates for DDEs is demonstrated with provided examples.

Data-Driven Control of Positive Linear Systems using Linear Programming

This paper presents a linear-programming based algorithm to perform data-driven stabilizing control of linear positive systems. A set of state-input-transition observations is collected up to magnitude-bounded noise. A state feedback controller and dual linear copositive Lyapunov function are created such that the set of all data-consistent plants is contained within the set of all stabilized systems. This containment is certified through the use of the Extended Farkas Lemma and solved via Linear Programming. Sign patterns and sparsity structure for the controller may be imposed using linear constraints. The complexity of this algorithm scales in a polynomial manner with the number of states and inputs. Effectiveness is demonstrated on example systems.

Peak Estimation of Hybrid Systems with Convex Optimization

Peak estimation of hybrid systems aims to upper bound extreme values of a state function along trajectories, where this state function could be different in each subsystem. This finite-dimensional but nonconvex problem may be lifted into an infinite-dimensional linear program (LP) in occupation measures with an equal objective under mild finiteness/compactness and smoothness assumptions. This LP may in turn be approximated by a convergent sequence of upper bounds attained from solutions of Linear Matrix Inequalities (LMIs) using the Moment-Sum-of-Squares hierarchy. The peak estimation problem is extended to problems with uncertainty and safety settings, such as measuring the distance of closest approach between points along hybrid system trajectories and unsafe sets.

Analysis and Control of Input-Affine Dynamical Systems using Infinite-Dimensional Robust Counterparts

Input-affine dynamical systems often arise in control and modeling scenarios, such as the data-driven case when state-derivative observations are recorded under bounded noise.
Common tasks in system analysis and control include optimal control, peak estimation, reachable set estimation, and maximum control invariant set estimation. Existing work poses these types of problems as infinite-dimensional linear programs in auxiliary functions with sum-of-squares tightenings. The bottleneck in most of these programs is the Lie derivative nonnegativity constraint posed over the time-state-control set. Decomposition techniques to improve tractability by eliminating the control variables include vertex decompositions (switching), or facial decompositions in the case where the polytopic set is a scaled box. This work extends the box-facial decomposition technique to allow for a robust-counterpart decomposition of semidefinite representable sets (e.g. polytopes, ellipsoids, and projections of spectahedra). These robust counterparts are proven to be equivalent to the original Lie constraint under mild compactness and regularity constraints. Efficacy is demonstrated under peak/distance/reachable set data-driven analysis problems and Region of Attraction maximizing control.

2022

Journal Articles

LCSS

Data-Driven Gain Scheduling Control of Linear Parameter-Varying Systems using Quadratic Matrix Inequalities

This paper synthesizes a gain-scheduled controller to stabilize all possible Linear Parameter-Varying (LPV) plants that are consistent with measured input/state data records. Inspired by prior work in data informativity and LTI stabilization, a set of Quadratic Matrix Inequalities is developed to represent the noise set, the class of consistent LPV plants, and the class of stabilizable plants. The bilinearity between unknown plants and ‘for all’ parameters is avoided by vertex enumeration of the parameter set. Effectiveness and computational tractability of this method is demonstrated on example systems.

AUT

Decomposed structured subsets for semidefinite and sum-of-squares optimization

Semidefinite programs (SDPs) are standard convex problems that are frequently found in control and optimization applications. Interior-point methods can solve SDPs in polynomial time up to arbitrary accuracy, but scale poorly as the size of matrix variables and the number of constraints increases. To improve scalability, SDPs can be approximated with lower and upper bounds through the use of structured subsets (e.g., diagonally-dominant and scaled-diagonally dominant matrices). Meanwhile, any underlying sparsity or symmetry structure may be leveraged to form an equivalent SDP with smaller positive semidefinite constraints. In this paper, we present a notion of decomposed structured subsets to approximate an SDP with structured subsets after an equivalent conversion. The lower/upper bounds found by approximation after conversion become tighter than the bounds obtained by approximating the original SDP directly. We apply decomposed structured subsets to semidefinite and sum-of-squares optimization problems with examples of H∞ norm estimation and constrained polynomial optimization. An existing basis pursuit method is adapted into this framework to iteratively refine bounds.

Conference Articles

CDC

Bounding the Distance of Closest Approach to Unsafe Sets with Occupation Measures

This paper presents a method to lower-bound the distance of closest approach between points on an unsafe set and points along system trajectories. Such a minimal distance is a quantifiable and interpretable certificate of safety of trajectories, as compared to prior art in barrier and density methods which offers a binary indication of safety/unsafety. The distance estimation problem is converted into a infinite-dimensional linear program in occupation measures based on existing work in peak estimation and optimal transport. The moment-SOS hierarchy is used to obtain a sequence of lower bounds obtained through solving Linear Matrix Inequalities in increasing size, and these lower bounds will converge to the true minimal distance as the degree approaches infinity under mild conditions (e.g. Lipschitz dynamics, compact sets)

CDC

Assessing the Quality of a Set of Basis Functions for Inverse Optimal Control via Projection onto Global Minimizers

Inverse optimization (Inverse optimal control) is the task
of imputing a cost function such that given test points (trajectories) are (nearly) optimal with respect to the discovered cost. Prior methods in inverse optimization assume that the true cost is a convex combination of a set of convex basis functions and that this basis is consistent with the test points. However, the consistency assumption is not always justified, as in many applications the principles by which the data is generated are not well understood. This work proposes using the distance between a test point and the set of global optima generated by the convex combinations of the convex basis functions as a measurement for the expressive quality of the basis with respect to the test point. A large minimal distance invalidates the set of basis functions. The concept of a set of global optima is introduced and its properties are explored in unconstrained and constrained settings. Upper and lower bounds for the minimum distance in the convex quadratic setting are implemented by bi-level gradient descent and an enriched linear matrix inequality respectively. Extensions to this framework include max-representable basis functions, nonconvex basis functions (local minima), and applying polynomial optimization techniques.

CDC

Data-Driven Superstabilizing Control of Error-in-Variables
Discrete-Time Linear Systems

This paper proposes a method to find super-stabilizing controllers for discrete-time linear systems that are
consistent with a set of corrupted observations. The L-infinity bounded measurement noise introduces a bilinearity between the unknown plant parameters and noise terms. A super-stabilizing controller may be found by solving a feasibility problem involving a set of polynomial nonnegativity constraints in terms of the unknown plant parameters and noise terms. A sequence of sum-of-squares (SOS) programs in rising degree will yield a super-stabilizing controller if such a controller exists. Unfortunately, these SOS programs exhibit very poor scaling as the degree increases. A theorem of alternatives is employed to yield equivalent, convergent (under mild conditions), and more computationally tractable SOS programs.

ROCOND

Facial Input Decompositions for Robust Peak Estimation under Polyhedral Uncertainty

This work bounds extreme values of state functions for a class of input-affine continuous-time systems that are affected by polyhedral-bounded uncertainty. Instances of these systems may arise in data-driven peak estimation, in which the state function must be bounded for all systems that are consistent with a set of state-derivative data records corrupted under L-infinity bounded noise. Existing occupation measure-based methods form a convergent sequence of outer approximations to the true peak value, given an initial set, by solving a hierarchy of semidefinite programs in increasing size. These techniques scale combinatorially in the number of state variables and uncertain parameters. We present tractable algorithms for peak estimation that scale linearly in the number of faces of the uncertainty-bounding polytope rather than combinatorially in the number of uncertain parameters by leveraging convex duality and a theorem of alternatives (facial decomposition). The sequence of decomposed semidefinite programs will converge to the true peak value under mild assumptions (convergence and smoothness of dynamics).

Preprints

SAIF: Sparse Adversarial and Interpretable Attack Framework

Adversarial attacks hamper the decision-making ability of neural networks by perturbing the input signal. The addition of calculated small distortion to images, for instance, can deceive a well-trained image classification network. In this work, we propose a novel attack technique called Sparse Adversarial and Interpretable Attack Framework (SAIF). Specifically, we design imperceptible attacks that contain low-magnitude perturbations at a small number of pixels and leverage these sparse attacks to reveal the vulnerability of classifiers. We use the Frank-Wolfe (conditional gradient) algorithm to simultaneously optimize the attack perturbations for bounded magnitude and sparsity with O(1/sqrt(T)) convergence. Empirical results show that SAIF computes highly imperceptible and interpretable adversarial examples, and outperforms state-of-the-art sparse attack methods on the ImageNet dataset.

Data-Driven Stabilizing and Robust Control of Discrete-Time Linear Systems with Error in Variables

This work presents a sum-of-squares (SOS) based framework to perform data-driven stabilization and robust control tasks on discrete-time linear systems where the full-state observations are corrupted by L-infinity bounded measurement noise (error in variable setting). Certificates of state-feedback superstability or quadratic stability of all plants in a consistency set are provided by solving a feasibility program formed by polynomial nonnegativity constraints. Under mild compactness and data-collection assumptions, SOS tightenings in rising degree will converge to recover the true superstabilizing controller, with slight conservatism introduced for quadratic stabilizability. The performance of this SOS method is improved through the application of a theorem of alternatives while retaining tightness, in which the unknown noise variables are eliminated from the consistency set description. This SOS feasibility method is extended to provide worst-case-optimal robust controllers under H2 control costs. The consistency set description may be broadened to include cases where the data and process are affected by a combination of L-infinity bounded measurement, process, and input noise. Further generalizations include varying noise sets, non-uniform sampling, and switched systems stabilization.

Peak Estimation aims to find the maximum value of a state function achieved by a dynamical system. This problem has been previously cast as a convex infinite-dimensional linear program on occupation measures, which can be approximately solved by a converging hierarchy of moment relaxations. In this letter, we present an algorithm to approximate optimal trajectories if the solutions to these relaxations satisfy rank constraints. We also extend peak estimation to maximin and safety analysis problems, providing a certificate that trajectories are bounded away from an unsafe set.

LCSS

Mediating Ribosomal Competition by Splitting Pools

Synthetic biology constructs often rely upon the introduction of “circuit” genes into host cells, in order to express novel proteins and thus endow the host with a desired behavior. The expression of these new genes “consumes” existing resources in the cell, such as ATP, RNA polymerase, amino acids, and ribosomes. Ribosomal competition among strands of mRNA may be described by a system of nonlinear ODEs called the Ribosomal Flow Model (RFM). The competition for resources between host and circuit genes can be ameliorated by splitting the ribosome pool by use of orthogonal ribosomes, where the circuit genes are exclusively translated by mutated ribosomes. In this work, the RFM system is extended to include orthogonal ribosome competition. This Orthogonal Ribosomal Flow Model (ORFM) is proven to be stable through the use of Robust Lyapunov Functions. The optimization problem of maximizing the weighted protein translation rate by adjusting allocation of ribosomal species is formulated.

Conference Articles

CDC

Peak Estimation for Uncertain and Switched Systems

Peak estimation bounds extreme values of a function of state along trajectories of a dynamical system. This paper focuses on extending peak estimation to continuous and discrete settings with time-independent and time-dependent uncertainty. Techniques from optimal control are used to incorporate uncertainty into an existing occupation measure-based peak estimation framework, which includes special consideration for handling switching uncertainties. The resulting infinite-dimensional linear programs can be solved approximately with Linear Matrix Inequalities arising from the moment-SOS hierarchy.

2020

Conference Articles

IFAC

Decomposed Structured Subsets for Semidefinite Optimization

Semidefinite programs (SDPs) are important computational tools in controls, optimization, and operations research. Standard interior-point methods scale poorly for solving large-scale SDPs. With certain compromise of solution quality, one method for scalability is to use the notion of structured subsets (e.g. diagonally-dominant (DD) and scaled-diagonally dominant (SDD) matrices), to derive inner/outer approximations for SDPs. For sparse SDPs, chordal decomposition techniques have been widely used to derive equivalent SDP reformations with smaller PSD constraints. In this paper, we investigate a notion of decomposed structured subsets by combining chordal decomposition with DD/SDD approximations. This notion takes advantage of any underlying sparsity via chordal decomposition, while embracing the scalability of DD/SDD approximations. We discuss the applications of decomposed structured subsets to semidefinite optimization. Basis pursuit for refining DD/SDD approximations are also incorporated into the decomposed structured subset framework, and numerical performance is improved as compared to standard DD/SDD approximations. These results are demonstrated on H∞ norm estimation problems for networked systems.

CDC

MIMO System Identification by Randomized Active-Set Methods

MIMO (multi-input multi-output) system identification is a particular instance of a parsimonious model selection problem. If the observed data is assumed to arise from a stable and low order plant, then the representing model should also be stable and have few poles in its realization. These constraints are challenging to impose in an L 1 or nuclear norm framework, especially when observations are non-uniformly sampled. This paper implements MIMO identification by randomized active-set methods, as realized by Fully Corrective Frank-Wolfe (FCFW). Reweighting pole-group penalties allow for further system sparsification while monotonically decreasing the regularized fitting error. Efficacy of the approach is shown on two examples.

Kernel dimensionality reduction (KDR) algorithms find a low dimensional representation of the original data by optimizing kernel dependency measures that are capable of capturing nonlinear relationships. The standard strategy is to first map the data into a high dimensional feature space using kernels prior to a projection onto a low dimensional space. While KDR methods can be easily solved by keeping the most dominant eigenvectors of the kernel matrix, its features are no longer easy to interpret. Alternatively, Interpretable KDR (IKDR) is different in that it projects onto a subspace before the kernel feature mapping, therefore, the projection matrix can indicate how the original features linearly combine to form the new features. Unfortunately, the IKDR objective requires a non-convex manifold optimization that is difficult to solve and can no longer be solved by eigendecomposition. Recently, an efficient iterative spectral (eigendecomposition) method (ISM) has been proposed for this objective in the context of alternative clustering. However, ISM only provides theoretical guarantees for the Gaussian kernel. This greatly constrains ISM’s usage since any kernel method using ISM is now limited to a single kernel. This work extends the theoretical guarantees of ISM to an entire family of kernels, thereby empowering ISM to solve any kernel method of the same objective. In identifying this family, we prove that each kernel within the family has a surrogate Φ matrix and the optimal projection is formed by its most dominant eigenvectors. With this extension, we establish how a wide range of IKDR applications across different learning paradigms can be solved by ISM. To support reproducible results, the source code is made publicly available on [code].

CCTA

A Model of Heave Dynamics for Bagged Air Cushioned Vehicles

This paper presents a simple model of the heave (up-and-down) dynamics of an air cushioned vehicle. A set of nonlinear differential equations are extended to the case of a bagged air skates using a Forchheimer porosity approximation. The model exhibits stability under atmospheric pressure, and a tendency towards instability in near-vacuum conditions. Inner estimates of regions of attractions are found to verify stability in atmosphere, and track simulation shows system disturbance rejection under a drifting subtrack height and gaps.

CCTA

Domain Adaptation Based Fault Detection in Label Imbalanced Cyberphysical Systems

In this paper we propose a data-driven fault detection framework for semi-supervised scenarios where labeled training data from the system under consideration (the “target”) is imbalanced (e.g. only relatively few labels are available from one of the classes), but data from a related system (the “source”) is readily available. An example of this situation is when a generic simulator is available, but needs to be tuned on a case-by-case basis to match the parameters of the actual system. The goal of this paper is to work with the statistical distribution of the data without necessitating system identification. Our main result shows that if the source and target domain are related by a linear transformation (a common assumption in domain adaptation), the problem of designing a classifier that minimizes a miss-classification loss over the joint source and target domains reduces to a convex optimization subject to a single (non-convex) equality constraint. This second-order equality constraint can be recast as a rank-1 optimization problem, where the rank constraint can be efficiently handled through a reweighted nuclear norm surrogate. These results are illustrated with a practical application: fault detection in additive manufacturing (industrial 3D printing). The proposed method is able to exploit simulation data (source domain) to substantially outperform classifiers tuned using only data from a single domain.

CDC

Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering

Semidefinite programs (SDPs) often arise in relaxations of some NP-hard problems, and if the solution of the SDP obeys certain rank constraints, the relaxation will be tight. Decomposition methods based on chordal sparsity have already been applied to speed up the solution of sparse SDPs, but methods for dealing with rank constraints are underdeveloped. This paper leverages a minimum rank completion result to decompose the rank constraint on a single large matrix into multiple rank constraints on a set of smaller matrices. The re-weighted heuristic is used as a proxy for rank, and the specific form of the heuristic preserves the sparsity pattern between iterations. Implementations of rank-minimized SDPs through interior-point and first-order algorithms are discussed. The problem of subspace clustering is used to demonstrate the computational improvement of the proposed method.