论文标题
在多项式优化问题中利用稀疏性和结构的有效数据结构：在Sostools中实现
Efficient Data Structures for Exploiting Sparsity and Structure in Representation of Polynomial Optimization Problems: Implementation in SOSTOOLS
论文作者
论文摘要
我们提出了一个新的数据结构，用于表示多项式变量的表示，在分析方案（SOS）程序中。在SOS程序中，变量$ s（x; q）$在自变量$ x $中是多项式，但是在决策变量$ q $中是线性的。但是，当前的SOS解析器无法利用多项式变量的半线性结构，将决策变量视为其表示中的自变量。这导致在多项式变量的存储和操纵方面导致不必要的开销，禁止解析器解决更大尺度的优化问题。为了消除此计算开销，我们介绍了多项式变量的新表示，即“ DPVAR”结构，即决策变量中的仿射。我们表明，DPVAR表示中变量的操作的复杂性随着决策变量的数量而有利地缩放。我们进一步表明，使用DPVAR结构，尤其是在利用MATLAB稀疏存储结构时，使用DPVAR结构的多项式变量所需的存储器相对较小。最后，我们将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;Q)$ are polynomial in the independent variables $x$, but linear in the decision variables $Q$. 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, prohibiting the parser from addressing larger-scale optimization problems. To eliminate this computational overhead, we introduce a new representation of polynomial variables, the "dpvar" structure, that is affine in the decision variables. We show that the complexity of operations on variables in the dpvar representation scales favorably with the number of decision variables. We further show that the required memory for storing polynomial variables is relatively small using the dpvar structure, particularly when exploiting the MATLAB sparse storage structure. Finally, we incorporate the dpvar data structure into SOSTOOLS 4.00, and test the performance of the parser for several polynomial optimization problems.
