论文标题
关于非convex二次程序的共同呈阳性和凸的替代视角
An Alternative Perspective on Copositive and Convex Relaxations of Nonconvex Quadratic Programs
论文作者
论文摘要
我们研究非凸二次程序的凸松弛。我们确定了一个所谓的可行性，保留了凸松弛，其中包括众所周知的共同阳性且双重的非负松弛度，并且只有在非convex Quadratic程序是可行的，并且只有可行的情况下，凸出放松是可行的。我们观察到，该家族中的每个凸松弛都隐含地诱导了二次程序可行区域的目标函数的凸低音。关于凸松弛的这种替代观点使我们能够建立相应凸低估器的几种有用的属性。特别是，如果二次程序的可行区域的衰退锥不包含任何负弯曲的方向，我们表明，由共同放松而产生的凸低估器正是二次程序的目标功能的凸封，这是二次程序的目标函数的凸膜，这是Burer众所周知的共同稳定性不足的另一个证明。我们还提出了一种算法配方，用于构建具有有限最佳价值但无限双重不负放松的二次程序实例。
We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, providing another proof of Burer's well-known result on the exactness of the copositive relaxation. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded doubly nonnegative relaxation.
