Paper Info
Title
Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
Abstract
We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that the use of SDP and RLT constraints together can produce bounds that are substantially better than either technique used alone. For highly symmetric problems we also consider the effect of symmetry-breaking based on tightened bounds on variables and/or order constraints.
Year
DOI
Venue
2009
10.1007/s10898-008-9372-0
J. Global Optimization
Keywords
Field
DocType
Semidefinite programming,Reformulation-linearization technique,Quadratically constrained quadratic programming,90C26,90C22
Second-order cone programming,Mathematical optimization,Quadratic growth,Quadratically constrained quadratic program,Mathematical analysis,Feasible region,Quadratic programming,Semidefinite programming,Linearization,Mathematics
Journal
Volume
Issue
ISSN
43
2-3
0925-5001
Citations 
PageRank 
References 
88
2.91
12
Authors
1
Name
Order
Citations
PageRank
Kurt M. Anstreicher163386.40