skip to main content

Title: Worst-Case Optimal Data-Driven Estimators for Switched Discrete-Time Linear Systems
This paper proposes a data-driven framework to address the worst-case estimation problem for switched discrete-time linear systems based solely on the measured data (input & output) and an ℓ ∞ bound over the noise. We start with the problem of designing a worst-case optimal estimator for a single system and show that this problem can be recast as a rank minimization problem and efficiently solved using standard relaxations of rank. Then we extend these results to the switched case. Our main result shows that, when the mode variable is known, the problem can be solved proceeding in a similar manner. To address the case where the mode variable is unmeasurable, we impose the hybrid decoupling constraint(HDC) in order to reformulate the original problem as a polynomial optimization which can be reduced to a tractable convex optimization using moments-based techniques.  more » « less
Award ID(s):
1638234 1808381 1814631 1646121
Author(s) / Creator(s):
Date Published:
Journal Name:
2019 IEEE 58th Conference on Decision and Control (CDC)
Page Range / eLocation ID:
3417 to 3422
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Bosonic encoding of quantum information into harmonic oscillators is a hardware efficient approach to battle noise. In this regard, oscillator-to-oscillator codes not only provide an additional opportunity in bosonic encoding, but also extend the applicability of error correction to continuous-variable states ubiquitous in quantum sensing and communication. In this work, we derive the optimal oscillator-to-oscillator codes among the general family of Gottesman-Kitaev-Preskill (GKP)-stablizer codes for homogeneous noise. We prove that an arbitrary GKP-stabilizer code can be reduced to a generalized GKP two-mode-squeezing (TMS) code. The optimal encoding to minimize the geometric mean error can be constructed from GKP-TMS codes with an optimized GKP lattice and TMS gains. For single-mode data and ancilla, this optimal code design problem can be efficiently solved, and we further provide numerical evidence that a hexagonal GKP lattice is optimal and strictly better than the previously adopted square lattice. For the multimode case, general GKP lattice optimization is challenging. In the two-mode data and ancilla case, we identify the D4 lattice—a 4-dimensional dense-packing lattice—to be superior to a product of lower dimensional lattices. As a by-product, the code reduction allows us to prove a universal no-threshold-theorem for arbitrary oscillators-to-oscillators codes based on Gaussian encoding, even when the ancilla are not GKP states.

    more » « less
  2. Topology optimization problems typically consider a single load case or a small, discrete number of load cases; however, practical structures are often subjected to infinitely many load cases that may vary in intensity, location and/or direction (e.g. moving/rotating loads or uncertain fixed loads). The variability of these loads significantly influences the stress distribution in a structure and should be considered during the design. We propose a locally stress-constrained topology optimization formulation that considers loads with continuously varying direction to ensure structural integrity under more realistic loading conditions. The problem is solved using an Augmented Lagrangian method, and the continuous range of load directions is incorporated through a series of analytic expressions that enables the computation of the worst-case maximum stress over all possible load directions. Variable load intensity is also handled by controlling the magnitude of load basis vectors used to derive the worst-case load. Several two- and three-dimensional examples demonstrate that topology-optimized designs are extremely sensitive to loads that vary in direction. The designs generated by this formulation are safer, more reliable, and more suitable for real applications, because they consider realistic loading conditions. 
    more » « less
  3. In this work, we consider the problem of mode clustering in Markov jump models. This model class consists of multiple dynamical modes with a switching sequence that determines how the system switches between them over time. Under different active modes, the observations can have different characteristics. Given the observations only and without knowing the mode sequence, the goal is to cluster the modes based on their transition distributions in the Markov chain to find a reduced-rank Markov matrix that is embedded in the original Markov chain. Our approach involves mode sequence estimation, mode clustering and reduced-rank model estimation, where mode clustering is achieved by applying the singular value decomposition and k-means. We show that, under certain conditions, the clustering error can be bounded, and the reduced-rank Markov chain is a good approximation to the original Markov chain. Through simulations, we show the efficacy of our approach and the application of our approach to real world scenarios. Index Terms—Switched model, Markov chain, clustering 
    more » « less
  4. We consider the problem of learning the underlying structure of a general discrete pairwise Markov network. Existing approaches that rely on empirical risk minimization may perform poorly in settings with noisy or scarce data. To overcome these limitations, we propose a computationally efficient and robust learning method for this problem with near-optimal sample complexities. Our approach builds upon distributionally robust optimization (DRO) and maximum conditional log-likelihood. The proposed DRO estimator minimizes the worst-case risk over an ambiguity set of adversarial distributions within bounded transport cost or f-divergence of the empirical data distribution. We show that the primal minimax learning problem can be efficiently solved by leveraging sufficient statistics and greedy maximization in the ostensibly intractable dual formulation. Based on DRO’s approximation to Lipschitz and variance regularization, we derive near-optimal sample complexities matching existing results. Extensive empirical evidence with different corruption models corroborates the effectiveness of the proposed methods. 
    more » « less
  5. Abstract

    Given the costs and a feasible solution for a minimum cost flow problem on a countably infinite network, inverse optimization involves finding new costs that are close to the original ones and that make the given solution optimal. We study this problem using the weighted absolute sum metric to quantify closeness of cost vectors. We provide sufficient conditions under which known results from inverse optimization in minimum cost flow problems on finite networks extend to the countably infinite case. These conditions ensure that recent duality results on countably infinite linear programs can be applied to our setting. Specifically, they enable us to prove that the inverse optimization problem can be reformulated as a capacitated, minimum cost circulation problem on a countably infinite network. Finite‐dimensional truncations of this problem can be solved in polynomial time when the weights equal one, which yields an efficient solution method. The circulation problem can also be solved via the shadow simplex method, where each finite‐dimensional truncation is tackled using the usual network Simplex algorithm that is empirically known to be computationally efficient. We illustrate these results on an infinite horizon shortest path problem.

    more » « less