Block Factor-Width-Two Matrices in Semidefinite Programming
Block Factor-Width-Two Matrices in Semidefinite Programming
复制标题
半定规划中的分块因子-宽度-两个矩阵
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Papachristodoulou
中科院分区：
文献类型：
--
作者：
Aivar Sootla;Yang Zheng;A. Papachristodoulou
在本文中，我们引入了一组块因子宽度二矩阵，它是因子宽度二矩阵的推广，并且是正半定矩阵的子集。块因子宽度二矩阵的集合是一个真锥体，我们计算其双锥体的闭合形式表达式。我们使用这些锥体来构建正半定矩阵锥体的内部和外部近似的层次结构。这些锥体的主要特征是它们能够将大的半定约束分解为许多较小的半定约束。作为此类矩阵的主要应用，我们设想了大规模半定可行性优化程序，包括平方和（SOS）程序。我们提供了 SOS 优化的数值示例，展示了这种分解的特性。
In this paper, we introduce a set of block factor-width-two matrices, which is a generalisation of factor-width-two matrices and is a subset of positive semidefinite matrices. The set of block factor-width-two matrices is a proper cone and we compute a closed-form expression for its dual cone. We use these cones to build hierarchies of inner and outer approximations of the cone of positive semidefinite matrices. The main feature of these cones is that they enable a decomposition of a large semidefinite constraint into a number of smaller semidefinite constraints. As the main application of these classes of matrices, we envision large-scale semidefinite feasibility optimisation programs including sum-of-squares (SOS) programs. We present numerical examples from SOS optimisation showcasing the properties of this decomposition.