Efficient Data Structures for Representation of Polynomial Optimization Problems: Implementation in SOSTOOLS
Efficient Data Structures for Representation of Polynomial Optimization Problems: Implementation in SOSTOOLS
复制标题
DOI：
10.1109/lcsys.2022.3183650
复制
发表时间：
2022-03
影响因子：
3
通讯作者：
Declan S. Jagt;Sachin Shivakumar;P. Seiler;M. Peet
中科院分区：
文献类型：
--
作者：
Declan S. Jagt;Sachin Shivakumar;P. Seiler;M. Peet
我们提出了一种新的数据结构，用于在平方和（SOS）程序解析中表示多项式变量。在 SOS 程序中，变量 $s(x;P)$ 在自变量 $x$ 中是多项式，但在决策变量 $P$ 中是线性的。然而，当前的 SOS 解析器未能利用多项式变量的半线性结构，将决策变量视为其表示中的自变量。这导致多项式变量的存储和操作产生不必要的开销。为了减少这种计算开销，我们引入了多项式变量的新表示形式，即 dpvar 结构，它允许解析器利用决策变量的结构。我们表明，使用 dpvar 结构显着降低了解析 SOS 程序所需的多项式运算的计算复杂度。我们进一步表明，使用 dpvar 结构时，存储多项式变量所需的内存复杂性显着降低，特别是与 MATLAB 压缩稀疏列 (CSC) 矩阵表示结合使用时。最后，我们将 dpvar 结构合并到 SOSTOOLS 4.00 中，并测试了几个多项式优化问题的性能。
We present a new data structure for representation of polynomial variables in the parsing of sum-of-squares (SOS) programs. In SOS programs, the variables $s(x;P)$ are polynomial in the independent variables $x$ , but linear in the decision variables $P$ . Current SOS parsers, however, fail to exploit the semi-linear structure of the polynomial variables, treating the decision variables as independent variables in their representation. This results in unnecessary overhead in storage and manipulation of the polynomial variables. To reduce this computational overhead, we introduce a new representation of polynomial variables, the dpvar structure, which allows the parser to exploit the structure of the decision variables. We show that use of the dpvar structure significantly reduces the computational complexity of the polynomial operations required for parsing SOS programs. We further show that the memory complexity required to store polynomial variables is significantly reduced when using the dpvar structure, particularly when combined with the MATLAB Compressed Sparse Column (CSC) matrix representation. Finally, we incorporate the dpvar structure into SOSTOOLS 4.00, and test performance for several polynomial optimization problems.