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.
Author Details
-
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]