CS Paper Radar

Certified Scalable Enclosures for Uncertain Underdetermined Systems

Rudra Prakash, Shaunak Sen

eess.SY q-bio.QM ·submitted 2026-10-08 10:36 UTC · v1
unusual

Abstract

The central challenge in underdetermined models with bounded uncertainty, such as in nonlinear design and estimation, is certifying the solution sets. Conventional solution methodologies, such as those based on Newton's method or on sampling-based uncertainty quantification, are either not applicable due to the underdetermined nature or do not give guarantees that all solutions have been found, assuming they converge. We addressed this issue for a problem that arises in nonlinear design, where a target steady-state box is prescribed and the parameters have to be found. We developed a trapezoidal linearisation method that rigorously encloses all solutions and combined it with a tractable linear programming method to compute the component-wise bounds. We showed that the resulting families of linear programs can iteratively contract an initial parameter region. A subdivision of the target state and the initial parameter region can improve the contraction and provide tighter enclosures. The trapezoidal relaxation gives a family of linear programs that can also be used for finding solutions for interval linear systems via the Oettli-Prager characterisation. We demonstrate the generality of the method through different applications, including nonlinear design in biomolecular circuits, a sensitivity analysis method, and in a compressed sensing context, and discuss the trade-off between enclosure tightness and computational cost.

Comment
18 pages, 1 figure (2 panels), 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

Floating-point, exact and certified computation for control: paradigms, pitfalls, and how to combine them

cs.SC ·2026-11-11 ·Christina Katsamaki, Fabrice Rouillier
similarity 0.54
Abstract

Many questions in linear systems theory have a discrete answer: is a polynomial Hurwitz, is a 2-D system structurally stable, is the peak gain finite, which solution of a Riccati equation is stabilizing? Algorithms implemented in floating point usually answer such questions, but often with a limited, or even no, guarantee on the result, which depends on a tolerance fixed a priori. Computer algebra and interval arithmetic provide other ways of computing, which give guarantees on the result, but usually at a higher cost. In this paper, we propose a short guide to these approaches: floating-point, exact, multiprecision and interval arithmetic, certified root isolation and certified Newton methods. Using small examples from control theory (each of them runs in a few seconds), we show what each approach guarantees and in which situations it fails, and how several approaches can be combined, for example by certifying a numerical solution, or by reducing a problem exactly before solving it with certified real solving. We then revisit the structural stability of 2-D systems (with and without parameters) and the computation of the $H_\infty$ norm, and we list the available implementations. The main examples are given as reproducible worksheets based on the PACE ecosystem.

0.32

Computing Robustness to Sparse Diagonal Uncertainty

eess.SY math.OC ·2026-09-13 ·Christoffer Kjellson, Emma Tegling
theory similarity 0.53
Abstract

A new robustness metric $ν$ was recently proposed as a substitute for the structured singular value $μ$ to better capture robustness to sparse diagonal uncertainty, but its computation has remained an open problem. In this paper, we show that computing $ν$ is equivalent to maximizing the spectral radius of a nonnegative matrix product. This equivalence allows us to transfer existing results on spectral-radius maximization to $ν$, including a refined upper bound and conditions under which the bounds coincide. We then provide reformulations and structural results that enable an algorithm to solve the nonconvex optimization problem for nontrivial problems using global solvers. This also enables identification of the most fragile parts of the system. Our results do not yet provide a scalable solution for computing $ν$, but they are an important step toward computability and interpretability.

0.17

A Reusable Framework for Robust Approximation Algorithms in the Interval Uncertainty Model

cs.DS ·2026-09-10 ·Ralf Klasing, Tobias Mömke, Émile Naquin
theory similarity 0.53
Abstract

Robust optimization under interval uncertainty aims to compute solutions that perform well on a range of scenarios that are described by interval-constrained costs. In this paper, we revisit a framework introduced by Ganesh, Maggs and Panigrahi in 2020 to study the robust optimization of NP-hard problems under interval uncertainty. We start by generalizing a result in the $\ell=0$ case, which transforms a category of approximation algorithms into a robust approximation algorithm. Furthermore, in the general case, we provide a theorem that turns any local search-based approximation algorithm into a robust approximation algorithm under three newly formalized conditions over the moves of the local search algorithm. We then use this result to present the first robust approximation algorithm for Weighted $k$-Set Cover, the third NP-hard problem known to admit a robust approximation, and the first since the publication of Ganesh, Maggs and Panigrahi's paper.

0.12

Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions

cs.LG cs.AIeess.SYmath.OC ·2026-11-11 ·Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Paré, Shreyas Sundaram
similarity 0.52
Abstract

State-of-the-art neural network verifiers evaluate linear relaxations over axis-aligned bounding boxes. However, verification domains in cyber-physical systems are rarely boxes. Reachability specifications, obstacle-avoidance constraints, and neural Lyapunov certificates typically yield oblique or non-convex polyhedral regions, over which box-based bounds become extremely loose. This paper proposes Fit-LRP (Fitting Linear Relaxations to Polytopes), a framework the implements exact optimization of affine bounds over non-convex domains (represented by unions of polytopes) by solving a sequence of small, low-dimensional linear programs. Our approach seamlessly enhances the final optimization step of LiRPA and $α,\! β$-CROWN branch-and-bound (BaB) algorithms. In BaB verification, approximating oblique constraints with axis-aligned splits causes severe combinatorial blowup and risks non-termination. By optimizing the final affine bound of a nonlinear function over the exact polyhedral state-space constraints our method eliminates box-induced over-approximations, enabling earlier search-tree pruning. On ARCH-COMP and neural Lyapunov benchmarks, Fit-LRP reduces branching on the hardest region by $47\times$, cuts worst-case verification time by $15\times$, and with region-wise partitioning, verifies on a single CPU $6.1\times$ faster than $α,\! β$-CROWN on a GPU.

0.23

Solution Methods for Infinite-Dimensional Generalized Disjunctive Programming

eess.SY math.OC ·2026-08-27 ·Daniel Nguyen, Joshua L. Pulsipher
similarity 0.51
Abstract

Generalized disjunctive programming (GDP) expresses mixed discrete-continuous decisions through Boolean indicators and disjunctions, and can be systematically solved via a library of methods proposed in the literature. The recent InfiniteGDP abstraction lifts this modeling layer to continuous domains such as time, space, and uncertainty, but only the big-M and hull reformulations, the two endpoints of the relaxation spectrum, have been generalized to the infinite setting. This work closes this gap by generalizing four other GDP solution methods to infinite-dimensional optimization: the multiple big-M reformulation, P-split reformulation, cutting plane reformulation, and the logic-based outer approximation algorithm. It further proposes MBM-GP, a novel Gaussian-process variant of multiple big-M that learns the big-M function over the infinite domain from a small subset of the subproblem solves. Moreover, these approaches are implemented in the Julia package InfiniteDisjunctiveProgramming.jl. The methods are benchmarked on case studies arising in dynamic and stochastic optimization. The results demonstrate how the generalized solution methods can outperform big-M and hull, with MBM-GP retaining the tightness of multiple big-M at a fraction of its reformulation cost.

0.23

Controllability Allocation Scores for Linear Infinite-Dimensional Systems

eess.SY math.OC ·2026-10-20 ·Daisuke Inoue, Kazuhiro Sato
similarity 0.51
Abstract · 16 pages, 4 figures

We define finite-time controllability allocation scores (CASs) as optimal solutions to two convex optimization problems that allocate a fixed actuation budget among prescribed input functions of linear infinite-dimensional continuum systems with selected target outputs. The objectives are expressed using controllability Gramians for the selected outputs and correspond to maximizing the volume of output changes reachable with unit control energy or minimizing the mean energy required for unit output changes. To compute these CASs, we discretize the system in space, construct the resulting Gramians, and solve the resulting allocation problems by a domain-aware projected gradient descent method. We study the behavior of CASs when the actuator-to-target responses of the spatially discretized systems converge to those of the continuum system as the mesh is refined. If the continuum system is target controllable, we show that the spatially discretized systems are also target controllable on sufficiently fine meshes and that the optimal values of the approximate problems converge to the optimal value for the continuum system. If the allocation problem for the continuum system has a unique CAS, we show that the CASs obtained from the spatially discretized problems converge to it. We also derive quantitative bounds on the errors between these CASs when the Gramian map for the continuum system distinguishes allocations. A two-dimensional advection-diffusion example illustrates how transport dynamics affect target controllability and CASs. Spatial refinement reveals apparent controllability caused by numerical diffusion and supports the theoretical convergence results.

0.26

Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling

cs.LG stat.ML ·2026-11-10 ·Yilin Zheng, Haowei Wang, Wenjia Wang, Szu Hui Ng
theory similarity 0.50
Abstract

Simulation optimization typically returns a single estimated optimal point. When decisions also depend on criteria evaluated independently of simulation, such as resource cost, the decision maker instead needs the set of designs whose expected performance lies within a tolerance of the optimum, often choosing the tolerance only after seeing the tradeoffs. We study how to identify these near-optimal regions on a continuous design space, simultaneously for all tolerances up to a prescribed maximum $T$, with region estimation error at most $η$. We show that region identification is not a by-product of optimization. Specifically, when $α>ν$, any procedure, even one given the optimal design in advance, needs at least $Ω\bigl(η^{-(2+d/ν)}\min\{1,KT^{d/α}\}\bigr)$ simulation evaluations, where $d$ is the dimension, $ν$ the smoothness, and $(K,α)$ the covering parameters that describe the geometry of the near-optimal designs. We propose SASORI, which returns an estimated optimal point and the regions for all tolerances from the same evaluations, matching this lower bound up to logarithmic factors. SASORI also achieves the optimal tradeoff between region estimation error and cumulative regret, and reduces to a minimax-optimal simulation optimization procedure at zero tolerance. Numerical experiments illustrate the effectiveness of our proposed method.

0.25

Generalized Semi-Infinite Programming for Robust Optimal Control with Decision-Dependent Uncertainty

eess.SY math.OC ·2026-09-01 ·J. Wehbeh, E. C. Kerrigan, E. Scaccia
benchmark similarity 0.50
Abstract · 6 pages, 0 figures, submitted to Transactions on Automatic Control

Generalized semi-infinite programs (GSIPs) arise in robust optimal control whenever the admissible uncertainty depends on the state or controls. Existing GSIP methods either impose restrictive structural assumptions or require global optimization that scales poorly to control problems. We present a general framework that reformulates any GSIP with mild regularity as an existence-constrained semi-infinite program, smoothing its disjunctive feasibility condition into differentiable existence constraints over a fixed index superset. The resulting program is solved by established adaptive discretization (cutting-plane) methods using only off-the-shelf nonlinear-programming solvers, and converges under standard assumptions. Treating the state trajectory as part of the uncertainty extends the framework to robust nonlinear optimal control with state-dependent uncertainty. We demonstrate it on a nonconvex benchmark GSIP and a satellite de-tumbling problem with dynamically varying inertia.

0.27