CS Paper Radar

Verifying Control Invariance of H-Polytopes is coNP-Complete

Mario Eduardo Villanueva, Boris Houska

eess.SY math.OC ·submitted 2026-10-27 07:40 UTC · v1
theory

Abstract

We prove that verifying whether an H-polytope is control invariant for a discrete-time linear system with polytopic input constraints is \textsc{coNP}-complete. This establishes a fundamental computational complexity barrier for set-theoretic control. As an immediate consequence, the exact computation of maximal control invariant subsets of H-polytopes is \textsc{coNP}-hard. These hardness results hold regardless of whether the input constraint set is given in H- or V-representation.

Closest papers

Nearest neighbours by meaning across the whole index.

Algebraic Characterization of Time-Varying Set Invariance

eess.SY ·2026-11-02 ·S. B. Alaoui, E. J. Wafo Wembe, A. Saoud
publishedtheory similarity 0.60
Abstract · The paper was accepted for publication in the CDC 2026

The verification of temporal forward invariance for dynamical systems subject to time-varying constraints is a foundational problem in the analysis of safety-critical systems. Existing methodologies rely on restrictive geometric assumptions, such as the Linear Independence Constraint Qualification (LICQ), or suffer from exponential computational complexity when applied to time-varying polytopes. This paper establishes a rigorous, unified, and computationally tractable framework for temporal safety verification. First, utilizing tools from nonsmooth analysis, we prove that a Nagumo-type geometric inclusion evaluated strictly on the boundary of the augmented graph is both necessary and sufficient for temporal forward invariance. Second, we provide an algebraic characterization of this condition requiring only the weaker Abadie Constraint Qualification (ACQ), generalizing standard Control Barrier Function (CBF) boundary conditions to non-smooth, multi-constraint domains. Finally, for the practical class of Linear Time-Invariant (LTI) systems with time-varying polytopic constraints, we deploy Farkas' Lemma to eliminate exponential vertex enumeration. By introducing a Lipschitz-bounded time-discretization scheme, we reduce the infinite-dimensional continuous-time verification problem to a finite, highly tractable set of decoupled Linear Programs (LPs).

0.39

Constrained Sparsest Input Selection for Structural Controllability is NP-Hard

eess.SY ·2026-10-22 ·Yuan Zhang, Jintao Zhang, Yun Feng
similarity 0.59
Abstract · 6 pages, 1 figure

We study the problem of selecting the fewest admissible input--state links that make a structured linear system structurally controllable. This objective counts nonzero entries from prescribed positions of the input matrix and is different from minimizing its number of nonzero columns. Prior work gives polynomial-time algorithms for several restricted cases, including single or dedicated inputs and prescribed input patterns satisfying additional graph-theoretic conditions. We give a polynomial-time reduction from perfect three-dimensional matching, establishing for the first time that the decision problem is NP-complete and the optimization problem is NP-hard. A refinement of the reduction yields an exact optimum relation and shows that the problem is APX-hard. An example also exhibits a strict integrality gap for the natural linear programming relaxation.

0.24

The existence of polyhedral invariants is undecidable for linear systems

cs.LO ·2026-09-25 ·David Monniaux
similarity 0.59
Abstract

The existence of polyhedral inductive invariants suitable for proving that a given control location is unreachable is undecidable for programs using only linear arithmetic over Z or Q, by reduction from 2-counter machines.

0.30

Configuration-Constrained Tube MPC for Difference-of-Convex Nonlinear Systems

eess.SY math.OC ·2026-09-07 ·Filippo Badalamenti, Jose A. Borja-Conde, Filiberto Fele, Teodoro Alamo, Daniel Limon
similarity 0.57
Abstract · 11 pages, 3 figures, submitted to Automatica

This paper develops a convex tube model predictive control formulation for constrained nonlinear systems. We consider dynamics described by a discrete-time state-space model with parametric and additive uncertainty that admits a difference-of-convex decomposition. Convex directional bounds of the nonlinear dynamics are combined with configuration-constrained polytopic tubes, whose predefined combinatorial structure yields an affine parameterization of their vertices. The resulting finite-dimensional sufficient conditions certify robust one-step tube propagation under parametric uncertainty and additive disturbances, while allowing the tube geometry and an associated vertex control law to be optimized jointly in a single convex program. An implicit terminal condition guarantees recursive feasibility and convergence of the predicted tube to a target robust control invariant set. Numerical results illustrate the closed-loop properties and the trade-off between geometric flexibility and computational complexity.

0.23

Hybrid Cones: Set Representation with Sharp Unions of Minimal Overhead for Nonlinear and Switched Linear Systems

eess.SY ·2026-10-16 ·Daniel Silvestre
similarity 0.56
Abstract · 19 pages

Reachability analysis and set-based estimation for nonlinear systems require set representations capable of capturing nonconvex geometry. Hybrid Zonotopes (HZs) have recently gained attention because they can encode a union of up to $2^n$ polytopic components. Recent work has further shown that several HZ operations can be made \textit{sharp}, meaning that relaxing the binary variables yields exactly the convex hull of the represented set. However, no known HZ construction provides a sharp union of two convex sets that adds only one binary generator and no further continuous generators or equality constraints to those of the operands. This limitation affects scalability in repeated union operations, ReLU neural-network reachability, and nonlinear propagation methods that cover graph sets by unions of simpler sets. This paper identifies a connection between the exact closed-form convex-hull operation for Constrained Convex Generators (CCGs) and the binary-generator structure underlying HZs. We propose Hybrid Cones that can encode up to $2^n$ norm-cone components. Hybrid Cones inherit the logical structure of HZs while allowing richer convex components, including polytopic and norm-based sets. They support sharp unions requiring only one added binary variable and can represent unions and intersections of polytopes and ellipsoids. As a key application, we derive an exact representation of the ReLU graph using only two continuous and one binary generators. Numerical experiments for a localization problem with a nonlinear energy measurement function approximated by a neural network and the stability verification of the closed loop of a double integrator corrupted by a nonlinear disturbance with a saturated Linear Quadratic Regulator (LQR) controller show substantial reduction in representation size and reduced conservatism in comparison with HZs.

0.34

Convex Safety Filtering via Spectral Selection for Nonconvex Safe Sets

eess.SY math.OC ·2026-10-08 ·Juan Augusto Paredes Salazar, James Usevitch, Ankit Goel
theory similarity 0.54
Abstract · 7 pages, 3 figures, submitted to the ACC 2027

The discrete-time control barrier function condition for a safe set that is a union of convex sets is nonconvex in the control input. For safe sets defined by a matrix concave function through the number of its nonnegative eigenvalues, this paper shows that the set is a union of convex sets, and that the nonconvexity arises because at least one member of the union must hold, not every member. Selecting eigenvectors of the matrix function at the current state yields a convex input constraint that acts only on the eigenvalues determining membership in the set. This constraint is implied by the matrix-wide condition of prior work, and it guarantees a geometric lower bound on each of those eigenvalues along closed-loop trajectories. A double-integrator simulation with a polytope obstacle and a spectrahedron obstacle compares the proposed filter with the matrix-wide condition.

0.25

Feasibility certificates for DeePC: A set invariance approach

eess.SY math.OC ·2026-11-15 ·Daniel O'Neill, Ross Drummond, Pablo R. Baldivieso-Monasterios
similarity 0.54
Abstract

DeePC is posed on a window of past inputs and outputs, so its feasible set is a set of histories and is not available in closed form. We write the DeePC solution as an implicit ReLU network whose weights are built from Hankel matrices and whose activation patterns are the critical regions of the underlying quadratic program. This gives, directly from the Hankel matrices, the feasible set of DeePC as a polyhedral projection, its explicit piecewise-affine control law, and an exact linear model of the history window. We compute three invariant sets of histories: the maximal positively invariant set of the unsaturated linear branch, the region of recursive feasibility of DeePC without terminal ingredients, and the maximal control invariant set of admissible histories. We show these sets are nested and provide numerical examples.

0.32

Safety Certificates for Systems under Attack via Stackelberg Set Games

eess.SY math.OC ·2026-11-13 ·Nikolaos Athanasopoulos, David Laverty, Gregory Provan, Quanyan Zhu
similarity 0.53
Abstract

We study a Stackelberg set selection game for linear systems subject to bounded disturbances and additive attacks. The defender selects the vector parameter of a polytopic safe set template; the attacker, after observing this choice, selects the vector parameter of an admissible attack set. The payoff is a signed, facet-normalised invariance margin that tests invariance exactly and quantifies either the available contraction or the facet inflation needed when invariance fails. Both controlled and robust controlled invariance are treated, corresponding to different information patterns for the control input. Exploiting the structure of parameterised polyhedra, we show that within each validity region the margin is concave in the attack parameter, which reduces the follower minimisation to finitely many extreme parameters. The complete max--min game is then solved by a finite family of LPs, one per defender validity region, each enforcing all attacker regions under a common defender decision and guaranteed margin. The framework handles hard state constraints and additional costs related to the safe set size, and recovers optimal set parameters together with state and attack realisations that activate the certificate. A load frequency control example under false data injection illustrates the construction, the validity decomposition, and the two information patterns.

0.26