论文标题
二次编程中SDP精确性的不变性
Invariants of SDP exactness in quadratic programming
论文作者
论文摘要
在本文中，我们通过固定可行的集合并考虑了确切的shor放松的目标函数的空间来研究二次程序的休闲。我们首先提供该区域在定义可行集合的发电机选择下不变的条件。然后，当可行集合在一般线性组的亚组的作用下不变时，我们描述了该区域。我们通过将这些结果应用于二进制二进制程序来得出结论。我们对目标功能进行了明确的描述，其中shor放松是精确的，并利用这些知识来设计一种为二进制二级程序提供候选解决方案的算法。
In this paper we study the Shor relaxation of quadratic programs by fixing a feasible set and considering the space of objective functions for which the Shor relaxation is exact. We first give conditions under which this region is invariant under the choice of generators defining the feasible set. We then describe this region when the feasible set is invariant under the action of a subgroup of the general linear group. We conclude by applying these results to quadratic binary programs. We give an explicit description of objective functions where the Shor relaxation is exact and use this knowledge to design an algorithm that produces candidate solutions for binary quadratic programs.
