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 input, measurement, and process noise (error in variable setting). Certificates of full-state-feedback robust performance, superstabilization or quadratic stabilization 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 worst-case optimal L-infinity (extended) superstabilizing controllers. With some conservatism, quadratically stabilizing controllers with certified H2 performance bounds can also be found. 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.
@article{miller2024eiv,author={Miller, Jared and Dai, Tianyu and Sznaier, Mario},journal={IEEE Transactions on Automatic Control},title={{Robust Data-Driven Control of Discrete-Time Linear Systems with Errors in Variables}},year={2024},volume={},number={},pages={1-15},abbr={TAC},bibtex_show={true},code={https://github.com/jarmill/error_in_variables},keywords={Noise;Symmetric matrices;Polynomials;Noise measurement;Linear matrix inequalities;Process control;Linear systems;Data-Driven Control;Robust Control;Optimization;Linear Matrix Inequality;Sum of Squares},url={https://ieeexplore.ieee.org/document/10643715},href={https://ieeexplore.ieee.org/document/10643715},html={https://ieeexplore.ieee.org/document/10643715},selected={true},tag={ddc},slides={EIV_Presentation__Austin.pdf},arxiv={2210.13430},doi={10.1109/TAC.2024.3447809}}
LCSS
Data-Driven Superstabilizing Control under Quadratically-Bounded Errors-in-Variables Noise
The Error-in-Variables model of system identification/control involves nontrivial input and measurement corruption of observed data, resulting in generically nonconvex optimization problems. This paper performs full-state-feedback stabilizing control of all discrete-time linear systems that are consistent with observed data for which the input and measurement noise obey quadratic bounds. Instances of such quadratic bounds include elementwise norm bounds (at each time sample), energy bounds (across the entire signal), and chance constraints arising from (sub)gaussian noise. Superstabilizing controllers are generated through the solution of a sum-of-squares hierarchy of semidefinite programs. A theorem of alternatives is employed to eliminate the input and measurement noise process, thus improving tractability. Effectiveness of the scheme is generated on an example system in the chance-constrained set-membership setting where the input and state-measurement noise are i.i.d. normally distributed.
EJC
Peak Estimation of Rational Systems using Convex Optimization
This paper presents algorithms that upper-bound the peak value of a state function along trajectories of a continuous-time system with rational dynamics. The finite-dimensional but nonconvex peak estimation problem is cast as a convex infinite-dimensional linear program in occupation measures. This infinite-dimensional program is then truncated into finite-dimensions using the moment-Sum-of-Squares (SOS) hierarchy of semidefinite programs. Prior work on treating rational dynamics using the moment-SOS approach involves clearing dynamics to common denominators or by adding lifting variables to handle reciprocal terms under new equality constraints. Our solution method uses a sum-of-rational method based on absolute continuity of measures. The Moment-SOS truncations of our program possess lower computational complexity and (empirically demonstrated) higher accuracy of upper bounds on example systems as compared to prior approaches.
@article{miller2023rational,title={{Peak Estimation of Rational Systems using Convex Optimization}},author={Miller, Jared and Smith, Roy S.},year={2024},arxiv={2311.08321},journal={European Journal of Control},pages={101088},issn={0947-3580},doi={https://doi.org/10.1016/j.ejcon.2024.101088},url={https://www.sciencedirect.com/science/article/pii/S0947358024001481},html={https://www.sciencedirect.com/science/article/pii/S0947358024001481},abbr={EJC},bibtex_show={true},publisher={Elsevier},tag={peak},code={http://doi.org/10.5905/ethz-1007-711}}
LCSS
Data-Driven Safe Control of Discrete-Time Non-Linear Systems
This letter proposes a framework to perform verifiably safe control of all discrete-time non-linear systems that are compatible with collected data. Most safety-maintaining control synthesis algorithms (e.g., control barrier functions, density functions) are limited to obtaining theoretical guarantees of safety in continuous-time, even while their implementation on real systems is typically in discrete-time. We first present a sum-of-squares based program to prove the existence of an (acausal) control policy that can safely stabilize all possible data-consistent systems. Causal control policies may be extracted by online optimization, and we provide sufficient conditions for the extraction of this control policy in general scenarios. As a specific case, we introduce a method for tractable online controller recovery when convexity assumptions are imposed on the candidate Lyapunov function and safety region descriptor. Discrete-time safe stabilization is demonstrated on three example systems.
@article{zheng2024ddcdiscrete,author={Zheng, Jian and Miller, Jared and Sznaier, Mario},journal={IEEE Control Systems Letters},title={{Data-Driven Safe Control of Discrete-Time Non-Linear Systems}},year={2024},volume={8},number={},pages={1553-1558},keywords={Safety;Polynomials;Lyapunov methods;Trajectory;Vectors;Stability criteria;Asymptotic stability;Data-driven control;Discrete-time systems;Nonlinear Systems;Safety;Stability;Sum-of-Squares},html={https://ieeexplore.ieee.org/document/10554661},url={https://ieeexplore.ieee.org/document/10554661},bibtex_show={true},doi={10.1109/LCSYS.2024.3412943},abbr={LCSS}}
Conference Articles
CDC
Peak Time-Windowed Mean Estimation using Convex Optimization
This paper presents an algorithmic approach towards bounding the peak time-windowed average value attained by a state function along trajectories of a dynamical system. An example includes the maximum average current flowing across a power line in any 5-minute window. The peak time-windowed mean estimation task may be posed as a finite-dimensional but nonconvex optimization problem in terms of an initial condition and stopping time. This problem can be lifted into an infinite-dimensional linear program in occupation measures, where no conservatism is introduced under compactness and dynamical regularity assumptions. The peak time-windowed mean estimation linear program is in turn truncated into a convergent sequence of semidefinite programs using the moment-Sum-of-Squares hierarchy. Effectiveness of bounding the time-windowed mean is demonstrated on example systems.
SysID
Frequency-Domain Identification of Discrete-Time Systems using Sum-of-Rational Optimization
We propose a computationally tractable method for the identification of stable canonical discrete-time rational transfer function models, using frequency domain data. The problem is formulated as a global non-convex optimization problem whose objective function is the sum of weighted squared residuals at each observed frequency datapoint. Stability is enforced using a polynomial matrix inequality constraint. The problem is solved globally by a moment-sum-of-squares hierarchy of semidefinite programs through a framework for sum-of-rational-functions optimization. Convergence of the moment-sum-of-squares program is guaranteed as the bound on the degree of the sum-of-squares polynomials approaches infinity. The performance of the proposed method is demonstrated using numerical simulation examples.
ACC
Data-Driven Superstabilization of Linear Systems under Quantization
Miller, Jared, Zheng, Jian, Sznaier, Mario, and Hixenbaugh, Chris
This paper focuses on the stabilization and regulation of linear systems affected by quantization in state-transition data and actuated input. The observed data are composed of tuples of current state, input, and the next state’s interval ranges based on sensor quantization. Using an established characterization of input-logarithmically-quantized stabilization based on robustness to sector-bounded uncertainty, we formulate a nonconservative infinite-dimensional linear program that enforces superstabilization of all possible consistent systems under assumed priors. We solve this problem by posing a pair of exponentially-scaling linear programs, and demonstrate the success of our method on example quantized systems.
@inproceedings{miller2023quantized,title={{Data-Driven Superstabilization of Linear Systems under Quantization}},author={Miller, Jared and Zheng, Jian and Sznaier, Mario and Hixenbaugh, Chris},arxiv={2309.13712},url={https://arxiv.org/abs/2309.13712},html={https://arxiv.org/abs/2309.13712},booktitle={American Control Conference},year={2024},abbr={ACC},bibtex_show={true},publisher={arXiv},tag={ddc},code={https://github.com/Jarmill/quantized_ddc}}
SysID
Low Order Systems in a Loewner Framework
Honarpisheh, Arya, Singh, Rajiv,
Miller, Jared, and Sznaier, Mario
This paper considers the problem of non-parametric identification of low-order models from time-domain experimental data using a combination of Caratheodory Fejer and Loewner-based interpolation, followed by a Loewner matrix Balanced Reduction (LBR) step. As we show in the paper, the Loewner matrix is an estimator for the trace norm of a system, playing a role similar to the one played by the Hankel matrix. However, utilizing Zolotarev numbers to establish decay rate bounds for singular values reveals that the decay of singular values in the Loewner matrix is considerably faster than that in the Hankel matrix. Thus, Loewner-based methods yield lower order systems, with the same error bound, than comparable ones based on Hankel matrices. The effectiveness of our method is demonstrated through a numerical example.
Preprints
Peak Time-Windowed Risk Estimation of Stochastic Processes
This paper develops a method to upper-bound extreme-values of time-windowed risks for stochastic processes. Examples of such risks include the maximum average or 90% quantile of the current along a transmission line in any 5-minute window. This work casts the time-windowed risk analysis problem as an infinite-dimensional linear program in occupation measures. In particular, we employ the coherent risk measures of the mean and the expected shortfall (conditional value at risk) to define the maximal time-windowed risk along trajectories. The infinite-dimensional linear program must then be truncated into finite-dimensional optimization problems, such as by using the moment-sum of squares hierarchy of semidefinite programs. The infinite-dimensional linear program will have the same optimal value as the original nonconvex risk estimation task under compactness and regularity assumptions, and the sequence of semidefinite programs will converge to the true value under additional properties of algebraic characterization. The scheme is demonstrated for risk analysis of example stochastic processes.
@preprint{miller2024timewindowrisk,title={{Peak Time-Windowed Risk Estimation of Stochastic Processes}},author={Miller, Jared and Schmid, Niklas and Tacchi, Matteo and Henrion, Didier and Smith, Roy S.},bibtex_show={true},code={https://www.research-collection.ethz.ch/handle/20.500.11850/662948},year={2024},eprint={2404.06961},archiveprefix={arXiv},url={https://arxiv.org/abs/2404.06961},href={https://arxiv.org/abs/2404.06961},primaryclass={math.OC}}
Algebraic Proofs of Path Disconnectedness using Time-Dependent Barrier Functions
Two subsets of a given set are path-disconnected if they lie in different connected components of the larger set. Verification of path-disconnectedness is essential in proving the infeasibility of motion planning and trajectory optimization algorithms. We formulate path-disconnectedness as the infeasibility of a single-integrator control task to move between an initial set and a target set in a sufficiently long time horizon. This control-infeasibility task is certified through the generation of a time-dependent barrier function that separates the initial and final sets. The existence of a time-dependent barrier function is a necessary and sufficient condition for path-disconnectedness under compactness conditions. Numerically, the search for a polynomial barrier function is formulated using the moment-sum-of-squares hierarchy of semidefinite programs. The barrier function proves path-disconnectedness at a sufficiently large polynomial degree. The computational complexity of these semidefinite programs can be reduced by elimination of the control variables. Disconnectedness proofs are synthesized for example systems.
@preprint{henrion2024setdisconnected,title={{Algebraic Proofs of Path Disconnectedness using Time-Dependent Barrier Functions}},author={Henrion, Didier and Miller, Jared and Din, Mohab Safey El},year={2024},eprint={2404.06985},bibtex_show={true},archiveprefix={arXiv},primaryclass={math.OC},url={https://arxiv.org/abs/2404.06985},href={https://arxiv.org/abs/2404.06985},code={https://github.com/jarmill/set_connected/}}
Maximizing Slice-Volumes of Semialgebraic Sets using Sum-of-Squares Programming
This paper presents an algorithm to maximize the volume of an affine slice through a given semialgebraic set. This slice-volume task is formulated as an infinite-dimensional linear program in continuous functions, inspired by prior work in volume computation of semialgebraic sets. A convergent sequence of upper-bounds to the maximal slice volume are computed using the moment-Sum-of-Squares hierarchy of semidefinite programs in increasing size. The computational complexity of this scheme can be reduced by utilizing topological structure (in dimensions 2, 3, 4, 8) and symmetry. This numerical convergence can be accelerated through the introduction of redundant Stokes-based constraints. Demonstrations of slice-volume calculation are performed on example sets.
@preprint{miller2024maximizing,title={{Maximizing Slice-Volumes of Semialgebraic Sets using Sum-of-Squares Programming}},author={Miller, Jared and Meroni, Chiara and Tacchi, Matteo and Velasco, Mauricio},year={2024},eprint={2403.04438},archiveprefix={arXiv},primaryclass={math.OC},url={https://arxiv.org/abs/2403.04438},html={https://arxiv.org/abs/2403.04438},bibtex_show={true},code={https://github.com/jarmill/slice_volume},slides={Slice_Volume_Presentation__MoPAT_Konstanz_.pdf}}
Unsafe Probabilities and Risk Contours for Stochastic Processes using Convex Optimization
This paper proposes an algorithm to calculate the maximal probability of unsafety with respect to trajectories of a stochastic process and a hazard set. The unsafe probability estimation problem is cast as a primal-dual pair of infinite-dimensional linear programs in occupation measures and continuous functions. This convex relaxation is nonconservative (to the true probability of unsafety) under compactness and regularity conditions in dynamics. The continuous-function linear program is linked to existing probability-certifying barrier certificates of safety. Risk contours for initial conditions of the stochastic process may be generated by suitably modifying the objective of the continuous-function program, forming an interpretable and visual representation of stochastic safety for test initial conditions. All infinite-dimensional linear programs are truncated to finite dimension by the Moment-Sum-of-Squares hierarchy of semidefinite programs. Unsafe-probability estimation and risk contours are generated for example stochastic processes.
@preprint{miller2024unsafe,title={{Unsafe Probabilities and Risk Contours for Stochastic Processes using Convex Optimization}},author={Miller, Jared and Tacchi, Matteo and Henrion, Didier and Sznaier, Mario},year={2024},eprint={2401.00815},archiveprefix={arXiv},arxiv={2401.00815},tag={peak},bibtex_show={true},code={https://github.com/jarmill/prob_unsafe/},primaryclass={math.OC},note={\href{https://arxiv.org/abs/2401.00815}{[link]}}}
2023
Theses
PhD
Safety Quantification for Nonlinear and Time-Delay Systems using Occupation Measures
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.
@phdthesis{miller2023thesis,title={Safety Quantification for Nonlinear and Time-Delay Systems using Occupation Measures},author={Miller, Jared},year={2023},school={Northeastern University},bibtex_show={true},selected={true},abbr={PhD},pdf={Thesis_Final.pdf},url={https://repository.library.northeastern.edu/files/neu:4f196v79r},html={https://repository.library.northeastern.edu/files/neu:4f196v79r},slides={Thesis_Presentation_Merged.pdf},poster={Safety_Poster__PhD_Expo.pdf},tag={peakddc}}
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.
@article{miller2023distance,title={{Bounding the Distance to Unsafe Sets with Convex Optimization}},author={Miller, Jared and Sznaier, Mario},year={2023},eprint={2110.14047},archiveprefix={arXiv},primaryclass={math.OC},tag={peak},note={arXiv: 2110.14047},url={https://ieeexplore.ieee.org/document/10149398},pdf={distance_arxiv.pdf},pages={1-15},journal={IEEE Transactions on Automatic Control},abbr={TAC},doi={10.1109/TAC.2023.3285862},code={https://github.com/Jarmill/distance},bibtex_show={true},slides={Distance_CDC_Presentation.pdf},arxiv={2110.14047},selected={true}}
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.
@article{zheng2023robustsafety,title={{Robust Data-Driven Safe Control using Density Functions}},author={Zheng, Jian and Dai, Tianyu and Miller, Jared and Sznaier, Mario},year={2023},journal={IEEE Control Systems Letters},eprint={2303.09004},arxiv={2303.09004},archiveprefix={arXiv},primaryclass={math.OC},url={https://ieeexplore.ieee.org/document/10158326},html={https://ieeexplore.ieee.org/document/10158326},tag={ddc},doi={10.1109/LCSYS.2023.3287801},volume={7},number={},pages={2611-2616},abbr={LCSS},bibtex_show={true},code={https://github.com/J-mzz/ddc-safety}}
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.
@inproceedings{miller2022eivarx,doi={https://doi.org/10.1016/j.ifacol.2023.10.1221},url={https://www.sciencedirect.com/science/article/pii/S2405896323016257},html={https://www.sciencedirect.com/science/article/pii/S2405896323016257},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},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}}
CDC
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.
@inproceedings{miller2023chancepeak,title={Peak Value-at-Risk Estimation for Stochastic Differential Equations using Occupation Measures},author={Miller, Jared and Tacchi, Matteo and Sznaier, Mario and Jasour, Ashkan},year={2023},tag={peak},abbr={CDC},booktitle={2023 62nd IEEE Conference on Decision and Control (CDC)},eprint={2303.16064},code={https://github.com/Jarmill/chance_peak},show_bibtex={true},html={https://ieeexplore.ieee.org/document/10383958},url={https://ieeexplore.ieee.org/document/10383958},slides={Chance_Peak_CDC_2023.pdf},bibtex_show={true},doi={10.1109/CDC49753.2023.10383958},primaryclass={math.OC}}
CDC
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.
@inproceedings{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},abbr={CDC},slides={Time_Delay_Presentation__NYU.pdf},eprint={2303.12863},archiveprefix={arXiv},primaryclass={math.OC},code={https://github.com/Jarmill/timedelay},booktitle={2023 62nd IEEE Conference on Decision and Control (CDC)},bibtex_show={true},url={https://ieeexplore.ieee.org/document/10384165},html={https://ieeexplore.ieee.org/document/10384165},arxiv={2303.12863}}
CDC
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.
@inproceedings{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},abbr={CDC},eprint={2303.12242},archiveprefix={arXiv},primaryclass={math.OC},booktitle={2023 62nd IEEE Conference on Decision and Control (CDC)},bibtex_show={true},url={https://ieeexplore.ieee.org/document/10383859},arxiv={2303.12242},html={https://ieeexplore.ieee.org/document/10383859},code={https://github.com/Jarmill/data_driven_pos},tag={ddc}}
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},arxiv={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 Value-at-Risk Estimation of Stochastic Processes using Occupation Measures
This paper formulates algorithms to upper-bound the maximum Value-at-Risk (VaR) of a state function along trajectories of stochastic processes. The VaR is upper bounded by two methods: minimax tail-bounds (Cantelli/Vysochanskij-Petunin) and Expected Shortfall/Conditional Value-at-Risk (ES). Tail-bounds lead to a infinite-dimensional Second Order Cone Program (SOCP) in occupation measures, while the ES approach creates a Linear Program (LP) in occupation measures. Under compactness and regularity conditions, there is no relaxation gap between the infinite-dimensional convex programs and their nonconvex optimal-stopping stochastic problems. Upper-bounds on the SOCP and LP are obtained by a sequence of semidefinite programs through the moment-Sum-of-Squares hierarchy. The VaR-upper-bounds are demonstrated on example continuous-time and discrete-time polynomial stochastic processes.
@preprint{miller2023chancepeak_long,title={Peak Value-at-Risk Estimation of Stochastic Processes using Occupation Measures},author={Miller, Jared and Tacchi, Matteo and Sznaier, Mario and Jasour, Ashkan},year={2023},tag={peak},archiveprefix={arXiv},code={https://github.com/Jarmill/chance_peak},show_bibtex={true},html={https://arxiv.org/abs/2303.16064},url={https://arxiv.org/abs/2303.16064},slides={Chance_Peak__INFORMS.pdf},bibtex_show={true},primaryclass={math.OC}}
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={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={MTNS_Robust_Counterpart.pdf},code={https://github.com/Jarmill/data_driven_occ},selected={true}}
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.
@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}}
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).
@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}}
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}}
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}}