On Doubly Positive Semidefinite Programming Relaxations (Journal of Computational Mathematics, 2018)
Recently, researchers have been interested in studying the semidefinite programming(SDP) relaxation model, where the matrix is both positive semidefinite and entry-wisenonnegative, for quadratically constrained quadratic programming (QCQP). Comparingto the basic SDP relaxation, this doubly-positive SDP model possesses additional $O(n^2)$ constraints, which makes the SDP solution complexity substantially higher than that forthe basic model with $O(n)$ constraints. In this paper, we prove that the doubly-positiveSDP model is equivalent to the basic one with a set of valid quadratic cuts. When QCQPis symmetric and homogeneous (which represents many classical combinatorial and nonconvexoptimization problems), the doubly-positive SDP model is equivalent to the basicSDP even without any valid cut. On the other hand, the doubly-positive SDP model couldhelp to tighten the bound up to 36%, but no more. Finally, we manage to extend some ofthe previous results to quartic models.
Keywords: Doubly nonnegative matrix; Semidefinite programming; Relaxation; quartic optimization.