Convex Hulls of Reachable Sets

• URL: http://arxiv.org/abs/2303.17674v4
• Date: Sat, 27 Jul 2024 21:13:14 GMT
• Title: Convex Hulls of Reachable Sets
• Authors: Thomas Lew, Riccardo Bonalli, Marco Pavone,
• Abstract summary: Reachable sets play a critical role in control, but remain notoriously challenging to compute. We characterize the convex hulls of reachable sets as the convex hulls of solutions of an ordinary differential equation with initial conditions on the sphere. This finite-dimensional characterization unlocks an efficient sampling-based estimation algorithm to accurately over-approximate reachable sets.
• Score: 18.03395556436054
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the convex hulls of reachable sets of nonlinear systems with bounded disturbances and uncertain initial conditions. Reachable sets play a critical role in control, but remain notoriously challenging to compute, and existing over-approximation tools tend to be conservative or computationally expensive. In this work, we characterize the convex hulls of reachable sets as the convex hulls of solutions of an ordinary differential equation with initial conditions on the sphere. This finite-dimensional characterization unlocks an efficient sampling-based estimation algorithm to accurately over-approximate reachable sets. We also study the structure of the boundary of the reachable convex hulls and derive error bounds for the estimation algorithm. We give applications to neural feedback loop analysis and robust MPC.

Related papers

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• Single-Loop Deterministic and Stochastic Interior-Point Algorithms for Nonlinearly Constrained Optimization [16.356481969865175]
  An interior-point algorithm is proposed, analyzed, and tested for solving objectively constrained continuous optimization problems. The algorithm is intended for the setting when-gradient, estimates are available and employed in place gradients, and when no objective function values are employed.
  arXiv  Detail & Related papers  (2024-08-29T00:50:35Z)
• Taming Score-Based Diffusion Priors for Infinite-Dimensional Nonlinear Inverse Problems [4.42498215122234]
  This work introduces a sampling method capable of solving Bayesian inverse problems in function space. It does not assume the log-concavity of the likelihood, meaning that it is compatible with nonlinear inverse problems. A novel convergence analysis is conducted, inspired by the fixed-point methods established for traditional regularization-by-denoising algorithms.
  arXiv  Detail & Related papers  (2024-05-24T16:17:01Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
  We consider the problem of concave utility reinforcement learning (CURL) with convex constraints. We propose a model-based learning algorithm that also achieves zero constraint violations.
  arXiv  Detail & Related papers  (2021-09-12T06:13:33Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  We present a new model of a general convex or non objective machine machine objectives. We propose an algorithm that solves a constraint with gradually relaxed point levels of each subproblem. We demonstrate the effectiveness of our new numerical scale problems.
  arXiv  Detail & Related papers  (2020-10-23T05:24:05Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
  We show that the problem of robust mean estimation in the presence of a constant adversarial fraction can be solved by gradient descent. Our work establishes an intriguing connection between the near non-lemma estimation and robust statistics.
  arXiv  Detail & Related papers  (2020-05-04T10:48:04Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)
• Variational Bayesian Methods for Stochastically Constrained System Design Problems [7.347989843033034]
  We study system design problems stated as parameterized programs with a chance-constraint set. We propose a variational Bayes-based method to approximately compute the posterior predictive integral.
  arXiv  Detail & Related papers  (2020-01-06T05:21:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.