我们引入了约束多项式带拓扑，这是一种新的非凸集合表示，它在线性映射、闵可夫斯基和、笛卡尔积、凸包、交、并、二次以及高阶映射下是封闭的。我们证明了上述集合运算的计算复杂度在表示大小上不超过多项式。约束多项式带共体是带共体、多边形、多项式带共体、Taylor模型和椭球体的一般化，这一事实进一步证实了这种新的集合表示的相关性。此外，从其他集合表示到约束多项式带拓扑的转换在维数上最多是多项式，我们提出了用更简单的集合表示来减小表示大小和封闭约束多项式带拓扑的有效方法。
许多应用，如控制器综合、状态估计和形式验证，都是基于用集合计算的算法[7,11,12,28]。因此，这些算法的性能主要取决于有效的集合表示。理想情况下，集合表示不仅在所有相关的集合操作下是封闭的，而且可以有效地计算这些操作。我们引入了约束多项式带拓扑，这是一种新的非凸集合表示，它在线性映射、闵可夫斯基和、笛卡尔积、凸包、交、并、二次以及高阶映射下是封闭的。这些操作的计算复杂度最多是表示大小的多项式。结合我们的有效的表示大小缩减方法，约束多项式带拓扑非常适合于许多集计算算法。
在过去的几年中，许多不同的集合表示已经用于或开发了基于集合的计算。典型集合表示之间的关系如图1所示。此外，表1显示了哪些集合表示在相关的集合操作下是封闭的。
图1
不同集合表示之间关系的可视化，其中A B表示B是A的泛化
表1集合表示与集合操作的关系
全尺寸工作台
所有凸集都可以等价地表示为它们的支持函数[17,Chapter C.2]。此外，对于支持函数，线性映射、闵可夫斯基和、笛卡尔积和凸包都是很容易计算的[16,Prop. 2]。尽管支持函数在交点下是封闭的，但是该操作的计算没有封闭形式的表达式，并且支持函数在并映射和二次映射下是不封闭的。椭球体和多面体是由支持函数表示的集合的特殊情况[16,Prop. 1]。椭球体仅在线性映射下是封闭的(见表1)，而多面体在线性映射、闵可夫斯基和、笛卡尔积、凸包和交点下是封闭的[15,Chapter 3.1]。多面体集合运算的计算复杂度取决于所使用的表示[30]，其中多面体的两种主要表示是半空间表示和顶点表示:对于半空间表示，由可逆矩阵和交叉点表示的线性映射计算成本低，而由不可逆矩阵、闵可夫斯基和和凸包表示的线性映射计算成本高[30]。如果没有去除冗余点，对于顶点表示来说，线性映射、闵可夫斯基和和凸包的计算是微不足道的，而计算交集则是np困难的[30]。
多面体的一个重要子类是分带多面体[31,Chapter 7.3]。由于分区可以用所谓的生成器紧凑地表示，因此它们非常适合表示高维集合。此外，线性映射、闵可夫斯基和和笛卡尔积可以精确有效地计算[4，表1]。zone otopes的两种扩展是zone otopes束[6]和约束zone otopes[29]，它们都可以表示任何有界多面体。约束分区还考虑分区因子的线性等式约束，而分区束则通过若干分区的交集隐式表示集合。带共体的两种特殊情况是具有线性无关生成器的带共体和多维区间的平行四边形。由于区间在线性映射下不是封闭的，使用区间计算的算法通常会将区间拆分以获得期望的精度[18]。
常见的非凸集表示有星集、水平集、泰勒模型和多项式分区。星集[8,13]的概念类似于约束分区的概念，但使用逻辑谓词而不是线性等式约束来约束分区因子的值。非线性函数的水平集[25]可以表示任何形状。虽然星集和水平集非常具有表现力(见图1)，但对于许多相关操作来说，它们是如何计算的尚不清楚(见表1)。泰勒模型[24]由多项式和区间余部分组成。与泰勒模型非常相似的一种集合表示是多项式带拓扑，它在[2]中首次被引入。最近在[21]中提出了一种计算效率高的多项式分区的稀疏表示。由于其多项式性质，Taylor模型和多项式带拓扑在二次和高阶映射下都是封闭的(见表1)。
在这项工作中，我们引入了约束多项式zone otopes，这是一种新的非凸集表示，它将约束zone otopes[29]使用的zone otopes因子添加相等约束的概念与[21]中的稀疏多项式zone otopes表示相结合。约束多项式分区在所有相关集合操作下都是封闭的(见表1)，可以表示图1中除了星集、水平集和由其支持函数定义的集合之外的任何集合。如表1所示，约束多项式分区是唯一已知计算所有相关集合操作的封闭形式表达式的集合表示。
在本工作的其余部分中，我们使用以下符号:集合用书法字母表示，矩阵用大写字母表示，向量用小写字母表示。其中，自然数集合记为，包含0的自然数集合记为，实数集合记为。给定一个集合，表示该集合的基数。给定一个向量，表示第i项。同样，给定一个矩阵，表示矩阵的第i行、第j列和矩阵第i行的第j项。给定一组正整数索引，用符号表示，其中[C D]表示两个矩阵C和D的连接，符号和表示适当维数的矩阵和向量，并返回对角线上的一个方阵。空矩阵记为[]，维数单位矩阵记为。此外，我们使用n维区间的简写。对于计算复杂度的推导，我们考虑所有的二进制操作，除了连接;也不考虑初始化。
让我们首先提供一些对本文其余部分很重要的定义。我们从分区开始:
(Zonotope) [14, Def. 1]给定一个恒定的偏移量和一个生成器矩阵，一个Zonotope定义为
标量被称为因子，我们用这个简写。
约束带拓扑[29]可以表示任意有界多面体:
(Constrained zone otope) [29, Def. 3]给定一个常量偏移量、一个生成器矩阵、一个约束矩阵和一个约束向量，定义约束zone otope为
我们用速记法。
多项式分区是在[2]中首次引入的一种非凸集表示。我们使用多项式分区的稀疏表示[21]:
(多项式带拓扑)[21,Def. 1]给定一个常数偏移量、一个生成器矩阵和一个指数矩阵，多项式带拓扑定义为
与[21,Def. 1]相反，我们明确地没有在G中积分常数偏移量c，并且我们没有考虑独立的生成器，因为每个具有独立生成器的多项式分区可以等效地表示为没有独立生成器的多项式分区[22,Prop. 1]。我们用速记法。
椭球体定义如下:
(椭球体)[10,Eq. 2.3]给定一个恒定的偏移量和一个对称正定矩阵，定义椭球体为
我们用速记法。
在本文中，我们考虑表1中列出的标准集操作。给定两个集合，一个集合，一个矩阵，和一个矩阵的离散集合，这些运算定义如下:
(1) (2) (3) (4) (5) (6) (7)
此外，在脚注1中，我们考虑另一个集合运算，我们称之为两个集合的线性组合:
(8）
对于凸集，凸包和线性组合是相同的。然而，对于本文所考虑的非凸集，这两种操作是不同的。我们考虑这两种操作，因为对于许多算法，如可达性分析[1,Eq.(3.4)]，计算线性组合而不是凸包就足够了。
摘要
1 介绍
2 定义
3.有限公司
约束多项式带拓扑
4 预赛
5 有限公司
从其他集合表示反转
6 附件由其他集合表示
7 集合操作
8 表示大小缩减
9 数值例子
10 结论
笔记
参考文献
致谢
作者信息
附录
搜索
导航
＃＃＃＃＃
在本节中，我们将介绍约束多项式分区(CPZs)。CPZ是通过在多项式分区上添加多项式等式约束来构造的:
给定一个常数偏移量、一个生成矩阵、一个指数矩阵、一个约束生成矩阵、一个约束向量和一个约束指数矩阵，定义一个约束多项式带拓扑为
当指数矩阵E和约束指数矩阵R不包含重复列或全零列时，约束多项式分区是正则的:
和
标量称为因子，其中因子的个数为p，生成子的个数为h，约束子的个数为m，约束子的个数为q。阶估计一个受约束的多项式分区的复杂度。我们用速记法。
集合的所有分量都有索引i，例如，定义5中定义的参数、、和都属于。存储CPZ所需的标量数为
（9）
因为c有n个元素，G有nh个元素，E有ph个元素，A有mq个元素，b有m个元素，还有pq个元素。我们称之为CPZ的表示大小。并且，我们将构造多项式所对应的多项式称为带拓扑。对于关于维数n的集合运算的计算复杂度的推导，我们假设
（10）
与。当使用cpz计算时，通常会将表示大小减少到所需的上限，这一事实证明了这一假设的合理性。
我们通过一个例子来说明cpz的概念:
的CPZ
定义集合
如图2所示。
图2
例1的多项式约束(左)、约束多项式分区(右，红色)和相应的构造多项式分区(右，蓝色)的可视化
我们从一些贯穿本文的初步结果开始。
让我们首先建立一些对以后的推导有用的恒等式。根据定义5对cpz的定义，认为
（11）
和
（12）
一些集合操作导致CPZ不是正则的。因此，我们引入将非正则CPZ转换为正则CPZ的操作。compactGen操作返回一个正则指数矩阵的CPZ:
给定，操作compactGen返回一个正则指数矩阵的表示，其复杂度为:
与
其中操作uniqueccolumns删除相同的矩阵列，直到所有列都是唯一的。
对于指数矩阵由两列组成的CPZ，它成立
对具有相同指数项的生成器求和不会改变集合，这证明了。此外，由于uniqueColomns操作删除了所有相同的矩阵列，并且我们将所有的零列添加到常量偏移量中，因此根据定义5，得出的指数矩阵是正则的。
复杂度我们假设通过首先对矩阵列进行排序，然后识别相同的邻居来实现操作uniqueColumns和集合的构造。此外，我们假设为了对矩阵列进行排序，首先对第一行中的项进行排序。对于第一行中具有相同条目的所有列，然后根据第二行中的条目对列进行排序。由于这个过程对所有p个矩阵行都是持续的，并且对矩阵的一行进行排序的复杂度为[19,Chapter 5]，因此对矩阵列进行排序的最坏情况复杂度为，为。相同邻居的识别和移除需要最多的比较操作，因此具有最坏的复杂性。而且，在最坏情况下，集合和的构造具有复杂性。最后，在最坏情况下，常数偏移量和发生器矩阵的构造具有一定的复杂性。因此，总体的复杂性是。
compactCon操作返回一个带正则约束指数矩阵的CPZ:
(紧凑约束)给定，操作compactCon返回一个正则约束指数矩阵的表示，其复杂度为:
与
其中操作uniqueccolumns删除相同的矩阵列，直到所有列都是唯一的。
这个证明类似于命题1的证明。
最后，我们根据[29,Prop. 3]的启发，在以下引理中引入CPZ对应的提升多项式zone - otope:
(提升多项式分区)给定，对应的提升多项式分区定义为
（13）
满足
根据定义5中cpz的定义，我们得到
在哪里。
根据引理1,CPZ可以解释为提升的多项式区域与子空间的交点。此外，使用提升的多项式分区，我们可以将多项式分区的结果转移到cpz，我们将在后面演示。由于指数和约束指数矩阵中的公共列，提升的多项式分区中潜在的冗余可以使用[21,Prop. 2]中多项式分区的紧化操作来去除。
随后，在第6节和第8节中，我们描述了如何用其他集合表示来封闭CPZ，以及如何通过用更简单的CPZ来封闭CPZ来减小CPZ的表示大小。这些外壳的密封性主要取决于相应的尺寸连接公司构造多项式分区。从那时起约束常常相交于只是因子超立方体的一部分
，我们可以缩小公司的规模构造多项式zo提前注意，以获得更紧密的结果。这可以通过承包商来实现:
给定一个区间和一个定义约束的向量域，该操作返回一个满足的区间
和
从而保证包含在的所有解也包含在收缩区间内。
存在许多复杂的实施承包商的方法，其中的概述在[18，第4章]中提供。我们可以计算一个更紧的定义域
通过应用co来求因子对多项式co求和CPZ的限制:
使用压缩域[l, u]，可以等价地表示为
我们在附录B中表明，该集合可以表示为CPZ。让我们通过一个例子来演示重新缩放:
我们考虑CPZ
如图3所示。如图3左侧所示nstraint o只与因子定义域的一小部分相交
，使得定义域为ntracted来
． 因此，重新缩放可以显著减少co的大小构造多项式分区，如图3右侧所示。
图3
从示例(红色，右侧)重新缩放的可视化，其中对应的约束在左侧显示。重新缩放前的构造多项式区域用蓝色表示，重新缩放后的构造多项式区域用绿色表示
本节展示如何将其他集合表示转换为cpz。
由于多项式分区只是一个没有约束的CPZ，因此在这种情况下转换是微不足道的。对于如[21,Def. 1]中使用附加独立生成器定义的多项式分区，可以首先使用[22,Prop. 1]将多项式分区转换为没有独立生成器的多项式分区。根据[21,Prop. 4]，由Taylor模型定义的集合可以等价地表示为多项式分区。而且，根据[21,Prop. 3]，任何分区构型都可以表示为多项式分区构型，任何区间都可以表示为分区构型[1,Prop. 2.1]。最后，约束带拓扑是CPZ的一种特殊情况，其中所有多项式函数都是线性的，因此转换很简单。综上所述，我们得到以下转换规则:
(14) (15) (16) (17)
区间的转换由于向量l和u的和和相减，相对于维数n具有复杂性，而所有其他转换具有恒定的复杂性，因为不需要计算。
将有界多面体表示为CPZ有两种可能。根据[20]和[21，定理1]，每一个有界多面体都可以表示为一个多项式分区。因此，任何有界多面体都可以转换为CPZ，首先将其表示为多项式分区构型，然后使用(17)将多项式分区构型转换为CPZ。而且，根据[29，定理1]，任何有界多面体都可以表示为约束的共体。因此，将有界多面体转换为CPZ的第二种可能性是，首先将多面体表示为约束带拓扑，然后使用(16)将约束带拓扑转换为CPZ。这两种方法中的哪一种产生更紧凑的表示取决于多面体。
任何椭球体都可以转换为CPZ:
(转换椭球)一个椭球可以等价地用CPZ表示:
(18)
其中特征值，特征值的矩阵D，和特征向量的矩阵V是由特征值分解得到的
(19)
转换的复杂度是。
(18)中的矩阵和向量b定义了约束
(20）
自
，(20)等价于约束条件
（21）
利用式(19)中矩阵Q的特征值分解可知
(22)
因为V是一个标准正交矩阵，满足。将(22)插入到定义4中椭球的定义中得到
（23)
我们定义CPZ的因子为，，因此
(24)
将(24)插入(23)最终得到
这就是证明的结论。
(19)中特征值分解的计算具有复杂度[26]。(18)中G的计算需要乘法和n个平方根的计算，因此具有复杂性。由于所有其他所需的操作都是串联的，因此总体复杂性是通过将特征值分解的复杂性和计算G的复杂性相加得出的。
为了加快计算速度，在基于集合的计算中，通常用更简单的集合表示来封装集合。因此，在本节中，我们将展示如何通过约束带拓扑、多项式带拓扑、带拓扑和区间来封闭cpz。所有外壳的过逼近误差可以通过应用4.4节所述的重新缩放来减小。为了演示外壳的密封性，我们使用CPZ
(25)
作为贯穿本节的运行示例。
我们首先展示了如何通过约束的分区来封闭CPZ:
给定，conZono操作返回一个约束的zonotope，包含:
与
其中，[21,Prop. 2]中定义的压缩操作返回一个正则多项式分区，而[21,Prop. 5]中定义的分区操作返回一个包含多项式分区的分区。计算复杂度与表示大小和维数n有关。
为了得到一个封闭约束带拓扑，我们计算了引理1中定义的相应提升多项式带拓扑的带拓扑圈闭。将提升的分区反变换到原始状态空间，然后得到封闭约束分区:
这里省略了紧化操作，因为它只改变集合的表示，而不改变集合本身。
复杂度令、、和表示提升多项式分区的维数、因子数和生成子数。根据[21,Prop. 2]，多项式分区的紧化操作具有复杂性。此外，zono操作的复杂性根据[21,Prop. 5]。因此，总体计算复杂度为
也就是用(10)
(25)中CPZ的封闭约束分区如图4所示。
显然，CPZ的封闭多项式分区可以简单地通过去掉约束来获得。然而，这可能会产生较大的过近似误差。另一种可能性是使用稍后在第8节中引入的13号提案来减少所有约束。哪种方法导致更紧密的外壳取决于CPZ。去掉约束后得到的(25)中CPZ的封闭多项式带拓扑如图4所示。
CPZ的分区或区间的围合可以使用前面提出的分区或多项式分区的约束围合来计算。对于多项式分区，可以使用[21,Prop. 5]计算封闭分区，并且可以基于[21,Prop. 7]中的支持函数框计算封闭区间。对于约束分区，封闭分区可以通过减少[29，章节4.2]中描述的所有约束来计算，封闭区间可以使用线性规划计算[27，章节1]。
图4
(25)的封闭约束分区(左)和封闭多项式分区(右)
下载原文档：https://link.springer.com/content/pdf/10.1007/s00236-023-00437-5.pdf
