Year: 2018
Author: Taoran Fu, Dongdong Ge, Yinyu Ye
Journal of Computational Mathematics, Vol. 36 (2018), Iss. 3 : pp. 391–403
Abstract
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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1708-m2017-0130
Journal of Computational Mathematics, Vol. 36 (2018), Iss. 3 : pp. 391–403
Published online: 2018-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 13
Keywords: Doubly nonnegative matrix Semidefinite programming Relaxation quartic optimization.