Inclusion conditions for the Constrained Polynomial Zonotopic case

論文技術要約：制約付き多項式ゾノトープ（CPZ）の包含条件

1. 背景と問題定義

• 背景: 到達可能性解析や故障検出などの分野では、集合表現（多面体、楕円体、ゾノトープなど）が広く利用されています。特に、ゾノトープはミンコフスキー和や線形変換に対する閉包性（計算効率の高さ）が優れていますが、複雑な非凸形状を表現するには限界があります。
• 課題: 非凸性を表現するために「制約付きゾノトープ（CZ）」や「制約付き多項式ゾノトープ（CPZ）」が提案されています。CPZ は多項式項を導入することで非凸形状を正確に記述できますが、その表現の複雑さ（生成子の数や行列の次元の増大）により、2 つの CPZ 集合間の包含関係（$P_1 \subseteq P_2$）を検証する効率的な手法が確立されていませんでした。
• 既存手法の限界: 従来の線形エンコーディングや既存のツール（CORA など）は、厳密な包含判定において保守的すぎる（偽陽性/偽陰性の発生）か、計算コストが高すぎるという問題を抱えていました。

2. 提案手法（メソドロジー）

著者らは、2 つの CPZ 集合間の包含関係を検証するための新しい非線形エンコーディングを提案しました。

• CPZ の定義:
  CPZ は、中心点 $c$、生成子行列 $G$、多項式指数行列 $E$、制約行列 $F$、制約定数 $\theta$、制約指数行列 $R$、およびパラメータ $\lambda$（$\|\lambda\|_\infty \leq 1$）を用いて定義されます。
  $$P = \left\{ x \in \mathbb{R}^d : x = c + \sum_{i=1}^n \left( \prod_{k=1}^s \lambda_k^{E(k,i)} \right) G(\cdot, i), \quad \sum_{i=1}^q \left( \prod_{k=1}^s \lambda_k^{R(k,i)} \right) F(\cdot, i) = \theta, \quad \|\lambda\|_\infty \leq 1 \right\}$$

• 包含条件の導出（Proposition 1）:
  $P_1 \subseteq P_2$ が成り立つための十分条件として、以下の連立方程式と不等式を導出しました。

  1. 中心点と生成子の関係: $c_1 = c_2 + G_2 \gamma$, $G_1 = G_2 \Gamma$
  2. 制約条件の整合性: 制約行列と定数ベクトルに関する線形変換関係（$\Pi F_1 = F_2 \Psi$, $\Pi \theta_1 = \theta_2 - F_2 \psi$）
  3. 非線形不等式条件: パラメータ空間における包含を保証するための対数不等式。
     $$(E_2^\top)^\dagger \cdot \log(|\gamma| + |\Gamma| \cdot \mathbf{1}) \leq \mathbf{0}$$
     $$(R_2^\top)^\dagger \cdot \log(|\psi| + |\Psi| \cdot \mathbf{1}) \leq \mathbf{0}$$
     ここで、$\dagger$ はモア・ペンローズ擬似逆行列、$\log$ は要素ごとの対数、$|\cdot|$ は絶対値です。

• 最適化フレームワークへの統合（Corollary 1）:
  上記の条件に含まれる絶対値演算子（$|\cdot|$）は、最適化問題において微分不可能または扱いにくい場合があります。これを回避するため、補助変数（$\alpha_\Gamma, \alpha_\Psi$）を導入し、絶対値を非負変数の線形結合として再定式化しました。これにより、対数項のみを含む非線形制約として表現され、最適化ソルバー（YALMIP など）との親和性が向上しました。

3. 主要な貢献

1. CPZ 包含判定のための非線形エンコーディングの提案: 線形制約と非線形（対数）不等式を組み合わせた、CPZ 間の包含を検証する初めての十分条件を提示しました。
2. 最適化適合性の向上: 絶対値演算子を排除した定式化（Corollary 1）により、この包含判定を直接最適化問題（例：最大正不変集合の計算）の制約条件として組み込むことを可能にしました。
3. 既存手法との理論的整合性: 提案手法を特殊化することで、既存の「制約付きゾノトープ（CZ）」の包含判定条件が導かれることを示し、理論的な一貫性を確認しました。

4. 結果と評価

• シミュレーション設定: 3 つの異なる CPZ 集合（$P_1, P_2, P_3$）を定義し、それらの相互包含関係を検証しました。
• 比較対象: 提案手法（Corollary 1）と、業界標準のツールボックス「CORA」の CONTAINS 関数を比較しました。
• 結果:
  • 精度: 提案手法は「Ground Truth（真の包含関係）」と完全に一致しました（偽陽性・偽陰性なし）。一方、CORA はすべてのケースで包含を判定できず（偽陰性）、事前処理による集合の過剰な拡大が原因であると推測されました。
  • 計算時間: 提案手法は CORA に比べて大幅に高速でした（例：$P_1 \subseteq P_2$ の判定で、CORA が約 9.15 秒に対し、提案手法は 1.34 秒）。CORA の大部分の時間は事前処理に費やされており、包含判定自体のアルゴリズム（CONTRACT）も提案手法より遅い傾向がありました。

5. 意義と今後の展望

• 意義: 非凸な幾何学形状を扱う際、計算効率と表現力のバランスが取れた CPZ に対して、信頼性の高い包含判定手法を提供しました。これは、複雑なシステムにおける到達可能性解析や、安全保証（Safety Verification）において極めて重要です。
• 今後の展望: 本論文で確立された包含条件を応用し、制約付き多項式ゾノトープの枠組みにおける「最大正不変集合（Maximal Positive Invariant Set）」の計算を行うことが今後の研究課題として挙げられています。

総括:
この論文は、非凸な集合表現である CPZ の実用的な利用を阻んでいた「包含判定」のボトルネックを解消し、最適化問題に直接組み込める効率的なアルゴリズムを提案した点で画期的です。理論的な厳密さと計算効率の両面で、既存のツールを凌駕する結果を示しています。