390028 UK Convex Representations and Relaxations for Non-convex Quadratic Optimization (2016W)

We consider convex relaxations for non-convex quadratic optimization that utilize semidefiniteness together with constraints obtained from the Reformulation-Linearization Technique (RLT) and generalizations of RLT. From a theoretical standpoint we show that these relaxations dominate convex relaxations obtained using some alternative methodologies, and also that in certain cases the relaxations in fact give exact representations (that is, they are tight). Computational results show that these convex relaxations usually provide excellent bounds, and for some problem classes are often empirically tight even when they are not provably tight.