full
search.png

Search

close.png

Cancel

arrow
Volume 36, Issue 3
On Doubly Positive Semidefinite Programming Relaxations

Taoran Fu, Dongdong Ge & Yinyu Ye

DOI: 10.4208/jcm.1708-m2017-0130

J. Comp. Math., 36 (2018), pp. 391-403.

Published online: 2018-06

Preview Purchase PDF 2034 34376

Cited by

google scholar semantic scholar
Export citation
  • 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.

  • Keywords

Doubly nonnegative matrix, Semidefinite programming, Relaxation, quartic optimization.

  • AMS Subject Headings

90C20, 90C22, 90C26, 65K05.

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

taoran30@sjtu.edu.cn (Taoran Fu)

ge.dongdong@mail.shufe.edu.cn (Dongdong Ge)

yinyu-ye@stanford.edu (Yinyu Ye)

  • BibTex
  • RIS
  • TXT
@Article{JCM-36-391, author = {Fu , TaoranGe , Dongdong and Ye , Yinyu}, title = {On Doubly Positive Semidefinite Programming Relaxations}, journal = {Journal of Computational Mathematics}, year = {2018}, volume = {36}, number = {3}, pages = {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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1708-m2017-0130}, url = {http://global-sci.org/intro/article_detail/jcm/12267.html} }
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 -

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.

Fu , TaoranGe , Dongdong and Ye , Yinyu. (2018). On Doubly Positive Semidefinite Programming Relaxations. Journal of Computational Mathematics. 36 (3). 391-403. doi:10.4208/jcm.1708-m2017-0130
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard