论文标题
在非交通性多项式优化中利用术语稀疏性
Exploiting term sparsity in Noncommutative Polynomial Optimization
论文作者
论文摘要
我们提供了一个名为NCTSSOS的半决赛编程松弛的新层次结构，以解决大规模稀疏的非交通性多项式优化问题。该层次结构的特征是对特征值和跟踪优化问题的输入数据中隐藏的术语稀疏性的开发。 NCTSSOS complements the recent work that exploits correlative sparsity for noncommutative optimization problems by Klep, Magron and Povh in arXiv:1909.00569, and is the noncommutative analogue of the TSSOS framework by Wang, Magron and Lasserre in arXiv:1912.08899.我们还提出了一个扩展利用的扩展，同时相关和术语稀疏性，如以前在交换案例ARXIV：2005.02828中所做的那样。在某些条件下，我们证明NCTSSOS层次结构的最佳趋于相应的密集SDP松弛的最佳。我们通过解决文献中的特征值/痕量优化问题以及最多涉及多达数千个变量的随机示例来说明NCTSSOS的效率和可扩展性。
We provide a new hierarchy of semidefinite programming relaxations, called NCTSSOS, to solve large-scale sparse noncommutative polynomial optimization problems. This hierarchy features the exploitation of term sparsity hidden in the input data for eigenvalue and trace optimization problems. NCTSSOS complements the recent work that exploits correlative sparsity for noncommutative optimization problems by Klep, Magron and Povh in arXiv:1909.00569, and is the noncommutative analogue of the TSSOS framework by Wang, Magron and Lasserre in arXiv:1912.08899. We also propose an extension exploiting simultaneously correlative and term sparsity, as done previously in the commutative case arXiv:2005.02828. Under certain conditions, we prove that the optimums of the NCTSSOS hierarchy converge to the optimum of the corresponding dense SDP relaxation. We illustrate the efficiency and scalability of NCTSSOS by solving eigenvalue/trace optimization problems from the literature as well as randomly generated examples involving up to several thousands of variables.
