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 qu...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 non- convex 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.展开更多
基金The second author＇s research was supported by Program for Innovative Research Team of Shanghai University of Finance and Economics （IRTSHUFE） and by National Natural Science Foundation of China （NSFC） Project 11471205 the third author＇s research was supported in part by NSF GOALI 0800151.
文摘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 non- convex 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.
