Facial Input Decompositions for Robust Peak and Reachable Set Estimation under Polyhedral Uncertainty

Jared Miller, Mario Sznaier

Abstract

Input-affine dynamical systems often arise in control and modeling scenarios, such as the data-driven case when state-derivative observations are recorded under bounded noise. Common tasks in system analysis and control include optimal control, peak estimation, reachable set estimation, and maximum control invariant set estimation. Existing work poses these types of problems as infinite-dimensional linear programs in auxiliary functions with sum-of-squares tightenings. The bottleneck in most of these programs is the Lie derivative nonnegativity constraint posed over the time-state-control set. Decomposition techniques to improve tractability by eliminating the control variables include vertex decompositions (switching), or facial decompositions in the case where the polytopic set is a scaled box. This work extends the box-facial decomposition technique to allow for a robust-counterpart decomposition of semidefinite representable sets (e.g. polytopes, ellipsoids, and projections of spectahedra). These robust counterparts are proven to be equivalent to the original Lie constraint under mild compactness and regularity constraints. Efficacy is demonstrated under peak/distance/reachable set data-driven analysis problems and Region of Attraction maximizing control.

Introduction: Addressing the Computational Bottleneck

In control theory, analyzing the "worst-case" behavior of a system—such as its maximum state value or its reachable set—is critical for safety and performance. For input-affine systems, where uncertain inputs or controls enter the dynamics linearly, these problems are typically framed as infinite-dimensional Linear Programs (LPs). Solving these requires the Sum-of-Squares (SOS) hierarchy, which converts the LP into a Semidefinite Program (SDP).

However, a major computational bottleneck exists: the Lie derivative constraint. This constraint must hold for every possible input $w$ within a set $W$. When $W$ is complex, such as a high-dimensional polytope or an ellipsoid, the resulting SDP becomes computationally prohibitive, often exceeding the memory limits of standard solvers. The following table provides a reference for the technical terminology used in this optimization framework.

Table of Abbreviations

Methodology: Robust Counterparts and SDR Sets

The authors introduce a method to decompose these hard constraints using robust optimization techniques. By applying convex duality, they introduce "multiplier" functions that effectively eliminate the uncertainty variable $w$ from the optimization problem.

Key methodological contributions include:

  1. Robust Counterparts: Transforming a single complex constraint into a set of simpler constraints that are independent of the uncertain inputs.
  2. Semidefinite Representable (SDR) Set Support: Extending previous "box" constraint methods to any SDR set, including polytopes, ellipsoids, and projections of spectahedra.
  3. Lifting for Discrete Time: Using auxiliary variables to restore linear structure in discrete-time systems, which are typically non-linear and difficult to handle with standard SOS.
  4. SOS Tightening: Proving that these robust counterparts can be approximated using polynomial SOS functions, ensuring convergence to the true optimal solution as the polynomial degree increases.

Key Insights: Efficiency and Equivalence

The most significant impact of this work is the dramatic reduction in computational complexity. In one benchmark, a standard SOS approach required a massive 8568x8568 PSD matrix. The proposed robust counterpart method reduced this to 34 smaller matrices of size 56x56, enabling solutions in seconds rather than crashing the solver.

Furthermore, the authors prove that this decomposition is not merely an approximation but is mathematically equivalent to the original constraint under mild regularity conditions. This makes the method highly suitable for data-driven control, where one might build a polytope of models consistent with noisy observations and seek a control law robust to all of them.

Results and Benchmarks

The method was evaluated on several dynamical systems to demonstrate its versatility:

  • Elliptope-Disturbed System: Demonstrated handling of noise within complex spectahedral sets.
  • Data-Driven Flow System: Successfully estimated dynamics and reachable sets from limited, noisy observations.
  • Twist System: Showed steady convergence of SOS bounds for peak estimation as polynomial degrees increased (e.g., from 1.000 at order 1 to 0.8174 at order 3).
  • Controlled Flow System: Successfully computed the Region of Attraction (ROA), identifying safe initial conditions despite bounded disturbances.

Conclusion

While the method significantly eases the burden of input variables, the "curse of dimensionality" remains for the state variables due to the nature of SOS polynomials. Future research may focus on relaxing current geometric constraints on the uncertainty set $W$ and implementing "warm-starts" for SDP solvers to facilitate real-time data-driven updates.

Summary updated

Abstract

Input-affine dynamical systems often arise in control and modeling scenarios, such as the data-driven case when state-derivative observations are recorded under bounded noise. Common tasks in system analysis and control include optimal control, peak estimation, reachable set estimation, and maximum control invariant set estimation. Existing work poses these types of problems as infinite-dimensional linear programs in auxiliary functions with sum-of-squares tightenings. The bottleneck in most of these programs is the Lie derivative nonnegativity constraint posed over the time-state-control set. Decomposition techniques to improve tractability by eliminating the control variables include vertex decompositions (switching), or facial decompositions in the case where the polytopic set is a scaled box. This work extends the box-facial decomposition technique to allow for a robust-counterpart decomposition of semidefinite representable sets (e.g. polytopes, ellipsoids, and projections of spectahedra). These robust counterparts are proven to be equivalent to the original Lie constraint under mild compactness and regularity constraints. Efficacy is demonstrated under peak/distance/reachable set data-driven analysis problems and Region of Attraction maximizing control.
BibTeX
@misc{miller2021facial,
  author = {Jared Miller and Mario Sznaier},
  title = {{Facial Input Decompositions for Robust Peak and Reachable Set Estimation under Polyhedral Uncertainty}},
  year = {2021},
  eprint = {2112.14838},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.14838},
}
Figure