论文标题
CS-TSSO：大规模多项式优化的相关性和期限稀疏性
CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization
论文作者
论文摘要
这项工作提出了一个新的Moment Sos层次结构，称为CS-TSSOS，用于解决大规模的稀疏多项式优化问题。它的新颖性是通过结合两个现有框架的优势来利用同时相关的稀疏性和项稀疏性来利用稀疏多项式优化。前者是由于Waki等人所致。而后者最初是由Wang等人提出的。后来在TSSOS层次结构中利用。在此过程中，我们获得了CS-TSSOS-半层次编程松弛的两级层次结构（i），至关重要的特性，涉及SDP矩阵的块和（ii），在某些条件下融合了融合到全局最佳的保证。我们证明了其在著名的最高切割问题和重要的工业最佳功率流问题的几个大规模实例上的效率和可伸缩性，其中最多涉及6000个变量和成千上万的约束。
This work proposes a new moment-SOS hierarchy, called CS-TSSOS, for solving large-scale sparse polynomial optimization problems. Its novelty is to exploit simultaneously correlative sparsity and term sparsity by combining advantages of two existing frameworks for sparse polynomial optimization. The former is due to Waki et al. while the latter was initially proposed by Wang et al. and later exploited in the TSSOS hierarchy. In doing so we obtain CS-TSSOS -- a two-level hierarchy of semidefinite programming relaxations with (i), the crucial property to involve blocks of SDP matrices and (ii), the guarantee of convergence to the global optimum under certain conditions. We demonstrate its efficiency and scalability on several large-scale instances of the celebrated Max-Cut problem and the important industrial optimal power flow problem, involving up to six thousand variables and tens of thousands of constraints.
