skip to main content

Title: 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).  more » « less
Award ID(s):
Author(s) / Creator(s):
Publisher / Repository:
IFA C papers on line
Date Published:
Journal Name:
Page Range / eLocation ID:
55 to 60
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. 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 infinitedimensional 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 semidefinite programs 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). 
    more » « less
  2. In this work, we introduce an interval formulation that accounts for uncertainty in supporting conditions of structural systems. Uncertainty in structural systems has been the focus of a wide range of research. Different models of uncertain parameters have been used. Conventional treatment of uncertainty involves probability theory, in which uncertain parameters are modeled as random variables. Due to specific limitation of probabilistic approaches, such as the need of a prior knowledge on the distributions, lack of complete information, and in addition to their intensive computational cost, the rationale behind their results is under debate. Alternative approaches such as fuzzy sets, evidence theory, and intervals have been developed. In this work, it is assumed that only bounds on uncertain parameters are available and intervals are used to model uncertainty. Here, we present a new approach to treat uncertainty in supporting conditions. Within the context of Interval Finite Element Method (IFEM), all uncertain parameters are modeled as intervals. However, supporting conditions are considered in idealized types and described by deterministic values without accounting for any form of uncertainty. In the current developed approach, uncertainty in supporting conditions is modeled as bounded range of values, i.e., interval value that capture any possible variation in supporting condition within a given interval. Extreme interval bounds can be obtained by analyzing the considered system under the conditions of the presence and absence of the specific supporting condition. A set of numerical examples is presented to illustrate and verify the accuracy of the proposed approach. 
    more » « less
  3. We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method—which is valid only in the case of continuous uncertainty—is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems. 
    more » « less
  4. In this paper, we present a method for updating robotic state belief through contact with uncertain surfaces and apply this update to a Kalman filter for more accurate state estimation. Examining how guard surface uncertainty affects the time spent in each mode, we derive a novel guard saltation matrix- which maps perturbations prior to hybrid events to perturbations after - accounting for additional variation in the resulting state. Additionally, we propose the use of parameterized reset functions - capturing how unknown parameters change how states are mapped from one mode to the next - the Jacobian of which accounts for additional uncertainty in the resulting state. The accuracy of these mappings is shown by simulating sampled distributions through uncertain transition events and comparing the resulting covariances. Finally, we integrate these additional terms into the “uncertainty aware Salted Kalman Filter”, uaSKF, and show a peak reduction in average estimation error by 24–60% on a variety of test conditions and systems. 
    more » « less
  5. This paper proposes a method to find superstabilizing 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 superstabilizing 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. 
    more » « less