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

Taoran Fu, Dongdong Ge & Yinyu Ye

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

Published online: 2018-06

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 = {Taoran and Fu and taoran30@sjtu.edu.cn and 6798 and School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai, China and Taoran Fu and Dongdong and Ge and ge.dongdong@mail.shufe.edu.cn and 6799 and School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai, China and Dongdong Ge and Yinyu and Ye and yinyu-ye@stanford.edu and 6800 and Department of Management Science and Engineering, Stanford University, Stanford, CA 94305 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 = {

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.

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