期刊
JOURNAL OF SYMBOLIC COMPUTATION
卷 122, 期 -, 页码 -出版社
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.jsc.2023.102258
关键词
Quadratic programming; Semidefinite programming; Convex relaxations
In this paper, we investigate the Shor relaxation of quadratic programs by fixing a feasible set and examining the space of objective functions for which the Shor relaxation is exact. We establish conditions for the invariance of this region under the choice of generators defining the feasible set and describe its characteristics when the feasible set is invariant under the action of a subgroup of the general linear group. Furthermore, we apply these findings to quadratic binary programs and present an algorithm that generates candidate solutions based on an explicit description of objective functions where the Shor relaxation is exact.
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.(c) 2023 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据