论文标题
在标准的二次程序上，具有确切和不确定的非负松弛
On Standard Quadratic Programs with Exact and Inexact Doubly Nonnegative Relaxations
论文作者
论文摘要
单个单元上的（非凸）二次形式（称为标准二次程序程序）的问题在完全阳性矩阵的计算上棘手的锥体上接受了一个精确的凸锥形配方。用较大但可拖动的非负矩阵的锥体（即，阳性半菲尼特矩阵和偏见的非负矩阵的锥）代替这种配方中的顽固性锥体，获得了所谓的双重性非负弛豫，其最佳值在原始问题上产生了降低原始问题的结合。我们介绍了一组标准的二次程序实例的完整代数表征，这些实例允许确切的非负松弛度。这种表征产生了用于构建此类实例的算法配方。此外，我们明确识别了三个实例家族，这些实例是确切的非负松弛。我们在实例的所谓凸图和双重不负松弛的紧密度之间建立了几个关系。我们还提供了一组实例的代数表征，该实例的双重非负弛豫具有正差距，并显示了如何使用此特征来构建此类实例。
The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over the computationally intractable cone of completely positive matrices. Replacing the intractable cone in this formulation by the larger but tractable cone of doubly nonnegative matrices, i.e., the cone of positive semidefinite and componentwise nonnegative matrices, one obtains the so-called doubly nonnegative relaxation, whose optimal value yields a lower bound on that of the original problem. We present a full algebraic characterization of the set of instances of standard quadratic programs that admit an exact doubly nonnegative relaxation. This characterization yields an algorithmic recipe for constructing such an instance. In addition, we explicitly identify three families of instances for which the doubly nonnegative relaxation is exact. We establish several relations between the so-called convexity graph of an instance and the tightness of the doubly nonnegative relaxation. We also provide an algebraic characterization of the set of instances for which the doubly nonnegative relaxation has a positive gap and show how to construct such an instance using this characterization.
