@Article{JCM-36-3,
author = {Taoran, Fu and Ge, Dongdong and Yinyu, Ye},
title = {On Doubly Positive Semidefinite Programming Relaxations},
journal = {Journal of Computational Mathematics},
year = {2018},
volume = {36},
number = {3},
pages = {391--403},
abstract = {<p style="text-align: justify;">Recently, researchers have been interested in studying the semidefinite programming
(SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise
nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing
to 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 for
the basic model with $O(n)$ constraints. In this paper, we prove that the doubly-positive
SDP model is equivalent to the basic one with a set of valid quadratic cuts. When QCQP
is symmetric and homogeneous (which represents many classical combinatorial and nonconvex
optimization problems), the doubly-positive SDP model is equivalent to the basic
SDP even without any valid cut. On the other hand, the doubly-positive SDP model could
help to tighten the bound up to 36%, but no more. Finally, we manage to extend some of
the previous results to quartic models.</p>},
issn = {1991-7139},
doi = {https://doi.org/10.4208/jcm.1708-m2017-0130},
url = {https://global-sci.com/article/84474/on-doubly-positive-semidefinite-programming-relaxations}
}