论文标题
抛物线放松，用于四次约束二次编程 - 第一部分：定义和基本属性
Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties
论文作者
论文摘要
对于一般二次约束二次编程（QCQP），我们提出了一种用凸二次约束描述的抛物线弛豫。抛物线放松的一个有趣的特性是原始的非凸起可行集合包含在抛物线放松的边界上。在某些假设下，该财产使人们能够通过客观惩罚恢复近乎最理想的可行点。此外，通过对需要一次性计算的最佳基础计算的坐标进行适当的变化，可以使易于解决的抛物线释放放松与半决赛编程（SDP）放松一样强大，这可以有效地支持需要解决convex代理序列的算法。这项工作的下一部分给出了大多数理论和计算结果[57]。
For general quadratically-constrained quadratic programming (QCQP), we propose a parabolic relaxation described with convex quadratic constraints. An interesting property of the parabolic relaxation is that the original non-convex feasible set is contained on the boundary of the parabolic relaxation. Under certain assumptions, this property enables one to recover near-optimal feasible points via objective penalization. Moreover, through an appropriate change of coordinates that requires a one-time computation of an optimal basis, the easier-to-solve parabolic relaxation can be made as strong as a semidefinite programming (SDP) relaxation, which can be effective in accelerating algorithms that require solving a sequence of convex surrogates. The majority of theoretical and computational results are given in the next part of this work [57].
