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.
@inproceedings{miller2022eivarx,doi={10.48550/ARXIV.2210.14893},url={https://arxiv.org/abs/2210.14893},html={https://arxiv.org/abs/2210.14893},author={Miller, Jared and Dai, Tianyu and Sznaier, Mario},title={{Superstabilizing Control of Discrete-Time ARX Models under Error in Variables}},publisher={arXiv},booktitle={22nd IFAC World Congress (upcoming)},year={2023},archiveprefix={arXiv},primaryclass={math.OC},tag={ddc},abbr={IFAC},note={arXiv: 2210.14893},arxiv={2210.14893},selected={false},bibtex_show={true},code={https://github.com/Jarmill/eiv_arx}}
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.
@preprint{miller2023crash,title={{Quantifying the Safety of Trajectories using Peak-Minimizing Control}},author={Miller, Jared and Sznaier, Mario},year={2023},eprint={2303.11896},archiveprefix={arXiv},tag={peakddc},primaryclass={math.OC},bibtex_show={true},url={https://arxiv.org/abs/2303.11896},html={https://arxiv.org/abs/2303.11896},code={https://github.com/Jarmill/crash-safety}}
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.
@preprint{miller2023delay,title={Peak Estimation of Time Delay Systems using Occupation Measures},author={Miller, Jared and Korda, Milan and Magron, Victor and Sznaier, Mario},year={2023},tag={peak},slides={Time_Delay_Presentation__NYU.pdf},eprint={2303.12863},archiveprefix={arXiv},primaryclass={math.OC},code={https://github.com/Jarmill/timedelay},bibtex_show={true},url={https://arxiv.org/abs/2303.12863},html={https://arxiv.org/abs/2303.12863},arxiv={https://arxiv.org/abs/2303.12863}}
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.
@preprint{miller2023ddcpos,title={{Data-Driven Control of Positive Linear Systems using Linear Programming}},author={Miller, Jared and Dai, Tianyu and Sznaier, Mario and Shafai, Bahram},year={2023},eprint={2303.12242},archiveprefix={arXiv},primaryclass={math.OC},bibtex_show={true},url={https://arxiv.org/abs/2303.12242},arxiv={https://arxiv.org/abs/2303.12242},html={https://arxiv.org/abs/2303.12242},code={https://github.com/Jarmill/data_driven_pos},tag={ddc}}
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.
@preprint{miller2023hybrid,title={{Peak Estimation of Hybrid Systems with Convex Optimization}},author={Miller, Jared and Sznaier, Mario},year={2023},eprint={2303.11490},archiveprefix={arXiv},url={https://arxiv.org/abs/2303.11490},html={https://arxiv.org/abs/2303.11490},arxiv={https://arxiv.org/abs/2303.11490},tag={peak},primaryclass={math.OC},code={https://github.com/Jarmill/hybrid_peak_est},bibtex_show={true}}
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.
@preprint{miller2023robustcounterpart,title={Analysis and Control of Input-Affine Dynamical Systems using Infinite-Dimensional Robust Counterparts},author={Miller, Jared and Sznaier, Mario},year={2023},eprint={2112.14838},url={https://arxiv.org/abs/2112.14838},html={https://arxiv.org/abs/2112.14838},archiveprefix={arXiv},primaryclass={math.OC},tag={peakddc},bibtex_show={true},slides={SIAM_data_driven.pdf},code={https://github.com/Jarmill/data_driven_occ},selected={true}}
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.
@preprint{zheng2023robustsafety,title={{Robust Data-Driven Safe Control using Density Functions}},author={Zheng, Jian and Dai, Tianyu and Miller, Jared and Sznaier, Mario},year={2023},eprint={2303.09004},arxiv={2303.09004},archiveprefix={arXiv},primaryclass={math.OC},url={https://arxiv.org/abs/2303.09004},html={https://arxiv.org/abs/2303.09004},tag={ddc},selected={false},bibtex_show={true},code={https://github.com/J-mzz/ddc-safety}}
2022
Journal Articles
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.
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.
@article{miller2022lpvqmi,title={{Data-Driven Gain Scheduling Control of Linear Parameter-Varying Systems using Quadratic Matrix Inequalities}},author={Miller, Jared and Sznaier, Mario},year={2022},abbr={LCSS},pdf={LPVQMI_LCSS.pdf},eprint={2209.06251},archiveprefix={arXiv},primaryclass={math.OC},tag={ddc},bibtex_show={true},journal={IEEE Control Systems Letters},doi={10.1109/LCSYS.2022.3227182},url={https://ieeexplore.ieee.org/abstract/document/9971732},html={https://ieeexplore.ieee.org/abstract/document/9971732},code={https://github.com/Jarmill/lpv_qmi},arxiv={2209.06251},selected={true}}
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).
@inproceedings{miller2022facial_short,title={{Facial Input Decompositions for Robust Peak Estimation under Polyhedral Uncertainty}},journal={IFAC-PapersOnLine},volume={55},number={25},pages={55-60},year={2022},tag={peakddc},slides={ROCOND_Data_Driven_Presentation.pdf},booktitle={10th IFAC Symposium on Robust Control Design (ROCOND)},issn={2405-8963},doi={https://doi.org/10.1016/j.ifacol.2022.09.323},url={https://www.sciencedirect.com/science/article/pii/S2405896322015750},html={https://www.sciencedirect.com/science/article/pii/S2405896322015750},author={Miller, Jared and Sznaier, Mario},keywords={Robust Optimization in Control, Uncertain Systems, Sum-of-Squares, Computational Methods in Control, Safety Certificates},abbr={ROCOND},code={https://github.com/Jarmill/data_driven_occ},bibtex_show={true}}
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.
@preprint{imtiaz2022saif,doi={10.48550/ARXIV.2212.07495},url={https://arxiv.org/abs/2212.07495},arxiv={2212.07495},note={arXiv: 2212.07495},archiveprefix={arXiv},primaryclass={cs.CV},author={Imtiaz, Tooba and Kohler, Morgan and Miller, Jared and Wang, Zifeng and Sznaier, Mario and Camps, Octavia and Dy, Jennifer},keywords={Computer Vision and Pattern Recognition (cs.CV), FOS: Computer and information sciences, FOS: Computer and information sciences},pdf={SAIF_arxiv.pdf},title={SAIF: Sparse Adversarial and Interpretable Attack Framework},bibtex_show={true},publisher={arXiv},year={2022},copyright={arXiv.org perpetual, non-exclusive license}}
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.
@preprint{miller2022eiv,title={Data-Driven Stabilizing and Robust Control of Discrete-Time Linear Systems with Error in Variables},author={Miller, Jared and Dai, Tianyu and Sznaier, Mario},year={2022},eprint={2210.13430},arxiv={2210.13430},archiveprefix={arXiv},tag={ddc},primaryclass={math.OC},note={arXiv: 2210.13430},bibtex_show={true},code={https://github.com/jarmill/error_in_variables},pdf={Noise_in_Variable__Journal_Arxiv.pdf},selected={true}}
Time-Frequency Regularized Overlapping Group Shrinkage
Epstein, Alexander, Magre, Nimish, and Miller, Jared
In this work, we denoise speech samples using predetermined structural knowledge of decomposable convex optimization problems. To this end, we exploit the grouping/clustering property observed with speech spectrograms to iteratively obtain a sparse clean speech signal using a mixed norm penalty term. We build upon the Overlapping Group Shrinkage (OGS) algorithm and introduce time-frequency weights to the cost function to rid the sparse clean signal of the residual noise. These time-frequency weighting extensions are also empirically shown to effectively handle impulsive noise types. The time-frequency weights may be targeted to suppress specific noise types at desired time slices to further improve the performance of the algorithm.
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.
@article{miller2020recovery,author={Miller, Jared and Henrion, Didier and Sznaier, Mario},journal={IEEE Control Systems Letters},title={{Peak Estimation Recovery and Safety Analysis}},year={2021},volume={5},number={6},tag={peak},pages={1982-1987},doi={10.1109/LCSYS.2020.3047591},abbr={LCSS},url={https://ieeexplore.ieee.org/document/9308943},html={https://ieeexplore.ieee.org/document/9308943},pdf={peak_recovery_arxiv.pdf},code={https://github.com/jarmill/peak/},bibtex_show={true},slides={CDC_peak_recovery.pdf}}
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.
@article{miller2020ribosome,author={Miller, Jared and Al-Radhawi, Muhammad Ali and Sontag, Eduardo Daniel},journal={IEEE Control Systems Letters},title={{Mediating Ribosomal Competition by Splitting Pools}},year={2021},volume={5},number={5},tag={ribosome},pages={1555-1560},doi={10.1109/LCSYS.2020.3041213},abbr={LCSS},url={https://ieeexplore.ieee.org/document/9483415},html={https://ieeexplore.ieee.org/document/9483415},pdf={mediating_ribosomes.pdf},code={https://gitlab.com/jarmill/Ribosomes},bibtex_show={true},slides={ACC_Ribosome_3.pptx}}
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.
@inproceedings{miller2021uncertain,author={Miller, Jared and Henrion, Didier and Sznaier, Mario and Korda, Milan},booktitle={60th IEEE Conference on Decision and Control (CDC)},title={{Peak Estimation for Uncertain and Switched Systems}},year={2021},volume={},number={},tag={peak},pages={3222-3228},doi={10.1109/CDC45484.2021.9683778},slides={CDC_uncertain.pdf},abbr={CDC},url={https://ieeexplore.ieee.org/document/9683778},html={https://ieeexplore.ieee.org/document/9683778},pdf={peak_uncertain_arxiv.pdf},code={https://github.com/jarmill/peak/},selected={true},bibtex_show={true}}
Preprints
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.
@preprint{miller2021distance,title={{Bounding the Distance to Unsafe Sets with Convex Optimization}},author={Miller, Jared and Sznaier, Mario},year={2021},eprint={2110.14047},archiveprefix={arXiv},primaryclass={math.OC},tag={peak},note={arXiv: 2110.14047},url={https://arxiv.org/abs/2110.14047},pdf={distance_arxiv.pdf},code={https://github.com/Jarmill/distance},bibtex_show={true},slides={Distance_CDC_Presentation.pdf},arxiv={2110.14047},selected={true}}
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.
@inproceedings{miller2020decomposed,author={Miller, Jared and Zheng, Yang and Sznaier, Mario and Papachristodoulou, Antonis},booktitle={21st IFAC World Congress},title={{Decomposed Structured Subsets for Semidefinite Optimization}},year={2020},bibtex_show={true},volume={},number={},tag={sparsity},abbr={IFAC},url={https://www.sciencedirect.com/science/article/pii/S2405896320316645},html={https://www.sciencedirect.com/science/article/pii/S2405896320316645},slides={IFAC_decomposed.pdf},poster={IPAM_decomposed_poster.pdf}}
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.
@inproceedings{miller2020mimo,author={Miller, Jared and Singh, Rajiv and Sznaier, Mario},booktitle={59th IEEE Conference on Decision and Control (CDC)},title={{MIMO System Identification by Randomized Active-Set Methods}},year={2020},volume={},number={},tag={mimo},pages={2246-2251},doi={10.1109/CDC42340.2020.9304402},code={https://github.com/Jarmill/mimoBB},url={https://ieeexplore.ieee.org/abstract/document/9304402},html={https://ieeexplore.ieee.org/abstract/document/9304402},abbr={CDC},bibtex_show={true}}
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].
@inproceedings{wu2019ism,author={Wu, Chieh and Miller, Jared and Chang, Yale and Sznaier, Mario and Dy, Jennifer},booktitle={Advances in Neural Information Processing Systems},editor={Wallach, H. and Larochelle, H. and Beygelzimer, A. and d\textquotesingle Alch\'{e}-Buc, F. and Fox, E. and Garnett, R.},pages={7915--7925},publisher={Curran Associates Inc.},title={{Solving Interpretable Kernel Dimensionality Reduction}},url={https://proceedings.neurips.cc/paper/2019/file/61f3a6dbc9120ea78ef75544826c814e-Paper.pdf},html={https://proceedings.neurips.cc/paper/2019/file/61f3a6dbc9120ea78ef75544826c814e-Paper.pdf},slides={ISM presentation.pdf},bibtex_show={true},abbr={NeurIPS},code={https://github.com/endsley/Interpretable_Kernel_Dim_Reduction},pdf={ism_arxiv.pdf},poster={ISM_NIPS2019.pdf},volume={32},year={2019}}
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.
@inproceedings{miller2019acv,author={Miller, Jared and Shafai, Bahram},booktitle={IEEE Conference on Control Technology and Applications (CCTA)},title={{A Model of Heave Dynamics for Bagged Air Cushioned Vehicles}},year={2019},volume={},number={},tag={acv},pages={976-981},doi={10.1109/CCTA.2019.8920508},url={https://ieeexplore.ieee.org/document/8920508},html={https://ieeexplore.ieee.org/document/8920508},bibtex_show={true},slides={CCTA_ACV_Levitation.pdf},abbr={CCTA}}
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.
@inproceedings{taskazan2019domain,author={Taskazan, Beg\"{u}m and Miller, Jared and Inyang-Udoh, Uduak and Camps, Octavia and Sznaier, Mario},booktitle={IEEE Conference on Control Technology and Applications (CCTA)},title={{Domain Adaptation Based Fault Detection in Label Imbalanced Cyberphysical Systems}},year={2019},volume={},number={},tag={sparsity},pages={142-147},doi={10.1109/CCTA.2019.8920608},abbr={CCTA},bibtex_show={true},url={https://ieeexplore.ieee.org/abstract/document/8920608},html={https://ieeexplore.ieee.org/abstract/document/8920608}}
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.
@inproceedings{miller2019rank,author={Miller, Jared and Zheng, Yang and Roig-Solvas, Biel and Sznaier, Mario and Papachristodoulou, Antonis},booktitle={IEEE 58th Conference on Decision and Control (CDC)},title={{Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering}},year={2019},volume={},number={},tag={sparsity},pages={4916-4921},doi={10.1109/CDC40024.2019.9029620},url={https://ieeexplore.ieee.org/document/9029620},html={https://ieeexplore.ieee.org/document/9029620},abbr={CDC},bibtex_show={true},poster={l4dc_poster_rank.pdf}}