Inclusion conditions for the Constrained Polynomial Zonotopic case

1. Problem Statement

Set-based representations are fundamental in control theory, specifically for reachability analysis and fault detection. While convex sets (like ellipsoids and standard zonotopes) offer computational efficiency, they struggle to represent complex, non-convex geometries accurately.

• The Gap: Constrained Polynomial Zonotopes (CPZs) were introduced to bridge this gap, offering the ability to model non-convex shapes while retaining an algebraic structure suitable for manipulation. However, a critical challenge remains: efficiently testing set inclusion ($P_1 \subseteq P_2$) for CPZs.
• The Difficulty: Existing inclusion tests for simpler sets (like polytopes or constrained zonotopes) rely on linear encodings. CPZs introduce non-linearities (polynomial terms) and equality constraints, making standard linear inclusion tests insufficient. Previous attempts to extend these tests to CPZs have either been too conservative or lacked a robust formulation suitable for integration into optimization frameworks.

2. Methodology

The authors propose a novel mathematical framework to derive sufficient conditions for testing inclusion between two CPZs.

A. Mathematical Formulation

The paper defines a CPZ $P$ using a center $c$, generators $G$, polynomial exponents $E$, equality constraint generators $F$, constraint bounds $\theta$, and equality exponents $R$. The set is defined by:
$$x = c + \sum (\text{polynomial terms in } \lambda) \cdot G, \quad \text{subject to } \sum (\text{polynomial terms in } \lambda) \cdot F = \theta, \quad \|\lambda\|_\infty \leq 1$$

B. Core Proposition (Prop. 1)

The authors derive a set of conditions involving transformation matrices ($\gamma, \Gamma, \Pi, \Psi, \psi$) that, if satisfied, guarantee $P_1 \subseteq P_2$.

• Linear Constraints: Conditions (3a)–(3d) ensure the centers, generators, and equality constraints of $P_1$ can be mapped to those of $P_2$.
• Nonlinear Constraints: Conditions (3e) and (3f) are the novel contribution. They utilize the logarithm and absolute value operators to bound the polynomial terms. Specifically, they ensure that the magnitude of the transformed parameters in $P_1$ does not exceed the unit hypercube bounds required for $P_2$.
  • The logic relies on the triangle inequality and the monotonicity of the logarithm to transform the complex polynomial inclusion problem into a check on the logarithms of the transformation coefficients.

C. Optimization Adaptation (Corollary 1)

A major hurdle in optimization is the non-differentiability of the absolute value operator ($|\cdot|$).

• The authors propose a reformulation using auxiliary variables ($\alpha_\Gamma, \alpha_\Psi$).
• This approach replaces the absolute value terms with linear equality constraints and non-negativity constraints ($\alpha \geq 0$), while retaining the logarithmic nonlinearity.
• This allows the inclusion test to be embedded directly into Non-Linear Programming (NLP) solvers without requiring piecewise linear approximations of the absolute value.

D. Special Cases

The paper demonstrates that their formulation naturally simplifies to existing results:

• If the polynomial exponents are identity matrices, the conditions reduce to the known inclusion tests for Constrained Zonotopes (CZ).
• If equality constraints are removed, it reduces to standard Polynomial Zonotopes (PZ).

3. Key Contributions

1. Novel Nonlinear Encodings: The first derivation of sufficient inclusion conditions specifically for Constrained Polynomial Zonotopes, handling both polynomial non-linearities and equality constraints simultaneously.
2. Optimization-Ready Formulation: The development of Corollary 1, which eliminates the explicit absolute value operator. This makes the inclusion test compatible with standard gradient-based optimization solvers, a crucial step for applications like computing Maximal Positive Invariant Sets (MPI).
3. Theoretical Unification: The framework generalizes previous inclusion tests for CZs and PZs, showing them as special cases of the proposed CPZ conditions.

4. Simulation Results

The authors validated their method using three CPZ sets with varying scaling factors ($P_1, P_2, P_3$) and compared their results against the CORA toolbox (a state-of-the-art reachability analysis tool).

• Accuracy:
  • Proposed Method: Achieved 100% accuracy on the test cases. It correctly identified all true inclusions and non-inclusions with no false positives or false negatives.
  • CORA Toolbox: Failed to detect any true inclusions (returned "0" for all positive cases). The authors attribute this to CORA's pre-processing steps, which inflate the sets (over-approximation) before testing, leading to conservative failures.
• Computation Time:
  • The proposed method was significantly faster. For the tested cases, it took between 0.58s and 1.34s.
  • CORA took between 9.15s and 10.97s, with the majority of time spent on pre-processing rather than the actual inclusion check.

5. Significance and Future Work

• Significance: This work solves a critical bottleneck in set-based control. By providing a computationally efficient and accurate inclusion test for non-convex sets, it enables the use of CPZs in complex control problems where convex approximations are too loose.
• Integration: The ability to formulate the test without absolute values is a breakthrough for optimization-based control, allowing the inclusion constraint to be a direct part of the cost function or constraints in real-time controllers.
• Future Directions: The authors plan to apply these inclusion conditions to compute Maximal Positive Invariant (MPI) sets for systems with polynomial dynamics and constraints, a task that was previously intractable with high accuracy.

In summary, the paper provides a rigorous, efficient, and optimization-friendly mathematical tool for verifying set inclusion in complex, non-convex geometries, outperforming current state-of-the-art tools in both speed and accuracy.