TY - JOUR
T1 - On Doubly Positive Semidefinite Programming Relaxations
AU - Fu , Taoran
AU - Ge , Dongdong
AU - Ye , Yinyu
JO - Journal of Computational Mathematics
VL - 3
SP - 391
EP - 403
PY - 2018
DA - 2018/06
SN - 36
DO - http://doi.org/10.4208/jcm.1708-m2017-0130
UR - https://global-sci.org/intro/article_detail/jcm/12267.html
KW - Doubly nonnegative matrix, Semidefinite programming, Relaxation, quartic optimization.
AB - <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>