Polyhedral approximations of the semidefinite cone and their application
Polyhedral approximations of the semidefinite cone and their application
复制标题
半定圆锥的多面体近似及其应用
DOI：
10.1007/s10589-020-00255-2
复制
发表时间：
2021
影响因子：
2.2
通讯作者：
Akihiro Tanaka and Akiko Yoshise
中科院分区：
文献类型：
--
作者：
Yuzhu Wang ;Akihiro Tanaka and Akiko Yoshise
我们开发了构造半定圆锥的一系列稀疏多面体近似的技术。受 Tanaka 和 Yoshise 提出的半定（SD）基（Ann Oper Res 265:155–182, 2018）的启发，我们提出了对 SD 基的简单扩展，以保持组成它的矩阵的稀疏性。我们证明使用扩展的 SD 基的多面体近似包含所有对角占优矩阵的集合，并且包含在所有缩放的对角占优矩阵的集合中。我们还证明了所有缩放对角占优矩阵的集合可以使用无限数量的扩展 SD 基来表示。我们使用我们的近似作为割平面方法中的初始近似来解决最大稳定集问题的半定松弛。研究发现，所提出的具有扩展 SD 基的方法比使用其他现有近似或直接解决半定松弛问题的方法显着更有效。
We develop techniques to construct a series of sparse polyhedral approximations of the semidefinite cone. Motivated by the semidefinite (SD) bases proposed by Tanaka and Yoshise (Ann Oper Res 265:155–182, 2018), we propose a simple expansion of SD bases so as to keep the sparsity of the matrices composing it. We prove that the polyhedral approximation using our expanded SD bases contains the set of all diagonally dominant matrices and is contained in the set of all scaled diagonally dominant matrices. We also prove that the set of all scaled diagonally dominant matrices can be expressed using an infinite number of expanded SD bases. We use our approximations as the initial approximation in cutting plane methods for solving a semidefinite relaxation of the maximum stable set problem. It is found that the proposed methods with expanded SD bases are significantly more efficient than methods using other existing approximations or solving semidefinite relaxation problems directly.