On Doubly Positive Semidefinite Programming Relaxations
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(n2) 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.
Author Details
Taoran Fu Email
Dongdong Ge Email
Yinyu Ye Email
-
A proximal DC approach for quadratic assignment problem
Jiang, Zhuoxuan | Zhao, Xinyuan | Ding, ChaoComputational Optimization and Applications, Vol. 78 (2021), Iss. 3 P.825
https://doi.org/10.1007/s10589-020-00252-5 [Citations: 3] -
Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
Kim, Sunyoung | Kojima, Masakazu | Toh, Kim-ChuanMathematical Programming, Vol. 193 (2022), Iss. 2 P.761
https://doi.org/10.1007/s10107-020-01594-y [Citations: 0] -
A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
Qian, Yitian | Pan, Shaohua | Bi, ShujunComputational Optimization and Applications, Vol. 84 (2023), Iss. 3 P.875
https://doi.org/10.1007/s10589-022-00443-2 [Citations: 0] -
Joint optimization of SINR and maximum sidelobe level for hybrid beamforming systems with sub-connected structure
Yang, Feng | Pei, Guochen | Hu, Lingna | Ding, Lianghui | Li, YangDigital Signal Processing, Vol. 109 (2021), Iss. P.102917
https://doi.org/10.1016/j.dsp.2020.102917 [Citations: 4]